计算复杂性基础  0839X1M05007H

学期:2020—2021学年(春)第二学期 | 课程属性:专业普及课 | 任课教师:黄桂芳,叶顶锋,吕克伟
授课时间: 星期一,第5、6、7 节
授课地点: 教一楼405
授课周次: 1、2、3、4、6、7、8、10、11、12、13、14、16
课程编号: 0839X1M05007H 课时: 40 学分: 2.00
课程属性: 专业普及课 主讲教师:黄桂芳,叶顶锋,吕克伟 助教:
英文名称: Foundation of Computational Complexity Theory 召集人:

教学目的、要求

本课程是理论计算机科学专业的基础课。通过本课程的学习,使同学了解计算机解决各类问题的难易程度,掌握计算复杂性的基本概念和思想方法,为进一步学习关于理论计算机科学的一些相关研究方向的专业课程(如:理论密码学)打下坚实的理论基础。

预修课程

离散数学

教 材

自编

主要内容

一、问题、算法及计算模型

二、不可判定性

三、计算复杂类

四、归约和完备性

五、NP类

六、随机化计算

七、在密码学中应用

八、论文阅读讨论

参考文献

Computational Complexity: A Conceptual Perspective,人民邮电出版社,2010。
Complexity Theory: A Modern Approach,机械工业出版社,
吕克伟编著:计算复杂性基础,国防工业出版社,2012。