离散数学课程简介(祝清顺版).ppt

主讲：祝清顺 教授,Discrete Mathematics,离散数学,科学出版社,离散数学课程简介,一、现代数学的两大分类,现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等。另一类是研究离散对象的离散数学。离散数学：Discrete Mathematics.研究离散对象及其相互间关系的一门数学学科。研究离散结构的数学分科。辞海离散数学研究的对象是离散量，一切以离散现象作为研究对象或对象之一的数学均称为离散数学。,连续数学VS离散数学印象,剪不断理还乱是离愁恰似一江春水向东流,枯藤老树昏鸦小桥流水人家古道西风瘦马夕阳西下断肠人在天涯,二、离散数学的发展过程,18世纪以前,数学基本上是研究离散对象的数量和空间关系的科学。之后,因天文学,物理学的发展,如行星轨道,牛顿三大力学定律等研究,极大地推动了连续数学(以微积分,数学物理方程,实、复变函数论为代表)的发展。离散对象的研究则处于停滞状态。20世纪30年代,图灵提出计算机的理论模型图灵机。,二、离散数学的发展过程,图灵机这种模型早于实际制造计算机十多年,现实的计算机的计算能力,本质上和图灵机的计算能力一样。由于在计算机内,机器字长总是有限的,它代表离散的数或其它离散对象，因此随着计算机科学和技术的迅猛发展,离散数学就显得重要。,三、离散数学与计算机的关系,计算机是一个离散的结构，计算机的研究对象大都是离散形式，离散数学当之无愧地可以充分描述计算机科学的离散性的特点，它是研究计算机科学的基本数学工具和最合适的理论手段。因此，离散数学是是计算机科学的专业基础核心课程，也是信息科学的数学基础。它在计算机理论研究及软硬件开发的各个领域都有广泛的应用。在计算机科学发展的过程中，各种理论问题的研究交错地使用着近代数学中的不同论题，这些论题都构成了离散数学的内容。,四、离散数学的内容,离散数学由多门数学分支组成 主要研究分支包括：数理逻辑、集合论、代数(近世代数)、图论、算法、组合数学、形式语言与自动机等等。每个分支基本上可以看成是一门独立的学科。数理逻辑：是计算机科学的基础，应熟练掌握将现实生活中的条件化成逻辑公式，并能做适当的推理，这对程序设计等课程是极有用处的。,四、离散数学的内容,离散结构：用来表示离散对象以及它们之间关系的抽象数学结构，包括：集合、排列、关系、树、图。组合分析：解决问题的一个重要方面就是计数或枚举对象，一种重要的数据结构。算法化思维：许多问题都可以通过构造一个可以被程序实现的算法来解决。它的三个步骤是：构造（选择合适的离散模型和操作步骤）、验证（算法的正确性）、评估（时间和空间的复杂性）。,四、离散数学的内容,离散数学各部分内容的关系并非相互独立，有着密切联系它们分别从不同角度出发，研究各种离散量之间数与形的关系。离散数学是计算机科学中一些课程的必备基础 数理逻辑是自动机理论、编译原理、人工智能的基础课程之一；集合论是数据库的基础课程之一；代数是密码学的基础课程之一；图论是逻辑设计的基础课程之一(通信网理论的基础)。,五、教学内容,教学内容 分为四个相对独立的部分：集合论、代数、图论与数理逻辑。,集合论,数理逻辑,图 论,代数结构,课程结构,离散数学,数理逻辑,命题逻辑,谓词逻辑,集 合 论,集合,函 数,二元关系,图 论,代数系统,代数结构,典型系统,图论基础,树,布尔代数,六、为什么要学习离散数学,计算机求解的基本模式是：实际问题 数学建模 算法设计 编程实现 离散数学可以为数学建模打下知识基础、为算法设计提供具体指导。离散数学结构实际上就是通用的抽象的模式的集合。告诉你各种模式的本质特征和它们之间的关系，以及选用它们的策略；告诉你哪些问题是可解的，哪些是当前在图灵机模型上无（最优）解的，哪些是可以得到近似较优的解。,掌握离散数学知识，为后续课程（数据结构、操作系统、编译理论、算法分析、系统结构、容错判断、机器定理证明、数据库原理、人工智能等）打下坚实的基础。简而言之，离散数学的作用就在于训练运用离散结构作为问题的抽象模型、构造算法、解决问题的能力.通过离散数学的学习，培养抽象思维，缜密概括和严密逻辑推理能力，掌握证明问题的方法。,六、为什么要学习离散数学,七、学习方法,课程特点：定义+定理+例题内容较杂，概念多，定理多，比较抽象，给学习带来一定难度。学习方法：1.准确掌握每个概念(包括内涵及外延).2.要有刻苦钻研精神,不断总结经验.3.在理解内容的基础上,要较多地做些习题,从而再进一步加深理解所学内容.4.注意培养分析问题和解决问题的能力.,6.认识离散数学的重要性,培养浓厚的学习兴趣.,7.学数学最好的方式是做数学.,聪明在于学习,天才在于积累.,学而优则用,学而优则创.,由薄到厚,由厚到薄.,马克思,恩格斯,要辨证而又唯物地了解自然,就必须熟悉数学.,一门科学,只有当它成功地运用数学时,才能达到真正完善的地步.,华罗庚,七、学习方法,八、教材与参考书,授课教材祝清顺、贾利新、刘楠编著离散数学科学出版社。参考教材左孝凌等编著离散数学上海科技文献出版社耿素云，屈婉玲编著离散数学(修订版)高等教育出版社,2004耿素云，屈婉玲编著离散数学学习指导与习题解析高等教育出版社,2005,如果你想在本教材的基础上拓展一点，可以看类似地更详细一些的书，当然也有雷同。耿素云：集合论与图论：离散数学第二分册，北京大学出版社，1998.屈婉玲：代数结构与组合数学：离散数学第三分册，北京大学出版社，1998.如果你想了解其它风格的教科书，可以看美国主流的离散数学教材。Rosen：离散数学及其应用(6版),机械工业出版社,英文影印版,2008.Kolman等：离散数学结构(5版),高等教育出版社,英文影印版,2005.Ross等：离散数学,清华大学出版社,英文影印版,2003.如果你只想多看一些题目,可以看专门的习题集。利普舒尔茨等：离散数学(全美经典数学指导系列),科学出版社,中文译本,2002.如果你觉得这些书的挑战性差一些，你可以看各分支学科的数学教科书。集合论、图论、抽象代数、数理逻辑与数学基础、,八、教材与参考书,结束语,课程开始了，仿佛一台戏的幕布已经拉开，到了向观众演出的时候了。希望本课程不只是揭开离散数学神秘的面纱，更重要的是激发大家学习离散数学的积极性,因为离散数学是一种科学、一种语言、一种艺术、一种思维方法，它应用于生活的方方面面，它无比丰富，引人入胜。离散数学很美，这就要看谁能够在以后的学习中发现它的美！应用它的美！挖掘它的美!没有人知道未来的世界会变得什么模样，但有一点我们能够做到，那就是：轰轰烈烈把握人生机遇，与时俱进无愧青春年华！,男儿何不带吴钩 收取关山五十州 请君暂上凌烟阁 若个书生万户侯 唐 李贺南园,人因梦想而伟大！因学习而改变！因行动而成功！祝您的人生从此与众不同！,结束语,END,