课程资源MIT 6.042Jsyllabus-课程大纲syllabus-课程大纲课程索引讲座阅读材料讲座幻灯片课堂问题作业单元 1：证明1.1 证明导论第 1.1–1.6 章 (PDF)欢迎来到 6.042J (PDF)证明导论 (PDF)第 1 节课课堂问题 (PDF)习题集 1 (PDF)1.2 证明方法第 1.7–1.9 章 (PDF)反证法 (PDF)分类讨论法 (PDF)分类讨论法示例 (PDF)第 2 节课课堂问题 (PDF)1.3 良序原理第 2.1–2.3 章 (PDF)良序原理 1 (PDF)良序原理 2 (PDF)良序原理 3 (PDF)第 3 节课课堂问题 (PDF)1.4 逻辑与命题第 3.1–3.5 章 (PDF)命题运算符 (PDF)数字逻辑 (PDF)真值表 (PDF)蕴涵 (PDF)命题逻辑 (PDF)第 4 节课课堂问题 (PDF)1.5 量词与谓词逻辑第 3.6 章 (PDF)谓词逻辑 1 (PDF)谓词逻辑 2 (PDF)谓词逻辑 3 (PDF)第 5 节课课堂问题 (PDF)习题集 2 (PDF)1.6 集合第 4.1–4.2 章 (PDF)集合定义 (PDF)集合运算 (PDF)第 6 节课课堂问题 (PDF)1.7 二元关系第 4.3–4.5 章 (PDF)关系 (PDF)关系映射 (PDF)有限基数 (PDF)第 7 节课课堂问题 (PDF)习题集 3 (PDF)1.8 数学归纳法第 5.1–5.3 章 (PDF)数学归纳法 (PDF)错误的归纳法(PDF - 1.2MB)强归纳法 (PDF)普通归纳法 vs 强归纳法 vs 良序原理 (PDF)第 8 节课课堂问题 (PDF)1.9 状态机——不变量第 5.4 章 (PDF)状态机不变量 (PDF)派生变量 (PDF)第 9 节课课堂问题 (PDF)习题集 4 (PDF)1.10 递归定义第 6 章 (PDF)递归数据 (PDF)结构归纳法 (PDF)递归函数 (PDF)第 10 节课课堂问题 (PDF)1.11 无限集第 7 章 (PDF)基数 (PDF)可数集 (PDF)康托尔定理 (PDF)停机问题 (PDF)罗素悖论 (PDF)集合论公理 (PDF)第 11 节课课堂问题 (PDF)单元 2：结构2.1 最大公约数第 8.1–8.5 章 (PDF)最大公约数和线性组合 (PDF)欧几里得算法 (PDF)普尔韦里泽算法 (PDF)《虎胆龙威》中的素数 (PDF)素数分解 (PDF)第 12 节课课堂问题 (PDF)习题集 5 (PDF)2.2 同余第 8.6–8.9 章 (PDF)同余 (PDF)模 N 逆元 (PDF)第 13 节课课堂问题 (PDF)2.3 欧拉定理第 8.10 章 (PDF)模幂运算：欧拉函数 (PDF)环 Z_n (PDF)第 14 节课课堂问题 (PDF)2.4 RSA 加密第 8.11–8.12 章 (PDF)RSA 公钥加密 (PDF)将因式分解简化为 SAT 问题 (PDF)第 15 节课课堂问题 (PDF)习题集 6 (PDF)2.5 有向图：游走与路径第 9.1–9.4 章 (PDF)有向图：游走与路径 (PDF)有向图：连通顶点 (PDF)第 16 节课课堂问题 (PDF)2.6 有向无环图第 9.5 章 (PDF)有向无环图 (PDF)调度 (PDF)时间 vs 处理器 (PDF)第 17 节课课堂问题 (PDF)习题集 7 (PDF)2.7 偏序和等价第 9.5–9.11 章 (PDF)偏序 (PDF)将偏序表示为子集关系 (PDF)等价关系 (PDF)第 18 节课课堂问题 (PDF)2.8 度与同构第 11.1–11.4 章 (PDF)度 (PDF)同构 (PDF)第 19 节课课堂问题 (PDF)2.9 着色与连通性第 11.7–11.9 章 (PDF)着色 (PDF)连通性 (PDF)k-连通性 (PDF)第 20 节课课堂问题 (PDF)习题集 8 (PDF)2.10 树第 11.9–11.10 章 (PDF)树 (PDF)树着色 (PDF)生成树 (PDF)第 21 节课课堂问题 (PDF)2.11 稳定匹配第 11.6 章 (PDF)稳定匹配 (PDF)匹配仪式 (PDF)最优稳定匹配 (PDF)二分图匹配 (PDF)霍尔定理 (PDF)第 22 节课课堂问题 (PDF)单元 3：计数3.1 求和与乘积第 13.1–13.5 章 (PDF)算术求和 (PDF)几何求和 (PDF)书籍堆叠 (PDF)积分方法 (PDF)斯特林公式 (PDF)第 23 节课课堂问题 (PDF)习题集 9 (PDF)3.2 渐近分析第 13.7 章 (PDF)渐近符号 (PDF)渐近性质 (PDF)渐近分析中的错误 (PDF)第 24 节课课堂问题 (PDF)3.3 用双射计数第 14.1–14.2 章 (PDF)加法和乘法法则 (PDF)用双射计数 (PDF)第 25 节课课堂问题 (PDF)习题集 10 (PDF)3.4 重复与二项式定理第 14.4–14.7 章 (PDF)广义计数法则 (PDF)两对扑克牌 (PDF)二项式定理 (PDF)簿记员法则，多项式定理 (PDF)第 26 节课课堂问题 (PDF)3.5 鸽巢原理，容斥原理第 14.8 章 (PDF)鸽巢原理 (PDF)容斥原理 (PDF)容斥原理：两集合证明 (PDF)第 27 节课课堂问题 (PDF)单元 4：概率 4.1 离散概率导论第 16.1–16.5 章 (PDF)树模型 (PDF)简化的蒙提霍尔问题树 (PDF)样本空间 (PDF)第 28 节课课堂问题 (PDF)习题集 11 (PDF)4.2 条件概率第 17.1–17.5 章 (PDF)条件概率 (PDF)全概率公式 (PDF)贝叶斯定理 (PDF)蒙提霍尔问题 (PDF)第 29 节课课堂问题 (PDF)4.3 独立性与因果关系第 17.7–17.8 章 (PDF)独立性 (PDF)相互独立 (PDF)第 30 节课课堂问题 (PDF)习题集 12 (PDF)4.4 随机变量，密度函数第 18.1–18.3 章 (PDF)更大的数字游戏 (PDF)随机变量：独立性 (PDF)随机变量：均匀分布与二项分布 (PDF)第 31 节课课堂问题 (PDF)4.5 期望第 18.4–18.5 章 (PDF)期望 (PDF)正面朝上的次数的期望值 (PDF)全期望公式 (PDF)平均故障时间 (PDF)期望的线性性质 (PDF)第 32 节课课堂问题 (PDF)4.6 偏差：马尔可夫与切比雪夫不等式第 19.1–19.3 章 (PDF)均值偏差 (PDF)马尔可夫不等式 (PDF)切比雪夫不等式 (PDF)方差 (PDF)第 33 节课课堂问题 (PDF)无作业4.7 抽样与置信度第 19.4–19.5 章 (PDF)大数定律 (PDF)独立抽样定理 (PDF)生日匹配 (PDF)抽样与置信度 (PDF)第 34 节课课堂问题 (PDF)4.8 随机游走与网页排名第 20.2 章 (PDF)随机游走 (PDF)平稳分布 (PDF)网页排名 (PDF)第 35 节课课堂问题 (PDF)