理论计算机科学导引 2.0 学分

授课教师

毛宇尘

认定

专业基础课

课程教材

INTRODUCTION TO THEORETICAL COMPUTER SCIENCE - BOAZ BARAK

分数构成

• 平时作业 20% （共四次）
• 小测 20% (共两次，每次一节课时间，3-4题)
• 期末考试 60%（判断 + 大题）

学习建议

这门课程难度高，需要认真对待。毛哥上课还是非常不错的，建议到课并认真做笔记。
平时成绩可以被期末考试覆盖，但这显然是不现实的。
尤其注意规约的书写方法，最难的部分是halting problem相关的规约与NPC的规约。
不可计算性问题的规约注意按照规范的方式（construct a TM N,s.t. M ... \(\iff\) N ...)
NPC的规约应在考试前关注SAT家族，vertex-cover，dominating set, independent set等问题的相互转换等。