浅淡离散数学sc【高教知识】

1、离散数学（1） 浅谈离散数学,Discrete Mathematics,1,全面分析,目 录,CSUFT SFGroup,2,全面分析,课程介绍,CSUFT SFGroup,时间（1-9，11-19）： 星期一： 3、4节(9:55 11:35) 星期四： 3、4节(9:55 11:35) 地点： 星期一： 一教南408 星期四： 一教南408,上课时间与地点,3,全面分析,课程介绍,教材及参考书 教材 屈婉玲，耿素云，离散数学（修订版），高等教育出版社，2008年3月 其它参考资料 离散数学，左孝凌著，上海科技文献出版社； 离散数学及其应用，傅彦、顾小丰著，电子工业出版 社； Discret

2、e Mathematical Structures（英文Fourth Edition），B Kolman, Robert C. Busby, Sharon Ross著，高等教育出版社； Discrete Mathematics and Its Applications (英文Fifth Edition), Kenneth H.Rosen著，机械工业出版社； 推荐 “中国地质大学 离散数学,CSUFT SFGroup,4,全面分析,教材,CSUFT SFGroup,5,全面分析,课程介绍,CSUFT SFGroup,内容介绍 第1部分: 数理逻辑 第2部分: 集合论 第3部分:代数论(略讲) 第

3、4部分: 图论 第五部分：讨论课（学以致用,6,全面分析,课程介绍,内容介绍数理逻辑 命题逻辑（1、2、3章） 谓词逻辑（4、5章） 内容介绍集合论 集合代数（6章） 关系（7章） 函数（8章） 内容介绍图论 基本概念：点、边、路、圈等（14章） Euler图、Hamilton图、最短路问题（15章） 树（16章） 平面图（17章,CSUFT SFGroup,7,全面分析,课程介绍,进度安排 漫长的：课程在19周结束。 紧张的：课程在20周考试,8,CSUFT SFGroup,8,全面分析,课程介绍,课程成绩 1、平时成绩（50%） 平时： 20% 平时作业：10% 出勤： 10%(三次被点名

4、缺课，肯定不及格) 小组讨论： 30%（分组、共同做题、分工准备、代表发言；包括了平时表现分） 2、考试成绩（50%） 期末考试：50%（闭卷,CSUFT SFGroup,9,全面分析,课程介绍,课程目标 侧重于掌握基本概念和基本知识。一方面，它给后继课，如数据结构、编译系统、操作系统、数据库原理、软件工程、计算机网络、程序设计等，提供必要的数学基础,CSUFT SFGroup,10,全面分析,课程介绍,课程目标 掌握必备的数学工具和培养抽象思考能力。通过学习离散数学，可以培养和提高自己的抽象思维和逻辑推理能力，为以后的软、硬件学习和研究开发工作，打下坚实的数学基础,CSUFT SFGroup

