自动机,可计算性和复杂性6.045J Automata, Computability, and Complexity |
|
课程网址: | http://ocw.mit.edu/courses/electrical-engineering-and-computer-sc... |
主讲教师: | Prof. Nancy Lynch |
开课单位: | 麻省理工学院 |
开课时间: | 信息不详。欢迎您在右侧留言补充。 |
课程语种: | 英语 |
中文简介: | 本课程为本科生开设,介绍计算的基本数学模型和无限物体的有限表示法。课程节奏比6.840J/18.404J慢。课程主题包括:有限自动机和正则语言、上下文无关语言、图灵机、部分递归函数、Church的论文、不可判定性、可还原性和完整性、时间复杂性和NP完整性、概率计算和交互证明系统。 |
课程简介: | This course is offered to undergraduates and introduces basic mathematical models of computation and the finite representation of infinite objects. The course is slower paced than 6.840J/18.404J. Topics covered include: finite automata and regular languages, context-free languages, Turing machines, partial recursive functions, Church's Thesis, undecidability, reducibility and completeness, time complexity and NP-completeness, probabilistic computation, and interactive proof systems. |
关 键 词: | 有限自动机; 基本数学模型; 概率计算 |
课程来源: | 信息不详。欢迎您在右侧留言补充。 |
最后编审: | 2017-04-15:lkn |
阅读次数: | 29 |