《可计算理论》教学大纲.doc

《可计算理论》教学大纲 一、课程简介 课程中文名称：可计算理论 课程英文名称：Computability Theory 课程中文简介： 通过介绍图林机、递归函数、URM等计算模型及它们的等价性证明，引入可计算的概念，建立对Church-Turing命题的认同，初步掌握问题的不可判定性的证明方法，形成对问题的可计算性/不可判定性的直觉。 授课内容包括：计算模型（图林机、递归函数、URM）、Church-Turing命题、哥德尔编码、S-m-n定理、通用程序、可判定性与半可判定性、递归集与递归可枚举集、规约与类、递归定理。对软件工程专业的学生而言，可计算理论课程将帮助其建立起对整个学科的定性认识，课程的基本内容将对其未来的技术职业产生不可替代的影响。 课程英文简介： The purpose of the course is to have the students establish the instinct about computability. By discussing the well-known computation models and the proof of their equivalence, Church-Turing Thesis is introduced and reinforced by exercises. At the technical level, the students are exposed to the basic approaches of recursion, numbering and diagonalization. The topics covered by the course include computation models, Church-Turing Thesis, Godel index, S-m-n theorem, universal program, decidability and partial decidability, recursive set and recursive enumerable set, reduction and degree, recursion theorem. 二、课程教学内容及学时分配（含实践、自学、作业、讨论等的内容及要求） 教学内容 学时 课堂教学 讨论 作业及要求 自学及要求 团组大作业及要求 计算模型 （图林机、递归函数、URM） 8 8 作业的目的是熟悉计算模型是如何进行计算的 要求上课前自学教材中的相关章节 课后要对授课内容进行复习，对证明进行推导 Church-Turing命题 4 4 让学生将上课时讲的等价性证明自己完整地证一遍 习题课 3 3 哥德尔编码、S-m-n定理 6 6 作业的主要目的是建立如下直觉：可计算的一定是可编码的，以及可以对编码进行操作 通用程序 4 4 作业的目的是建立通用计算机的概念 可判定性与半可判定性 5 5 作业的目的是熟悉可判定性和半可判定性的论述方法 递归集与递归可枚举集 5 5 作业的目的是熟悉递归集和递归可枚举集的算法描述方法 规约与类 5 5 学会对问题的分类 递归定理 5 5 作业的目的是熟练递归定理的应用 习题与总结复习课 3 3 三、教学方法 本课程的教学实践活动运用多种教学方法和手段： 课程网站：扩充课堂内容，提供补充资料、电子课件。 习题课：第一次习题课确保学生对可计算的概念有个直观的认识，学期末习题课总结可计算理论的证明思路和方法。 答疑：主讲老师和助教将通过邮件、教学系统的渠道，对同学们课后遇到的问题进行解答。 四、考核及成绩评定方式 最终成绩由平时作业合期末考试成绩组合而成。各部分所占比例如下： 平时作业和上课参与程度：30%。主要考核对知识点的掌握程度。 期末考试：70%。主要考核对课程所有知识点的掌握和推理能力。 五、教材及参考书目 教材： Computability: an introduction to recursive function theory, Nigel Cutland, Cambridge University Press, 1990. 参考书目： Computability Theory, Barry Cooper, Chapman Hall/CRC, 2004. 可计算理性与计算复杂性导论，张立昂，北京大学出版社，2004。 撰写人：傅育熙