2024-春季-IToC-读书班（已结束）

1. 参与人员

非常欢迎修过计算理论类似课程的硕博研究生来线下讨论！

2. 参考教材

[PDF] Introduction to the Theory of Computation 3rd Michael Sipser, 2012.（简称 IToC）

3. 目的

计算理论 (Theory of Computation) 是计算机科学的基础之一，其研究计算问题的可解性、复杂性以及计算模型等内容。学习 IToC 可以帮助建立对计算机科学基础的深刻理解，为未来 AI 算法的设计和分析奠定坚实的理论基础。

4. 主要内容

大致上来说，首先我们需要一种准确的语言来表达到底计算本质上是什么，不同的科学家抽象出不同的计算模型，于是我们必须考查这些模型的表达能力（第一部分：什么是计算）；

其次，我们发现计算是有局限的，并不是什么问题都能计算，那什么是可计算的问题呢？有什么问题是不可计算的呢？（第二部分：什么可计算）；

最后，如果某些问题是可解的，存在某种算法可以解决这个问题，那么这种算法的效率该如何度量呢？我们需要一种通用的标准度量，并建立相关理论（第三部分：复杂性理论）。

5. 参考资料

6. 讲解章节

主要内容为 IToC 的前 9 章，第 0 章为自学内容 。若无法读懂书本，可观看作者 Sipser 对应章节的视频讲解。

7. 时间安排

日程：4月12日 ~ 7月12日（每周五）

时间：下午 16:00~18:00

地点：南雍楼东 514 室 或 121 室

序号 时间 主讲人 书籍章节 课程内容
1 4月12日 肖逸飞，彭智祥 IToC 1 正则语言
2 4月19日 王未，郎丛宁 IToC 2 上下无关文法
3 4月26日 花鹏宇 IToC 3 丘奇-图灵论题
4 5月10日 王炯达 IToC 4 可判定性
5 5月17日 胡哲理 IToC 5 可归约性
考试月
6 7月2日 杨枢栋，褚子源 IToC 5 剩余内容 & IToC 6 可计算理论的高级专题
7 7月3日 王萌，金剑涵 IToC 7 时间复杂性
8 7月5日 杨博 IToC 8 空间复杂性
9 7月23日 何显 IToC 9 难解性

8. 注意事项