离散数学-前言2013下.ppt

《离散数学-前言2013下.ppt》由会员分享，可在线阅读，更多相关《离散数学-前言2013下.ppt（74页珍藏版）》请在三一办公上搜索。

1、离 散 数 学,中国石油大学（华东）,计算机与通信工程学院计算机科学系,2023年11月16日星期四,引 言,离散数学是现代数学的一个重要分支，是计算机类专业的重要课程。它以研究离散量的结构及其相互间的关系为主要目标，其研究对象一般是有限个或可数个元素，因此离散数学可以充分描述计算机学科离散性的特点。由于离散数学在计算机科学中的重要作用，国内外几乎所有大学的计算机类专业的教学计划中都将其列为核心课程进行重点建设，它是其他骨干课程，如数据结构、操作系统、人工智能、计算机网络、软件工程、编译原理等的先修课程，国内许多大学将其作为计算机专业类研究生入学考试的内容。,引 言,为什么离散数学在计算学科的

2、知识掌握中有着举足轻重的意义呢?,？,引 言,1.计算学科的概念2.计算科学与数学的关系3.计算学科与离散数学的关系4.离散数学课程概述5.离散数学与计算机软件6.离散数学在国外的状况7.关于离散数学的一些应用8.如何学习离散数学,1.计算学科的概念,计算学科（Computing Science）即我们所熟悉的计算机科学与技术及相关学科的简称。计算学科是对描述和变换信息的算法过程，包括其理论、分析、设计、效率分析、实现和应用等进行的系统研究的一门学科。它涉及计算过程的分析如可计算性、算法，研究有关计算机的各种现象、揭示其规律与本质如计算机的设计和使用、可计算性硬件和软件的实际实现问题。,1.计

3、算学科的概念,计算学科的基本问题是能行与效率的问题,即它的核心问题是“能行”问题(Practicability)：1)什么是（实际）可计算的？什么是（实际）不可计算的？2)如何保证计算的自动性、有效性及正确性？,1.计算学科的概念,计算学科作为现代技术的标志，已成为世界各国经济增长的主要动力。但如何认识这门学科，它究竟属于理科还是工科，属于科学还是属于工程的范畴，这是困扰国内外计算机科学界很长时间且争论不休的问题。计算学科诞生于20世纪40年代初，它的理论基础可以说在这之前就已经建立起来了。正是电子数字计算机的问世才促进这一门学科的发展。,1.计算学科的概念,世人一般公认1946年2月14日研

4、制成功的ENIAC（电子数字积分器和计算器，Electronic Numerical Integrator and Calculator）是世界上第一台通用电子数字计算机（事实上，早在1943年，英国数学家图灵领导制造出了一台名叫“巨人”（Colossus）的电子计算机，它专门用于译码。由于英国政府的保密制度，故人们对它的成就了解甚少）。美国的普渡大学于1962年开设了最早的计算机科学学位课程。,1.计算学科的概念,在计算机产生之初及随后的一、二十年时间里，计算机主要用于数值计算。大多数科学家认为使用计算机仅为编程问题，不需作任何深刻的科学思考，计算机从本质上说是一种职业而一门学科。到了20世

5、纪70、80年代，计算技术得到了迅猛的发展和广泛的应用，并开始渗透到大多数科学领域。这时人们普遍争论的问题是：计算机科学是否作为一门学科？它是科学还是工程？它属于理科还是工科？或者只是一门技术、一个计算商品的研制者或销售者？,1.计算学科的概念,1985年春，ACM（美国计算机协会）和IEEECS（国际电子电气工程师学会计算机分会）组成联合攻关小组，开始了对“计算作为一门学科”的存在性证明。1989年1月，该小组提交了计算作为一门学科（Computing as a discipline）的报告。第一次给出了计算学科一个透彻的定义，回答了计算学科中长期以来一直争论的一些问题，完成了计算学科的“存

6、在性”证明，还提出了未来计算科学教育必须解决的二个重大问题整个学科核心课程详细设计及整个学科综述性导引课程的构建。1991年，在这报告的基础上提交了关于计算学科教学计划CC1991（Computing Curricula 1991）。2001年12月，提交了最终的CC2001报告。,1.计算学科的概念,计算作为一门学科报告及CC1991、CC2001一起解决了三个重要问题：第一个重大问题（计算作为一门学科的存在性证明）的解决。对学科本身的发展至关重要。如果在众多分支领域都取得了重大成果并已得到广泛应用的“计算”，连作为一门学科的地位都不清楚，那么它的发展势必要受到很大的限制。,1.计算学科的概

