课程编号：1111001
　　课程名称：计算理论
　　英文名称：ELEMENTS OF THE THEORY OF COMPUTATION
　　学分学时：3学分，54学时
　　开课学期：第一学期
　　开课学院：计算机学院
　　课程类型：硕士生选修课
　　先修课程：离散数学
　　主讲教师：金小刚 杨建刚
　　课程内容与基本要求：（限200字，5号字，宋体）
计算理论是计算机科学的基础课程，其主要内容包括形式语言与自动机、Turing机的可计算性与递归函数和计算复杂性三大部分，课程中采用了数学的处理问题的方法和计算计算机科学的观点。课程的基本要求如下：
　　1）了解和掌握形式语言的相关概念，通过对其生成模型和接受装置加以研究，获得不同复杂性的形式语言：正则语言、上下文无关语言和无限制语言。
　　2）了解各种计算模型（有穷自动机、下推自动机和Turing机）的不同的计算能力，进而理解Church-Turing论题。
　　3）掌握递归函数的有关内容，深化可计算性的理解。
　　4）对计算复杂性的问题有一个初步的了解。