组合数学.pdf

063301组合数学32 学时/ 2 学分英文译名：Combinatorics适用领域：计算机应用技术、计算机软件理论、计算机系统结构、信息安全开课单位：计算机科学与技术学院任课教师：钱真、沈晶、潘海为教学目的：组合数学是现代数学中发展最快的数学分支，它的发展与计算机的发展密不可分， 高速计算机使得各领域中组合问题的求解成为可能 同时， 计算机科学本身的发展又带来了大量具有挑战性的组合问题 通过本课程的学习， 目的是使学生掌握组合计数的基本原理和方法，了解典型的组合优化问题和模型，了解组合设计的基础知识，培养学生的组合思维方法和组合技巧的运用预备知识或先修课程要求：高等数学，初等数论教学方式及学时分配：课堂授课 32 学时学时教学内容教学方式2组合数学的起源，组合数学研究的典型问题、基本计数原理授课2集合的排列与组合、多重集的排列与组合授课2二项式定理、牛顿二项式定理、多项式定理授课2组合恒等式及其应用、排列与组合的生成算法授课2普通母函数及其应用授课2指数型母函数及其应用授课2递推关系及其应用授课2递推关系与母函数授课2全或型容斥公式、全非型公式、特定型的容斥公式及其应用授课2错位排列、带有禁止位置的排列授课2简单形式鸽巢原理、加强型鸽巢原理授课2Ramsey 定理授课4群与置换群的基本概念，Polya 定理授课2Polya 定理、伯恩赛德引理授课2均衡不完全的区组设计，Hadamard 矩阵、拉丁方设计授课2简介组合优简介组合优化问题授课教学主要内容以及对学生的要求：学习内容：围绕组合数学的基本问题，重点介绍组合计数问题的求解方法、简介组合中存在问题和组合优化问题的求解。

要求：学生学习本课程应具备的先修知识是高等数学(I)、(II)、初等数论内容摘要：组合数学是一门研究离散对象的科学主要研究满足一定条件的组态（组合模型） 的存在性问题、计数问题、构造问题及组合优化问题本课程介绍的主要内容包括： 加法规则、乘法规则、一一对应规则；线排列和圆排列、不可重组合与可重组合、二项式及多项式定理、排列和组合的生成算法；重点介绍组合计数问题的求解方法，包括递推关系及其求解；用母函数求解递推关系，母函数在排列组合中的应用；物件性质的组合，特定、全非、恰 K 性质型容斥原理；鸽巢原理，Ramsey 原理；Burnside 引理，polya 定理，母函数型的 Polya 定理；简介存在问题和组合优化问题，包括拉丁方设计，均衡不完全的区组设计，Hadamard 矩阵；搜索与优化，动态规划法考核方式：闭卷笔试课程主要教材：组合数学.卢开澄.清华大学出版社主要参考书目：[1]程序设计中的组合数学.吴文虎主编.清华大学出版社,2005[2]组合数学.RichardA. Brualdi 著.冯舜玺等译.机械工业出版社,2005063302计算理论32 学时/ 2 学分英文译名：Theory of Computation适用领域：计算机软件与理论，计算机应用技术开课单位：计算机科学与技术学院任课教师：黄少滨，姚念民，韩启龙教学目的：提高计算机理论修养，深刻认识计算以及计算机的局限性，了解集合，语言或计算的复杂度分类。

预备知识或先修课程要求：离散数学教学方式及学时分配：全部使用多媒体手段课堂授课学时 教学内容教学方式2程序设计语言和可计算函数 S 和可计算函数授课2宏指令，原始递归函数，原始递归谓词授课2迭代运算，配对函数，原始递归运算授课2子函数的可计算性授课2停机问题，通用程序授课2递归可枚举集，Turing 的基本模型授课2Turing 机与可计算性与它接受的语言授课2非确定型 Turing 机授课2半 Thue 过程，文法，授课2部分递归函数授课2判定问题，字问题和 Post 对应问题授课2一阶逻辑的判定问题，有穷自动机授课2正则表达式，非正则语言授课2上下文无关文法，泵引理授课2下推自动机，确定型下推自动机授课2上下文有关文法，时间，空间复杂性授课教学主要内容及对学生的要求： 教学主要内容包括可计算性， 形式语言与自动机和计算复杂性和计算复杂性需学习过高等数学、离散数学、数理逻辑课程内容摘要：首先学习 4 个基本的计算模型：程序设计语言 S，部分递归函数，文法和 Turing 机，证明它们的等价性其中包括原始递归函数，通用程序，Turing 机，过程和文法， 不可判定的问题等概念和定理 然后学习形式语言与自动机方面的知识， 包括 4 种文法，重点学习正则语言和上下文无关语言。

