每周二1-3pm 每周四10-noon 理教410
期末考试 12月30日（周二）下午
授课老师
刘天任 [email protected] 静园五院103-2
Office hour 周五2-4pm
助教
李翰禹 [email protected]
李柄辉 [email protected]
张质源 [email protected]
王颖 [email protected]
王迪 [email protected]
李新年 [email protected]
柯绎思 [email protected]
柯怿憬 [email protected]
后面可能也会安排一些助教的office hour。
教材和参考资料
大纲参考邓小铁和王畅写的《离散数学与结构》而这本书又是基于 Rafael
Pass 和 Wei-Lung Dustin Tseng 的 “A Course in Discrete Structures”。
按章节分, 可以参考
- 逻辑部分: Logic and Structure (Dirk van Dalen)
- 抽象代数: 抽象代数学 (姚慕生); Abstract Algebra (Dummit-Foote)
- 信息论: Information Theory: From Coding to Learning
(Polyanskiy-Wu)
- 离散傅里叶: Fourier Transforms in Computer Science (Daniel
Štefankovič)
- 马尔可夫链: Markov Chains and Mixing Times (Levin)
- 概率方法: Probabilistic Method (Alon-Spencer); Probabilistic Method
(Matoušek-Vondrák)
参考资料。
成绩
成绩（调分前）= 40% 作业 + 30% 期中考试 + 30% 期末考试 +
笔记额外加分
作业
大致一周一次, 周四出作业, 下周四收纸质版,
再下周反馈批改后的作业以及参考答案。
授课内容
今年有李新年助教和几位同学提供的笔记
(last updated Dec 4)
- Sep 9 朴素集合论
- Sep 11 命题逻辑, 自然演绎
- Natural Deduction 在 Logic and Structure 中有介绍
- System K 在 Sequents and Trees 中有介绍
- HW1 参考答案（Updated on Sep 25）
- Sep 16 自然演绎的完备性, RAA, Kripke model
- 网上有很多关于 Kripke model 和直觉主义的材料, 我参考的是 A Brief
Introduction to the Intuitionistic Propositional Calculus
- Sep 18 一阶逻辑, 一阶逻辑的自然演绎
- HW2 参考答案
- Sep 23 Peano 算术, 一阶逻辑的完备性
- Sep 25 ZFC 集合论, Gödel 不完备定理
- HW3 参考答案
- Sep 30 初等数论
- Oct 9 群, 正规子群
- HW4 参考答案
- Oct 14 群同态, 群同构定理, 有限生成Abel群
- Oct 16 群作用, 共轭类方程, Sylow定理
- HW5 参考答案
- Oct 21 环, 环同态, 理想, 环同构定理
- Oct 23 有特殊性质的整环
- HW6 参考答案
- Oct 28 域
- Oct 30 Galois理论 (王迪)
- Nov 4 期中考试 可以带2张A4纸小抄
试卷 参考答案
- Nov 6 基本计数, 容斥原理, 鸽笼原理
- HW7 参考答案
- Nov 11 生成函数
- Nov 13 Burnside & Polya
- HW8 参考答案
(Updated Nov 27)
- Nov 18 概率, 概率生成函数
- Nov 20 熵, 散度
- HW9 参考答案
- Nov 25 集中不等式, Sanov & Chernoff
- Nov 27 离散傅里叶变换
- 离散傅里叶变换主要参考“Fourier Transforms in Computer Science”
- HW10
- Dec 2 压缩
- Dec 4 信道编码
- 信息论的部分主要参考 MIT 6.441 课程笔记和据此整理的教材“Information
Theory: From Coding to Learning”
- HW11
- Dec 9 and Dec 11 马尔可夫链
(计划)
- HW 题库, 包括往年考试题
2024年的授课内容：
- Sep 10 朴素集合论
- Sep 12 命题逻辑
- Sep 19 自然演绎的完备性, RAA, Kripke model
- Sep 24 and Sep 26 一阶逻辑, ZFC
集合论, Gödel 不完备定理
- Oct 8 and Oct 10
类型论（李翰禹）
- Oct 15 初等数论
- Oct 17 群
- Oct 22 群同构, 正规子群, 有限生成Abel群
- Oct 24 群作用, 共轭类方程, Sylow定理
- Oct 22 环, 环同态, 理想, 环同构定理
- Oct 24 有特殊性质的整环
- Nov 5 域
- Nov 7 期中考试 可以带2张A4纸小抄
试卷
- Nov 12 组合计数
- Nov 14 概率
- Nov 19 生成函数
- Nov 21 Burnside & Polya
- Nov 26 熵, 散度
- Nov 28 Sanov & Chernoff
- Dec 3 压缩
- Dec 5 信道编码
- 信息论的部分主要参考 MIT 6.441 课程笔记和据此整理的教材“Information
Theory: From Coding to Learning”
- Dec 10 离散傅里叶变换
- Dec 12 马尔可夫链
- Dec 17 马尔可夫链
- 建议参考 Markov Chain and Mixing Time
- Dec 19 图
- Dec 24 and Dec 26 概率方法
- 可以参考两本名为“Probabilistic Method”教材中的任意一本
- Dec 31 期末考试 可以带4张A4纸小抄
试卷