离散数学

授课老师

刘天任 [email protected] 静园五院103-2

Office hour 周五2-4pm

助教

李翰禹 [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% 期末考试

作业

大致一周一次，周四出作业，下周四收纸质版，再下周反馈批改后的作业以及参考答案。

• Sep 10 朴素集合论
• Sep 12 命题逻辑
  • Natural Deduction 在 Logic and Structure 中有介绍
  • System K 在 Sequents and Trees 中有介绍
• HW1 答案
  • Sep 13 修改了第3题，修改了第4题的提示
• Sep 19 自然演绎的完备性，RAA，Kripke model
  • 网上有很多关于 Kripke model 和直觉主义的材料，我参考的是 A Brief Introduction to the Intuitionistic Propositional Calculus
• HW2 答案
  • Sep 20 修正了第二题中 Kripke model 的定义
• Sep 24 and Sep 26 一阶逻辑，ZFC 集合论，Godel 不完备定理
• HW3 答案
• Oct 8 and Oct 10 类型论（李翰禹）
• Oct 15 初等数论
• Oct 17 群
• HW4 答案
• Oct 22 群同构，正规子群，有限生成Abel群
• Oct 24 群作用，共轭类方程，Sylow定理
• HW5 答案
• Oct 22 环，环同态，理想，环同构定理
• Oct 24 有特殊性质的整环
• Nov 5 域
• Nov 7 期中考试 可以带2张A4纸小抄 答案
• Nov 12 组合计数
• Nov 14 概率
• HW6 答案
• Nov 19 生成函数
• Nov 21 Burnside & Polya
• HW7 答案
• Nov 26 熵，散度
• Nov 28 Sanov & Chernoff
• HW8 答案
• Dec 3 压缩
• Dec 5 信道编码
  • 信息论的部分主要参考 MIT 6.441 课程笔记和据此整理的教材“Information Theory: From Coding to Learning”
• HW9 答案
• Dec 10 离散傅里叶变换
• Dec 12 马尔可夫链
• HW10 答案
• Dec 17 马尔可夫链
  • 建议参考 Markov Chain and Mixing Time
• Dec 19 图
• HW11 答案
• Dec 24 and Dec 26 概率方法
  • 可以参考两本名为“Probabilistic Method”教材中的任意一本
• HW12 答案 不提交
• Dec 31 期末考试 可以带4张A4纸小抄 答案

教学大纲可以参考去年的授课内容：