最后学习计算复杂性方面的知识， 包括时间和空间复杂性，NP 完全性等考核方式：开卷笔试课程主要教材： 《可计算性与计算复杂性导引》张立昂北京大学出版社主要参考书目：[1]Introduction to the Theory of Computation, Michael Sipser, Thomson Learning,2002.9（有中文译本）[2]Elements of the Theory of Computation(Second Edition), Prentice Hall,Inc. 1998(有中文译本)063302随机过程32 学时/ 2 学分英文译名：Stochastic Processes适用领域：计算机应用技术、计算机软件与理论、计算机系统结构任课教师：马春光开课单位：计算机科学与技术学院预备知识或先修课程要求：学生必须具备高等数学和概率论基础知识教学目的：通过课程学习，使学生初步掌握随机过程的基本理论和方法，掌握几类重要随机过程模型并熟悉它们的应用背景，培养严谨的数学思维教学方式及学时分配：课堂讲授 28 学时，课堂讨论 4 学时学时 教学内容教学方式2概率空间，随机变量及其分布授课2随机变量的数字特征，随机变量的特征函数（1）授课2随机变量的特征函数（2） ，条件数学期望授课2随机过程定义，随机过程的分类和举例授课2随机过程的有限维分布函数族，随机过程的数字特征课堂讨论2复随机过程，几类重要的随机过程授课2泊松过程的定义，泊松过程的数学模型授课2泊松过程的到达时间与到达时间分布授课2泊松过程的条件分布，复合泊松过程授课2习题课课堂讨论2马尔可夫过程的定义，马尔可夫链的转移概率与概率分布（1）授课2马尔可夫链的转移概率与概率分布（2） ，马尔可夫链例题授课2齐次马尔可夫链状态分类授课2齐次马尔可夫链状态空间的分解授课2转移概率的稳定性能授课2习题课课堂讨论教学主要内容及对学生的要求：教学内容包括概率论基础、随机过程的基本概念、泊松过程、马尔可夫过程等三部分。

选修本课程的学生应该具有高等数学和概率论基础知识，应该具有敢于钻研理论问题的态度、较为严谨的数学思维和较好的自主学习能力内容摘要：概率论基础知识；随机过程的一般概念，随机过程的分布及其数字特征，常见的几类随机过程的定义、背景和性质；泊松过程的定义，泊松过程相关分布，泊松过程的实际应用和若干推广；平稳过程、正态过程、维纳过程的定义、基本性质、实际背景；马尔可夫过程、马尔可夫链的基本概念，转移概率与概率分布，状态分类与性质， 极限分布，平稳分布与状态空间的分解考核方式：闭卷，笔试课程主要教材：随机过程. 张卓奎, 陈慧婵. 西安电子科技大学出版社,2003.主要参考书目：[1]随机过程同步学习. 张卓奎, 陈慧婵. 西安电子科技大学出版社,2004.[2]Introduction to Probability. DimitriP.Bertsekas, John N. Tsitsiklis. MIT LectureNotes.063401现代计算机体系结构32 学时/2 学分英文译名：Archtecture of Modern Computer适用领域：计算机应用技术计算机系统结构开课单位：计算机科学与技术学院任课教师：李静梅教学目的：通过本课程的学习，要求学生能够掌握计算机系统结构的分析和设计方法，同时掌握最新的计算机流水技术、分支预测技术和并行处理技术。

