湖南工业大学研究生课程教学大纲课程编号：00812015编写人：唐承亮编写日期：2022-02-20计算理论与算法设计课程中文名称TheoryofComputation&DesignofAlgorithms课程英文名称春季开课单位开课学期计算机学院课程类别计算机科学与技术专业专业基础课职称唐承亮副教授联系电话主讲教师13873382719教学团队成员向华政彭成学时32教学及考学分n闭卷考试理论教学与实践教学相结合核方式面向学科（专业考核V考试计算机科学与技术学位领域）方式口考查预修课程形式语言或编译原理课程内容：《计算理论与算法设计》是计算机专业的一门专业基础课，计算理论将描述算法的本质，揭示计算机算法的能与不能、快与慢以及足够快的近似技巧等。一、计算理论导引：自动机、可计算性与复杂性：数学概念和术语：定义、定理和证明。2学时二、正则语言和上下文无关语言：有穷自动机、非确定性、正则表达式、非正则语4学时言、上下文无关文法、下推自动机、非上下文无关语言。4学时三、丘奇一图灵论题：图灵机、图灵机的变形、算法的定义。四、可判定性和可归约性：可判定语言：停机问题、图灵不可识别语言、语言理论中的不可判定问题、映射可归约性。4学时五、高级专题：递归定理、逻辑理论可判定性、图灵可归约性、信息定义。2学时六、复杂性理论与空间复杂性：度量复杂性、P类、NP类、NP完全性、NP完全问题、萨维奇定理、PSPACE类、PSPACE完全性、L类和NL类、NL完全。4学时七、算法设计与分析的基本概念、数学基础：通过典型的实际例子，介绍算法在计算机科学与技术中的地位、算法的基本概念、怎样分析算法、怎样设计算法：算法复杂2学时性函数的阶、求和方法、递归方程的求解方法和master定理、计数与概率
湖南工业大学研究生课程教学大纲 课程编号：00812015 编写人：唐承亮 编写日期：2022-02-20 课程中文名称 计算理论与算法设计 课程英文名称 Theory of Computation & Design of Algorithms 开课学期 春季 开课单位 计算机学院 课程类别 计算机科学与技术专业 专业基础课 主讲教师 唐承亮 职称 副教授 联系电话 13873382719 教学团队成员 向华政 彭成 学时 32 学分 2 教学及考 核方式 理论教学与实践教学相结合 闭卷考试 面向学科（专业 学位领域） 计算机科学与技术 考核 方式 √考试 □考查 预修课程 形式语言或编译原理 课程内容 ： 《计算理论与算法设计》是计算机专业的一门专业基础课，计算理论将描述算法的 本质，揭示计算机算法的能与不能、快与慢以及足够快的近似技巧等。 一、计算理论导引：自动机、可计算性与复杂性；数学概念和术语；定义、定理和 证明。 2 学时 二、正则语言和上下文无关语言：有穷自动机、非确定性、正则表达式、非正则语 言、上下文无关文法、下推自动机、非上下文无关语言。 4 学时 三、丘奇－图灵论题：图灵机、图灵机的变形、算法的定义。 4 学时 四、可判定性和可归约性：可判定语言；停机问题、图灵不可识别语言、语言理论 中的不可判定问题、映射可归约性。 4 学时 五、高级专题：递归定理、逻辑理论可判定性、图灵可归约性、信息定义。2 学时 六、复杂性理论与空间复杂性：度量复杂性、P 类、NP 类、NP 完全性、NP 完全 问题、萨维奇定理、PSPACE 类、PSPACE 完全性、L 类和 NL 类、NL 完全。 4 学时 七、算法设计与分析的基本概念、数学基础：通过典型的实际例子，介绍算法在计 算机科学与技术中的地位、算法的基本概念、怎样分析算法、怎样设计算法；算法复杂 性函数的阶、求和方法、递归方程的求解方法和 master 定理、计数与概率。 2 学时
八、分治算法的设计与分析原理：介绍分治算法的设计原理，用分治方法设计和2学时分析合并排序算法与快速排序算法。九、贪心算法的设计与分析原理：介绍贪心算法的基本概念，以活动选择问题为例讨论贪心算法的设计与分析原理，贪心算法的理论基础，Huffman编码问题和任务调度问题的算法设计与分析。2学时十、近似算法的设计分析原理：介绍随机算法的设计与分析原理，特别是随机算法的性能分析和概率分析方法，随机选择算法、随机快速排序算法以及其他几个随机算法2学时的设计与分析。十一、树搜索策略原理：介绍宽度第一搜索策略、深度第一搜索策略、爬山搜索策2学时略、Best-First搜索策略、分枝界限搜索策略、A*算法等。十二、修剪搜索方法原理：介绍修剪搜索方法的一般原理，求解选择问题、双变量2学时线性规划问题和1-Center问题的修剪搜索算法的设计与分析。课程内容英文简介Theory of Computation (TOC) is the study of the inherent capabilities and limitations ofcomputers: not just the computers of today, but any computers that could ever be built. By itsnature,thesubjectisclosetomathematics,withprogressmadebyconjectures,theorems,andproofs. What sets TOC apart, however, is its goal of understanding computation -- not only asa tool but as a fundamental phenomenon in its own right. We are interested in a broad range ofToC topics, including algorithms, complexity theory, cryptography, distributed computing,computational geometry, computational biology, and quantum computing. Algorithm designto make the students master the computer application in some actual problems solvingalgorithm, To make the students master the basic principle and technology of algorithm design,Make students have to for a given actual problem to design and implementation of algorithm,and evaluation of the algorithm; Make students to develop the problems to be solved, try todesign the best algorithm of good habits课程教学目标及重点、难点：了解和掌握形式语言的相关概念，掌握自动机的基本概念和基本理论，熟练掌握有穷自动机，下推自动机，Turing机，了解各种计算模型（有穷自动机、下推自动机和Turing机）的不同的计算能力，进而理解Church-Turing论题；掌握递归函数的有关内容，深化可计算性的理解：对计算复杂性的问题有一个初步的了解，能综合运用于各种基本问题的解决，为学习其它计算机课程提供计算理论方面的基础。算法设计要使学生掌握计
八、分治算法的设计与分析原理 ：介绍分治算法的设计原理，用分治方法设计和 分析合并排序算法与快速排序算法。 2 学时 九、贪心算法的设计与分析原理：介绍贪心算法的基本概念，以活动选择问题为例 讨论贪心算法的设计与分析原理，贪心算法的理论基础， Huffman 编码问题和任务调 度问题的算法设计与分析。 2 学时 十、近似算法的设计分析原理：介绍随机算法的设计与分析原理，特别是随机算法 的性能分析和概率分析方法，随机选择算法、随机快速排序算法以及其他几个随机算法 的设计与分析。 2 学时 十一、树搜索策略原理：介绍宽度第一搜索策略、深度第一搜索策略、爬山搜索策 略、Best-First 搜索策略、分枝界限搜索策略、A*算法等。 2 学时 十二、修剪搜索方法原理：介绍修剪搜索方法的一般原理，求解选择问题、双变量 线性规划问题和 1-Center 问题的修剪搜索算法的设计与分析。 2 学时 课程内容英文简介 Theory of Computation (TOC) is the study of the inherent capabilities and limitations of computers: not just the computers of today, but any computers that could ever be built. By its nature, the subject is close to mathematics, with progress made by conjectures, theorems, and proofs. What sets TOC apart, however, is its goal of understanding computation - not only as a tool but as a fundamental phenomenon in its own right. We are interested in a broad range of TOC topics, including algorithms, complexity theory, cryptography, distributed computing, computational geometry, computational biology, and quantum computing. Algorithm design to make the students master the computer application in some actual problems solving algorithm, To make the students master the basic principle and technology of algorithm design, Make students have to for a given actual problem to design and implementation of algorithm, and evaluation of the algorithm; Make students to develop the problems to be solved, try to design the best algorithm of good habits. 课程教学目标及重点、难点： 了解和掌握形式语言的相关概念，掌握自动机的基本概念和基本理论，熟练掌握有 穷自动机，下推自动机，Turing 机，了解各种计算模型（有穷自动机、下推自动机和 Turing 机）的不同的计算能力，进而理解 Church-Turing 论题；掌握递归函数的有关内容，深 化可计算性的理解；对计算复杂性的问题有一个初步的了解，能综合运用于各种基本问 题的解决，为学习其它计算机课程提供计算理论方面的基础。算法设计要使学生掌握计
算机应用中经常出现的一些实际问题的求解算法：使学生掌握常用的算法设计的基本原理与技术；使学生具有能针对所给实际问题来设计和实现算法，以及评价算法的能力：培养学生对于所要解决的问题，总是努力去设计出尽可能好的算法的良好习惯重点：形式语言的相关概念，自动机的基本概念和基本理论，Turing机计算能力，0-3型文法，判定性，NP-完全性。基本的非数值算法设计技术，包括递归与分治策略、贪心法、动态规划法、图的遍历方法等；难问题的算法设计技术，包括回溯法、分枝限界法，以及随机算法等难点：Turing机，0-3型文法，判定性，NP-完全性，难问题的算法设计技术。教学要求：一、深入了解可计算性的基础概念和基本理论，如形式语言与自动机，递归函数，入转换演算，图灵机，0-3型文法，判定性，NP-完全性等。二、掌握与计算机应用结合紧密的几个分支技术，如前后文无关文法、确定性语法分析，编译相关技术，语法分析树，LR(K)文法等，掌握相关的编程结构与技术要点。三、掌握基本的非数值算法设计技术，包括递归与分治策略、贪心法、动态规划法、图的遍历方法等；难问题的算法设计技术，包括回溯法、分枝限界法，以及随机算法等。四、能把计算理论与算法设计运用于自已领域的研究，分析在自己的研究领域中出现的算法、计算复杂度问题、判定性问题，NP-问题，增强阅读理解文献的能力，提高自已撰写的论文的理论深度。教材及主要参考书：[1]．（美）迈克尔.塞普瑟（MichaelSipser）著，段磊唐常杰译．计算理论导引（原书第3版）．机械工业出版社，2019，11.[2].（美）乔恩·克莱因伯格（JonKleinberg）著，王海鹏译．算法设计．人民邮电出版社，2021，3.[3].Kozen，Dexter.自动机和可计算理论（AutomataandComputability）：NewYork,NY:Springer-Verlag,1999.ISBN:0387949070[4].汪荣贵，杨娟，薛丽霞编著．算法设计与应用．机械工业出版社，2017，9.大作业：一、编程设计（如确定性语法分析，语法分析树，LR(K)文法，算法设计）。二、就某一内容（相关章节加上相关文献）做一次30一60分钟的presentation
算机应用中经常出现的一些实际问题的求解算法；使学生掌握常用的算法设计的基本原 理与技术；使学生具有能针对所给实际问题来设计和实现算法，以及评价算法的能力； 培养学生对于所要解决的问题，总是努力去设计出尽可能好的算法的良好习惯。 重点：形式语言的相关概念，自动机的基本概念和基本理论，Turing 机计算能力， 0-3 型文法，判定性，NP-完全性。基本的非数值算法设计技术，包括递归与分治策略、 贪心法、动态规划法、图的遍历方法等；难问题的算法设计技术，包括回溯法、分枝限 界法，以及随机算法等 难点：Turing 机，0-3 型文法，判定性，NP-完全性，难问题的算法设计技术。 教学要求： 一、深入了解可计算性的基础概念和基本理论，如形式语言与自动机，递归函数，λ转 换演算,图灵机， 0-3 型文法，判定性，NP-完全性等。 二、掌握与计算机应用结合紧密的几个分支技术，如前后文无关文法、确定性语法分析， 编译相关技术，语法分析树，LR(K)文法等，掌握相关的编程结构与技术要点。 三、掌握基本的非数值算法设计技术，包括递归与分治策略、贪心法、动态规划法、图 的遍历方法等；难问题的算法设计技术，包括回溯法、分枝限界法，以及随机算法等。 四、能把计算理论与算法设计运用于自己领域的研究，分析在自己的研究领域中出现的 算法、计算复杂度问题、判定性问题，NP-问题，增强阅读理解文献的能力，提高自己 撰写的论文的理论深度。 教材及主要参考书： [1]. （美）迈克尔.塞普瑟（Michael Sipser）著,段磊 唐常杰译. 计算理论导引（原 书第 3 版）. 机械工业出版社, 2019，11. [2]. （美）乔恩·克莱因伯格（Jon Kleinberg）著，王海鹏 译. 算法设计. 人民 邮电出版社,2021，3. [3]. Kozen, Dexter. 自动机和可计算理论（Automata and Computability）. New York, NY: Springer-Verlag, 1999. ISBN: 0387949070. [4]. 汪荣贵，杨娟，薛丽霞编著. 算法设计与应用. 机械工业出版社, 2017，9. 大作业： 一、编程设计（如确定性语法分析，语法分析树，LR(K)文法，算法设计）。 二、就某一内容（相关章节加上相关文献）做一次 30—60 分钟的 presentation