计算机科学与技术学院

《计算机科学与技术学院》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机科学与技术学院063301组合数学32学时/2学分英文译名：Combinatorics适用领域：计算机应用技术、计算机软件理论、计算机系统结构、信息安全开课单位：计算机科学与技术学院任课教师：钱真、沈晶、潘海为教学目的：组合数学是现代数学中发展最快的数学分支，它的发展与计算机的发展密不可分，高速计算机使得各领域中组合问题的求解成为可能。同时，计算机科学本身的发展又带来了大量具有挑战性的组合问题。通过本课程的学习，目的是使学生掌握组合计数的基本原理和方法，了解典型的组合优化问题和模型，了解组合设计的基础知识，培养学生的组合思维方法和组合技巧的运用。预备知识或先修课程要求：高等数学，初等数论

2、教学方式及学时分配：课堂授课32学时学时教学内容教学方式2组合数学的起源，组合数学研究的典型问题、基本计数原理授课2集合的排列与组合、多重集的排列与组合授课2二项式定理、牛顿二项式定理、多项式定理授课2组合恒等式及其应用、排列与组合的生成算法授课2普通母函数及其应用授课2指数型母函数及其应用授课2递推关系及其应用授课2递推关系与母函数授课2全或型容斥公式、全非型公式、特定型的容斥公式及其应用授课2错位排列、带有禁止位置的排列授课2简单形式鸽巢原理、加强型鸽巢原理授课2Ramsey定理授课4群与置换群的基本概念，Polya定理授课2Polya定理、伯恩赛德引理授课2均衡不完全的区组设计，Hada

3、mard矩阵、拉丁方设计授课2简介组合优简介组合优化问题授课教学主要内容以及对学生的要求：学习内容：围绕组合数学的基本问题，重点介绍组合计数问题的求解方法、简介组合中存在问题和组合优化问题的求解。要求：学生学习本课程应具备的先修知识是高等数学(I)、(II)、初等数论。内容摘要：组合数学是一门研究离散对象的科学。主要研究满足一定条件的组态（组合模型）的存在性问题、计数问题、构造问题及组合优化问题。本课程介绍的主要内容包括：加法规则、乘法规则、一一对应规则；线排列和圆排列、不可重组合与可重组合、二项式及多项式定理、排列和组合的生成算法；重点介绍组合计数问题的求解方法，包括递推关系及其求解；用母函

4、数求解递推关系，母函数在排列组合中的应用；物件性质的组合，特定、全非、恰K性质型容斥原理；鸽巢原理，Ramsey原理；Burnside引理，polya定理，母函数型的Polya定理；简介存在问题和组合优化问题，包括拉丁方设计，均衡不完全的区组设计，Hadamard矩阵；搜索与优化，动态规划法。考核方式：闭卷笔试课程主要教材：组合数学.卢开澄．清华大学出版社主要参考书目：[1]程序设计中的组合数学．吴文虎主编．清华大学出版社，2005[2]组合数学．RichardA.Brualdi著.冯舜玺等译．机械工业出版社，2005063302计算理论32学时/2学分英文译名：TheoryofComputa

5、tion适用领域：计算机软件与理论，计算机应用技术开课单位：计算机科学与技术学院任课教师：黄少滨，姚念民，韩启龙教学目的：提高计算机理论修养，深刻认识计算以及计算机的局限性，了解集合，语言或计算的复杂度分类。预备知识或先修课程要求：离散数学教学方式及学时分配：全部使用多媒体手段课堂授课。学时教学内容教学方式2程序设计语言和可计算函数S和可计算函数授课2宏指令，原始递归函数，原始递归谓词授课2迭代运算，配对函数，原始递归运算授课2子函数的可计算性授课2停机问题，通用程序授课2递归可枚举集，Turing的基本模型授课2Turing机与可计算性与它接受的语言授课2非确定型Turing机授课2半Thu

6、e过程，文法，授课2部分递归函数授课2判定问题，字问题和Post对应问题授课2一阶逻辑的判定问题，有穷自动机授课2正则表达式，非正则语言授课2上下文无关文法，泵引理授课2下推自动机，确定型下推自动机授课2上下文有关文法，时间，空间复杂性授课教学主要内容及对学生的要求：教学主要内容包括可计算性，形式语言与自动机和计算复杂性和计算复杂性。需学习过高等数学、离散数学、数理逻辑课程。内容摘要：首先学习4个基本的计算模型：程序设计语言S，部分递归函数，文法和Turing机，证明它们的等价性。其中包括原始递归函数，通用程序，Turing机，过程和文法，不可判定的问题等概念和定理。然后学习形式语言与自动机方

7、面的知识，包括4种文法，重点学习正则语言和上下文无关语言。最后学习计算复杂性方面的知识，包括时间和空间复杂性，NP完全性等。考核方式：开卷笔试。课程主要教材：可计算性与计算复杂性导引．张立昂．北京大学出版社主要参考书目：[1]IntroductiontotheTheoryofComputation,MichaelSipser,ThomsonLearning，2002.9（有中文译本）[2]Elem