预备知识或先修课程要求：基本掌握程序设计、数据结构、操作系统、编译原理、计算机原理、数字逻辑、微机系统与接口、嵌入式技术教学方式及学时分配：多媒体与黑板结合授课，理论授课学时16，专题讲座与讨论 12 学时， 实验 4 学时学时教学内容教学方式2计算机系统性能评价标准专题讨论2先进微体系结构（多核处理器、流处理器及 PIM 结构）的比较授课2流水线中的相关和冲突（数据相关、结构相关、控制相关）授课2相关与冲突的解决方案（基于 WinDLX 实现）授课2用实例解决流水线中的相关现象（1）实验2用实例解决流水线中的相关现象（2）实验2指令集并行技术与循环展开技术授课2超标量、超流水及超长指令字处理机介绍（模拟分析）授课2超线程技术（粗粒度多线程、细粒度多线程及同时多线程技术）专题讨论2SIMD 计算机的结构（全并行 SIMD 阵列处理机、流水线 SIMD 向量处理机）专题讨论2MIMD 计算机体系结构、计算模型（MIMD 共享存储模型,MIMD 分布存储模型,MIMD 通讯联接模型）专题讨论2共享存储体系与多处理机中的 Cache 一致性 （协议分析） 、 基于目录的 Cache一致性（协议分析）授课2指令分支预测技术专题讨论2RISC、CSIC 及 EPIC 混合体系结构专题讨论2互联网络结构（超立方体、混洗交换、网格结构、交叉开关）授课2体系结构中的单级互联网络与多级互联网络及消息传送授课教学主要内容及对学生的要求：本课程主要立足于系统设计者的角度，分析和评价影响系统性能、价格等的因素；研究计算机系统结构的分析和设计方法；掌握各种并行处理技术在现代计算机系统中的应用和实现方法。

要求学生具有数字逻辑、计算机组成原理、程序设计、操作系统和数据结构等方面的知识基础，具有独立查阅、学习相关文献的能力内容摘要：第 1 章介绍计算机系统结构的基本概念、指令系统的设计思想与寻址方式、I/O 系统的整体设计及其流量分析、存储体系发展过程和设计实现的几种常用技术手段，这部分内容是学习计算机系统结构必需具备的最基本知识，要求学生必需全面了解与掌握；第 2 章介绍流水处理技术以及超流水、超标量和超长指令字处理机超流水和超标量流水线技术的采用，可以在一个时钟周期内完成多条指令的执行； 而 VLIW 描述了另外一种指令集的设计思想，在这种指令集中编译器把许多简单、独立的指令组合到一条指令字中；第 3 章介绍并行处理机设计的基础知识，主要介绍并行处理机的互连网络、消息传递机制以及基于多处理单元阵列结构的并行算法等内容；第 4 章讨论多处理机系统的相关技术，包括多处理器的概念、分类、结构和性能，介绍把多台处理机组成高并行度系统的关键技术，并深入分析这类系统的改进方法；第 5 章介绍非诺依曼结构的新型计算机体系结构， 包括数据流计算机、 归约机、 数据库与知识库机、以及智能计算机等；第 6 章介绍嵌入式计算机系统的基本概念，分析软硬件的组成和设计过程；第 7 章介绍嵌入式系统的高级形式—SoC 系统；第 8 章着重介绍多内核处理器的设计，包括 Cache 组织方式、Cache 一致性协议、片上互连网络设计以及同步机制等问题。

考核方式：实验(30 分)+专题讨论(30 分)+期末考试(40 分)课程主要教材：[1]现代计算机系统结构.李静梅等.清华大学出版社,2009主要参考书目：[1]计算机系统结构（第四版）.李学干.西安电子科技大学出版社,2006[2]计算机系统结构.郑纬民.清华大学出版社,2007[3] 《计算机系统结构》学习指导与题解.李学干.西安电子科技大学出版社,2006[4] 《计算机系统结构》典型题解析与实战模拟.张春元,罗莉.国防科技大学出版社,2007063402高级计算机网络32 学时/ 2 学分英文译名：Advanced Computer Network适用领域：计算机应用技术、计算机软件与理论任课教师：王慧强 国林开课单位：计算机科学与技术学院预备知识或先修课程要求：计算机网络教学目的： 通过该。