目录

第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