集合論離散數學

離散數學（2）

引言

計算機學院信息安全與智能信息處理研究室李舟軍教授2023/2/11引言2主要內容 1.

計算機中的數學

2.

離散數學的內容、特點和歷史

3.

為什么要學習離散數學？

4.

如何學好離散數學？

5.本課程的教學內容2023/2/11引言3

計算機中的數學2023/2/11引言4集合關系函數邏輯基礎消解邏輯演算歸納法圖論樹自動機及正規(guī)表達式文法及文法分析圖靈機和可計算理論布爾代數群、環(huán)、域排列組合概率統(tǒng)計知識點羅列數論基礎計數理論算法分析遞歸及遞推關系—演算矩陣及其算法復雜性理論2023/2/11引言5關系集合函數邏輯基礎消解邏輯演算歸納法圖論樹自動機及正規(guī)表達式文法及文法分析圖靈機和可計算理論布爾代數群、環(huán)、域排列組合概率統(tǒng)計知識點羅列數論基礎計數理論算法分析遞歸及遞推關系—演算矩陣及其算法復雜性理論關系集合函數邏輯基礎消解邏輯演算歸納法圖論樹數論基礎計數理論布爾代數群、環(huán)、域排列組合離散數學

邏輯基礎

關系、集合、函數（數論、計數）證明技術

圖論與樹代數結構布爾代數2023/2/11引言6關系集合函數邏輯基礎消解邏輯演算歸納法圖論樹自動機及正規(guī)表達式文法及文法分析圖靈機和可計算理論布爾代數群、環(huán)、域排列組合概率統(tǒng)計知識點羅列數論基礎計數理論算法分析遞歸及遞推關系—演算矩陣及其算法復雜性理論數論基礎計數理論算法分析遞歸及遞推關系—演算矩陣及其算法復雜性理論自動機及正規(guī)表達式文法及文法分析圖靈機和可計算理論布爾代數群、環(huán)、域排列組合概率統(tǒng)計計算機科學引論

組合學

自動機理論可計算性理論

-演算證明技術2023/2/11引言7關系集合函數邏輯基礎消解邏輯演算歸納法圖論樹自動機及正規(guī)表達式文法及文法分析圖靈機和可計算理論布爾代數群、環(huán)、域排列組合概率統(tǒng)計知識點羅列數論基礎計數理論算法分析遞歸及遞推關系—演算矩陣及其算法復雜性理論

文法及文法分析群、環(huán)、域概率統(tǒng)計其它課程覆蓋算法設計與分析：算法分析、復雜性理論；編譯原理：文法及文法分析；計算機安全與保密：群、環(huán)、域；

線性代數：矩陣及其算法：概率論與數理統(tǒng)計：概率統(tǒng)計。程序設計：遞歸和遞推關系。2023/2/11引言8涉及課程離散數學抽象代數程序設計編譯原理計算機安全與保密算法設計與分析函數式程序設計概率論與數理統(tǒng)計線性代數形式語言與自動機2023/2/11引言9

離散數學內容、特點和歷史2023/2/11引言10離散數學內容離散數學是現代數學的一個分支，目前主要包括：

集合論

介紹樸素集合論

5,6,7,8章

數理邏輯

1,2,3,4章

圖論

9,10,11,12,13,14,15章

可計算理論 遞歸函數

抽象代數 群、環(huán)、域和布爾代數

自動機理論

組合學

離散概率論2023/2/11引言11離散數學特點離散性：與連續(xù)性相對；能行性：與計算機相關， 又稱能行可計算性，有窮性。2023/2/11引言12中秋節(jié)快樂!給你10個月餅，每天至少吃一個，多吃不限，連續(xù)幾天把月餅吃完，有多少種不同的吃法？

月餅的吃法：2023/2/11引言13離散數學發(fā)展歷史現代數學的一些內容在十九世紀出現計算機的誕生和發(fā)展，計算機研究中涉及到各種數學工具，促進了數學的發(fā)展。60年代末、70年代初，國際計算機界（美國）把從事計算機研究所需的數學工具統(tǒng)稱為離散數學，又稱計算機數學、程序設計數學基礎。2023/2/11引言14

為什么要學習離散數學2023/2/11引言15學習目標培養(yǎng)抽象思維和嚴格邏輯推理能力掌握處理離散結構所必須的描述工具和方法

2023/2/11引言16軟件設計任務的典型模型2023/2/11引言17

如何學好離散數學2023/2/11引言18如何學好離散數學了解問題背景弄清基本概念掌握基本方法2023/2/11引言19

正確處理好學與思的關系：“學而不思則惘，思而不學則殆”動（腦+手）勤把握四個環(huán)節(jié)：

課前（瀏覽預習，只求了解）

課堂（認真聽講，當場消化）

課后（立即復習，融會貫通）

課余（多做習題，舉一反三）

方法與環(huán)節(jié)2023/2/11引言20內容：集合論，圖論

教學方法：以講為主（交互式的），結合自學，突出重點、難點?？己朔绞剑洪]卷考試。參考資料：1.離散數學、離散數學習題與解析，檀鳳琴、何自強，科學出版社。2.離散數學，王兵山等，國防科技大學出版社3.離散數學，耿素云、屈婉玲等，高等教育出版社4.DiscreteMathematicalStructures,BernardKolman,RobertC.Busby,SharonRoss，清華大學出版社本課程的教學內容和方法2023/2/11引言21

第二篇集合論第五章集合的基本概念及其運算第六章關系第七章函數第八章自然數和基數2023/2/11引言22

第三篇圖論

第九章基本概念第十章通路問題第十一章圖的矩陣表示第十二章樹第十三章穿程問題第十四章二分圖的匹配問題第十五章平面圖及色數

2023/2/11引言23主講教師:李舟軍教授辦公室: