» MIT 开放式课件首页 » 电气工程与计算机科学 » 自动机、可计算性以及计算复杂性理论，2005 春季

6.045J/18.400J 自动机、可计算性以及计算复杂性理论，2005 春季

一个NP完全问题. "P和NP相等吗?" 是现代数学中最重要的尚未解决的问题之一。（图片由MIT OCW提供。）

课程特点

本课程的特点是有一系列的作业。除此之外习题课上还有很多实际问题。 6.045J 是“计算机理论科学”系的一门核心专业课。

课程简介

本课程是为本科生开设的一门课，介绍计算的基本数学模型以及怎样用有限的信息来表示无穷的对象。本课程紧随着 6.840J/18.404J. 主要涵盖以下几个主题: 有穷状态自动机和正则语言, 上下文无关语言, 图灵机, 部分递归函数, Church定理, 不可判定性, 可归约性和完全性, 时间复杂度和NP-完全性, 概率计算, 交互式证明系统.

师资

授课老师:
Prof. Nancy Lynch

课程安排

讲座:
2节 / 星期
1.5 小时 / 节

习题课:
1节/星期
1小时/节

课程级别

本科生

翻译人员

张家发南京大学软件学院06级硕士

翻译人单位

南京大学

新增特性

下载本课程

翻译

葡萄牙语

西班牙语

反馈意见

请您把关于OCW或本课程的反馈意见发给我们.

搜索