離散數(shù)學(xué)

第一章 集合論基礎(chǔ)
1.1 集合的基本概念
習(xí)題1.1
1.2 關(guān)系
1.2.1 關(guān)系的基本概念及其性質(zhì)
1.2.2 等價(jià)關(guān)系
1.2.3 部分序關(guān)系
習(xí)題1.2
1.3 映射
1.3.1 集合的基數(shù)
1.3.2 可數(shù)集合
1.3.3 不可數(shù)集甘
習(xí)題1.3
1.4 集合在計(jì)算機(jī)科學(xué)中的應(yīng)用
1.4.1 關(guān)系在關(guān)系數(shù)據(jù)庫(kù)中的應(yīng)用
1.4.2 關(guān)系代數(shù)與數(shù)據(jù)子語(yǔ)言
1.4.3 等價(jià)關(guān)系在計(jì)算機(jī)中的應(yīng)用
1.4.4 序關(guān)系在項(xiàng)目管理中的應(yīng)用
第二章 命題邏輯
2.1 命題以及邏輯聯(lián)結(jié)詞
2.1.1 命題
2.1.2 邏輯聯(lián)結(jié)詞
習(xí)題2.1
2.2 命題公式
2.2.1 公式
2.2.2 解釋
習(xí)題2.2
2.3 命題公式的等價(jià)關(guān)系和蘊(yùn)涵關(guān)系
2.3.1 公式的等價(jià)
2.3.2 公式的蘊(yùn)涵
2.3.3 演繹
2.3.4 公式蘊(yùn)涵的證明方法
習(xí)題2.3
2.4 范式
2.4.1 析取范式和合取范式
2.4.2 主析取范式和主合取范式
2.4.3 恒真恒假性的判定
習(xí)題2.4
2.5 命題邏輯在二值邏輯器件和語(yǔ)句邏輯中的應(yīng)用
第三章 謂詞邏輯
3.1 謂詞邏輯的基本概念
3.1.1 謂詞和量詞
3.1.2 改名規(guī)則
習(xí)題3.1
3.2 謂詞公式
3.2.1 公式
3.2.2 解釋
習(xí)題3.2
3.3 謂詞公式的等價(jià)關(guān)系和蘊(yùn)涵關(guān)系
3.3.1 公式的等價(jià)和蘊(yùn)涵
3.3.2 謂詞演算的推理理論
習(xí)題3.3
3.4 范式
3.4.1 前束范式
3.4.2 Skolem范式
習(xí)題3.4
3.5 例
習(xí)題3.5
3.6 謂詞邏輯的應(yīng)用
3.6.1 謂詞邏輯與數(shù)據(jù)子語(yǔ)言
3.6.2 謂詞邏輯與邏輯程序設(shè)計(jì)語(yǔ)言
第四章 圖與網(wǎng)絡(luò)
4.1 圖
4.1.1 圖的基本概念
4.1.2 權(quán)圖Dijkstra算法
習(xí)題4.1
4.2 樹(shù)
4.2.1 樹(shù)及其等價(jià)命題
4.2.2 最優(yōu)樹(shù)Kruskal算法
4.2.3 求最優(yōu)樹(shù)的其他算法
習(xí)題4.2
4.3 有向圖Euler路
4.3.1 有向圖與有向樹(shù)
4.3.2 Euler路Euler圖
4.3.3 無(wú)向圖無(wú)向圖中的Euler路
習(xí)題4.3
4.4 Hamilton圖
4.4.1 Hamilton路Hamilton圖的必要條件
4.4.2 Hamilton圖的若干充分條件
習(xí)題4.4
4.5 平面圖
4.5.1 平面圖判定Kuratowski判字準(zhǔn)則
4.5.2 平面圖的Euler公式
4.5.3 平面圖的對(duì)偶圖Plato體
4.5.4 平面圖的著色
習(xí)題4.5
4.6 匹配二部圖
習(xí)題4.6
4.7 Konig無(wú)限性引理
習(xí)題4.7
4.8 網(wǎng)絡(luò)優(yōu)化算法
4.8.1 圖與網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)
4.8.2 單源最短路徑問(wèn)題具體算法及實(shí)現(xiàn)和比較
4.8.3 最大流問(wèn)題具體算法及實(shí)現(xiàn)和比較
習(xí)題4.8
第五章 數(shù)論基礎(chǔ)
5.1 整除性輾轉(zhuǎn)相除
5.1.1 整除及其性質(zhì)
5.1.2 輾轉(zhuǎn)相除
5.1.3 利用數(shù)的數(shù)碼特征判別某些整除性
習(xí)題5.1
5.2 互質(zhì)質(zhì)因數(shù)分解
5.2.1 整數(shù)互質(zhì)
5.2.2 質(zhì)數(shù)與合數(shù)算術(shù)基本定理
習(xí)題5.2
5.3 合同一次同余式
5.3.1 合同及其性質(zhì)
5.3.2 剩余類一次同余式
習(xí)題5.3
5.4 秦九韶定理Euler函數(shù)
5.4.1 一次同余式組秦九韶定理
5.4.2 一元高次同余式的化簡(jiǎn)
5.4.3 剩余系遍歷Euler函數(shù)
習(xí)題5.4
5.5 一元高次同余式二次剩余
5.5.1 一元高次同余式的解
5.5.2 二次同余式二次剩余
5.5.3 二次剩余的判定Legendre符號(hào)
習(xí)題5.5
5.6 數(shù)論在計(jì)算機(jī)通信安全中的應(yīng)用
5.6.1 密碼系統(tǒng)
5.6.2 凱撒密碼
5.6.3 Vigenere密碼
5.6.4 Hill加密算法
5.6.5 RSA公鑰系統(tǒng)
習(xí)題5.6
第六章 群與環(huán)
6.1 代數(shù)系統(tǒng)
習(xí)題6.1
6.2 群的定義
6.2.1 半群
6.2.2 群
6.2.3 群的性質(zhì)
習(xí)題6.2
6.3 置換群
6.3.1 置換的定義
6.3.2 置換的輪換表法
6.3.3 置換的順向圈表示
6.3.4 置換的奇偶性
習(xí)題6.3
6.4 子群及其陪集
6.4.1 子群的定義
6.4.2 子群的判別條件
6.4.3 循環(huán)群
6.4.4 陪集
習(xí)題6.4
6.5 同構(gòu)及同態(tài)
6.5.1 同態(tài)映射
6.5.2 同構(gòu)映射
6.5.3 同態(tài)核
習(xí)題6.5
6.6 環(huán)
6.6.1 環(huán)的定義
6.6.2 環(huán)的性質(zhì)
習(xí)題6.6
6.7 環(huán)同態(tài)
6.7.1 理想
6.7.2 環(huán)中合同關(guān)系
6.7.3 環(huán)同態(tài)與同構(gòu)
6.7.4 單純環(huán)與極大理想
習(xí)題6.7
6.8 群與環(huán)在計(jì)算機(jī)科學(xué)中的應(yīng)用
6.8.1 計(jì)數(shù)問(wèn)題
6.8.2 糾錯(cuò)碼
第七章 多項(xiàng)式有限域
67.1 域的特征素域
7.1.1 域的特征
7.1.2 素域
習(xí)題7.1
7.2 多項(xiàng)式的整除性
習(xí)題7.2
7.3 多項(xiàng)式的根
習(xí)題7.3
7.4 有理域上的多項(xiàng)式
習(xí)題7.4
7.5 分圓多項(xiàng)式
7.5.1 復(fù)數(shù)域上的分圓多項(xiàng)式
7.5.2 任意域上的分圓多項(xiàng)式
習(xí)題7.5
7.6 有限域
習(xí)題7.6
7.7 多項(xiàng)式編碼方法及其實(shí)現(xiàn)
習(xí)題7.7
第八章 格與布爾代數(shù)
8.1 引言
8.2 格的定義
習(xí)題8.2
8.3 格的性質(zhì)
8.3.1 對(duì)偶原理
8.3.2 格的其他性質(zhì)
8.3.3 格的同態(tài)與同構(gòu)
習(xí)題8.3
8.4 幾種特殊的格
8.4.1 有界格
8.4.2 有余格
8.4.3 分配格
8.4.4 模格
習(xí)題8.4
8.5 布爾代數(shù)
8.5.1 布爾代數(shù)的定義及其性質(zhì)
8.5.2 有限布爾代數(shù)的表示理論
8.5.3 布爾代數(shù)的同態(tài)與同構(gòu)
習(xí)題8.5
8.6 布爾表達(dá)式的化簡(jiǎn)問(wèn)題
習(xí)題8.6
8.7 格與布爾代數(shù)在計(jì)算機(jī)科學(xué)中的應(yīng)用
8.7.1 開(kāi)關(guān)電路函數(shù)
8.7.2 邏輯門(mén)
8.7.3 全加器的邏輯設(shè)計(jì)
第九章 語(yǔ)言和有限狀態(tài)機(jī)
9.1 語(yǔ)言和語(yǔ)法
9.1.1 語(yǔ)法結(jié)構(gòu)
9.1.2 語(yǔ)法結(jié)構(gòu)的類型
9.1.3 演繹樹(shù)
9.1.4 Backus-Naurform
習(xí)題9.1
9.2 帶有輸出的有限狀態(tài)機(jī)
習(xí)題9.2
9.3 沒(méi)有輸出的有限狀態(tài)機(jī)
習(xí)題9.3
9.4 語(yǔ)言識(shí)別
9.4.1 正則集合
9.4.2 KLEENE定理
9.4.3 其他幾種類型的有限狀態(tài)機(jī)
習(xí)題9.4
9.5 Turing機(jī)
習(xí)題9.5
參考文獻(xiàn)