7、念,第二个重大问题（整个学科核心课程详细设计）的解决，将为高校制定计算机教学计划奠定基础。确定一个公认的本科生应该掌握的核心内容，将避免教学计划设计中的随意性，从而为我们科学地制定教学计划奠定基础。,1.计算学科的概念,第三个重大问题（整个学科综述性导引课程的构建）的解决，将使人们对整个学科的认知科学化、系统化和逻辑化。如果人们对计算学科的认知能建立在公理化的基础之上，则该学科可被认为是严谨的科学、成熟的学科，从而有助于它的发展，并将由此而得到人们的尊重。,1.计算学科的概念,攻关小组的结论是：计算学科所研究的根本问题是能行问题（什么能被（有效地）自动进行）。计算学科的基本原理已纳入理论、抽象

8、和设计这3个具有科学技术方法意义的过程中。学科的各分支领域正是通过这3个过程来实现它们各自的目标。而这3个过程要解决的都是计算过程中的“能行性”和“有效性”问题。这两个问题渗透在包括硬件和软件在内的理论、方法、技术的研究和应用的研究和开发之中，且学科的方法论的主要理论基础以离散数学为代表的构造性数学与能行性问题形成了天然的一致。,2.计算科学与数学的关系,数学是现代科学的重要基础，当然也是计算科学的主要基础。数学方法在现代科技的发展中已经成为一种必不可少的认识手段。它的主要作用是为科技研究提供：（1）简洁精确的形式化语言；（2）数量分析和计算的方法；（3）逻辑推理的工具。人们公认高技术本质上就

9、是数学技术，而计算学科（即我们所熟悉的计算机科学与技术）也离不开数学。,2.计算科学与数学的关系,从数学的角度出发，数学本身可分为连续数学和离散数学。离散和连续是现实世界中物质运动对立统一的两个方面，离散数学和连续数学是描述、刻画现实物质世界的重要工具。最早的数学本质上是一种离散型的数学，但随着微积分的出现，对整个数学的研究发生了深刻的影响。人们以一种连续的观点研究数学，描述自然科学研究中的各种具体问题，从而形成了现在占统治地位的连续数学。,2.计算科学与数学的关系,随着现代科学技术的发展，特别是计算机科学技术的兴起，离散数学又重新找到了它自己原有的位置。“能行性”这个计算学科的根本问题决定了

10、计算机本身的结构和它处理的对象都是离散型的，甚至许多连续型问题也必须在转化为离散型问题以后才能被计算机处理。所以计算机科学与技术本质上是一门离散数学技术。,2.计算科学与数学的关系,在计算科学中，无论是理论研究还是技术研究的成果，最终目标要体现在计算机软件产品的程序指令系统应能机械地、严格地按照程序指令执行，决不能无故出错。计算机系统的这一客观属性和特点决定了计算机的设计、制造、以及各种软件系统开发的每一步都应该是严密的、精确无误的。就目前基于图灵机这一理论计算模型和存储程序式思想设计制造的计算机而言，它们只能处理离散问题或可用构造性方式描述的问题，而且这些问题必须对给定的论域存在有穷表示。,

11、2.计算科学与数学的关系,至于非离散的连续性问题，如实数域上的函数计算，方程求根等还只能用近似的逼近方法。于是，由于计算模型的非连续性特点，使得以严密、精确著称的数学尤其是以离散数学为代表的应用数学成为描述计算学科理论、方法和技术的主要工具。数学与电子科学（特别是微电子技术）构成了计算学科的基础。,2.计算科学与数学的关系,与数学相比，电子技术的重要性对计算科学而言不如数学，因为数学提供了计算科学最重要的学科思想和方法论基础，而电子技术只提供了电子计算机的实现技术，它仅仅只是对计算科学许多思想和方法的一种当前最现实、最有效的实现技术手段而已。当科学技术的手段提到发展时，完全有可能有某一项新技术

