北京郵電大學06年博士考試大綱_離散數學

北京郵電大學06年博士考試大綱_離散數學 E<p<"UjcCJ  
北京郵電大學2006年博士研究生考試大綱——206離散數學 QO>)ug+  
206離散數學 y#P_ }Kfo  
一、 考試要求 1wE`
kbC<  
要求考生系統地掌握離散數學的基本概念、基本定理和方法，具有較強的邏輯思維和抽象思維能力，能夠靈活運用所學的內容和方法解決計算機科學中的實際問題。 l$!Z};mw0E  
二、 考試內容 f*EDSJu\  
1、 數理邏輯 ]vuxeu[cu,  
1) 命題和聯結詞，謂詞與量詞，合適公式，賦值，解釋與指派，范式 5>:p'zI  
2) 命題形式化，等價式與對偶式，蘊含式，推理與證明 x} f)P  
3) 證明方法 PWV+M@  
4) 數學歸納法 OTEx9  
2、 集合論 PKev)M;C+  
1) 集合代數，笛卡爾乘積，關系與函數，關系的性質與運算 H:t2;Z'  
2) 等價關系，劃分 :2lM7|@/  
3) 偏序關系與偏序集，格 ?QcS$
i  
3、 計數 2{G7ignv
 
1) 排列與組合，容斥原理，鴿巢原理 D7v.Xq|  
2) 離散概率 YCBUc<)  
3) 函數的增長與遞推關系 G[ q<P  
4、 圖論 #b1/2=PA  
1) 歐拉圖與哈密頓圖，平面圖與對偶圖，二部圖與匹配，圖的著色 =]L#v2@  
2) 樹，樹的遍歷，最小生成樹 2~)q080jh  
3) 最短路經，最大流量 ?`B6I!S0[  
5、 形式語言與自動機 8WwLKZ}  
1) 語言與文法，正則表達式與正則集 .Zx7+`i  
2) 有限狀態自動機，自動機與正則語言 &RlYw#*1.  
6、 代數系統 U6M&7l8  
1) 二元運算，群與半群，積群與商群，同態與同構 tTe: Oq  
2) 群與編碼 !_:|mu'  
3) 格與布爾代數，環與域 *%dWNvN4X  
三、 試卷結構 EkP(]F  
1、 考試時間為3小時，滿分100分。 1gH>B5`  
2、 題目類型：計算題、簡答題和證明題。