第一章 集合論基礎(chǔ)
1.1 集合的概念和術(shù)語
1.1.1 集合的基本概念和表示
1.1.2 集合之間的關(guān)系
1.1.3 集合族
1.2 集合的運(yùn)算
1.2.1 集合的基本運(yùn)算
1.2.2 冪集
1.2.3 n元組和笛卡兒乘積
*1.2.4 廣義并和廣義交
1.3 集合運(yùn)算的性質(zhì)
1.3.1 集合恒等式
1.3.2 集合演算
1.3.3 對偶原理
1.4 有限集合的計數(shù)
*1.5 羅素悖論
1.6 小結(jié)
1.7 習(xí)題
第二章 數(shù)論基礎(chǔ)
2.1 最大公因數(shù)和最小公倍數(shù)
2.1.1 整除、同余、最大公因數(shù)和最小公倍數(shù)
2.1.2 歐幾里得算法
2.1.3 最大公因數(shù)和最小公倍數(shù)的性質(zhì)
2.2 素數(shù)
2.2.1 整數(shù)的素分解
2.2.2 素性探測
2.3 一次同余方程
2.3.1 一次同余方程
2.3.2 一次同余方程組
*2.3.3 大整數(shù)的剩余表示法
*2.4 RSA公鑰密碼體制
2.5 小結(jié)
2.6 習(xí)題
第三章 命題邏輯
3.1 命題
3.1.1 命題與邏輯聯(lián)結(jié)詞
3.1.2 命題公式
3.2 等值演算
3.2.1 等值的概念
3.2.2 等值演算
3.2.3 對偶原理
3.3 范式
3.3.1 主析取范式
3.3.2 主合取范式
3.3.3 聯(lián)結(jié)詞的完備集
3.4 自然推理系統(tǒng)P
3.5 消解
3.6 小結(jié)
3.7 習(xí)題
第四章 一階邏輯
4.1 謂詞和謂詞公式
4.1.1 謂詞和量詞
4.1.2 謂詞公式
4.2 謂詞公式的等值演算和前束范式
4.3 一階邏輯的推理理論
4.4 小結(jié)
4.5 習(xí)題
第五章 關(guān)系
5.1 關(guān)系的概念
5.1.1 二元關(guān)系
5.1.2 二元關(guān)系的表示
*5.1.3 n元關(guān)系
5.2 關(guān)系運(yùn)算
5.2.1 關(guān)系的基本運(yùn)算
5.2.2 關(guān)系運(yùn)算的性質(zhì)
5.3 關(guān)系的特殊性質(zhì)及其閉包
5.3.1 關(guān)系的特殊性質(zhì)
5.3.2 關(guān)系的閉包
5.4 等價關(guān)系和劃分
5.4.1 等價關(guān)系和等價類
5.4.2 劃分和等價關(guān)系
*5.4.3 測試用例設(shè)計之等價類劃分法
5.5 偏序關(guān)系
5.5.1 偏序關(guān)系和偏序集
5.5.2 哈斯圖
5.5.3 偏序集的性質(zhì)
*5.5.4 拓?fù)湫蛄?
*5.5.5 格
5.6 小結(jié)
5.7 習(xí)題
第六章 函數(shù)和集合的基數(shù)
6.1 函數(shù)的概念和性質(zhì)
6.1.1 函數(shù)的基本概念
6.1.2 函數(shù)的復(fù)合和逆
*6.2 集合的基數(shù)
6.2.1 集合的等勢
6.2.2 可數(shù)集
6.2.3 無限集和集合的基數(shù)
*6.3 數(shù)字計算機(jī)的不可解問題
6.3.1 不可解問題的存在性
6.3.2 停機(jī)問題
6.4 小結(jié)
6.5 習(xí)題
第七章 圖論基礎(chǔ)
7.1 圖及其表示
7.1.1 圖的概念
7.1.2 圖的矩陣表示
7.1.3 幾種特殊的簡單圖
7.1.4 子圖和圖運(yùn)算
7.2 握手定理
7.3 圖的連通性
7.3.1 通路和回路
7.3.2 圖的連通性
7.3.3 矩陣運(yùn)算和連通性
*7.4 最短通路和Dijkstra算法
7.4.1 廣度優(yōu)先搜索算法
7.4.2 帶權(quán)圖和Dijkstra算法
7.5 頂點(diǎn)著色
7.6 圖同構(gòu)
7.7 小結(jié)
7.8 習(xí)題
第八章 具有特殊性質(zhì)的圖
8.1 歐拉圖
8.1.1 歐拉圖的概念
8.1.2 無向歐拉圖的性質(zhì)
8.1.3 有向歐拉圖的性質(zhì)
8.2 哈密頓圖
8.2.1 哈密頓圖的概念
8.2.2 無向哈密頓圖的性質(zhì)
*8.2.3 格雷碼
*8.2.4 競賽圖
8.3 平面圖
8.3.1 平面圖的概念
8.3.2 平面圖的性質(zhì)
8.4 無向樹
8.4.1 無向樹的概念
8.4.2 無向樹的基本性質(zhì)
*8.4.3 求最小生成樹的Kruskal算法
8.5 有向樹
8.5.1 有向樹和根樹及其簡單性質(zhì)
8.5.2 決策樹和排序算法的時間復(fù)雜度下限
*8.5.3 最優(yōu)樹和Huffman算法
*8.6 偶圖及其匹配
8.7 小結(jié)
8.8 習(xí)題
第九章 基本計數(shù)方法
9.1 鴿籠原理
9.2 加法原理與乘法原理
9.3 排列與組合
9.3.1 排列
9.3.2 組合
9.4 二項(xiàng)式系數(shù)
9.5 可重復(fù)的排列和組合
9.5.1 可重復(fù)的排列
9.5.2 可重復(fù)的組合
9.6 容斥原理
9.7 生成排列和組合
9.7.1 生成排列
9.7.2 生成組合
9.8 小結(jié)
9.9 習(xí)題
第十章 遞推關(guān)系和生成函數(shù)
10.1 遞推關(guān)系
10.2 常系數(shù)線性遞推關(guān)系
10.2.1 求解常系數(shù)線性齊次遞推關(guān)系
*10.2.2 求解常系數(shù)線性非齊次遞推關(guān)系
10.3 生成函數(shù)
10.3.1 冪級數(shù)型生成函數(shù)
10.3.2 指數(shù)型生成函數(shù)
10.4 生成函數(shù)應(yīng)用舉例
10.5 小結(jié)
10.6 習(xí)題
第十一章 代數(shù)結(jié)構(gòu)基礎(chǔ)
11.1 代數(shù)系統(tǒng)
11.2 二元運(yùn)算的性質(zhì)
11.3 同態(tài)和同構(gòu)
11.4 小結(jié)
11.5 習(xí)題
第十二章 群
12.1 群
12.2 子群
12.2.1 子群
12.2.2 元素的階
12.3 循環(huán)群
12.4 陪集和正規(guī)子群
*12.5 群同態(tài)
12.6 變換群和置換群
*12.7 群碼
12.7.1 糾錯碼的基本概念
12.7.2 二元線性碼的生成矩陣與校驗(yàn)矩陣
12.7.3 群碼的譯碼
12.8 小結(jié)
12.9 習(xí)題
第十三章 環(huán)和域
13.1 環(huán)
13.1.1 環(huán)的定義
13.1.2 特殊元素和性質(zhì)
13.1.3 環(huán)的分類
13.2 子環(huán)、理想和商環(huán)
13.2.1 子環(huán)和理想
*13.2.2 商環(huán)
13.3 環(huán)同態(tài)
13.4 域
13.4.1 域的基本概念和簡單性質(zhì)
13.4.2 有限域
*13.4.3 擴(kuò)域的性質(zhì)和幾何作圖問題
*13.5 有限域上的遍歷矩陣及其在密碼學(xué)中的應(yīng)用
13.5.1 有限域Fq上的遍歷矩陣
13.5.2 遍歷矩陣在密碼學(xué)中的應(yīng)用
13.6 小結(jié)
13.7 習(xí)題
第十四章 格和布爾代數(shù)
14.1 格
14.1.1 偏序格
14.1.2 代數(shù)格
14.2 有界格、有補(bǔ)格和分配格
14.3 布爾代數(shù)
14.3.1 布爾代數(shù)和布爾格
14.3.2 有限布爾代數(shù)
14.3.3 對偶原理
14.4 小結(jié)
14.5 習(xí)題