12、归结为有效地取代电子技术（如光技术、生物技术等等），但计算科学的数学基础可能变化不大。,2.计算科学与数学的关系,从事计算科学的人都知道，计算科学中不仅许多理论是用数学描述的，而且许多技术也是用数学描述的。大多数计算科学理论不仅仅是对研究对象变化规律的陈述，而且由于能行性这一本质的核心问题和特点的作用，理论描述中常通过方法折射出技术的思想和步骤，而从理论通过方法跨越到技术则完全取决于理论的深刻认识和理解。一个人如果看懂了以形式化方法描述的技术文献，自然明白技术上应该怎样去做。,2.计算科学与数学的关系,至于计算机技术专业的学生为何要学习数学这个问题的答案，了解了上面所讲的计算学科与数学的关系后

13、就不言而喻了：计算机科学植根于数学，从而数学是必须掌握的基础知识；另外如果我们已经拥有牢固的数学基础，则能大大提高我们本身的逻辑推理能力、抽象思维能力和形式化思维能力，从而今后在学习任何一门计算机科学的专业主干课程时，都不会遇上任何思维理解上的困难。,3.计算学科与离散数学的关系,(1)从计算机科学学科发展的需要看离散数学的地位。20世纪的计算机出现，带动了世界性的信息革命的伟大进程。计算机科学在信息革命中的学科地位有如牛顿力学在工业革命中的学科地位一样，由计算机出现带动的信息革命当然计算机科学将起着主导的作用。,3.计算学科与离散数学的关系,当前计算机科学在发展过程中面对着如下两个问题：一是

14、信息革命要求计算机科学要将计算机的应用扩大到包含所有的问题领域和深入到每个问题领域的深处而越来越细致越来越复杂；二是一旦让计算机去解决问题，那么计算机应自动地在有限和有效的时间内得出解。前者指出计算机科学的任务就是要用计算机的硬件、外设和软件构成一个系统，使得许多不同领域的问题都能在这样的计算机系统中得到解决。为了完成这个任务，就必须用一种符号语言构成一个包括了不同领域的通用模型。,3.计算学科与离散数学的关系,离散数学就是指出构成一个包括了不同领域的通用模型的思维方法，并且告诉我们怎样用不同的语言（符号语言、图形语言、逻辑语言等）从最简单的对象（集合）出发表示通用模型。后者指出计算机科学必须

15、了解让计算机去解决问题在通用模型中的结构，由于要求在有限和有效时间内计算机自动完成，那么问题求解的方法必然是构造性的，所了解的结构必然是一种离散结构。离散数学中的求解问题的方法就是基于离散结构的构造性思维方法。,3.计算学科与离散数学的关系,从离散数学的基本内容和计算学科的发展情况来看，许多计算学科的问题，都可以在离散数学的范围中表达，都可以试验抽象为离散数学的问题，不能否认离散数学在较通用的层面上描述了计算学科所表现出来的信息革命的许多模型，为现代计算学科的发展和应用提供了理论基础。从学习的角度来看，离散数学的思维方法能够为计算机科学所用，“离散数学能够使我们在更高的高度去了解和学习计算机科

16、学”。,3.计算学科与离散数学的关系,因此可以说高等数学将大家从中学的传统的欧基里德的思维方式带进高等教育的基于工业革命的学科表达语言的富于创造性的思维方式，而离散数学将大家带进信息革命的学科表达语言中去发展和创造具有时代特点的先进的思维方式。,3.计算学科与离散数学的关系,(2)从计算机科学学生能力角度培养的看离散数学的作用。计算机出现的五十多年间，人们追求着和出现了许多计算机信息革命带来的信息产品，但是信息产品受工业产品的观念上的影响，使得计算机科学的学科发展带来了偏差，使得整个学科的发展都是“软件跟着硬件走”。我们不能将自己的学生培养成计算机系统的奴隶，而应该培养成计算机系统的主人，我们

