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

第一章 集合論基礎(chǔ)
1.1 集合的基本概念
習(xí)題1.1
1.2 關(guān)系
1.2.1 關(guān)系的基本概念及其性質(zhì)
1.2.2 等價關(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 集合在計算機科學(xué)中的應(yīng)用
1.4.1 關(guān)系在關(guān)系數(shù)據(jù)庫中的應(yīng)用
1.4.2 關(guān)系代數(shù)與數(shù)據(jù)子語言
1.4.3 等價關(guān)系在計算機中的應(yīng)用
1.4.4 序關(guān)系在項目管理中的應(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 命題公式的等價關(guān)系和蘊涵關(guān)系
2.3.1 公式的等價
2.3.2 公式的蘊涵
2.3.3 演繹
2.3.4 公式蘊涵的證明方法
習(xí)題2.3
2.4 范式
2.4.1 析取范式和合取范式
2.4.2 主析取范式和主合取范式
2.4.3 恒真恒假性的判定
習(xí)題2.4
2.5 命題邏輯在二值邏輯器件和語句邏輯中的應(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 謂詞公式的等價關(guān)系和蘊涵關(guān)系
3.3.1 公式的等價和蘊涵
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ù)子語言
3.6.2 謂詞邏輯與邏輯程序設(shè)計語言
第四章 圖與網(wǎng)絡(luò)
4.1 圖
4.1.1 圖的基本概念
4.1.2 權(quán)圖Dijkstra算法
習(xí)題4.1
4.2 樹
4.2.1 樹及其等價命題
4.2.2 最優(yōu)樹Kruskal算法
4.2.3 求最優(yōu)樹的其他算法
習(xí)題4.2
4.3 有向圖Euler路
4.3.1 有向圖與有向樹
4.3.2 Euler路Euler圖
4.3.3 無向圖無向圖中的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 平面圖的對偶圖Plato體
4.5.4 平面圖的著色
習(xí)題4.5
4.6 匹配二部圖
習(xí)題4.6
4.7 Konig無限性引理
習(xí)題4.7
4.8 網(wǎng)絡(luò)優(yōu)化算法
4.8.1 圖與網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)
4.8.2 單源最短路徑問題具體算法及實現(xiàn)和比較
4.8.3 最大流問題具體算法及實現(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 一元高次同余式的化簡
5.4.3 剩余系遍歷Euler函數(shù)
習(xí)題5.4
5.5 一元高次同余式二次剩余
5.5.1 一元高次同余式的解
5.5.2 二次同余式二次剩余
5.5.3 二次剩余的判定Legendre符號
習(xí)題5.5
5.6 數(shù)論在計算機通信安全中的應(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)在計算機科學(xué)中的應(yīng)用
6.8.1 計數(shù)問題
6.8.2 糾錯碼
第七章 多項式有限域
67.1 域的特征素域
7.1.1 域的特征
7.1.2 素域
習(xí)題7.1
7.2 多項式的整除性
習(xí)題7.2
7.3 多項式的根
習(xí)題7.3
7.4 有理域上的多項式
習(xí)題7.4
7.5 分圓多項式
7.5.1 復(fù)數(shù)域上的分圓多項式
7.5.2 任意域上的分圓多項式
習(xí)題7.5
7.6 有限域
習(xí)題7.6
7.7 多項式編碼方法及其實現(xiàn)
習(xí)題7.7
第八章 格與布爾代數(shù)
8.1 引言
8.2 格的定義
習(xí)題8.2
8.3 格的性質(zhì)
8.3.1 對偶原理
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 布爾表達式的化簡問題
習(xí)題8.6
8.7 格與布爾代數(shù)在計算機科學(xué)中的應(yīng)用
8.7.1 開關(guān)電路函數(shù)
8.7.2 邏輯門
8.7.3 全加器的邏輯設(shè)計
第九章 語言和有限狀態(tài)機
9.1 語言和語法
9.1.1 語法結(jié)構(gòu)
9.1.2 語法結(jié)構(gòu)的類型
9.1.3 演繹樹
9.1.4 Backus-Naurform
習(xí)題9.1
9.2 帶有輸出的有限狀態(tài)機
習(xí)題9.2
9.3 沒有輸出的有限狀態(tài)機
習(xí)題9.3
9.4 語言識別
9.4.1 正則集合
9.4.2 KLEENE定理
9.4.3 其他幾種類型的有限狀態(tài)機
習(xí)題9.4
9.5 Turing機
習(xí)題9.5
參考文獻