北京郵電大學(xué)2006年博士研究生考試大綱——206離散數(shù)學(xué)
206離散數(shù)學(xué)
一、 考試要求
要求考生系統(tǒng)地掌握離散數(shù)學(xué)的基本概念、基本定理和方法，具有較強(qiáng)的邏輯思維和抽象思維能力，能夠靈活運(yùn)用所學(xué)的內(nèi)容和方法解決計(jì)算機(jī)科學(xué)中的實(shí)際問題。
二、 考試內(nèi)容
1、 數(shù)理邏輯
1) 命題和聯(lián)結(jié)詞，謂詞與量詞，合適公式，賦值，解釋與指派，范式
2) 命題形式化，等價(jià)式與對偶式，蘊(yùn)含式，推理與證明
3) 證明方法
4) 數(shù)學(xué)歸納法
2、 集合論
1) 集合代數(shù)，笛卡爾乘積，關(guān)系與函數(shù)，關(guān)系的性質(zhì)與運(yùn)算
2) 等價(jià)關(guān)系，劃分
3) 偏序關(guān)系與偏序集，格
3、 計(jì)數(shù)
1) 排列與組合，容斥原理，鴿巢原理
2) 離散概率
3) 函數(shù)的增長與遞推關(guān)系
4、 圖論
1) 歐拉圖與哈密頓圖，平面圖與對偶圖，二部圖與匹配，圖的著色
2) 樹，樹的遍歷，最小生成樹
3) 最短路經(jīng)，最大流量
5、 形式語言與自動機(jī)
1) 語言與文法，正則表達(dá)式與正則集
2) 有限狀態(tài)自動機(jī)，自動機(jī)與正則語言
6、 代數(shù)系統(tǒng)
1) 二元運(yùn)算，群與半群，積群與商群，同態(tài)與同構(gòu)
2) 群與編碼
3) 格與布爾代數(shù)，環(huán)與域
三、 試卷結(jié)構(gòu)
1、 考試時間為3小時，滿分100分。
2、 題目類型：計(jì)算題、簡答題和證明題。