17、的学生不能给计算机系统所塑造，将他们变成计算机，而是教育学生怎样地塑造计算机系统。,3.计算学科与离散数学的关系,在计算机科学知识掌握的过程中应是“硬件跟着软件走，软件跟着模型走，模型跟着学科实际应用走；学科实际应用跟着自然走”。而最主要的培养环节应该是软件跟着模型走，模型跟着学科实际应用走。关于学生的培养目标就是要培养自己的学生能够根据实际应用问题提出计算机应用的模型，并用硬件和软件资源去构造计算机系统去完成模型中所提出来的工作。,3.计算学科与离散数学的关系,因此，我们的学生需要如下三个方面的能力：构造模型的能力；算法设计的能力；程序设计的能力。所谓构造模型的能力就是在通用的语言（例如数量

18、代数和非数量代数的语言、符号逻辑语言、数理统计语言等）中构造解决实际问题的模型的能力。换言之，用通用语言关于现实需要计算机求解的实际问题进行编码，使现实需要计算机求解的实际问题描述成领域性模型（如管理模型、控制模型、推理模型、学习模型等），离散数学中的大部分内容是讨论构造或生成领域性模型的基本方法。,3.计算学科与离散数学的关系,所谓算法设计的能力是应用计算机的基本能力，也是计算机应用学科的计算机应用基础和应用技术的一个基本问题。让计算机来解决问题，目前人们不仅要告诉计算机需要做什么？而且还要告诉计算机怎样做？当领域性模型化为计算机能懂的计算模型后，将需要计算机解决的问题写成规划过程告诉计算机

19、做什么和怎样做，使得计算机根据这个规划各步骤能自动地得到问题的解，这种规划就是解决这个问题的算法。算法过程的控制是算法设计的关键，它决定算法的存在性和算法的效率。算法过程的控制是由计算模型的结构来决定的。离散数学中所讨论的离散结构（例如偏序结构、良序结构、群、环、域、各种代数格、置换、范畴等）以及这些结构的同态、同构等，在算法设计中都起着重要的作用。,3.计算学科与离散数学的关系,(3)关于计算机科学的思维方法看离散数学的思维训练。既然我们要作为计算机系统的主人去塑造能满足实际应用的计算机系统，那么怎样塑造计算机系统呢？去塑造计算机系统需要什么样的思维方法呢？,3.计算学科与离散数学的关系,首

20、先，计算机系统要解决的问题并不是个别的问题，也并不是某个领域上的特殊问题，要解决某个领域的所有能用计算机进行计算的问题，因此，关于计算机科学的思维方法必须是在足够通用的层面上的思维方法。如果所掌握或所习惯的思维方法仅限制在是某些特殊的领域，那么，随着计算机应用的不断扩大和计算机信息革命的不断扩大，将会使得思维的方法带有很大的局限性。当然，最通用的层面是自然层面，然而，自然层面上的对象还不能为现代计算机(现代计算模型)所了解。因为，我们选择塑造计算机系统的层面既带有最大的通用性，又能为现代计算机系统所了解的层面。在现代计算技术的支持下，这个层面就是符号处理层面。,3.计算学科与离散数学的关系,其

21、次，我们是要去塑造计算机系统，我们的所有思维都要立足于能“塑造”性，因此，思维的可构造性，即在考虑构成计算机系统的所有对象都必须能够有某种方法在有限的时间内构造出来。因此塑造计算机系统的基本思维是构造性思维。,3.计算学科与离散数学的关系,再其次，构造性思维建立在怎样的结构上，换言之，找寻满足构造性思维的对象结构。换言之，找寻满足构造性思维的对象结构。显然在连续结构上是很难进行构造性思维的，在连续结构上存在着不能用符号完全表示的对象。例如，一个无理数它不能用0，1，2，3，4，5，6，7，8，9完全表示出来。因为计算机只认识符号，所以塑造计算机系统的构造性思维在某种离散结构上进行。因此，计算机

22、科学的基本思维是在符号处理的通用层面上的基于离散结构的构造性思维。离散数学就是在符号处理的通用层面上讨论满足构造性思维的离散结构。,4.离散数学课程概述,离散数学，又称为组合数学。离散数学是计算机出现以后迅速发展起来的一门数学分支。计算机科学就是算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是离散数学。离散数学的发展改变了传统数学中分析和代数占统治地位的局面。,4.离散数学课程概述,离散数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。微

