《ch00引言》由会员分享，可在线阅读，更多相关《ch00引言（71页珍藏版）》请在金锄头文库上搜索。
1、离散数学,引 言,离散数学是现代数学的一个重要分支，是计算机类专业的重要课程。它以研究离散量的结构及其相互间的关系为主要目标，其研究对象一般是有限个或可数个元素，因此离散数学可以充分描述计算机学科离散性的特点。由于离散数学在计算机科学中的重要作用，国内外几乎所有大学的计算机类专业的教学计划中都将其列为核心课程进行重点建设，它是其他骨干课程，如数据结构、操作系统、人工智能、计算机网络、软件工程、编译原理等的先修课程，国内许多大学将其作为计算机专业类研究生入学考试的内容。,引 言,为什么离散数学在计算学科的知识掌握中有着举足轻重的意义呢?,？,1.计算学科的概念,计算学科（Computing Sc
2、ience）即我们所熟悉的计算机科学与技术(Computer Science and Technology)。计算学科是对描述和变换信息的算法过程，包括其理论、分析、设计、效率分析、实现和应用等进行的系统研究的一门学科。它涉及计算过程的分析如可计算性、算法，研究有关计算机的各种现象、揭示其规律与本质如计算机的设计和使用、可计算性硬件和软件的实际实现问题。,1.计算学科的概念,计算学科的基本问题是能行与效率的问题,即它的核心问题是“能行”问题(Practicability)： 1)什么是（实际）可计算的？什么是（实际）不可计算的？ 2)如何保证计算的自动性、有效性及正确性？,1.计算学科的概念,
3、计算学科作为现代技术的标志，已成为世界各国经济增长的主要动力。但如何认识这门学科，它究竟属于理科还是工科，属于科学还是属于工程的范畴，这是困扰国内外计算机科学界很长时间且争论不休的问题。 计算学科诞生于20世纪40年代初，它的理论基础可以说在这之前就已经建立起来了。正是电子数字计算机的问世才促进这一门学科的发展。,1.计算学科的概念,世人一般公认1946年2月14日研制成功的ENIAC（电子数字积分器和计算器，Electronic Numerical Integrator and Calculator）是世界上第一台通用电子数字计算机（事实上，早在1943年，英国数学家图灵领导制造出了一台名叫
4、“巨人”（Colossus）的电子计算机，它专门用于译码。由于英国政府的保密制度，故人们对它的成就了解甚少）。美国的普渡大学于1962年开设了最早的计算机科学学位课程。,1.计算学科的概念,在计算机产生之初及随后的一、二十年时间里，计算机主要用于数值计算。大多数科学家认为使用计算机仅为编程问题，不需作任何深刻的科学思考，计算机从本质上说是一种职业而一门学科。 到了20世纪70、80年代，计算技术得到了迅猛的发展和广泛的应用，并开始渗透到大多数科学领域。这时人们普遍争论的问题是：计算机科学是否作为一门学科？它是科学还是工程？它属于理科还是工科？或者只是一门技术、一个计算商品的研制者或销售者？,1
5、.计算学科的概念,1985年春，ACM（美国计算机协会）和IEEECS（国际电子电气工程师学会计算机分会）组成联合攻关小组，开始了对“计算作为一门学科”的存在性证明。1989年1月，该小组提交了计算作为一门学科（Computing as a discipline）的报告。第一次给出了计算学科一个透彻的定义，回答了计算学科中长期以来一直争论的一些问题，完成了计算学科的“存在性”证明，还提出了未来计算科学教育必须解决的二个重大问题整个学科核心课程详细设计及整个学科综述性导引课程的构建。1991年，在这报告的基础上提交了关于计算学科教学计划CC1991（Computing Curricula 199
6、1）。2001年12月，提交了最终的CC2001报告。,1.计算学科的概念,计算作为一门学科报告及CC1991、CC2001一起解决了三个重要问题： 第一个重大问题（计算作为一门学科的存在性证明）的解决。对学科本身的发展至关重要。如果在众多分支领域都取得了重大成果并已得到广泛应用的“计算”，连作为一门学科的地位都不清楚，那么它的发展势必要受到很大的限制。,1.计算学科的概念,第二个重大问题（整个学科核心课程详细设计）的解决，将为高校制定计算机教学计划奠定基础。确定一个公认的本科生应该掌握的核心内容，将避免教学计划设计中的随意性，从而为我们科学地制定教学计划奠定基础。,1.计算学科的概念,第三个
7、重大问题（整个学科综述性导引课程的构建）的解决，将使人们对整个学科的认知科学化、系统化和逻辑化。如果人们对计算学科的认知能建立在公理化的基础之上，则该学科可被认为是严谨的科学、成熟的学科，从而有助于它的发展，并将由此而得到人们的尊重。,1.计算学科的概念,攻关小组的结论是：计算学科所研究的根本问题是能行问题（什么能被（有效地）自动进行）。计算学科的基本原理已纳入理论、抽象和设计这3个具有科学技术方法意义的过程中。学科的各分支领域正是通过这3个过程来实现它们各自的目标。而这3个过程要解决的都是计算过程中的“能行性”和“有效性”问题。这两个问题渗透在包括硬件和软件在内的理论、方法、技术的研究和应用
8、的研究和开发之中，且学科的方法论的主要理论基础以离散数学为代表的构造性数学与能行性问题形成了天然的一致。,2.计算科学与数学的关系,数学是现代科学的重要基础，当然也是计算科学的主要基础。数学方法在现代科技的发展中已经成为一种必不可少的认识手段。它的主要作用是为科技研究提供： （1）简洁精确的形式化语言； （2）数量分析和计算的方法； （3）逻辑推理的工具。 人们公认高技术本质上就是数学技术，而计算学科（即我们所熟悉的计算机科学与技术）也离不开数学。,2.计算科学与数学的关系,从数学的角度出发，数学本身可分为连续数学和离散数学。离散和连续是现实世界中物质运动对立统一的两个方面，离散数学和连续数学
9、是描述、刻画现实物质世界的重要工具。最早的数学本质上是一种离散型的数学，但随着微积分的出现，对整个数学的研究发生了深刻的影响。人们以一种连续的观点研究数学，描述自然科学研究中的各种具体问题，从而形成了现在占统治地位的连续数学。,2.计算科学与数学的关系,随着现代科学技术的发展，特别是计算机科学技术的兴起，离散数学又重新找到了它自己原有的位置。“能行性”这个计算学科的根本问题决定了计算机本身的结构和它处理的对象都是离散型的，甚至许多连续型问题也必须在转化为离散型问题以后才能被计算机处理。所以计算机科学与技术本质上是一门离散数学技术。,2.计算科学与数学的关系,在计算科学中，无论是理论研究还是技术
10、研究的成果，最终目标要体现在计算机软件产品的程序指令系统应能机械地、严格地按照程序指令执行，决不能无故出错。计算机系统的这一客观属性和特点决定了计算机的设计、制造、以及各种软件系统开发的每一步都应该是严密的、精确无误的。就目前基于图灵机这一理论计算模型和存储程序式思想设计制造的计算机而言，它们只能处理离散问题或可用构造性方式描述的问题，而且这些问题必须对给定的论域存在有穷表示。,2.计算科学与数学的关系,至于非离散的连续性问题，如实数域上的函数计算，方程求根等还只能用近似的逼近方法。于是，由于计算模型的非连续性特点，使得以严密、精确著称的数学尤其是以离散数学为代表的应用数学成为描述计算学科理论
11、、方法和技术的主要工具。数学与电子科学（特别是微电子技术）构成了计算学科的基础。,2.计算科学与数学的关系,与数学相比，电子技术的重要性对计算科学而言不如数学，因为数学提供了计算科学最重要的学科思想和方法论基础，而电子技术只提供了电子计算机的实现技术，它仅仅只是对计算科学许多思想和方法的一种当前最现实、最有效的实现技术手段而已。当科学技术的手段提到发展时，完全有可能有某一项新技术归结为有效地取代电子技术（如光技术、生物技术等等），但计算科学的数学基础可能变化不大。,2.计算科学与数学的关系,从事计算科学的人都知道，计算科学中不仅许多理论是用数学描述的，而且许多技术也是用数学描述的。大多数计算科
12、学理论不仅仅是对研究对象变化规律的陈述，而且由于能行性这一本质的核心问题和特点的作用，理论描述中常通过方法折射出技术的思想和步骤，而从理论通过方法跨越到技术则完全取决于理论的深刻认识和理解。一个人如果看懂了以形式化方法描述的技术文献，自然明白技术上应该怎样去做。,2.计算科学与数学的关系,至于计算机技术专业的学生为何要学习数学这个问题的答案，了解了上面所讲的计算学科与数学的关系后就不言而喻了：计算机科学植根于数学，从而数学是必须掌握的基础知识；另外如果我们已经拥有牢固的数学基础，则能大大提高我们本身的逻辑推理能力、抽象思维能力和形式化思维能力，从而今后在学习任何一门计算机科学的专业主干课程时，
13、都不会遇上任何思维理解上的困难。,3.计算学科与离散数学的关系,(1)从计算机科学学科发展的需要看离散数学的地位。 20世纪的计算机出现，带动了世界性的信息革命的伟大进程。计算机科学在信息革命中的学科地位有如牛顿力学在工业革命中的学科地位一样，由计算机出现带动的信息革命当然计算机科学将起着主导的作用。,3.计算学科与离散数学的关系,当前计算机科学在发展过程中面对着如下两个问题： 一是信息革命要求计算机科学要将计算机的应用扩大到包含所有的问题领域和深入到每个问题领域的深处而越来越细致越来越复杂；二是一旦让计算机去解决问题，那么计算机应自动地在有限和有效的时间内得出解。前者指出计算机科学的任务就是
14、要用计算机的硬件、外设和软件构成一个系统，使得许多不同领域的问题都能在这样的计算机系统中得到解决。为了完成这个任务，就必须用一种符号语言构成一个包括了不同领域的通用模型。,3.计算学科与离散数学的关系,离散数学就是指出构成一个包括了不同领域的通用模型的思维方法，并且告诉我们怎样用不同的语言（符号语言、图形语言、逻辑语言等）从最简单的对象（集合）出发表示通用模型。后者指出计算机科学必须了解让计算机去解决问题在通用模型中的结构，由于要求在有限和有效时间内计算机自动完成，那么问题求解的方法必然是构造性的，所了解的结构必然是一种离散结构。离散数学中的求解问题的方法就是基于离散结构的构造性思维方法。,3
15、.计算学科与离散数学的关系,从离散数学的基本内容和计算学科的发展情况来看，许多计算学科的问题，都可以在离散数学的范围中表达，都可以试验抽象为离散数学的问题，不能否认离散数学在较通用的层面上描述了计算学科所表现出来的信息革命的许多模型，为现代计算学科的发展和应用提供了理论基础。从学习的角度来看，离散数学的思维方法能够为计算机科学所用，“离散数学能够使我们在更高的高度去了解和学习计算机科学” 。,3.计算学科与离散数学的关系,因此可以说高等数学将大家从中学的传统的欧基里德的思维方式带进高等教育的基于工业革命的学科表达语言的富于创造性的思维方式，而离散数学将大家带进信息革命的学科表达语言中去发展和创
16、造具有时代特点的先进的思维方式。,3.计算学科与离散数学的关系,(2)从计算机科学学生能力角度培养的看离散数学的作用。 计算机出现的五十多年间，人们追求着和出现了许多计算机信息革命带来的信息产品，但是信息产品受工业产品的观念上的影响，使得计算机科学的学科发展带来了偏差，使得整个学科的发展都是“软件跟着硬件走”。我们不能将自己的学生培养成计算机系统的奴隶，而应该培养成计算机系统的主人，我们的学生不能给计算机系统所塑造，将他们变成计算机，而是教育学生怎样地塑造计算机系统。,3.计算学科与离散数学的关系,在计算机科学知识掌握的过程中应是“硬件跟着软件走，软件跟着模型走，模型跟着学科实际应用走；学科实际应用跟着自然走”。而最主要的培养环节应该是软件跟着模型走，模型跟着学科实际应用走。关于学生的培养目标就是要培养自己的学生能够根据实际应用问题提出计算机应用的模型，并用硬件和软件资源去构造计算机系统去完成模型中所提出来的工作。,3.计算学科与离散数学的关系,因此，我们的学生需要如下三个方面的能力：构造模型的能力；算法设计的能力；程序设计的能力。 所谓构造模型的能力就是在通用的语言
