《计算机科学与技术学院》由会员分享,可在线阅读,更多相关《计算机科学与技术学院(42页珍藏版)》请在金锄头文库上搜索。
1、计算机科学与技术学院063301 组合数学 32 学时/ 2 学分英文译名:Combinatorics适用领域:计算机应用技术、计算机软件理论、计算机系统结构、信息安全开课单位:计算机科学与技术学院任课教师:钱真、沈晶、潘海为教学目的:组合数学是现代数学中发展最快的数学分支,它的发展与计算机的发展密不可分,高速计算机使得各领域中组合问题的求解成为可能。同时,计算机科学本身的发展又带来了大量具有挑战性的组合问题。通过本课程的学习,目的是使学生掌握组合计数的基本原理和方法,了解典型的组合优化问题和模型,了解组合设计的基础知识,培养学生的组合思维方法和组合技巧的运用。 预备知识或先修课程要求:高等数
2、学,初等数论教学方式及学时分配:课堂授课 32 学时学时 教学内容 教学方式2 组合数学的起源,组合数学研究的典型问题、基本计数原理 授课2 集合的排列与组合、多重集的排列与组合 授课2 二项式定理、牛顿二项式定理、多项式定理 授课2 组合恒等式及其应用、排列与组合的生成算法 授课2 普通母函数及其应用 授课2 指数型母函数及其应用 授课2 递推关系及其应用 授课2 递推关系与母函数 授课2 全或型容斥公式、全非型公式、特定型的容斥公式及其应用 授课2 错位排列、带有禁止位置的排列 授课2 简单形式鸽巢原理、加强型鸽巢原理 授课2 Ramsey 定理 授课4 群与置换群的基本概念,Polya
3、定理 授课2 Polya 定理、伯恩赛德引理 授课2 均衡不完全的区组设计,Hadamard 矩阵、拉丁方设计 授课2简介组合优简介组合优化问题 授课教学主要内容以及对学生的要求:学习内容:围绕组合数学的基本问题,重点介绍组合计数问题的求解方法、简介组合中存在问题和组合优化问题的求解。要 求:学生学习本课程应具备的先修知识是高等数学(I)、(II)、初等数论。内容摘要:组合数学是一门研究离散对象的科学。主要研究满足一定条件的组态(组合模型)的存在性问题、计数问题、构造问题及组合优化问题。本课程介绍的主要内容包括:加法规则、乘法规则、一一对应规则;线排列和圆排列、不可重组合与可重组合、二项式及多
4、项式定理、排列和组合的生成算法;重点介绍组合计数问题的求解方法,包括递推关系及其求解;用母函数求解递推关系,母函数在排列组合中的应用;物件性质的组合,特定、全非、恰 K 性质型容斥原理;鸽巢原理,Ramsey 原理;Burnside 引理,polya 定理,母函数型的 Polya 定理;简介存在问题和组合优化问题,包括拉丁方设计,均衡不完全的区组设计,Hadamard 矩阵;搜索与优化,动态规划法。考核方式:闭卷笔试课程主要教材:组合数学.卢开澄清华大学出版社主要参考书目:1 程序设计中的组合数学吴文虎主编清华大学出版社,20052 组合数学Richard A. Brualdi 著.冯舜玺等译
5、机械工业出版社, 2005063302 计算理论 32 学时/ 2 学分英文译名:Theory of Computation适用领域:计算机软件与理论,计算机应用技术开课单位:计算机科学与技术学院任课教师:黄少滨,姚念民,韩启龙教学目的:提高计算机理论修养,深刻认识计算以及计算机的局限性,了解集合,语言或计算的复杂度分类。预备知识或先修课程要求:离散数学教学方式及学时分配:全部使用多媒体手段课堂授课。学时 教学内容 教学方式2 程序设计语言和可计算函数 S 和可计算函数 授课2 宏指令,原始递归函数,原始递归谓词 授课2 迭代运算,配对函数,原始递归运算 授课2 子函数的可计算性 授课2 停机
6、问题,通用程序 授课2 递归可枚举集,Turing 的基本模型 授课2 Turing 机与可计算性与它接受的语言 授课2 非确定型 Turing 机 授课2 半 Thue 过程,文法, 授课2 部分递归函数 授课2 判定问题,字问题和 Post 对应问题 授课2 一阶逻辑的判定问题,有穷自动机 授课2 正则表达式,非正则语言 授课2 上下文无关文法,泵引理 授课2 下推自动机,确定型下推自动机 授课2 上下文有关文法,时间,空间复杂性 授课教学主要内容及对学生的要求:教学主要内容包括可计算性,形式语言与自动机和计算复杂性和计算复杂性。需学习过高等数学、离散数学、数理逻辑课程。内容摘要:首先学习
7、 4 个基本的计算模型:程序设计语言 S,部分递归函数,文法和 Turing 机,证明它们的等价性。其中包括原始递归函数,通用程序,Turing 机,过程和文法,不可判定的问题等概念和定理。然后学习形式语言与自动机方面的知识,包括 4 种文法,重点学习正则语言和上下文无关语言。最后学习计算复杂性方面的知识,包括时间和空间复杂性,NP 完全性等。考核方式:开卷笔试。课程主要教材:可计算性与计算复杂性导引张立昂北京大学出版社 主要参考书目: 1 Introduction to the Theory of Computation, Michael Sipser, Thomson Learning,2
8、002.9(有中文译本)2 Elements of the Theory of Computation(Second Edition), Prentice Hall,Inc. 1998(有中文译本)063303 随机过程 32 学时/ 2 学分英文译名:Stochastic Processes适用领域:计算机应用技术、计算机软件与理论、计算机系统结构任课教师:马春光开课单位:计算机科学与技术学院预备知识或先修课程要求:学生必须具备高等数学和概率论基础知识教学目的:通过课程学习,使学生初步掌握随机过程的基本理论和方法,掌握几类重要随机过程模型并熟悉它们的应用背景,培养严谨的数学思维。教学方式及学
9、时分配:课堂讲授 28 学时,课堂讨论 4 学时。学时 教学内容 教学方式2 概率空间,随机变量及其分布 授课2 随机变量的数字特征,随机变量的特征函数(1) 授课2 随机变量的特征函数(2) ,条件数学期望 授课2 随机过程定义,随机过程的分类和举例 授课2 随机过程的有限维分布函数族,随机过程的数字特征 课堂讨论2 复随机过程,几类重要的随机过程 授课2 泊松过程的定义,泊松过程的数学模型 授课2 泊松过程的到达时间与到达时间分布 授课2 泊松过程的条件分布,复合泊松过程 授课2 习题课 课堂讨论2 马尔可夫过程的定义,马尔可夫链的转移概率与概率分布(1) 授课2 马尔可夫链的转移概率与概
10、率分布(2) ,马尔可夫链例题 授课2 齐次马尔可夫链状态分类 授课2 齐次马尔可夫链状态空间的分解 授课2 转移概率的稳定性能 授课2 习题课 课堂讨论教学主要内容及对学生的要求:教学内容包括概率论基础、随机过程的基本概念、泊松过程、马尔可夫过程等三部分。选修本课程的学生应该具有高等数学和概率论基础知识,应该具有敢于钻研理论问题的态度、较为严谨的数学思维和较好的自主学习能力。内容摘要:概率论基础知识;随机过程的一般概念,随机过程的分布及其数字特征,常见的几类随机过程的定义、背景和性质;泊松过程的定义,泊松过程相关分布,泊松过程的实际应用和若干推广;平稳过程、正态过程、维纳过程的定义、基本性质
11、、实际背景;马尔可夫过程、马尔可夫链的基本概念,转移概率与概率分布,状态分类与性质,极限分布,平稳分布与状态空间的分解。考核方式:闭卷,笔试课程主要教材:随机过程张卓奎, 陈慧婵西安电子科技大学出版社,2003.主要参考书目:1 随机过程同步学习辅导张卓奎, 陈慧婵西安电子科技大学出版社,2004.2 随机过程初级教程 (第二版). 美Samuel Karlin, Howard M. Taylor 著, 庄兴元, 陈宗洵, 陈庆华 译. 人民邮电大学出版社, 2007.3 A First Course in Stochastic Processes (英文版, 第二版). Samuel Kar
12、lin, Howard M. Taylor. 人民邮电出版社, 2007.4 Introduction to Probability. Dimitri P. Bertsekas, John N. Tsitsiklis. MIT Lecture Notes.063401 现代计算机体系结构 32 学时/2 学分英文译名:Archtecture of Modern Computer适用领域:计算机应用技术计算机系统结构开课单位:计算机科学与技术学院任课教师:李静梅教学目的:通过本课程的学习,要求学生能够掌握计算机系统结构的分析和设计方法,同时掌握最新的计算机流水技术、分支预测技术和并行处理技术。预
13、备知识或先修课程要求:基本掌握程序设计、数据结构、操作系统、编译原理、计算机原理、数字逻辑、微机系统与接口、嵌入式技术教学方式及学时分配:多媒体与黑板结合授课,理论授课学时 16,专题讲座与讨论 12 学时,实验4 学时学时 教学内容 教学方式2 计算机系统性能评价标准 专题讨论2 先进微体系结构(多核处理器、流处理器及 PIM 结构)的比较 授课2 流水线中的相关和冲突(数据相关、结构相关、控制相关) 授课2 相关与冲突的解决方案(基于 WinDLX 实现) 授课2 用实例解决流水线中的相关现象(1) 实验2 用实例解决流水线中的相关现象(2) 实验2 指令集并行技术与循环展开技术 授课2
14、超标量、超流水及超长指令字处理机介绍(模拟分析) 授课2 超线程技术(粗粒度多线程、细粒度多线程及同时多线程技术) 专题讨论2 SIMD 计算机的结构(全并行 SIMD 阵列处理机、流水线 SIMD 向量处理机) 专题讨论2 MIMD 计 算 机 体 系 结 构 、 计 算 模 型 ( MIMD 共 享 存 储 模 型 ,MIMD 分 布 存 储 模 型 ,MIMD通 讯 联 接 模 型 )专题讨论2 共 享 存 储 体 系 与 多 处 理 机 中 的 Cache 一 致 性 ( 协 议 分 析 ) 、 基 于 目 录 的 Cache 一 致 性( 协 议 分 析 )授课2 指令分支预测技术
15、专题讨论2 RISC、 CSIC 及 EPIC 混合体系结构 专题讨论2 互联网络结构(超立方体、混洗交换、网格结构、交叉开关) 授课2 体系结构中的单级互联网络与多级互联网络及消息传送 授课教学主要内容及对学生的要求:本课程主要立足于系统设计者的角度,分析和评价影响系统性能、价格等的因素;研究计算机系统结构的分析和设计方法;掌握各种并行处理技术在现代计算机系统中的应用和实现方法。要求学生具有数字逻辑、计算机组成原理、程序设计、操作系统和数据结构等方面的知识基础,具有独立查阅、学习相关文献的能力。内容摘要:第 1 章介绍计算机系统结构的基本概念、指令系统的设计思想与寻址方式、I/O 系统的整体
16、设计及其流量分析、存储体系发展过程和设计实现的几种常用技术手段,这部分内容是学习计算机系统结构必需具备的最基本知识,要求学生必需全面了解与掌握;第 2 章介绍流水处理技术以及超流水、超标量和超长指令字处理机。超流水和超标量流水线技术的采用,可以在一个时钟周期内完成多条指令的执行;而 VLIW 描述了另外一种指令集的设计思想,在这种指令集中编译器把许多简单、独立的指令组合到一条指令字中;第 3 章介绍并行处理机设计的基础知识,主要介绍并行处理机的互连网络、消息传递机制以及基于多处理单元阵列结构的并行算法等内容;第 4 章讨论多处理机系统的相关技术,包括多处理器的概念、分类、结构和性能,介绍把多台处理机组成高并行度系统的关键技术,并深入分析这类系统的改进方法;第 5 章介绍非诺依曼结构的新型计算机体系结构,包括数据流计算机、归约机、数据库与知识库机、以及智能计算机等