23、积分和近代数学的发展为近代的工业革命奠定了基础。而离散数学的发展则是奠定了计算机革命的基础。计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散的对象，而不是在作数值计算。正是因为有了组合算法才使人感到，计算机好象是有思维的。,4.离散数学课程概述,在1997年11月的南开大学离散数学研究中心成立大会上，吴文俊院士指出，每个时代都有它特殊的要求，使得数学出现一个新的面貌，产生一些新的数学分支，离散数学这个新的分支也是在时代的要求下产生的。最近，吴文俊院士又指出，信息技术很可能会给数学本身带来一场根本性的变革，而离散数学则将显示出它的

24、重要作用。杨乐院士也指出离散数学无论在应用上和理论上都具有越来越重要的位置，它今后的发展是很有生命力，很有前途的，中国应该倡导这个方面的研究工作。,4.离散数学课程概述,万哲先院士甚至举例说明了华罗庚，许宝禄，吴文俊等中国老一辈的数学家不仅重视离散数学，同时还对离散数学中的一些基本问题作了重大贡献。迫于中国离散数学发展自身的需要，以及中国信息产业发展的需要，在中国发展离散数学已经迫在眉睫，刻不容缓。,5.离散数学与计算机软件,随着计算机网络的发展，计算机的使用已经影响到了人们的工作，生活，学习，社会活动以及商业活动，而计算机的应用根本上是通过软件来实现的。我国在软件上的落后，要说出根本的原因可

25、能并不是很简单的事，除了技术和科学上的原因外，可能还跟我们的文化，管理水平，教育水平，思想素质等诸多因素有关。除去这些人文因素以外，一个最根本的原因就是我国的信息技术的数学基础十分薄弱，这个问题不解决，我们就难成为软件强国。,5.离散数学与计算机软件,然而问题决不是这么简单，信息技术的发展已经涉及到了很深的数学知识，而数学本身也已经发展到了很深、很广的程度，并不是单凭几个聪明的头脑去想想就行了，而更重要的是需要集体的合作和力量，就象软件的开发需要多方面的人员的合作。美国的软件之所以能领先，其关键就在于在数学基础上他们有很强的实力，有很多杰出的人才。,5.离散数学与计算机软件,中国的软件产业的发

26、展已向数学基础提出了急切的需求：网络算法和分析，信息压缩，网络安全，编码技术，系统软件，并行算法，数学机械化和计算机推理，等等。例如数据挖掘(data mining)今后的计算机要向更加智能化的方向发展，其出路仍然是数学的算法，和数学的机械化。,6.离散数学在国外的状况,纵观全世界软件产业的情况，易见一个奇特的现象：美国处于绝对的垄断地位。造成这种现象的一个根本的原因就是计算机科学在美国的飞速发展。当今计算机科学界的最权威人士很多都是研究离散数学出身的。美国最重要的计算机科学系（MIT，Princeton，Stanford，Harvard，Yale，.）都有第一流的离散数学家。计算机科学通过对

27、软件产业的促进，带来了巨大的效益，这已是不争之事实。,6.离散数学在国外的状况,离散数学在国外早已成为十分重要的学科，甚至可以说是计算机科学的基础。一些大公司，如IBM，AT&T都有全世界最强的组合研究中心。Microsoft 的Bill Gates近来也在提倡和支持计算机科学的基础研究。例如，Bell实验室的有关线性规划算法的实现，以及有关计算机网络的算法，由于有明显的商业价值，显然是没有对外公开的。美国已经有一种趋势，就是与新的算法有关的软件是可以申请专利的。如果照这种趋势发展，世界各国对离散数学和计算机算法的投入和竞争必然日趋激烈。,6.离散数学在国外的状况,美国政府也成立了离散数学及理

28、论计算机科学中心DIMACS（与Princeton大学，Rutgers大学，AT&T 联合创办的，设在Rutgers大学），该中心已是离散数学理论计算机科学的重要研究阵地。美国国家数学科学研究所（Mathematical Sciences Research Institute，由陈省身先生创立）在1997年选择了离散数学作为研究专题，组织了为期一年的研究活动。,6.离散数学在国外的状况,日本的NEC公司还在美国的设立了研究中心，理论计算机科学和离散数学已是他们重要的研究课题，该中心主任R.Tarjan即是离散数学的权威。美国重要的国家实验室（Los Alamos国家实验室，以造出第一颗原子弹著

