常用下载   /  加入收藏  
 
 
    欢迎访问!今天是2018年05月21日  星期一  四月初七      
更多»公告
    当前位置: 首页 » 本科生教育 » 教学大纲 » 信息与计算科学 »  《组合数学》教学大纲
 上一篇:《数理方程》教学大纲
 下一篇:《模糊数学》教学大纲
《组合数学》教学大纲
作者:管理员  来源:本站原创  发布时间:2016年5月11日  点击次数:473

《组合数学》教学大纲

Combinatorics

 

课程编码:09A03100              学分: 3.0      课程类别: 专业任选课

计划学时:48               其中讲课:48   实验或实践:0        上机:0

适用专业:信息与计算科学

推荐教材:许胤龙,孙淑玲. 组合数学引论(2)[M]. 合肥:中国科学技术大学出版社, 2010.

参考书目:

[1] 曹汝成. 组合数学[M]. 广州:华南理工大学出版社,2000.

[2] 卢开澄, 卢华明. 组合数学(4) [M]. 清华大学出版社, 2006.

[3] 单壿. 单壿老师教你学数学(组合数学的问题与方法) [M].上海:华东师范大学出版社, 2011.

[4] 殷剑宏. 组合数学[M].北京:机械工业出版社, 2006.

[5] 柯召, 魏万迪.组合论(上、下册) [M]. 北京:科学出版社, 1981.

[6] 姜建国, 岳建国. 组合数学(2) [M]. 西安:西安电子科技大学出版社, 2007.

[7] 史济怀. 组合恒等式[M]. 合肥:中国科学技术大学出版社, 2009.

[8] 罗伯茨等. 应用组合数学(英文版)(2) [M]. 北京:机械工业出版社, 2005.

[9] 李乔. 组合学讲义[M]. 北京:高等教育出版社, 2008.

[10] 布鲁迪 (Brualdi R.A.), 冯舜玺. 组合数学(原书第4) [M]. 北京:机械工业出版社. 2005.

[11] Fred S.Roberts, Barry Tesman, 冯速. 应用组合数学(原书第2) [M]. 北京:机械工业出版社, 2007.

 

课程的教学目的与任务

   组合数学主要研究一组离散对象满足一定条件的安排的存在性,以及这种安排的构造、枚举计数及优化等问题,它是整个离散数学的一个重要组成部分。课程的教学目的是让学生掌握基本的组合计数、构造和优化方法,为研究和解决计算机科学、管理科学及其它学科分支的问题打下数学基础。

课程的基本要求

本课程对数学的先修课程是高等代数。要求学生通过学习能够掌握用鸽巢原理证明一些存在性问题,用排列组合知识解决基本的排列组合问题,会用容斥原理解决多模式的计数问题,会建立和求解一些基本的递推关系,掌握生成函数这种解决计数问题的一般方法,会用Polya计数定理求解存在置换问题的计数问题。

本课程的特点是技巧性强,对于其它数学课程的依赖性弱,所以问题比较容易理解,但解决起来却有很大难度。同时,该课程对于某些问题又有一些一般性方法。学生学习中要注意增加独立思考,体会思考组合问题的乐趣,学习一些证明技巧。通过做必要的习题掌握一些一般性的方法。一题多解是组合数学的一大特点,学生要注意多总结梳理,才能达到对问题的深刻理解。

各章节授课内容、教学方法及学时分配建议(含课内实验)

 

第一章:  鸽巢原理                      建议学时:8学时

[教学目的与要求] 了解组合数学的基本问题;理解鸽巢原理及其加强形式的内容和Ramsey数及推广的Ramsey数的含义;掌握用鸽巢原理证明一些组合问题的存在性的方法,掌握Ramsey数及推广的Ramsey数的性质。