5、,11,全面分析,目 录,CSUFT SFGroup,12,全面分析,本节讲解思路,本节目的：揭开离散数学的神秘面纱,离散数学的发展,什么是数学,什么是离散数学,CSUFT SFGroup,13,全面分析,数学,数学：于现实对象与理念之间;心智的产物 柏拉图(古希腊公元前427-前347,什么是数学,CSUFT SFGroup,14,全面分析,数学是研究数量的科学 亚里士多德(公元前384-前322,数是一种离散的数量; 量是一种连续的数量,研究数及其属性的学科叫做算术 研究量及其属性的学科叫做几何,什么是数学,CSUFT SFGroup,15,全面分析,数学是研究顺序和度量的科学 笛卡尔 (

6、法国1596-1650,顺序=数 度量=量,什么是数学,CSUFT SFGroup,16,全面分析,数学=逻辑 -罗素(英国1872-1970,理发师：村里所有不自己理发的人都由我给他们理发，我也只给这些人理发,问：理发师的头发由谁理呢,罗素悖论,什么是数学,CSUFT SFGroup,逻辑是数学的少年时代 数学是逻辑的成年时代,17,全面分析,科朗.罗宾斯（美），数学是什么，1941年 数学作为人类智慧的一种表达形式，反映生动活泼的意念、深入细致的思考以及完美和谐的愿望。它的基础是逻辑和直觉、分析和推理、共性和个性,CSUFT SFGroup,什么是数学,18,全面分析,本身已如此一目了然，

7、以致于没有任何词汇能够把他解说得更清楚的事物，绝不要试图给他下定义，以免被所使用的含混不清的词汇所欺骗 帕斯卡（法国） 数学的定义： 数学是一种知识体系，是经过严密的逻辑推理而形成的系统化的理论知识总和，它既反映了人们对“现实世界的空间形式和数量关系”的认识，又反映了人们对“可能的量的关系和形式”的认识,什么是数学,CSUFT SFGroup,19,全面分析,相关数学课程 初等代数、高等代数 平面几何、立体几何 高等数学 线性代数 矩阵分析 离散数学 概率与数理统计 数学分析 复变函数 泛函分析 模糊数学,什么是数学,CSUFT SFGroup,20,全面分析,离散数学 Discrete Ma

8、thematics,什么是离散数学,CSUFT SFGroup,21,全面分析,离散数学是计算机出现以后迅速发展起来的一门数学分支。计算机科学就是算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是离散数学。离散数学的发展改变了传统数学中分析和代数占统治地位的局面。 离散数学是现代数学的一个重要分支，是计算机科学与技术的理论基础，所以又称为计算机数学，是计算机科学与技术专业的核心、骨干课程,离散数学概述,什么是离散数学,CSUFT SFGroup,22,全面分析,离散数学-研究离散结构的数学分科。（辞海） 相对于研究连续量的微积分

9、，离散数学是研究各种各样的离散量的结构及离散量之间的关系的一门学科。 两个关键概念： 离散量：数、点、符号；通常用集合表示； 通常是有限的或可数的元素。 结构：是什么，由哪些元素组成,什么是离散数学,CSUFT SFGroup,23,全面分析,从数学的角度出发，数学本身可分为连续数学和离散数学。离散和连续是现实世界中物质运动对立统一的两个方面，离散数学和连续数学是描述、刻画现实物质世界的重要工具,什么是离散数学,离散的印象： 枯藤老树昏鸦，小桥流水人家，古道西风瘦马，夕阳西下，断肠人在天涯。 天净沙秋思元.马致远,连续的印象： 剪不断，理还乱，是离愁恰似一江春水向东流。 南唐.李煜,CSUFT

10、 SFGroup,24,全面分析,离散数学的定义： 离散数学是研究各种各样的离散量的结构及离散量之间的关系的一门学科。 研究对象：离散量 离散量（或离散对象）：有限个或可数个元素 离散数学是现代数学的一个重要分支，是计算机类专业的重要课程。它以研究离散量的结构及其相互间的关系为主要目标，其研究对象一般是有限个或可数个元素。它充分描述了计算机科学离散性的特点,什么是离散数学,CSUFT SFGroup,25,全面分析,问题 张三说李四在说谎，李四说王五在说谎，王五说张三、 李四都在说谎，问张三，李四，王五三人，到底谁说真话，谁说假话？ 答案 张三说谎，王五说谎，李四说真话,什么是离散数学,26,

11、全面分析,问题 求1到250之间能被2,3,5和7任何一个整除的整数个数。 答案 193,什么是离散数学,27,全面分析,分类问题、识别问题,什么是离散数学,28,全面分析,指数运算与算术运算的关系 axay =axy 指数运算与算术运算有什么内在联系,什么是离散数学,29,全面分析,中国邮路问题：邮递员从邮局出发，走遍每条街最后回到邮局，问邮递员怎样走才能走出一条路程最短的路线,什么是离散数学,30,全面分析,已知一种电文密文格式由编号为A、B、C、D、E、F、G、H的8个信号组成，这7个信号出现的概率分别是：P(A)= 0.06, P(B)=0.12, P(C)=0.45, P(D)=0.

12、04, P(E)=0.11, P(F)=0.03, P(G)=0.10，P(H)=0.09，怎样才能为这8个信号编码得到最优编码,什么是离散数学,31,全面分析,什么是离散数学,32,全面分析,18世纪以前, 数学基本上是研究离散对象的数量和空间关系的科学。 之后,因天文学,物理学的发展,如行星轨道,牛顿三大力学定律等研究,极大地推动了连续数学(以微积分,数学物理方程, 实、复变函数论为代表)的发展。 离散对象的研究则处于停滞状态。 20世纪30年代, 图灵提出计算机的理论模型图灵机。 这种模型早于实际制造计算机十多年,现实的计算机的计算能力, 本质上和图灵机的计算能力一样。 由于在计算机内,

13、机器字长总是有限的, 它代表离散的数或其它离散对象，因此随着计算机科学和技术的迅猛发展,离散数学就显得重要,离散数学的发展,CSUFT SFGroup,33,全面分析,有关科学家：Von Neumann、图灵、 Abel、Galois、 Hawking、吴文俊 冯诺依曼,离散数学的发展,CSUFT SFGroup,34,全面分析,图灵,阿兰麦席森图灵（Alan Mathison Turing，1912.6.231954.6.7），英国数学家、逻辑学家，被称为人工智能之父。他是计算机逻辑的奠基者，许多人工智能的重要方法也源自于这位伟大的科学家。他对计算机的重要贡献在于他提出的有限状态自动机也就是

14、图灵机的概念，对于人工智能，它提出了重要的衡量标准“图灵测试”，如果有机器能够通过图灵测试，那他就是一个完全意义上的智能机，和人没有区别了。 他所创立的数学模型一图灵机(离散数学内容之一)在可计算性理论中起着重要作用，为计算机的诞生奠定了坚实的理论基础他杰出的贡献使他成为计算机界的第一人，现在人们为了纪念这位伟大的科学家将计算机界的最高奖定名为“图灵奖,CSUFT SFGroup,35,全面分析,Niels Abel,A statue of Abel in Oslo,CSUFT SFGroup,36,全面分析,Evariste Galois,CSUFT SFGroup,37,全面分析,Step

15、hen William Hawking,CSUFT SFGroup,38,全面分析,吴文俊先生,CSUFT SFGroup,39,全面分析,目 录,40,全面分析,本节讲解思路,五、“有趣”、“好玩”、“应用性强,三、培养抽象思维能力、逻辑思维能力和创新能力,四、使我们写出优秀的程序解决实际问题,一、与计算机学科的联系,二、它是后续计算机课程的先导和基础,41,全面分析,计算机学科的一个重要特点离散性,硬件 软件（系统软件、应用软件,模 型,算法（程序运行逻辑,数据表示、存储,程序编写、执行,离 散 数 学,一、与计算机学科的联系,CSUFT SFGroup,42,全面分析,离散数学是计算机出

16、现以后迅速发展起来的一门数学分支。计算机科学就是算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是离散数学。离散数学是计算机科学与技术的理论基础。如果说“高科技本质上是数学技术”的话，计算机科学与技术基本上是离散数学技术。所以离散数学又称为计算机数学，是计算机科学与技术专业的核心、骨干课程,一、与计算机学科的联系,CSUFT SFGroup,43,全面分析,从离散数学的基本内容和计算学科的发展情况来看，许多计算学科的问题，都可以在离散数学的范围中表达，都可以试验抽象为离散数学的问题，离散数学在较通用的层面上描述了计算学科所表现出

17、来的信息革命的许多模型，为现代计算学科的发展和应用提供了理论基础。从学习的角度来看，离散数学的思维方法能够为计算机科学所用，“离散数学能够使我们在更高的高度去了解和学习计算机科学”,一、与计算机学科的联系,CSUFT SFGroup,44,全面分析,45,它给后继课提供必要的数学基础； 离散数学的后继课程： 数字电路、编译原理、数据结构、 操作系统、数据库系统、算法的分析与设计、软件工程、人工智能、多媒体技术、计算机网络等专业课程以及 信息管理、信号处理、模式识别、 数据加密等相关课程,二、它是后续计算机课程的先导和基础,CSUFT SFGroup,45,全面分析,46,第一部分 数理逻辑 自

18、动机理论、编译原理、人 工智能的理论课程基础之一 第二部分 集合论 集合：一种重要的数据结构 关系：关系数据库的理论基础 函数：所有计算机语言中不可 缺少的一部分,离散数学与后继课程,二、它是后续计算机课程的先导和基础,CSUFT SFGroup,46,全面分析,第三部分 代数系统 计算机编码和纠错码理论 数字逻辑设计基础 计算机使用的各种运算 第四部分 图论 数据结构、操作系统、编译原理 计算机网络原理的基础,离散数学与后继课程,二、它是后续计算机课程的先导和基础,CSUFT SFGroup,47,全面分析,离散数学特点-离散性、抽象性、逻辑性、可行性。 （）掌握一些典型的数学方法论：演绎法

19、、归纳法、类比法、反例法、反证法等等。 （）通过离散数学课程的学习，可以培养数学抽象能力；用数学语言描述问题的能力；逻辑思维能力；数学论证能力。即培养抽象、表示、推理、论证的能力,CSUFT SFGroup,三、培养抽象思维能力、逻辑思维能力和创新能力,48,全面分析,计算机求解的基本模式是：实际问题 数学建模 算法设计 编程实现 离散数学为数学建模打下知识基础、为算法设计提供具体指导 离散数学结构实际上就是通用的抽象的模式的集合。告诉你各种模式的本质特征和它们之间的关系，以及选用它们的策略；告诉你哪些问题是可解的，哪些是当前在图灵机模型上无（最优）解的，哪些是可以得到近似/较优解的。 简而言

20、之，离散数学的作用就在于训练运用离散结构针对科研和生产中产生的问题来建立数学模型，设计新的算法并论证算法的有效性；并写出优秀的程序来解决实际问题,四、使我们写出优秀的程序解决实际问题,CSUFT SFGroup,49,全面分析,五、“有趣”、“好玩”、“应用性强,离散数学是“美”与“理”的完美体现，要抱着欣赏的态度去学习。 离散数学无处不在。 主要应用于在各种复杂的关系中找出最优方案。 离散数学完全可以看成是一门量化了的关系学，量化了的运筹学，量化了的管理学。 例如：世界近代三大数学难题、出差派遣问题、船夫过河问题、工作调度和安排问题、航空调度和航班设定问题、交通规划与管理问题、中国邮路问题、

21、工程工序管理问题、地面铺砖问题、网络布局问题、金融分析问题、哥尼斯堡七桥问题、一笔画问题、蚂蚁比赛问题,CSUFT SFGroup,50,全面分析,1、四色猜想问题,一张世界地图，若用一种颜色对一个国家着色，那么只需四种颜色，即可以保证每两个相邻的国家颜色不同。 世界近代三大数学难题之一。1852年，英国弗南西斯格思里(Francis Guthrie)提出四色猜想。 1976年，在J. Koch的算法的支持下，美国数学家阿佩尔(Kenneth Appel)与哈肯(Wolfgang Haken)在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿判断，终于完成了四色定理的

22、计算机证明。 最近人们发现了更简单的证明,CSUFT SFGroup,51,全面分析,52,A，B，C，D四人中要派两个人出差，按下述三个条件有几种派法？ 如何派？ 若A去则C和D中要去一个人； B和C不能都去； C去则D要留下,2、出差派遣问题,CSUFT SFGroup,52,全面分析,3、船夫过河问题,船夫要把一匹狼、一只羊和一棵白菜运过河。 只要船夫不在场,羊就会吃白菜、狼就会吃羊。 船夫的船每次只能运送一种东西。 怎样才能把三者都运过河,CSUFT SFGroup,53,全面分析,4、工作调度和安排问题,如在生产原子弹的曼哈顿计划中，涉及到很多工序、很多人员安排、很多元件生产 怎样合

23、理调度各种人员的工作？ 怎样科学安排各种工序间的衔接？ 怎样计划使整个工期的时间尽可能短,CSUFT SFGroup,54,全面分析,5、航空调度和航班设定问题,怎样周密设定各个航班，以满足不同旅客转机的需求？ 怎样同时也使得每个机场的各个航班的起降分布合理？ 另外，在一些航班有延误的特殊情况下，怎样作出科学的调整,CSUFT SFGroup,55,全面分析,6、交通规划与管理问题,哪些地方可能是阻塞要地？ 哪些地方应设单行道？ 立交桥建在哪里最合适？ 红绿灯怎样设置最合理,CSUFT SFGroup,56,全面分析,7、中国邮路问题,一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到

24、邮局，应按怎样的路线走，他所走的路程才会最短呢？ 由我国数学家管梅谷在1962年首先提出的，因此，在国际上称为中国邮路问题,CSUFT SFGroup,57,全面分析,8、工程工序管理问题,世界著名的假日饭店在其科学的管理中严格规定了有关工序： 清洁工第一步是换什么，洗什么？第二步又做什么？ 同时需要确保他进出房间的次数最少？ 一个如此简单的工作都要讲究工程工序管理，那么更复杂的的工作就更不用说了,CSUFT SFGroup,58,全面分析,9、地面铺砖问题,用形状相同的方形砖块，无疑可将地面铺满（不考虑边缘的特殊情况） 而如用不同形状，又非方形的砖块来铺地面时，能否铺满？ 这一常见的实际的简

25、单问题，也涉及到很深的数学原理,CSUFT SFGroup,59,全面分析,10、网络布局问题,一个通信网络怎样布局最节省？ 美国的贝尔实验室和IBM公司都有世界一流的组合数学家在研究这个问题。 该问题关系到巨大的经济效益,CSUFT SFGroup,60,全面分析,11、金融分析问题,投资方案的确定。 怎样找出好的投资组合以降低投资风险。 南开大学组合数学研究中心开发出“金沙股市风险分析系统”，已投放市场，为短线投资者提供有效的风险防范工具,CSUFT SFGroup,61,全面分析,12、一笔画问题,所谓一笔画，就是从图形上的某点出发，笔不离开纸，而且每条线都只画一次不准重复。 什么样的图

26、形能一笔画成呢,CSUFT SFGroup,62,全面分析,13、蚂蚁比赛问题,甲乙两只蚂蚁进行比赛： 从他们所在的结点出发，在图中走过所有的边，最后到达C处，如果他们的速度相同，问谁先到达目的地,CSUFT SFGroup,63,全面分析,14、哥尼斯堡七桥问题,18世纪时，欧洲有一个风景秀丽的小城哥尼斯堡，那里有七座桥。如图所示。当时哥尼斯堡的居民中流传着一道难题：一个人怎样才能一次走遍七座桥，每座桥只走过一次，最后回到出发点,CSUFT SFGroup,64,全面分析,15、环游世界问题,从正十二面体的一个顶点出发，沿着正十二面体的棱前进，要把二十个顶点无一遗漏地全部通过，而且每个顶点恰

27、好只通过一次，最后回到出发点，这样，便是哈密尔顿周游世界问题,CSUFT SFGroup,65,全面分析,离散数学中有一个著名问题：是否存在稳定婚姻的问题。假如能找到两对夫妇（如张（男）-李（女）和赵（男）-王（女），如果张（男）更喜欢王（女），而王（女）也更喜欢张（男），那么这样就可能有潜在的不稳定性。离散数学的方法可以找到一种婚姻的安排方法，使得没有上述的不稳定情况出现（当然这只是理论上的结论）。这种离散数学的方法却有一个实际的用途：美国的医院在确定录取住院医生时，他们将考虑申请者的志愿的先后次序，同时也给申请排序。按这样的次序考虑出的总的方案将没有医院和申请者两者同时后悔的情况。实际上，高考学生的最后录取方案也可以用这种方法,16、是否存在稳定婚姻的问题,CSUFT SFGroup,66,全面分析,67,17、与我们息息相关的问题,CSUFT SFGroup,67,全面分析,目 录,68,68,全面分析,首先要明确的是，由于离散数学是一门数学课，且是由几个数学分支综合在一起的，内容繁多，非常抽象，因此即使是数学系的学生学起来都会倍感困难，对计算机专业的学生来说就更是如此。大家普遍反映这是大学四年最难学的一门课之一。