· 学校主页    · 学院主页

《计算理论》

发布时间:2011-03-17  浏览次数:2204

 

计算理论

一、课程基本信息


课程编号:063302
中文名称:计算理论
英文名称:Theory of Computation
课程性质:必修课
考核方式:考试
总 学 时:32
总 学 分:2
任课教师:
韩启龙
预修课程:离散数学、数据结构、算法复杂性初步


二、内容简介

         计算机科学与其它学科一样同样有它自己的基本问题:什么是算法?什么是能计算的?什么是不能计算的?什么时候可以认为一个算法是实际可行的?60多年来计算机科学家一直在考虑这些问题并且给出充满智慧的回答,这一切对计算机科学产生了深刻的影响。本课程的目的是介绍渗透在计算机科学中的这些基本思想、模型和结果,它们都是该领域的基本范例,它们有很多理由是值得学习的。首先,现代计算机科学中的很多东西直接或间接地以它们为基础。其次,这些思想和模型是漂亮、有力的,是数学建模的杰出例子,是有长久价值的。此外,它们更是历史的一部分,是我们这个领域的“共同潜意识”。不首先了解它们,是很难理解计算机科学的。

       本课程主要是针对计算机科学与技术专业的硕士生开设的一门理论课程,总学时为32学时,其主要内容包括形式语言与自动机、Turing机的可计算性与递归函数,计算复杂性以及数理逻辑的相关内容。考试有闭卷考试和平时作业两部分组成,其中闭卷部分占80%,主要考查这门课程所涉及的基本理论、原理和经典的结论,为强调证明思想的重要性,在闭卷考试部分证明占20分;而平时作业占20%,要求大家去跟踪目前这一领域中的新思想、新方法。

 

三、教材及主要参考资料

教材:

《计算理论》 唐常杰译 机械工业出版社

参考资料:

1. Elements of The Theory of Computation (Second Edition) Harry R.Lewis,Christos H.Papadimtriou Prentice Hall清华大学出版社(影印版)

2. Introduction to the Theory of Computation(计算理论导引)Michael Sipser 机械工业出版社

3. 自动机理论、语言和计算导论(第2版)John E.Hopcroft,Rajeev Motwani,Jeffrey D.Ullman清华大学出版社(影印版


四、课程资料下载

 


   


    
 

 

© 2017哈尔滨工程大学计算机科学与技术学院
地址:哈尔滨市南岗区南通大街145号哈尔滨工程大学21号楼 邮编:150001 电话:0451-82519406
管理维护:智能信息处理研究中心 技术支持:信息化处