计算理论导论

2010年07月07日

        该课程主要面向理论计算机方向的低年级研究生开课,要求选课同学有良好的数学基础、以及基本的理论计算机基础。

        该课程向学生介绍计算理论的主要内容,侧重于近当代复杂性理论的重要主题,使学生了解复杂性理论领域的重要问题和结果。加强学生的理论计算机基础,同时帮助学生了解理论计算机学科算法方向的知识,以便选择自己将来的主要研究方向。

        课程内容包括:回顾可计算性理论的主要内容,介绍复杂性理论的基本主题,包括基本复杂性类如P、NP、PSPACE和BPP等;电路和Parity不在AC0中的证明;时间和空间层级定理;去随机化的主要结果;PCP定理和不可近似性;理论密码学;自然性证明等。

        教学方式以课堂授课为主,辅以专题讨论,由学生进行论文阅读训练和综述汇报,以期帮助选课学生明确今后的研究目标。