29、称于世），从曼哈顿计划以来一直重视应用数学的研究，包括离散数学的研究。.美国另外一个重要的国家实验室Sandia国家实验室有一个专门研究离散数学和计算机科学的机构，主要从事组合编码理论和密码学的研究，在美国政府以及国际学术界都具有很高的地位。,6.离散数学在国外的状况,由于生物学中的DNA的结构和生物现象与离散数学有密切的联系，各国对生物信息学的研究都很重视，这也是离散数学可以发挥作用的一个重要领域。由于DNA就是离散数学中的一个序列结构，美国科学院院士，近代离散数学的奠基人Rota教授预言，生物学中的组合问题将成为离散数学的一个前沿领域。,6.离散数学在国外的状况,美国的大学，国家研究机构，

30、工业界，军方和情报部门都有许多离散数学的研究中心，在研究上投入了大量的经费。但他们得到的收益远远超过了他们的投入，更主要的是他们还聚集了离散数学领域全世界最优秀的人才。高层次的软件产品处处用到离散数学，更确切地说就是组合算法。传统的计算机算法可以分为两大类，一类是组合算法，一类是数值算法（包括计算数学和与处理各种信息数据有关的信息学）。,6.离散数学在国外的状况,近年来计算机算法又多了一类：那就是符号计算算法。吴文俊院士开创的机器证明方法就属于符号计算，引起了国际上的高度评价，被称为吴方法。而国际上还有专门的符号计算杂志。符号算法和吴方法跟代数组合学也有十分密切的联系。离散数学，数值计算（包括

31、计算数学，科学计算，非线性科学，和与处理各种信息数据有关的信息学）和统计学可能是应用最广的数学分支，而离散数学的价值甚至不亚于统计学和数值计算。,6.离散数学在国外的状况,最近Thomson Science公司创刊的一份电子刊物离散数学和理论计算机科学即是一个很好的说明。它的内容涉及离散数学和计算机科学的众多方面。由于计算机软件的促进和需求，离散数学已成为一门既广博又深奥的学科，需要很深的数学基础，逐渐成为了数学的主流分支。,6.离散数学在国外的状况,20世纪公认的伟大数学家盖尔芳德预言离散数学和几何学将是21世纪数学研究的前沿阵地。这一观点不仅得到国际数学界的赞同，也得到了中国数学界的赞同和

32、响应。除上述以外，欧洲也在积极发展离散数学，英国、法国、德国、荷兰、丹麦、奥地利、瑞典、意大利、西班牙等国家都建立了各种形式的离散数学研究中心。近几年，南美国家也在积极推动离散数学的研究。澳大利亚，新西兰也组建了很强的离散数学研究机构。,6.离散数学在国外的状况,值得一提的是亚洲的发达国家也十分重视离散数学的研究。日本有离散数学研究中心，并且从美国引进人才，不仅支持日本国内的研究，还出资支持美国的有关课题的研究，这样使日本的离散数学这几年的发展极为迅速。台湾、香港两地也从美国引进人才，大力发展离散数学。新加坡，韩国，马来西亚也在积极推动离散数学的研究和人才培养。台湾的数学研究中心也正在考虑把离

33、散数学作为重点方向来发展。世界各地对离散数学的如此钟爱显然是有原因的，那就是没有离散数学就没有计算机科学，没有计算机软件。,7.关于离散数学的一些应用,例1 在日常生活中我们常常遇到离散数学的问题。如果你仔细留心一张世界地图，你会发现用一种颜色对一个国家着色，那么一共只需要四种颜色就能保证每两个相邻的国家的颜色不同。这样的着色效果能使每一个国家都能清楚地显示出来。但要证明这个结论确是一个著名的世界难题，最终借助计算机才得以解决，最近人们才发现了一个更简单的证明。,7.关于离散数学的一些应用,例2 我国古代的河洛图上记载了三阶幻方，即把从一到九这九个数按三行三列的队行排列，使得每行，每列，以及两

34、条对角线上的三个数之和都是一十五。离散数学中有许多象幻方这样精巧的结构。1977年美国旅行者1 号、2号宇宙飞船就带上了幻方以作为人类智慧的信号。,7.关于离散数学的一些应用,例3 一个邮递员从邮局出发，要走完他所管辖的街道，他应该怎样选择什么样的路径，这就是著名的中国邮递员问题，由中国离散数学家管梅谷教授提出，著名离散数学家J.Edmonds和他的合作者给出了一个解答。,7.关于离散数学的一些应用,例4 一个班级的学生共计选修A、B、C、D、E、F六门课程，其中一部分人同时选修D、C、A，一部分人同时选修B、C、F，一部分人同时选修B、E，还有一部分人同时选修A、B，期终考试要求每天考一门课

