离散数学引言

海不择细流，故能成其大,山不拒细壤，方能就其高,离散数学,总学时:56理论学时:50,绪论内容目录,离散数学概述离散数学研究内容教学内容教材及参考书目,概述离散数学的定义,离散数学DiscreteMathematics研究离散结构的数学分科。辞海79年版，P355是研究离散量的结构及其相互关系的学科。,概述和计算机科学联系,和计算机科学联系紧密是计算机科学的支撑学科之一，也是信息科学的数学基础。在计算机理论研究及软硬件开发的各个领域都有广泛的应用。在计算机科学发展的过程中，各种理论问题的研究交错地使用着近代数学中的不同论题，这些论题构成了离散数学。,离散数学研究内容,离散数学由多门数学分支组成主要研究分支包括：数理逻辑、集合论、代数(近世代数)、图论、算法、组合数学、形式语言与自动机等等。每个分支基本上可以看成是一门独立的学科。,离散数学研究内容,各部分内容的关系并非相互独立，有着密切联系它们分别从不同角度出发，研究各种离散量之间数与形的关系。都是计算机科学中一些课程的必备基础数理逻辑是自动机理论、编译原理、人工智能的基础课程之一集合论是数据库的基础课程之一代数是密码学的基础课程之一图论是逻辑设计的基础课程之一(通信网理论的基础),学习离散数学的重要性,用一组基本的指令来编制一个计算机程序，非常类似于从一组公理来构造一个数学证明。D.E.Knuth(克纽斯)1974年Turing奖获得者代表作:TheArtofComputerProgramming,学习离散数学的重要性,我现在年纪大了，搞了这么多年软件，错误不知犯了多少，现在觉悟了。我想，假如我早在数理逻辑上好好下点功夫的话，我就不会犯这么多错误。不少东西逻辑学家早就说过了，可是我不知道。要是我能年轻20岁的话，我就会回去学逻辑。E.W.Dijkstra(戴克斯特拉)1972年Turing奖获得者,教学内容,教学内容四个相对独立的部分：数理逻辑集合论代数(略讲)图论,数理逻辑_是计算机科学的基础，应熟练掌握将现实生活中的条件化成逻辑公式，并能做适当的推理，这对程序设计等课程是极有用处的。,集合论_数学的基础，对于学习程序设计、数据结构、编译原理等几乎所有计算机专业课程和数学课程都很有用处。熟练掌握有关集合、函数、关系等基本概念。,代数结构_对于抽象数据类型、形式语义的研究很有用处。培养数学思维，将以前学过的知识系统化、形式化和抽象化。熟练掌握有关代数系统的基本概念，以及群、环、域等代数结构的基本知识。,图论_对于解决许多实际问题很有用处，对于学习数据结构、编译原理课程也很有帮助。要求掌握有关图、树的基本概念，以及如何将图论用于实际问题的解决，并培养其使用数学工具建立模型的思维方式。,数学共发生几次危机?,集合论部分,第一次危机_公度比危机,第二次危机_无穷小危机,第三次危机_集合论的危机,齐人固善盗乎?_,论辩中的复杂问语_(二)中曾叙述了一个复杂问语:梅内德谟:你已停止打你父亲,是吗?,数理逻辑,著名苏格拉底三段论：所有的人都是要死的，苏格拉底是人，所以，苏格拉底是要死的。,古希腊著名的半费之讼,_二难推理(P46),哥尼斯堡城被Pregel河分成了四部分,它们之间有七座桥,如图所示。当时人们提出了一个问题:能否从城市的某处出发,过每座桥一次且仅一次最后回到原处。,图论部分,1736年瑞士著名数学家欧拉(Euler)解决了(立陶宛)哥尼斯堡城七桥问题,教学内容,教学侧重点掌握必备的数学工具和培养抽象思考能力。侧重于基本概念和基本知识的介绍。,教学内容,离散数学后续课程自动机理论、可计算性理论、人工智能、形式语言及语法分析、数据结构、数据库、信息管理与检索、高级程序设计语言、开关理论、逻辑设计和程序理论等等。,此课的特点及学习方法：,特点：内容较杂，概念多，定理多，比较抽象，给学习带来一定难度。学习方法：1.准确掌握每个概念(包括内涵及外延)。2.要有刻苦钻研精神,不断总结经验。3.在理解内容的基础上，要较多地做些习题，从而再进一步加深理解所学内容。4.注意培养分析问题和解决问题的能力,6.认识离散数学的重要性,培养浓厚的学习兴趣.,7.学数学最好的方式是做数学.,聪明在于学习,天才在于积累.,学而优则用,学而优则创.,由薄到厚,由厚到薄.,马克思,恩格斯,要辨证而又唯物地了解自然,就必须熟悉数学.,一门科学,只有当它成功地运用数学时,才能达到真正完善的地步.,华罗庚,教材及参考书目,教材耿素云，离散数学，高等教育出版社参考书目王遇科，离散数学，北京理工大学出版社离散数学，王孝喜等译，电子工业出版社DiscreteMathematicalStructures,BernardKolman,RobertC.Busby,SharonRoss,Prentic