离散数学课件：第一章 绪论

离散数学2/31绪论WhatisDiscreteMathematics

Whystudy

DiscreteMathematicsUsesofDiscreteMathinComputerScience&SoftwareEngineering

教材目录

Topicswillbecovered

课程计划与要求课程特点与学习方法

3/31Whatis

DiscreteMathematics?又称计算机数学是现代数学的重要分支计算机专业课程中的核心基础课程之一Mathematicsthatdealswithdiscreteobjectsandstructures绪论4/31WhatisDiscreteMathematics?离散数学是专门研究离散量的结构与相互间关系的数学理论与数学方法属于现代数学的一个分支，是计算机科学基础理论的核心课程，是计算机专业(CS、CE、SE)最重要的专业基础课之一旨在训练分析问题的能力介绍研究问题的方法论培养抽象思维和严密逻辑推理的能力5/31离散对象（DiscreteObjects）有限或可数个元素Separatedfromeachother(Oppositeofcontinuous)e.g.,integers,people,house,Continuousobjects:e.g.,realnumber离散结构（DiscreteStructures）Theabstractmathematicalstructuresusedtorepresentdiscreteobjectsandrelationshipsbetweentheobjectse.g.集合(sets),关系(relations),图(graphs)WhatisDiscreteMathematics?6/31离散性是计算机科学的显著特点也是研究自动控制、管理科学、电子工程等的重要工具Informationisstoredandmanipulatedbycomputersinadiscretefashion.0101101…Asastudentincomputersciencemajor,youneedtoknowthebasiclanguageandconceptualfoundationforallofthecomputerscience,i.e.,DiscreteMath!Discretemathconceptsarealsowidelyusedthroughoutmath,science,engineering,economics,biology,etc.,…Whystudy

DiscreteMathematics?7/31Gettrainingforrationalthought!离散数学是一门高度概括性、抽象性的科学研究一类问题的解决方法为一类问题建立统一的求解过程按照规定的程序步骤机械地进行下去为机械化提供可能Whystudy

DiscreteMathematics?8/31UsesofDiscreteMathinComputerScienceNetworkingDatabaseImageProcessingProgrammingLanguagesCompilers&InterpretersArtificialIntelligenceDigitalCircuit&CircuitDesignComputerArchitectureOperatingSystemsSecurity&Cryptography(密码学)AdvancedAlgorithms&DataStructuresGraphics&Animationlogistics(物流)SoftwareEngineering9/31Somequestions在举重比赛中，有两名副裁判，一名主裁判。当两名以上裁判（必须包括主裁判在内）认为运动员举杠铃合格，按电钮，才裁决合格。试设计该表决器的电路。设计一台自动售货机，它只能接受五毛和一元的硬币，当投入硬币总值超过一块五时，给出一根冰棍，并找回余额。10/31Somequestions印刷电路板需要多少层？哪些线路断开会导致整个电路不通？网络设计的可靠性怎么样？如果某些线路受损是否还能通讯？11/31Somequestions有N个士兵（1<=N<=100),编号依次为1,2,...,N.队列训练时，指挥官要把士兵从高到矮排成一行，但指挥官只知道“1比2高，7比5高”这样的比较结果，能否把士兵排好队呢？在设计一个组装工件的流水线时，我们知道零件2要在零件1之前装，零件5要在零件9之前装…，如何设计这个流水线呢？12/31软件工程的离散数学基础抽象与逐步求精

为了对付大型复杂的软件系统，须采用传统的“分解”方法。软件工程的分解是从横向和纵向(即空间和时间)两个方面进行的。

自顶向下逐层分解的过程，也是一个逐层抽象的过程。13/31软件工程的离散数学基础抽象

人类在认识复杂现象的过程中使用的最强有力的思维工具是抽象。人们在实践中认识到，在现实世界中一定事物、状态或过程之间总存在着某些相似的方面(共性)。把这些相似的方面集中和概括起来，暂时忽略它们之间的差异，这就是抽象。或者说，抽象就是抽出事物的本质特性而暂时不考虑它们的细节。14/31软件工程的离散数学基础抽象

由于人类思维能力的限制，如果每次面临的因素太多，是不可能做出精确思维的。处理复杂系统的惟一有效的方法是用层次的方式构造和分析它。一个复杂的动态系统首先可以用一些高级的抽象概念构造和理解，这些高级概念又可以用一些较低级的概念构造和理解，如此进行下去，直至最低层的具体元素。15/31软件工程的离散数学基础抽象

