加入收藏 | 设为首页 | 搜索
计算机学院( 国家示范性软件学院 )简介
北京邮电大学1977年开设计算机通信本科专业,1985年成立计算机工程系,1998年成立计算机科学与技术学院。2008年,按照“学科归位”的原则,将计算机科学与技术学院等六个单位计算机学科的资源重新整合为计算机学院。2020年,将原计算机学院、软件学院、网络技术研究院调整、合并组建新的计算机学院(国家示范性软件学院),并支撑网络与交换技术国家重点实验室(北京邮电大学)。
课程信息
可计算性理论
课程编号  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
先修课程  数理逻辑,离散数学
开课学期  秋
更多内容