《组合数学》PPT课件

《《组合数学》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、组合数学RichardA.Brualdi著冯舜玺等编译机械工业出版社任课教师：廖虎1办公室：软件学院四楼专业教研室办公电话：88451128住宅电话：82495874移动电话：13096981182电子邮件：xaLiaohu@126.com2绪论组合数学是一门古老的数学分支，其思想在社会科学、信息论、生物科学以及其他传统自然科学领域得到了广泛的应用。组合数学在计算机出现以后得以迅速发展。计算机科学就是算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机3科学的核心，而研究离散对象的

2、科学恰恰就是离散数学和组合数学；组合数学的发展改变了传统数学中分析和代数占统治地位的局面。现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另一类就是研究离散对象的组合数学。组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科学、编码和4密码学、物理、化学、生物等学科中均有重要应用。微积分和近代数学的发展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序就是算法，在绝

3、大多数情况下，计算机的算法是针对离散的对象，而不是在作数值计算。5正是因为有了组合算法才使人感到，计算机好象是有思维的。组合数学不仅在软件技术中有重要的应用价值，在企业管理，交通规划，战争指挥，金融分析等领域都有重要的应用。在美国有一家用组合数学命名的公司，他们用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。6此外，试验设计也是具有很大应用价值的学科，它的数学原理就是组合设计。用组合设计的方法解决工业界中的试验设计问题，在美国已有专门的公司开发这方面的软件。最近，德国一位著名组合数学家利用组合数

4、学方法研究药物结构，为制药公司节省了大量的费用，引起了制药业的关注。7组合数学与计算机软件随着计算机网络的发展，计算机的使用已经影响到了人们的工作，生活，学习，社会活动以及商业活动，而计算机的应用根本上是通过软件来实现的。在美国有一种说法：将来一个国家的经济实力可以直接从软件产业反映出来。8我国在软件上的落后，要说出根本的原因可能并不是简单的事，除了技术和科学上的原因外，可能还跟我们的文化(汉字)，管理水平，教育水平，思想素质等诸多因素有关。除去这些人文因素以外，一个最根本的原因就是我国的信息技术的数学基础

5、十分薄弱，这个问题不解决，我们就难成为软件强国。9然而问题决不是这么简单，信息技术的发展已经涉及到了很深的数学知识，而数学本身发展程度并不是单凭几个聪明的头脑去想想就行了，而更重要的是需要集体的合作和力量，就象软件的开发需要多方面的人员的合作。美国的软件之所以能领先，其关键就在于在数学基础上他们有很强的实力，有很多杰出的人才。10一般人可能会认为数学是一门纯粹的基础科学，1+1的解决可能不会有任何实际的意义。如果真是这样，一门纯粹学科的发展落后几年，甚至十年，关系也不大。然而中国的软件产业的发展已向数学基础

6、提出了急切的需求：网络算法和分析、信息压缩、网络安全、编码技术、系统软件、并行算法、数学机械化和计算机推理11等等。此外，与实际应用有关的还有许多许多需要数学基础的算法，如运筹规划，金融工程，计算机辅助设计等。如果我们的软件产业还是把眼光一直盯在应用软件和第二次开发，那么我们在应用软件这个领域也会让国外的企业抢去很大的市场。如果我们现在在信息技术的数学基础上，大力支持和投入，那将是亡羊补牢，犹未为晚；12胡锦涛同志在1998年接见“五四”青年奖章获得者时发表的讲话中指出：组合数学是不同于传统的纯数学的一个分

7、支，它还是一门应用学科，一门交叉学科。他希望中国的组合数学研究能够为国家的经济建设服务。如果21世纪是信息社会的世纪，那么21世纪也必将是组合数学大有可为的世纪。13《组合数学》课每周上课两次，4学时，安排14周，共56学时。根据教学计划和培养目标要求，我们学习以下内容：第一章什么是组合数学第二章鸽巢原理第三章排列与组合第四章生成排列与组合第五章二项式系数第六章容斥原理及其应用第七章递推关系与生成函数第八章特殊计数序列14考核方式：期末笔试占70%，平时作业占30%，每星期一交一次作业。由各个班长送到四楼办

8、公室。本课件制作由廖虎独立完成，该课件几乎可以取代教材，已经公布在学院公共实验室网上，同学们可以自己下载浏览。15第1章什么是组合数学组合数学是一门古老的数学分支，其思想在社会科学、信息论、生物科学以及其他传统自然科学领域得到了广泛的应用。组合学问题在生活中随处可见。在计算机科学领域，组合数学是算法设计理论以及算法分析理论的重要数学工具。16例如，计算下列赛制下总的比赛次数：n个球队参赛，每队只和其他队比赛一次;