離散數學：思維與挑戰

目錄

第1 章集合論................................................................ 1

1.1 集合與集合運算......................................................................... 1

1.2 關系..................................................................... 5

1.3 函數及其他............................................................................ 9

習題集1 ................................................................................ 14

1.4 康托的對角線論證....................................................................... 17

1.5 集合大小的比較......................................................................... 21

習題集2 .................................................................................. 26

1.6 偏序..................................................................... 28

1.7 良序定理與序數......................................................................... 32

1.8 基數、超限歸納與鏈.................................................................... 36

習題集3 ..................................................................................... 42

第2 章遞推關系.................................................................... 45

2.1 Karatsuba 算法：遞歸算法的一個例子............................................ 45

2.2 遞推關系、通解與特解................................................................. 46

2.3 生成函數方法............................................................................ 52

習題集4 ................................................................................. 56

2.4 零化子方法............................................................................... 59

2.5 漸近復雜度、遞歸樹與主定理........................................................ 64

習題集5 ............................................................................... 70

第3 章群論............................................................................... 72

3.1 群的基礎知識............................................................................ 72

3.2 子群、陪集與拉格朗日定理........................................................... 76

3.3 循環群、生成元與有限生成群........................................................ 80

習題集6 ................................................................................ 87

3.4 正規子群、商群與同構定理........................................................... 89

3.5 柯西定理、p-群與西羅定理........................................................... 97

3.6 對稱群與置換............................................................................ 100

習題集7 .............................................................................. 106

第4 章數論......................................................................... 109

4.1 既約剩余系及相關定理................................................................. 109

4.2 更多關於既約剩余系的定理........................................................... 112

4.3 二次剩余.......................................................................... 116

習題集8 ................................................................................ 122

4.4 二次互反律...........................................................................124

習題集9 ............................................................................... 130

4.5 連分數................................................................... 130

習題集10 ........................................................................... 138

4.6 格：數的幾何............................................................................ 140

習題集11 ........................................................................ 147

第5 章圖論..................................................................... 148

5.1 一些定義與戴科斯特拉算法........................................................... 148

5.2 更多定義與包含三角形的圖........................................................... 153

習題集12 ............................................................................... 158

5.3 樹..................................................................... 160

5.4 生成樹..................................................................166

習題集13 .......................................................................... 171

5.5 圖著色與色數............................................................................ 172

5.6 著色多項式...................................................................... 178

習題集14 ..................................................................................182

5.7 圖匹配............................................................................. 183

習題集15 ............................................................................ 189

5.8 歐拉回路和哈密頓圈.................................................................... 190

習題集16 ........................................................................ 196

第6 章理論計算機科學簡介.................................................................... 198

6.1 圖靈機與停機問題....................................................................... 198

習題集17 ......................................................................... 202

6.2 兩個隨機化算法......................................................................... 203

習題集18 .......................................................................... 207

6.3 零知識證明：一種密碼學原語........................................................ 207

習題集19 .......................................................................... 212

6.4 策略博弈與均衡......................................................................... 213

習題集20 ......................................................................... 220

參考文獻.............................................................................. 221

索引................................................................................ 226