【授课教师】刘田
【课程编号】04830260
【课程名称】理论计算机科学基础
【课程类型】本科生选修课
【课程性质】核心
【学时学分】周学时3,3学分
【先修要求】计算概论A,离散数学
【基本目的】
      使学生了解计算理论的研究对象、基本内容和基本方法,对计算有一个大的理论框架,掌握用计算模型来研究计算理论问题的手段和方法。
      1.通过可计算性理论的学习, 学生将理解什么是可计算的,什么是不可计算的,能回答“什么是计算”这样的问题。
      2.通过对形式语言与自动机理论的学习,将为学生提供学习编译原理、软件形式化等课程的知识基础。
      3.通过对计算复杂性理论的学习,学生将理解什么是容易计算的,什么是难以计算的,建立有效算法的概念。
      4.通过对计算理论中高级专题的接触,将使学生了解目前的发展方向,激发学生进一步深入学习的兴趣。
【内容提要】
      1.可计算性理论的基本内容:可计算函数、原始递归函数、通用程序、递归可枚举集、Turing机、Church-Turing论题、不可判定性等。
      2.形式语言与自动机理论的基本内容:Chomsky谱系、正则语言与有穷自动机、上下文无关语言与下推自动机、上下文有关语言与线性界限自动机等。
      3.计算复杂性理论的基本内容:复杂性度量、加速定理、时空分层定理、常见的复杂性类、NP完全性、近似算法等。
      4.介绍计算理论中的高级专题:计算随机性、密码学、非常规计算模型等。
【教学方式】
      课堂讲授与网络辅助相结合,每周讲授3学时.每次课后都有书面作业3-5题,每次作业都有课上总结.讲义和辅助材料将通过网络发布。
【教材参考】
      1.张立昂编著,可计算性与计算复杂性导引,北大出版社,1996。
      2.M.Sipser著, 张立昂、王捍贫、黄雄译,计算理论导引,机械工业出版社,2000。
      3.H.R.Lewis著,张立昂、刘田译,计算理论基础,清华大学出版社,2000。
      4.J.E.Hopcroft, R.Motwani, J.D.Ullman ,Introduction to Automata Theory,Languages,and Computation (Secend Edition) 自动机理论、语言和计算导引(第二版),影印版,清华大学出版社,2002。
      5.M.D.Davis, E.J.Weyuker著,张立昂、陈进元、耿素云译,可计算性、复杂性、语言,理论计算机科学基础,清华大学出版社,1989。
【成绩评定】作业占10%,平时测验(两次)占20%,期末考试70%。
【开课学期】春季
 

关于我们

研究方向

开设课程

科研成果

成员介绍

生活掠影

加入我们