计算复杂性理论

◆ ◆

个人介绍

计算复杂性理论

主讲教师：段会川

学校：	山东师范大学
开课院系：	信息科学与工程学院
专业大类：	计算机科学与技术
课程英文名称：	Computational Complexity
学分：	2
课时：	36

1 课程简介
《计算复杂性理论》是计算机软件与理论学术学位硕士研究生的核心课程，也是计算机应用技术学术学位硕士专业和软件工程、计算机技术专业学位硕士专业的重要基础课程之一。
本课程将系统地介绍计算理论的三大主要内容：自动机与语言、可计算性理论和计算复杂性理论。通过这些内容的学习，为学生开展计算机科学与技术及相关领域的研究奠定坚实的计算和算法理论支撑。
2 内容说明
在教学过程中，我们发现我院招收的硕士学位研究生在本课程的先修课上基础不一，有半数以上的学生没有系统化地学习过《算法设计与分析》。《算法设计与分析》课程不仅是本课程的关键先修课，同时也是计算机专业开展科学研究和工程应用工作的核心支撑课程。为此，本次课程将教学内容分成了两篇，即《算法设计与分析》篇和《计算理论》篇，两者各占大约1/2的教学内容和时间。

教学方法

课堂教学与课下学习相结合

鉴于本课程内容覆盖到了两门重要专业课程的范围，而教学计划只有36学时，本课程教学过程中将采用课堂教学与适量的学生课下学习相结合的教学方式。

算法可视化教学辅助工具的运用

为解决教学内容与有限学时间的矛盾，同时也是为了提高教学效率、提升教学质量和效果，本课程将深入应用最有代表性的算法可视化教学辅助工具，包括：

1. 计算理论可视化教学辅助工具JFLAP系统

杜克大学的S. Rodger教授开发的JFLAP系统（http://www.jflap.org/）是算法可视化方面最有代表性且有巨大深度的成果之一。JFLAP系统是一个本地Java系统，它将《计算复杂性理论》课程中的知识点以GUI界面的方式进行诠释和解析。JFLAP的内容包括形式语言实验，非确定性有限自动机，非确定性下推自动机，多带Turing机，多种类型的文法、语法分析和L-系统。除了这些构造性和测时性例子以外，JFLAP还实现了从一种自动机形式到另外一种自动机形式的构造性证明实验，如将NFA变换为DFA、最少状态DFA、正则表达式以及正则语法等。

2. 新加坡国立大学可视化算法系统VisuAlgo

新加坡国立大学Steven Halim博士的可视化算法系统VisuAlgo（http://visualgo.net/）是该领域另一个最具代表性的成果。该系统基于HTML/CSS/JS技术，目前已经实现了排序类、栈类、哈希表、二叉堆等近20组算法的可视化。

3. 弗吉尼亚理工大学可视化算法系统Algoviz

由弗吉尼亚理工大学的C. Shaffer教授、J. Ernst教授，杜克大学的S. Rodger教授，以及威斯康辛大学的T. Naps教授合作的OpenDSA电子书项目(http://algoviz.org/OpenDSA/)开发了一个配套的算法可视化系统Algoviz (http://algoviz.org)。Algoviz目前由一个来自于全世界18所名校的20多名计算机专业教授组成的专家委员会指导，系统已经实现了600多组算法的可视化演示。Algoviz是一个基于互联网的系统，它以Java Applet的方式将数据结构与算法中知识点以网络化、可视化、动态化的方式进行演示和交互。

参考教材

Introduction to the Design and Analysis of Algorithms (3rd Edition), Anany Levitin, Pearson Education, Oct 2011, ISBN-10: 0132316811, ISBN-13: 978-0132316811.

算法设计与分析基础(第3版), (美)Anany Levitin著, 潘彦译, 清华大学出版社, 2015年1月, ISBN：9787302386346

Introduction to the Theory of Computation，3rd edition，Michael Sipser，Cengage Learning，Jun, 2012, ISBN-10: 113318779X, ISBN-13: 978-1133187790.

《计算理论导引》(第3版)，(美)迈克尔·西普塞(Michael Sipser)，段磊、唐常杰译，机械工业出版社，2015 年8月, ISBN：9787111499718.

封面图片及片花视频来源

封面图片来源

P versus NP problem

片花来源

NP Completeness for Dummies: NP Hard and NP Complete Problems (lec 2)

This video lecture is produced by S. Saurabh. He is B.Tech from IIT and MS from USA.

课程评价

教学资源

课程章节资源

课程章节	\| 文件类型		\| 修改时间	\| 大小	\| 备注
1.1 第1章算法概述		文档 .pptx	2017-04-10	3.10MB
1.2 第2章基于比较的排序算法		文档 .pptx	2017-04-10	2.17MB
1.3 第3章递归与分治方法		文档 .pptx	2017-04-10	4.48MB
1.4 第4章贪心法		文档 .pdf	2017-04-10	81.26MB
1.5 第5章穷举法		文档 .pptx	2017-04-10	1.64MB
1.6 第6章回溯法		文档 .pptx	2017-04-10	3.06MB
1.7 第7章动态规划方法(上)		文档 .pptx	2017-04-10	3.23MB
1.8 第8章动态规划方法(下)		文档 .pptx	2017-04-10	2.14MB
1.9 第9章分支限界法		文档 .pdf	2017-04-10	52.18MB
2.1 第0章绪论		文档 .pdf	2017-04-10	51.56MB
2.2 第1章正则语言		文档 .pdf	2017-04-10	118.47MB
2.3 第2章上下文无关文法(*)		文档 .pdf	2017-04-10	122.38MB
2.4 第3章丘奇图灵论题		文档 .pdf	2017-04-10	53.02MB
2.5 第4章可判定性		文档 .pdf	2017-04-10	40.64MB
2.6 第5章可归约性(*)		文档 .pdf	2017-04-10	54.04MB
2.7 第6章可计算性理论的高级专题(*)		文档 .pdf	2017-04-10	52.87MB
2.8 第7章时间复杂性		文档 .pdf	2017-04-10	106.08MB
2.9 第8章空间复杂性(*)		文档 .pdf	2017-04-10	62.44MB
2.10 第9章难解性(*)		文档 .pdf	2017-04-10	59.41MB
2.11 第10章复杂性理论高级专题(*)		文档 .pdf	2017-04-10	102.83MB

下载在线观看进入课程章节同步到网盘

课程章节

上篇算法设计与分析

下篇计算理论

提示框

取消进入课程

提示框

确定要报名此课程吗？

确定取消