2009版计算机科学与技术学院工学硕士研究生专业课程教学大纲.doc

计算机科学与技术学院 063301 组合数学 32学时/ 2学分 英文译名：Combinatorics 适用领域：计算机应用技术、计算机软件理论、计算机系统结构、信息安全 开课单位：计算机科学与技术学院 任课教师：钱真、沈晶、潘海为 教学目的：组合数学是现代数学中发展最快的数学分支，它的发展与计算机的发展密不可分，高速计算机使得各领域中组合问题的求解成为可能。同时，计算机科学本身的发展又带来了大量具有挑战性的组合问题。通过本课程的学习，目的是使学生掌握组合计数的基本原理和方法，了解典型的组合优化问题和模型，了解组合设计的基础知识，培养学生的组合思维方法和组合技巧的运用。 预备知识或先修课程要求：高等数学，初等数论 教学方式及学时分配：课堂授课32学时 学时 教学内容 教学方式 2 组合数学的起源，组合数学研究的典型问题、基本计数原理 授课 2 集合的排列与组合、多重集的排列与组合 授课 2 二项式定理、牛顿二项式定理、多项式定理 授课 2 组合恒等式及其应用、排列与组合的生成算法 授课 2 普通母函数及其应用 授课 2 指数型母函数及其应用 授课 2 递推关系及其应用 授课 2 递推关系与母函数 授课 2 全或型容斥公式、全非型公式、特定型的容斥公式及其应用 授课 2 错位排列、带有禁止位置的排列 授课 2 简单形式鸽巢原理、加强型鸽巢原理 授课 2 Ramsey定理 授课 4 群与置换群的基本概念，Polya定理 授课 2 Polya定理、伯恩赛德引理 授课 2 均衡不完全的区组设计，Hadamard矩阵、拉丁方设计 授课 2 简介组合优简介组合优化问题 授课 教学主要内容以及对学生的要求： 学习内容：围绕组合数学的基本问题，重点介绍组合计数问题的求解方法、简介组合中存在问题和组合优化问题的求解。 要 求：学生学习本课程应具备的先修知识是高等数学(I)、(II)、初等数论。 内容摘要：组合数学是一门研究离散对象的科学。主要研究满足一定条件的组态（组合模型）的存在性问题、计数问题、构造问题及组合优化问题。本课程介绍的主要内容包括：加法规则、乘法规则、一一对应规则；线排列和圆排列、不可重组合与可重组合、二项式及多项式定理、排列和组合的生成算法；重点介绍组合计数问题的求解方法，包括递推关系及其求解；用母函数求解递推关系，母函数在排列组合中的应用；物件性质的组合，特定、全非、恰K性质型容斥原理；鸽巢原理，Ramsey原理；Burnside引理，polya定理，母函数型的Polya定理；简介存在问题和组合优化问题，包括拉丁方设计，均衡不完全的区组设计，Hadamard矩阵；有哪些信誉好的足球投注网站与优化，动态规划法。 考核方式：闭卷笔试 课程主要教材：组合数学.卢开澄清华大学出版社 主要参考书目： [1] 程序设计中的组合数学吴文虎主编清华大学出版社，2005 [2] 组合数学Richard A. Brualdi著.冯舜玺等译机械工业出版社，2005 063302 计算理论 32学时/ 2学分 英文译名：Theory of Computation 适用领域：计算机软件与理论，计算机应用技术 开课单位：计算机科学与技术学院 任课教师：黄少滨，姚念民，韩启龙 教学目的：提高计算机理论修养，深刻认识计算以及计算机的局限性，了解集合，语言或计算的复杂度分类。 预备知识或先修课程要求：离散数学 教学方式及学时分配：全部使用多媒体手段课堂授课。 学时 教学内容 教学方式 2 程序设计语言和可计算函数S和可计算函数 授课 2 宏指令，原始递归函数，原始递归谓词 授课 2 迭代运算，配对函数，原始递归运算 授课 2 子函数的可计算性 授课 2 停机问题，通用程序 授课 2 递归可枚举集，Turing的基本模型 授课 2 Turing机与可计算性与它接受的语言 授课 2 非确定型Turing机 授课 2 半Thue过程，文法， 授课 2 部分递归函数 授课 2 判定问题，字问题和Post对应问题 授课 2 一阶逻辑的判定问题，有穷自动机 授课 2 正则表达式，非正则语言 授课 2 上下文无关文法，泵引理 授课 2 下推自动机，确定型下推自动机 授课 2 上下文有关文法，时间，空间复杂性 授课 教学主要内容及对学生的要求：教学主要内容包括可计算性，形式语言与自动机和计算复杂性和计算复杂性。需学习过高等数学、离散数学、数理逻辑课程。 内容摘要：首先学习4个基本的计算模型：程序设计语言S，部分递归函数，文法和Turing机，证明它们的等价性。其中包括原始递归函数，通用程序，Turing机，过程和文法，不可判定的问