2023年春季学期，本课程开放了本研同堂，欢迎大家来选课！

(2023.1.26 更新：目前本科生在教务系统选课页面可以看到这门课了，但选课人数已满，如需选课请咨询计算机学院研究生教学秘书 张老师 dimple@ustc.edu.cn ，我不知道能否在系统直接申请个性化？)

说明 (写于2021年春季学期结束后)：我没有选修这门课，但前前后后旁听了一半多的课时，所以下面的评价主要针对课程本身，关于考试和给分的具体情况请其他同学补充。

这门课是2020研究生新版培养方案中新开设的，计算机软件与理论专业的基础课，40课时，2学分。这学期的上课时间是15-18周，每周两次课，每次上一个上午，实际授课28课时。

（补充说明一下，为什么到期末才开课呢？据黄老师说，由于是第一次开课，且课程难度较大，学院大部分老师不愿意上，上学期期末教学秘书才找到黄老师，最后黄老师不得已接下了这门课，所以这学期前面一大半时间都在准备。）

这门课使用的教材是Sipser 的 Introduction to the Theory of Computation, Third Edition，在课程主页上有电子版。对应的中译本是《计算理论导引》（原书第3版）。

课程内容主要包括三个部分：自动机理论（计算的模型）、可计算性理论（哪些问题可计算？哪些问题不可计算？）、计算复杂性理论（哪些问题是难的？哪些问题是容易的？）。

• 第1章 绪论
• 第2章 Automata and Languages
  • 2.1 Regular Languages
  • 2.2 Context-free Languages
• 第3章 Computability Theory
  • 3.1 The Church-Turing Thesis
  • 3.2 Decidability
  • 3.3 Reducibility
• 第4章 Complexity Theory
  • 4.1 Time Complexity
  • 4.2 Space Complexity

实际上课程中的很多内容大家在其他课程中多少接触过一些，但这门课是对这些知识的一个系统的讲解，每一个定理都会经过严格地证明。

黄老师在第一次课就说，这是一门数学课，难度是比较大的，经常提醒大家要及时预习和复习，保证充足睡眠。虽然是第一次开课，但看得出来，黄老师是在很用心地对待这门课，课件制作得很精良（可以称得上是赏心悦目），并且每讲完一处比较难的地方会停下来问大家听懂了没有，大部分同学都听懂了才会继续讲，否则会停下来和大家讨论，或再讲一遍。这也是我给10分的原因。

课程的考核方式是半开卷（可带一张手写A4纸）。据黄老师第一节课所说，80%的题目与作业相关，剩下的20%是压轴题，会考课程中所讲到的一个证明。

由于是第一次开课，难免有一些不足。首先就是上课时间，这门课期末才开课，大部分同学都在考试，所以压力是比较大的（不过从明年开始就会和其他课程一样从学期开始就上课）。另外，可以看得出黄老师在尽力把内容讲明白，但因为是第一次上课，很多地方显得不太熟练，偶尔也会有一些小错误。但我相信后面会上得越来越好！

最后还想多说几句，我们为什么要学习计算理论？这里引用南京大学尹一通老师在豆瓣上给《计算理论导引》所写的书评（链接）中的一段话，与大家共勉：

然而，尽管我对这本书和这门学问都很推崇，我对于学习计算理论的必要性却并不坚定。我自己喜欢这些，可我该如何向别人解释学习它是必要的？

Sipser在前言中也试图说明这个问题:"After all, isn't theory arcane, boring, and worst of all, irrelevant?"
他很认真的试图从几个方面说服学生，计算理论是“有用”的，但我总觉得这些说服很徒劳：书中的三个部分，对于搞研究的人来说，前两个领域已经或走到头了或不再是主流研究趣味了，只有复杂度尚活跃，但也只是个理论方向之一；而对于那些有志于业界工作的学生，后两个部分几乎永远不会在工作中用到，而只有第一部分的自动机，可能会用到一点点正则表达式。

看来，从“有用”这个方向去为计算理论辩护，难免会遭遇尴尬和勉强。

我能想到的理由就只剩两个：
（一）这些是计算机科学的根本，没有它们计算机科学不能算作是个正经学问，因此，一个自称计算机科学专业的人，应当知道这些。
（二）这些是美好的，值得在短暂的人生中去经历去见识。

我觉得这已是足够的理由了。

感谢黄文超老师，让我在科大计算机学院听到这样一门优质的课程。推荐大家明年来选！

我没上黄老师的这门课，但我还是想点评（瞎说）一下。

我觉得黄老师的PPT写得很好，把书上的重点写出来了，为同学们省下了大量的时间。

如果课上听不懂或者实在没办法翘了课，也可以听听Sisper老爷子的网课，他讲的非常好（毕竟书也是他写的～）。

另外，我感觉这种课挺难、挺硬的，不是那种可以突击的课。所以选课时要慎重，比如可以想想自己是否有时间或者是否对算法/形式化方法/计算理论感兴趣。

(暴论一句：相比什么大物实验、量子物理、数理方程，这才是属于CS学生的数理基础！）

课程属于数学类，需要点想象力，逻辑能力

作业是不难的，考试比作业还简单