第l章 基础：逻辑. 集合和函数
1. 1 逻辑
1. 1. 1 引言
1. 1. 2 命题
1. 1. 3 翻译语言的句子
1. 1. 4 布尔检索
l. 1. 5 逻辑运算和位运算练习
1. 2 命题等价
1. 2. 1 引言
1. 2. 2 逻辑等价练习
1. 3 谓词和量词
1. 3. 1 引言
1. 3. 2 量词
1. 3. 3 翻译语句为逻辑表达式
1. 3. 4 选自Lewis Carroll的例子(选读)
1. 3. 5 绑定变量
1. 3. 6 否定练习
1. 4 集合
1. 4. 1 引言
1. 4. 2 幂集合
1. 4. 3 笛卡儿积练习
1. 5 集合运算
1. 5. 1 引言
1. 5. 2 集合相等
1. 5. 3 扩展的并集和交集
1. 5. 4 集合的计算机表示练习
1. 6 函数
1. 6. 1 引言
1. 6. 2 一对一函数和映上函数
1. 6. 3 反函数和函数组合
1. 6. 4 函数的图像
1. 6. 5 几个重要的函数练习
1. 7 序列与求和
1. 7. 1 引言
1. 7. 2 序列
1. 7. 3 特殊的整数序列
1. 7. 4 求和
1. 7. 5 基数(选读)练习
1. 8 函数增长
1. 8. 1 引言
1. 8. 2 大O符号
1. 8. 3 函数组合的增长
1. 8. 4 大Ω和大Ξ符号
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第2章 基础：算法. 整数和矩阵
2. 1 算法
2. 1. 1 引言
2. 1. 2 搜索算法练习
2. 2 算法的复杂性
2. 2. 1 引言练习
2. 3 整数和除法
2. 3. 1 引言
2. 3. 2 除法
2. 3. 3 素数
2. 3. 4 除法算法
2. 3. 5 最大公约数和最小公倍数
2. 3. 6 模运算
2. 3. 7 同余应用
2. 3. 8 密码学练习
2. 4 整数和算法
2. 4. 1 引言
2. 4. 2 欧几里德算法
2. 4. 3 整数表示
2. 4. 4 整数运算算法练习
2. 5 数论应用
2. 5. 1 引言
2. 5. 2 若干有用的结果
2. 5. 3 线性同余
2. 5. 4 中国余数定理
2. 5. 5 大整数的计算机算术运算
2. 5. 6 伪素数
2. 5. 7 公钥密码学
2. 5. 8 RSA加密
2. 5. 9 RSA解密
2. 5. 10 用RSA作公钥系统练习
2. 6 矩阵
2. 6. 1 引言
2. 6. 2 矩阵运算
2. 6. 3 矩阵乘法运算
2. 6. 4 矩阵的转置和幂
2. 6. 5 0-1矩阵练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第3章 数学推理
3. 1 证明方法
3. 1. 1 引言
3. 1. 2 推理规则
3. 1. 3 谬误
3. 1. 4 带量词命题的推理规则
3. 1. 5 证明定理的方法
3. 1. 6 定理与量词
3. 1. 7 停机问题
3. 1. 8 关于证明的一些评注练习
3. 2 数学归纳法
3. 2. 1 引言
3. 2. 2 良序性
3. 2. 3 数学归纳法
3. 2. 4 数学归纳法证明的例子
3. 2. 5 数学归纳法的第二原理练习
3. 3 递归定义
3. 3. 1 引言
3. 3. 2 递归地定义函数
3. 3. 3 递归地定义集合练习
3. 4 递归算法
3. 4. 1 引言
3. 4. 2 递归与迭代练习
3. 5 程序正确性
3. 5. 1 引言
3. 5. 2 程序验证
3. 5. 3 推理规则
3. 5. 4 条件语句
3. 5. 5 循环不变量
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第4章 计数
4. 1 计数的基础
4. 1. 1 引言
4. 1. 2 基本的计数原则
4. 1. 3 容斥原理
4. 1. 4 树图练习
4. 2 鸽巢原理
4. 2. 1 引言
4. 2. 2 推广的鸽巢原理
4. 2. 3 巧妙使用鸽巢原理练习
4. 3 排列与组合
4. 3. 1 引言
4. 3. 2 排列
4. 3. 3 组合
4. 3. 4 二项式系数
4. 3. 5 二项式定理练习
4. 4 离散概率
4. 4. 1 引言
4. 4. 2 有限概率
4. 4. 3 事件组合的概率
4. 4. 4 概率的推理练习
4. 5 概率论
4. 5. 1 引言
4. 5. 2 概率赋值
4. 5. 3 事件的组合
4. 5. 4 条件概率
4. 5. 5 独立性
4. 5. 6 伯努利实验与二项式分布
4. 5. 7 随机变量
4. 5. 8 期望值
4. 5. 9 独立随机变量
4. 5. 10 方差
4. 5. 11 切比雪夫不等式
4. 5. 12 平均状态下的计算复杂性练习
4. 6 一般性的排列和组合
4. 6. 1 引言
4. 6. 2 有重复的排列
4. 6. 3 有重复的组合
4. 6. 4 具有不可区别物体的集合的排列
4. 6. 5 把物体放入盒子练习
4. 7 生成排列和组合
4. 7. 1 引言
4. 7. 2 生成排列
4. 7. 3 生成组合
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第5章 高级计数技术
5. 1 递推关系
5. 1. 1 引言
5. 1. 2 递推关系
5. 1. 3 用递推关系构造模型练习
5. 2 求解递推关系
5. 2. 1 引言
5. 2. 2 求解常系数线性齐次递推关系
5. 2. 3 常系数线性非齐次的递推关系练习
5. 3 分而治之关系
5. 3. 1 引言
5. 3. 2 分而治之关系练习
5. 4 生成函数
5. 4. 1 引言
5. 4. 2 关于幂级数的有用的事实
5. 4. 3 计数问题与生成函数
5. 4. 4 使用生成函数求解递推关系
5. 4. 5 使用生成函数证明恒等式练习
5. 5 容斥
5. 5. 1 引言
5. 5. 2 容斥原理练习
5. 6 容斥原理的应用
5. 6. 1 引言
5. 6. 2 容斥原理的另一种形式
5. 6. 3 伊拉脱森筛
5. 6. 4 映上函数的个数
5. 6. 5 错位排列
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第6章 关系
6. 1 关系及其性质
6. 1. 1 引言
6. 1. 2 函数作为关系
6. 1. 3 集合上的关系
6. 1. 4 关系的性质
6. 1. 5 关系的组合练习
6. 2 n元关系及其应用
6. 2. 1 引言
6. 2. 2 n元关系
6. 2. 3 数据库和关系练习
6. 3 关系的表示
6. 3. 1 引言
6. 3. 2 用矩阵表示关系
6. 3. 3 用图表示关系练习
6. 4 关系的闭包
6. 4. 1 引言
6. 4. 2 闭包
6. 4. 3 有向图的路径
6. 4. 4 传递闭包
6. 4. 5 沃舍尔算法练习
6. 5 等价关系
6. 5. 1 引言
6. 5. 2 等价关系
6. 5. 3 等价类
6. 5. 4 等价类与划分练习
6. 6 偏序
6. 6. 1 引言
6. 6. 2 字典顺序
6. 6. 3 哈斯图
6. 6. 4 极大元素与极小元素
6. 6. 5 格
6. 6. 6 拓扑排序
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第7章 图
7. 1 图的介绍
7. 1. 1 图的种类
7. 1. 2 图模型练习
7. 2 图的术语
7. 2. 1 引言
7. 2. 2 基本术语
7. 2. 3 一些特殊的简单图
7. 2. 4 偶图
7. 2. 5 特殊类型的图的一些应用
7. 2. 6 从旧图到新图练习
7. 3 图的表示和图的同构
7. 3. 1 引言
7. 3. 2 图的表示
7. 3. 3 相邻矩阵
7. 3. 4 关联矩阵
7. 3. 5 图的同构练习
7. 4 连通性
7. 4. 1 引言
7. 4. 2 通路
7. 4. 3 无向图连通性
7. 4. 4 有向图中的连通性
7. 4. 5 通路与同构
7. 4. 6 统计顶点之间的通路练习
7. 5 欧拉通路与哈密顿通路
7. 5. 1 引言
7. 5. 2 欧拉回路和欧拉通路的充要条件
7. 5. 3 哈密顿通路和回路练习
7. 6 最短通路问题
7. 6. 1 引言
7. 6. 2 一个最短通路算法
7. 6. 3 旅行推销员问题练习
7. 7 平面性图
7. 7. 1 引言
7. 7. 2 欧拉公式
7. 7. 3 库拉图斯基定理练习
7. 8 图着色
7. 8. 1 引言
7. 8. 2 图着色的应用
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第8章 树
8. 1 介绍树
8. 1. 1 树作为模型
8. 1. 2 树的性质练习
8. 2 树的应用
8. 2. 1 引言
8. 2. 2 二叉搜索树
8. 2. 3 决策树
8. 2. 4 前缀码练习
8. 3 树的遍历
8. 3. 1 引言
8. 3. 2 通用地址系统
8. 3. 3 遍历算法
8. 3. 4 中缀. 前缀和后缀记法练习
8. 4 树与排序
8. 4. 1 引言
8. 4. 2 排序的复杂性
8. 4. 3 冒泡排序
8. 4. 4 归并排序练习
8. 5 生成树
8. 5. 1 引言
8. 5. 2 一些构造生成树的算法
8. 5. 3 回溯练习
8. 6 最小生成树
8. 6. 1 引言
8. 6. 2 最小生成树算法
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第9章 布尔代数
9. 1 布尔函数
9. 1. 1 引言
9. 1. 2 布尔表达式和布尔函数
9. 1. 3 布尔代数中的恒等式
9. 1. 4 对偶性
9. 1. 5 布尔代数的抽象定义练习
9. 2 布尔函数的表示
9. 2. 1 积之和展开式
9. 2. 2 函数完备性练习
9. 3 逻辑门电路
9. 3. 1 引言
9. 3. 2 门的组合
9. 3. 3 电路的例子
9. 3. 4 加法器练习
9. 4 电路的极小化
9. 4. 1 引言
9. 4. 2 卡诺图
9. 4. 3 无需在意条件
9. 4. 4 奎因-莫可拉斯基方法
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第10章 计算模型
10. 1 语言和文法
10. 1. 1 引言
10. 1. 2 短语结构文法
10. 1. 3 短语结构文法的类型
10. 1. 4 派生树
10. 1. 5 巴科斯-诺尔范式练习
10. 2 带输出的有限状态机
10. 2. 1 引言
10. 2. 2 带输出的有限状态机练习
10. 3 不带输出的有限状态机
10. 3. 1 引言
10. 3. 2 串的集合
10. 3. 3 有限状态自动机练习
10. 4 语言的识别
10. 4. 1 引言
10. 4. 2 正则集合
10. 4. 3 克莱因定理
10. 4. 4 正则集合和正则文法
10. 4. 5 一个不能由有限状态自动机识别语言
10. 4. 6 一些更强大的机器练习
10. 5 图灵机
10. 5. 1 引言
10. 5. 2 图灵机的定义
10. 5. 3 用图灵机识别集合
10. 5. 4 用图灵机计算函数
10. 5. 5 不同类型的图灵机
10. 5. 6 丘奇-图灵论题
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
附录A 指数函数和对数函数
附录B 伪代码
奇数练习题答案
推荐读物
参考文献
鄂公网安备 42010302001612号 