软件工程过程的每一步都是对软件解法的抽象层次的一次精化。在可行性研究阶段，软件作为系统的一个完整部件；在需求分析期间，软件解法是使用在问题环境内熟悉的方式描述的；当由总体设计向详细设计过渡时，抽象的程度也就随之减少了；最后，当源程序写出来以后，也就达到了抽象的最低层。16/31软件工程的离散数学基础抽象

随着软件开发工程的进展，在软件结构每一层中的模块，表示了对软件抽象层次的一次精化。软件结构顶层的模块，控制了系统的主要功能并影响全局；在软件结构底层的模块，完成对数据的一个具体处理，用自顶向下由抽象到具体的方式分配控制，简化了软件的设计和实现，提高了软件的可理解性和可测试性，使软件更容易维护。17/31软件工程的离散数学基础逐步求精

逐步求精是人类解决复杂问题时采用的基本方法，也是许多软件工程技术(例如，规格说明技术，设计和实现技术)的基础。可以把逐步求精定义为：“为了集中精力解决主要问题而尽量推迟对问题细节的考虑。”18/31软件工程的离散数学基础逐步求精

逐步求精能帮助软件工程师把精力集中在与当前开发阶段最相关的那些方面上，而忽略那些对整体解决方案来说虽然是必要的，然而目前还不需要考虑的细节，这些细节将留到以后再考虑。

Miller法则：一个人在任何时候都只能把注意力集中在(7±2)个知识块上。19/31软件工程的离散数学基础逐步求精

人类智力有局限性，我们只能在这个前提下尽我们的最大努力工作。可以把逐步求精看作是一项把一个时期内必须解决的种种问题按优先级排序的技术。逐步求精方法确保每个问题都将被解决，而且每个问题将在适当的时候被解决，但是，在任何时候一个人都不需要同时处理7个以上知识块。20/31软件工程的离散数学基础逐步求精

逐步求精最初是由Wirth提出的一种自顶向下的设计策略。Wirth本人对逐步求精曾做过如下概括说明：21/31软件工程的离散数学基础逐步求精“我们对付复杂问题的最重要的办法是抽象，因此，对一个复杂的问题不应该立刻用计算机指令、数字和逻辑符号来表示，而应该用较自然的抽象语句来表示，从而得出抽象程序。抽象程序对抽象的数据进行某些特定的运算并用某些合适的记号(可能是自然语言)来表示。对抽象程序做进一步的分解，并进入下一个抽象层次，这样的精细化过程一直进行下去，直到程序能被计算机接受为止。这时的程序可能是用某种高级语言或机器指令书写的。”22/31软件工程的离散数学基础逐步求精

求精实际上是细化过程。我们从在高抽象级别定义的功能陈述(或信息描述)开始，也就是说，该陈述仅仅概念性地描述了功能或信息，但是并没有提供功能的内部工作情况或信息的内部结构。求精要求设计者细化原始陈述，随着每个后续求精(即细化)步骤的完成而提供越来越多的细节。23/31软件工程的离散数学基础逐步求精

抽象与求精是一对互补的概念。抽象使得设计者能够说明过程与数据，同时却忽略低层细节。事实上，可以把抽象看作是一种通过忽略多余的细节同时强调有关的细节而实现逐步求精的方法。求精则帮助设计者在设计过程中逐步揭示出低层细节。这两个概念都有助于设计者在设计演化过程中创造出完整的设计模型。24/31离散数学的主要内容数理逻辑：研究推理的共性关系理论：研究关系的共性代数结构：研究运算的共性图论：数论：25/31教材离散数学费洪晓刘丽珏主编天津大学出版社26/31教材目录第一篇数论第一章数论基础

第二篇数理逻辑第二章命题逻辑第三章谓词逻辑第三篇集合论第四章集合第五章二元关系第六章函数第四篇图论第七章无向图第八章有向图第五篇代数系统第九章代数结构基础第十章格与布尔代数27/31参考书离散数学（第三版），方世昌编著，西安电子科技大学出版社屈婉玲/耿素云/张立昂，离散数学，高等教育出版社左孝凌等，离散数学，上海科学技术文献出版社28/31课程计划与要求授课学时48考试成绩计算平时成绩30分作业考勤课堂提问期末考试70分作业要求基本每次课后均布置作业作业在讲完一章内容后一起交认真独立完成，字迹潦草将不予批改按时上交29/31课程特点与学习方法课程特点数学理论与数学方法双重特性研究的内容具有高度概括性研究一类问题的解决方法研究具体问题的抽象，用以指导对具体问题的分析30/