2021山東大學826離散數學研究生考試大綱 正文

826-離散數學
考試要求
要求考生系統地理解與掌握離散數學的基本概念、計算和證明方法，以及應用概念和方法進行應用問題離散建模、計算求解和邏輯推理的能力。要求考生具有抽象思維能力，邏輯推理能力，和綜合運用所學的知識分析問題和解決問題的能力。
考試內容
1.  邏輯和證明基礎：命題邏輯及其應用、命題等價式、命題邏輯等價演算、謂詞、量詞、嵌套量詞、推理規則、證明方法和策略
2.  基本結構：集合基本概念及其運算、函數、序列及求和、集合的基數
3.  算法：算法的基本概念、搜索算法、排序問題、貪婪算法、函數的增長、算法的復雜度
4.  初等數論：整除性和模算術、整數進制表示和運算算法、素數、最大公約數、最小公倍數、歐幾里得算法、最大公約數的線性組合表示、線性同余方程、中國剩余定理、費馬小定理、原根、離散對數問題
5.  歸納與遞歸：數學歸納法原理及其運用、強歸納法及其運用、良序性質、遞歸定義與結構歸納法、遞歸算法、程序正確性
6.  計數：計數基礎、鴿巢原理、排列與組合及其推廣、二項式系數與恒等式、生成排列和組合
7.  關系：二元關系基本概念及其性質、n元關系及其應用、關系的表示（關系矩陣、關系圖）、關系的閉包、等價關系、偏序
8.  圖：圖的基本概念、圖模型、圖的基本術語、幾種特殊類型圖、二部圖和匹配、圖的表示與圖的同構、圖的連通性、歐拉通路、哈密頓通路、最短通路算法、平面圖及其應用、圖的著色問題。
9.  樹：樹的基本概念、樹的基本性質及其應用、樹的遍歷算法、樹的編碼、生成樹、最小生成樹。
10. 布爾代數：布爾函數及其表示、邏輯門電路、電路極小化。
考試形式
考試形式為閉卷、筆試，考試時間為180分鐘，滿分為150分。
參考教材
離散數學及其應用（原書第7版），Kenneth H. Rosen，機械工業出版社
原作名: Discrete Mathematics and Its Applications，譯者: 徐六通、楊娟、吳斌

山東大學

本文來源：http://m.btfokj.cn/shandongdaxue/cankaoshumu_379843.html