图论与组合数学教学大纲2016修改版.doc

图论与组合数学教学大纲一、课程名称：图论与组合数学 二、课程代码：021301001957三、课程英文名称：Graph Theory and Combinatorics 四、课程负责人：刘任任，肖芬，曹春红五、学时与学分：48学时（理论40学时，实验8学时），3.0学分六、课程性质：必修 七、适用专业：工科本科计算机科学与技术专业八、选课对象：计算机科学与技术专业九、预修课程：集合论与数理逻辑、C语言程序设计I、数据结构十、课程教材与参考书目：课程教材：1. 刘任任编著， 离散数学，中国铁道出版社，2009年12月；2. 刘任任主编，离散数学题解与分析，中国铁道出版社，2010年10月。参考书目：1. Kneneth H. Rosen, Discete Mathematics and Its Applications, Fifth Edition,2003年；2. Richard Johnsonbaugh, Discrete Mathematics, Prentice Hall Inc., 2000年；3. Kolman B., etc., Discrete Mathematical Structures， Prentice Hall Inc., 2001；4. Brualdi, R.A. (美)，组合数学(第四版)，北京机械工业出版社， 2005年2月；5. 卢开澄，组合数学，清华大学出版社，6. 孙吉贵等编著，离散数学，高等教育出版社，2002年；7. 陈莉等编著，离散数学，高等教育出版社，2002年。十一、开课单位：信息工程学院十二、课程与能力培养中的对应关系1、能力1.2: 掌握计算机科学与技术专业所要求的数学和自然科学基本知识，能将其用于计算机复杂工程问题的分析与建模；2、能力2.1：掌握文献检索、资料查询的基本方法，能够运用现代技术获取相关文献，具有资料阅读和文献研究能力，并用于计算机科学与技术相关的复杂工程问题的分析和推理；3、能力2.2：通过理论与实践相结合的系统学习，能够识别复杂工程问题中所涉及的数学、自然科学及计算机科学与技术专业的相关理论知识。十三、课程的目标图论和组合数学是现代数学的重要分支，是研究离散结构的存在、计数、分析和优化等问题的一门科学，是计算机科学与技术专业的基础理论课程。通过本课程的学习，使学生掌握图论与组合数学的基本原理和方法，了解和掌握无向图、有向图、连通图、排列与组合、容斥原理、递推关系和生成函数等基本知识，灵活运用所学知识对一些简单问题进行建模并编程求解。十四、教学内容、教学要求与学时分配序号教学内容教学要求学时教学方式能力序号1一、 绪论1. 图论与组合数学的发展史2. 图论与组合数学的关系和研究内容 3.图论与组合数学的应用举例1.掌握图论与组合数学的定义和内容；2.了解图论与组合数学的发展史、应用领域和发展方向。2学时授课辅导12二、 排列组合基本计数法则1. 两个基本的计数法则 2. 基本排列组合的计数方法 3. 可重复排列组合数的计数方法 4. 组合数应用5. 鸽巢原理 1. 了解加法原则和乘法原则，会求简单的排列组合问题；2. 掌握多重集合的排列和组合技巧；3. 掌握鸽巢原理，根据具体问题构造合适的鸽巢。4学时授课辅导1、33三、容斥原理1. 容斥原理介绍2. 有禁止位的排列1. 了解容斥原理的内容；2. 灵活运用对称筛公式解相关问题。4学时授课辅导14四、递推关系和生成函数1. 递推关系及其解法2. 生成函数1. 会建立递推关系，并用生成函数、迭代归纳法等求解递推关系；2. 了解Fibonacci数及其相关性质；3. 了解生成函数在组合计数中的应用。4学时授课辅导1、35五、 图与子图1. 图论基础知识2. 图的表示3. 图的运算，子图4. 图的连通性5. 最短通路问题应用1. 理解图、简单图、自图以及图的同构的定义；2. 理解图的连通性概念，掌握相关结论；3. 了解最短路问题及相关的算法。6学时授课辅导1、26六、树1. 树的定义2. 生成树3. 最优树应用1. 了解树的特性，理解生成树的定义；2. 掌握最优生成树算法。4学时授课辅导17七、E图和H图1. 七桥问题与E图2. 周游世界问题与H图3. 旅行商问题应用1. 掌握欧拉图与哈密顿图的相关理论和判别准则；2. 掌握TSP问题应用和求解方法。2学时授课辅导1、28八、匹配和独立1. 匹配2. 独立集和覆盖3. Ramsy 数1. 理解顶点、边的独立和覆盖的定义；2.利用Ramsy解决实际问题。4学时授课辅导1、39九、平面图1. 平面图的概念2. 欧拉公式3. 平面图着色1. 理解平面图；2. 利用欧拉公式求解具体问题；3. 掌握图的着色。2学时授课辅导110十、有向图1. 有向图的概念2. 有向通路3. 有向树4. 哈夫曼编码5. 网络最大流应用1. 了解有向图与无向图在问题建模时的区别及应用领域；2. 理解无向图中相关知识在有向图中的描述；3. 掌握哈夫曼编码、网络最大流中的相关应用。8学时授课辅导1、2、3十五、实验教学目的图论与组合数学实验是验证、巩固和补充课堂教学的理论知识的必要环节，通过图论与组合数学实验，培养学生初步具备问题建模和求解的能力；正确处理实验数据的能力，分析和综合实验结果以及撰写实验报告的能力。十六、实验教学内容及要求1、掌握排列组合数的基本法则，生成n个数的排列，从n个数中取m个数的组合数；2、实现最短路径求解算法；3、实现最优树构造算法，旅行商问题求解； 4、掌握哈夫曼编码原理，并实现。十七、实验教学安排本课程实验的具体安排如下：序号实验项目项目任务 实验要求实验类型实验学时能力序号1排列组合实验用VC+ 6.0编程实现排列、组合计数方法，递归计算Fabonacci数写出实验报告(包括排列、组合以及Fabonacci数的程序代码及结果记录)验证212最短路径实验用VC+ 6.0编程实现Dijkstra算法，求任意两点间的单源最短路径能正确输出结果，写出实验室报告（包括步骤、结果、解决方法、体会）综合22、33旅行商问题实验用VC+ 6.0编程实现最优树构造算法，实现TSP的求解写出实验室报告（包括算法、数据结构、程序代码以及运行结果）综合22、34最优树编码理解最优树的编码和译码，并用VC+ 6.0编程实现。对每个结点进行正确的编码并输出，并写出实验报告综合22、3十八、实验成绩考核与评定根据学生的实验