[教学重点与难点重点是鸽巢原理及其加强形式、Ramsey数的定义。难点是用鸽巢原理证明问题的方法。

[   ] 以课堂教授为主,课堂讨论为辅。

[   ]

第一节 鸽巢原理的简单形式

第二节 鸽巢原理的加强形式

第三节 Ramsey问题与Ramsey

第四节 Ramsey数的推广

 

第二章:  基本计数问题                 建议学时:8学时

[教学目的与要求] 理解并掌握多重集合的排列与组合问题中一些结论及其证明过程,第二类Stirling数及正整数分拆数的递推公式及其证明方法,掌握几种组合恒等式的证明方法,理解Ferrers图的含义及其应用于正整数的无序分拆的意义,理解并熟练掌握八种分配问题的计数方法,熟练利用组合分析的方法证明组合恒等式及某些计数问题。

[教学重点与难点重点是八种基本的计数问题的求解方法,难点是第二类Stirling数及正整数分拆数的递推公式及其证明方法,以及用组合分析的方法证明组合恒等式及某些计数问题。

[   ] 以课堂教授为主,课堂讨论为辅。

[   ]

第一节 加法原理与乘法原理

第二节 排列与组合

第三节 多重集合的排列与组合

第四节 二项式系数

第五节 集合的分划与第二类Stirling

第六节 正整数的分拆

第七节 分配问题综述

第三章:容斥原理                 建议学时:8学时

[教学目的与要求] 记住容斥原理的内容,理解其证明方法;能运用容斥原理解决具有有限重复数的多重集合的r组合数问题、错排问题、有禁止模式的排列问题和实际依赖于所有变量的函数个数的确定问题;记住麦比乌斯反演公式的形式,理解其证明过程,能运用它解决可重复的圆排列问题。

[教学重点与难点重点是容斥原理的内容及其证明方法,难点是有禁止模式的排列问题和实际依赖于所有变量的函数个数的确定问题和可重复的圆排列问题。

[   ] 以课堂教授为主,课堂讨论为辅。

[   ]

第一节 容斥原理

第二节 容斥原理的应用

第三节 麦比乌斯反演及可重复的圆排列

第四章:  递推关系                建议学时:8学时

[教学目的与要求] 掌握几种递推关系的建立方法;理解并掌握常系数线性齐次及非齐次递推关系的求解方法;能运用迭代归纳法求解递推关系;记住并理解Fibonacci数和Catalan数的定义及递推公式,会推导Fibonacci数和Catalan数的一些性质,能运用它们解决一些组合计数问题。

[教学重点与难点重点是递推关系的建立方法、常系数线性齐次及非齐次递推关系的求解方法、Fibonacci数和Catalan数的定义、递推公式及性质;难点是Catalan数的定义、递推公式及性质。

[   ] 以课堂教授为主,课堂讨论为辅。

[   ]

第一节 递推关系的建立

第二节 常系数线性齐次递推关系的求解

第三节 常系数线性非齐次递推关系的求解

第四节 常系数线性非齐次递推关系的求解

第五节 Fibonacci数和Catalan 

第五章:  生成函数                建议学时:8学时

[教学目的与要求] 理解形式幂级数的来历及其性质;能运用生成函数求解递推关系;掌握组合数的生成函数、排列数的指数型生成函数、分拆数的生成函数、组合型及排列型分配问题的生成函数的形式,能运用它们解决这些计数问题;掌握棋子多项式的形式,能运用它解决有限制位置的排列问题。

[教学重点与难点重点是生成函数的来历、性质,以及用生成函数解决各类问题的方法。难点是各类组合计数问题的生成函数的确定方法,棋子多项式的应用。

[   ] 以课堂教授为主,课堂讨论为辅。

[   ]

第一节 形式幂级数

第二节 形式幂级数的性质

第三节 用生成函数求解递推关系

第四节 生成函数在计数问题中的应用

第五节 有限制位置的排列及棋子多项式 

第六章:  Pólya计数理论                建议学时:8学时

[教学目的与要求] 理解置换群的基本知识;理解并掌握正多面体染色问题的数学模型建立方法;理解并掌握Burnside引理的内容及相关概念,会用Burnside引理解决计数问题;理解映射的等价类的定义,熟练掌握Pólya计数定理的内容,能熟练运用其解决染色计数问题。

[教学重点与难点重点是Pólya计数定理的推导过程及解决一些简单问题的方法,这是本章的难点,也是组合数学这门课程中最难的内容。

[   ] 以课堂教授为主,课堂讨论为辅。

[   ]

第一节 置换群的基本知识

第二节 计数问题的数学模型

第三节 Burnside引理

第四节 映射的等价类

第五节 Pólya计数定理

 

撰稿人:许振宇   审稿人:靳绍礼

 
» 上一篇:《数理方程》教学大纲
» 下一篇:《模糊数学》教学大纲
check_website_is_ok,made by zheng_guang_yu,Do not delete
 
Copyright 济南大学数学科学学院. All rights reserved.
地址:济南市市中区南辛庄西路336号济南大学西校区第七教学楼   邮编:250022   电话(传真):0531-82767313