35、，六天内考完，为了减轻学生负担，要求每人都不会连续参加考试，试设计一个考试日程表。,7.关于离散数学的一些应用,例5 一个人带着一只狼、一只羊和一捆草要渡河，由于船太小，人做摆渡者一次只能运送一个“乘客”，很显然，如果人不在，狼要吃羊，羊要吃草，问人怎样才能把它们平安地渡过河去？,7.关于离散数学的一些应用,例6 网络计划技术 我们还会遇到更复杂的调度和安排问题。例如，在生产原子弹的曼哈顿计划中，涉及到很多工序，许多人员的安排，很多元件的生产，怎样安排各种人员的工作，以及各种工序间的衔接，从而使整个工期的时间尽可能短？这些都是离散数学典型例子。,7.关于离散数学的一些应用,假日饭店的管理中，也

36、严格规定了有关的工序，如清洁工的第一步是换什么，清洗什么，第二步又做什么，总之，他进出房间的次数应该最少。既然，这样一个简单的工作都需要讲究工序，那么一个复杂的工程就更不用说了。库房和运输的管理也是典型的离散数学问题。怎样安排运输使得库房充分发挥作用，进一步来说，货物放在什么地方最便于存取（如存储时间短的应该放在容易存取的地方）。,7.关于离散数学的一些应用,一个通讯网络怎样布局最节省？美国的贝尔实验室和IBM公司都有世界一流的离散数学家在研究这个问题，这个问题直接关系到巨大的经济利益。我们知道，用形状相同的方型砖块可以把一个地面铺满（不考虑边缘的情况），但是如果用不同形状，而又非方型的砖块来

37、铺一个地面，能否铺满呢？这不仅是一个与实际相关的问题，也涉及到很深的离散数学问题。,7.关于离散数学的一些应用,航空调度和航班的设定也是离散数学的问题。怎样确定各个航班以满足不同旅客转机的需要，同时也使得每个机场的航班起落分布合理。此外，在一些航班有延误等特殊情况下，怎样作最合理的调整，这些都是离散数学的问题。对于城市的交通管理，交通规划，哪些地方可能是阻塞要地，哪些地方应该设单行道，立交桥建在哪里最合适，红绿灯怎样设定最合理，如此等等，全是离散数学的问题。,7.关于离散数学的一些应用,离散数学中有一个著名问题：是否存在稳定婚姻的问题。假如能找到两对夫妇（如张（男）-李（女）和赵（男）-王（女

38、），如果张（男）更喜欢王（女），而王（女）也更喜欢张（男），那么这样就可能有潜在的不稳定性。离散数学的方法可以找到一种婚姻的安排方法，使得没有上述的不稳定情况出现（当然这只是理论上的结论）。这种离散数学的方法却有一个实际的用途：美国的医院在确定录取住院医生时，他们将考虑申请者的志愿的先后次序，同时也给申请排序。按这样的次序考虑出的总的方案将没有医院和申请者两者同时后悔的情况。实际上，高考学生的最后录取方案也可以用这种方法。,7.关于离散数学的一些应用,总之，离散数学无处不在，它的主要应用就是在各种复杂关系中找出最优的方案。所以离散数学完全可以看成是一门量化的关系学，一门量化了的运筹学，一门量化

39、了的管理学。胡锦涛同志在1998年接见“五四”青年奖章时发表的讲话中指出，离散数学不同于传统的纯数学的一个分支，它还是一门应用学科，一门交叉学科。他希望中国的离散数学研究能够为国家的经济建设服务。,8.如何学习离散数学,首先要明确的是，由于离散数学是一门数学课，且是由几个数学分支综合在一起的，内容繁多，非常抽象，因此即使是数学系的学生学起来都会倍感困难，对计算科学专业的学生来说就更是如此。大家普遍反映这是大学四年最难学的一门课之一。但鉴于离散数学在计算科学中的重要性，这是一门必须牢牢掌握的课程。既然如此，在学习离散数学时，大家最应该牢记的是唐诗“熟读唐诗三百首，不会做诗也会吟。”学习过程是一个

