可计算性理论
来源：365英国上市公司官网
发布日期：2019-01-21浏览量：次
| 课程编号 |
812.5*021 |
| 课程名称 |
可计算性理论 |
| 任课老师 |
刘晓鸿 |
| 课程类型 |
必修/学位课 |
| 课程阶段 |
博士 |
| 学时学分 |
36学时2学分 |
| 基本要求 |
递归集与可枚举集的一般性质；不可解度最基本的分类，复杂度基本分类。 |
| 内容提要 |
基本计算模型，递归集与递归可枚举集的一般性质；不可解度中基本分类，基本的方法；
类似方法之下计算复杂度的结构NP一完全性。
|
| 教学方式 |
|
| 指定教材 |
|
| 参考书目 |
1. M.D Davis，《Computability Complexity and Languages》，New York：Academic Press，
1983（教材）
2. N. Cutlaml，《Computability》，Cambridge Univ. Press，1980
3. R.I. Soare，《Recursively Enumerable Sets and Degrees》，Springer-Verlag，1987
|
| 先修课程 |
数理逻辑，离散数学 |
| 开课学期 |
秋 |
