如果你感到对未来的迷茫，又有对自身能力的自信，推荐你选择本课。本课会让你明白，自动机和上下文无关文法的能力边界在哪里；计算机的工作有哪些是可计算的；如果能计算，计算的复杂性是多大；并行算法、密码学复杂度、电路复杂性如何刻画和计算。你会惊奇地发现，大部分我们希望解决的事情都是 NP-Hard 的 (ie. 比所有 NP 问题都要难) 乃至不可计算的。有了一个通透的了解，可以帮助你用一个更高的角度和更抽象的思维理解计算机的一切。

本科前期学的东西是 RE DFA CFL PDA 等的性质和相互转换，主要是熟悉一下精准表达问题的数学语言，也比较简单 (本人期中 98 平均分也很高)。如果你对编译原理、NLP、Model Checking 等有兴趣，可以来选一选。后期学的是图灵机相关内容，这部分凝结了世界上最聪明的脑袋想出来的内容，非常抽象和烧脑，但是学完之后可以获得大脑的升级，有信心理解其他同等抽象的内容。

而且非常有意思 (期末考试压轴题：证明《羊了个羊》是 NP-Complete 的