40、扎扎实实积累的过程，不能打马虎眼。离散数学是理论性较强的学科，学习离散数学的关键是对离散数学（集合论、数理逻辑和图论）有关基本概念的准确掌握，对基本原理及基本运算的运用，并要多做练习。,8.如何学习离散数学,离散数学的特点是：(1)知识点集中，概念和定理多：离散数学是建立在大量概念之上的逻辑推理学科，概念的理解是我们学习这门学科的核心。不管哪本离散数学教材，都会在每一章节列出若干定义和定理，接着就是这些定义定理的直接应用。掌握、理解和运用这些概念和定理是学好这门课的关键。要特别注意概念之间的联系，而描述这些联系的则是定理和性质。,8.如何学习离散数学,(2)方法性强：离散数学的特点是抽象思维能

41、力的要求较高。通过对它的学习，能大大提高我们本身的逻辑推理能力、抽象思维能力和形式化思维能力，从而今后在学习任何一门计算机科学的专业主干课程时，都不会遇上任何思维理解上的困难。离散数学的证明题多，不同的题型会需要不同的证明方法（如直接证明法、反证法、归纳法、构造性证明法），同一个题也可能有几种方法。但是离散数学证明题的方法性是很强的，如果知道一道题用什么方法讲明，则很容易可以证出来，否则就会事倍功半。因此在平时的学习中，要勤于思考，对于同一个问题，尽可能多探讨几种证明方法，从而学会熟练运用这些证明方法。同时要善于总结。,8.如何学习离散数学,在学习离散数学的过程，对概念的理解是学习的重中之重。

42、一般来说，由于这些概念（定义）非常抽象（学习线性代数时会有这样的经历），初学者往往不能在脑海中建立起它们与现实世界中客观事物的联系。这往往是离散数学学习过程中初学者要面临的第一个困难，他们觉得不容易进入学习的状态。因此一开始必须准确、全面、完整地记住并理解所有的定义和定理。具体做法是在进行完一章的学习后，用专门的时间对该章包括的定义与定理实施强记。只有这样才可能本课程的抽象能够适应，并为后续学习打下良好的基础。,8.如何学习离散数学,学数学就要做数学，离散数学的学习也不例外。学习数学不仅限于学习数学知识，更重要的还在于学习数学思维方法。要做到这一点，学习者将要面临的第二个困难是需要花费大量的时

43、间做课后习题。但是切记离散数学的题目数量自然是无穷无尽的，但题目的种类却很有限。尤其是在命题证明的过程中，最重要的是要掌握证明的思路和方法。解离散数学的题，方法是非常重要的，如果拿到一道题，立即能够看出它所属的类型及关联的知识点，就不难选用正确的方法将其解决，反之则事倍功半。由此可见，在平常学习中，要善于总结和归纳，仔细体会题目类型和此类题目的解题套路。如此多作练习，则即使遇到比较陌生的题也可以较快地领悟其本质，从而轻松解出。,8.如何学习离散数学,因此，只要肯下功夫，人人都能有扎实的基础，拥有足够的数学知识，特别是能大大提高本身的逻辑推理能力、抽象思维能力和形式化思维能力，从而今后在学习任何

44、一门计算机科学的专业主干课程时，都不会遇上任何思维理解上的困难。,离散数学参考资料,离散数学，左孝凌著，上海科技文献出版社；离散数学，耿素云、屈婉玲著，高等教育出版社；离散数学及其应用，傅彦、顾小丰著，电子工业出版 社；Discrete Mathematical Structures（英文Fourth Edition），B Kolman,Robert C.Busby,Sharon Ross著，高等教育出版社；Discrete Mathematics and Its Applications(英文Fifth Edition),Kenneth H.Rosen著，机械工业出版社；,课程内容,（一）数理逻辑（二）集合论（三）代数结构（四）图论,成绩评定,平时成绩（到课情况、书面作业、平时测验）占20%，期末考试占70%。注：课堂提问表现好的适当加分经常缺课、无故迟到、早退、不认真听讲的酌情扣分。,2023/11/16,Thank You!,