《可計算理論》教學大綱

1、可計算理論教學大綱一、課程簡介課程中文名稱：可計算理論課程英文名稱：computability theory課程中文簡介：通過介紹圖林機、遞歸函數(shù)、urm等計算模型及它們的等價性證明，引入可計算的概念，建立對church-turing命題的認同，初步掌握問題的不可判定性的證明方法，形成對問題的可計算性/不可判定性的直覺。授課內(nèi)容包括：計算模型（圖林機、遞歸函數(shù)、urm）、church-turing命題、哥德爾編碼、s-m-n定理、通用程序、可判定性與半可判定性、遞歸集與遞歸可枚舉集、規(guī)約與類、遞歸定理。對軟件工程專業(yè)的學生而言，可計算理論課程將幫助其建立起對整個學科的定性認識，課程的基本內(nèi)容將

2、對其未來的技術職業(yè)產(chǎ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 stud

3、ents 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, r

4、eduction and degree, recursion theorem. 二、課程教學內(nèi)容及學時分配（含實踐、自學、作業(yè)、討論等的內(nèi)容及要求）教學內(nèi)容學時課堂教學討論作業(yè)及要求自學及要求團組大作業(yè)及要求計算模型（圖林機、遞歸函數(shù)、urm）88作業(yè)的目的是熟悉計算模型是如何進行計算的1） 要求上課前自學教材中的相關章節(jié)2） 課后要對授課內(nèi)容進行復習，對證明進行推導church-turing命題44讓學生將上課時講的等價性證明自己完整地證一遍習題課33哥德爾編碼、s-m-n定理66作業(yè)的主要目的是建立如下直覺：可計算的一定是可編碼的，以及可以對編碼進行操作通用程序44作業(yè)的目的是建立通用計算

5、機的概念可判定性與半可判定性55作業(yè)的目的是熟悉可判定性和半可判定性的論述方法遞歸集與遞歸可枚舉集55作業(yè)的目的是熟悉遞歸集和遞歸可枚舉集的算法描述方法規(guī)約與類55學會對問題的分類遞歸定理55作業(yè)的目的是熟練遞歸定理的應用習題與總結復習課33三、教學方法本課程的教學實踐活動運用多種教學方法和手段：課程網(wǎng)站：擴充課堂內(nèi)容，提供補充資料、電子課件。習題課：第一次習題課確保學生對可計算的概念有個直觀的認識，學期末習題課總結可計算理論的證明思路和方法。答疑：主講老師和助教將通過郵件、教學系統(tǒng)的渠道，對同學們課后遇到的問題進行解答。四、考核及成績評定方式最終成績由平時作業(yè)合期末考試成績組合而成。各部分所占比例如下：平時作業(yè)和上課參與程度：30%。主要考核對知識點的掌握程度。期末考試：70%。主要考核對課程所有知識點的掌握和推理能力。五、教材及參考書目教材：1. computability: an introduction to recursive function theory, nigel cutland, cambridge university press, 1990.參考書目：1. computabilit