0离散数学述.pptVIP

离散结构（离散数学）（Discrete Mathematics） 授课教师：林旭东 联系电话电子邮箱：hunanlxd@ 教材与学习指导用书 (1)《离散数学----21世纪大学本科计算机专业系列教材》； 作者： 屈婉玲，耿素云，张立昂　 清华大学出版社；ISBN：9787302107576 (2)《离散数学习题解答与学习指导——21世纪大学本科计算机专业系列教材》； 作者： 屈婉玲，耿素云，张立昂 清华大学出版社； ISBN： 9787302120391 参考书目 (1)《离散数学》；作者：左孝凌 等编著 出版社：上海科学技术文献出版社 (2)《离散数学》；作者：杨炳儒 编著 出版社：人民邮电出版社 (3)《离散数学》；作者：刘书家 等编著 出版社：电子工业出版社 一.现代数学的两大分类 一类是研究连续对象的,如:分析、方程等 另一类就是研究离散对象的离散数学 离散数学不仅在基础数学研究中具有极其重要的应用，在其它的学科中也有重要的应用，如计算机科学、编码和密码学、物理、化学、生物等均有重要应用。 二.什么是离散数学 离散数学的研究对象是离散量，一切以离散现象作为其研究对象或对象之一的数学均称为离散数学，其研究各种各样的离散量的结构及之间的关系。 计算机是一个离散结构，计算机的研究对象大都是离散形式，离散数学当之无愧地可以充分描述计算机科学的离散性特点，是研究计算机科学的基本数学工具和最合适的理论手段。 1.研究离散对象的科学 离散数学主要研究6个方面的内容：数理逻辑、集合论、代数结构、图论、组合数学、形式语言与自动机。 离散数学是计算机问世后，迅速发展起来的一门数学分支。 计算机科学就是算法的科学，而计算机所处理的对象就是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是离散数学。 离散数学的发展，改变了传统数学中分析和代数占统治地位的局面。 2.计算机革命的基础 微积分和近代数学的发展，为近代的工业革命奠定了基础；而离散数学的发展则是奠定了计算机革命的基础。 计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序就是算法，在绝大多数情况下，计算机的算法就是针对离散的对象。 正是因为有了离散算法，才使计算机好象有了思维。 3.数学的主流分支 汤姆森科学公司创刊的电子刊物《离散数学和理论计算机科学》即是一个很好的说明，它的内容涉及离散数学和计算机科学的众多方面。 计算机软件的促进和需求，使离散数学已成为一门既广博又深奥的学科，其需要很深的数学基础，逐渐成为数学的主流分支。 伟大数学家盖尔芳德预言离散数学和几何学将是下一个世纪数学研究的前沿阵地，这一观点不仅得到国际数学界的赞同，也得到了中国数学界的认可和响应。 4.现代科学的重要分支 离散数学 是现代科学的一个重要分支； 是计算机科学中基础理论的核心课程； 是一门在基础数学研究中具有极其重要地位的综合数学学科； 在其它的学科，如编码和密码学、物理、化学、生物等学科中均有重要应用。 5.重视“能行性”的研究 解决一个问题，首先要证明该问题解的“存在性”，还需找到有限的、有规则的解决步骤，这与连续数学的讨论方法完全不同。 图灵(Turing)机。1936年为研究可计算性问题而建立的基本结构思想，很好地描述了运算过程的一个数学模型。 丘奇(Chruch)论题。任何一个算法都可用一个图灵机描述，为1946年计算机的问世在理论上奠定了理论基础。 三.学习目的 掌握离散数学知识，为后续课程（如数据结构、操作系统、编译原理、数字逻辑、算法分析、逻辑程序设计、体系结构、容错诊断、机器定理证明、网络、人工智能等）的学习打下坚实的理论基础。 通过离散数学的学习，培养抽象思维、慎密概括和严密逻辑推理能力，掌握解决问题的方法。 四.典型实例 离散数学无所不在。 它的主要应用就是在各种复杂关系中找出最优的方案。 离散数学，完全可以看成是一门量化的关系学，一门量化了的运筹学，一门量化了的管理学。 列举以下典型实例： 1.船夫问题 在数学游戏中，有这样一类问题： 一个船夫要把一只狼，一只羊和一棵白菜运过河。 当人不在场时，狼要吃羊，羊要吃白菜，而且船夫的船每趟只能运其中一个过河。 问船夫怎样才能把三者都运过河去？ 2.工作调度和安排问题 泡茶问题：洗水壶(1分钟)，拿茶(1分钟)，泡茶(1分钟)，洗茶壶(2分钟)、洗茶杯(2分钟)，烧水(10分钟)。如何安排？ 曼哈顿计划：生产原子弹涉及很多工序，许多人员和部门，很多元件的