离散数学 Discrete Mathematics 郭永芳 guoyongfang.2006@yahoo.com.cn 河北工业大学计算机科学技术与软件学晚
河北工业大学计算机科学技术与软件学院 离散数学 Discrete Mathematics 郭永芳 guoyongfang.2006@yahoo.com.cn
离散数学是什么? 离散数学是计算机出现以后迅速发展起 来的一门数学分支。计算机科学就是算 法的科学,而计算机所处理的对象是离 散的数据,所以离散对象的处理就成了 计算机科学的核心,而研究离散对象的 科学恰恰就是离散数学。 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 离散数学是计算机出现以后迅速发展起 来的一门数学分支。计算机科学就是算 法的科学，而计算机所处理的对象是离 散的数据，所以离散对象的处理就成了 计算机科学的核心，而研究离散对象的 科学恰恰就是离散数学。 离散数学是什么？
离散数学是什么? 离散数学是现代数学的一个重要分支 是计算机类专业的重要课程。它以研究 离散量的结构及其相互间的关系为主要 目标,其研究对象一般是有限个或可数 个元素,因此离散数学可以充分描述计 算机学科离散性的特点 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 离散数学是什么？ 离散数学是现代数学的一个重要分支， 是计算机类专业的重要课程。它以研究 离散量的结构及其相互间的关系为主要 目标，其研究对象一般是有限个或可数 个元素，因此离散数学可以充分描述计 算机学科离散性的特点
关于离散数学的一些应用 一个邮递员从邮局出发,要走完他 所管辖的街道,他应该怎样选择什么样 的路径,这就是著名的"中国邮递员问题 ",由中国离散数学家管梅谷教授提出, 著名离散数学家]. Edmonds和他的合作 者给出了一个解答。 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 关于离散数学的一些应用 一个邮递员从邮局出发，要走完他 所管辖的街道，他应该怎样选择什么样 的路径，这就是著名的"中国邮递员问题 "，由中国离散数学家管梅谷教授提出， 著名离散数学家J. Edmonds和他的合作 者给出了一个解答
关于离散数学的一些应用 个班级的学生共计选修A、B、C D、E、F六门课程,其中一部分人同时 选修D、C、A,一部分人同时选修B、C、 F,一部分人同时选修B、E,还有一部 分人同时选修A、B,期终考试要求每天 考一门课,六天内考完,为了减轻学生 负担,要求每人都不会连续参加考试, 试设计一个考试日程表。 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 一个班级的学生共计选修A、B、C、 D、E、F六门课程，其中一部分人同时 选修D、C、A，一部分人同时选修B、C、 F，一部分人同时选修B、E，还有一部 分人同时选修A、B，期终考试要求每天 考一门课，六天内考完，为了减轻学生 负担，要求每人都不会连续参加考试， 试设计一个考试日程表。 关于离散数学的一些应用
关于离散数学的一些应用 个人带着一只狼、一只羊和一捆草 要渡河,由于船太小,人做摆渡者一次 只能运送一个“乘客”,很显然,如果 人不在,狼要吃羊,羊要吃草,问人怎 样才能把它们平安地渡过河去? Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 一个人带着一只狼、一只羊和一捆草 要渡河，由于船太小，人做摆渡者一次 只能运送一个“乘客”，很显然，如果 人不在，狼要吃羊，羊要吃草，问人怎 样才能把它们平安地渡过河去？ 关于离散数学的一些应用
关于离散数学的一些应用 网络计划技术 我们还会遇到更复杂的调度和安排 问题。例如,在生产原子弹的曼哈顿计 划中,涉及到很多工序,许多人员的安 排,很多元件的生产,怎样安排各种人 员的工作,以及各种工序间的衔接,从 而使整个工期的时间尽可能短?这些都 是离散数学典型例子。 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 网络计划技术 我们还会遇到更复杂的调度和安排 问题。例如，在生产原子弹的曼哈顿计 划中，涉及到很多工序，许多人员的安 排，很多元件的生产，怎样安排各种人 员的工作，以及各种工序间的衔接，从 而使整个工期的时间尽可能短？这些都 是离散数学典型例子。 关于离散数学的一些应用
关于离散数学的一些应用 个通讯网络怎样布局最节省?美国 的贝尔实验室和IBM公司都有世界一流 的离散数学家在研究这个问题,这个问 题直接关系到巨大的经济利益。 我们知道,用形状相同的方型砖块 可以把一个地面铺满(不考虑边缘的情 况),但是如果用不同形状,而又非方 型的砖块来铺一个地面,能否铺满呢? 这不仅是一个与实际相关的问题,也涉 及到很深的离散数学问题。 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 一个通讯网络怎样布局最节省？美国 的贝尔实验室和IBM公司都有世界一流 的离散数学家在研究这个问题，这个问 题直接关系到巨大的经济利益。 我们知道，用形状相同的方型砖块 可以把一个地面铺满（不考虑边缘的情 况），但是如果用不同形状，而又非方 型的砖块来铺一个地面，能否铺满呢？ 这不仅是一个与实际相关的问题，也涉 及到很深的离散数学问题。 关于离散数学的一些应用
关于离散数学的一些应用 航空调度和航班的设定也是离散数学的问 题。怎样确定各个航班以满足不同旅客转机的 需要,同时也使得每个机场的航班起落分布合 理。此外,在一些航班有延误等特殊情况下, 怎样作最合理的调整,这些都是离散数学的问 题 对于城市的交通管理,交通规划,哪些地 方可能是阻塞要地,哪些地方应该设单行道, 立交桥建在哪里最合适,红绿灯怎样设定最合 理,如此等等,全是离散数学的问题。 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 航空调度和航班的设定也是离散数学的问 题。怎样确定各个航班以满足不同旅客转机的 需要，同时也使得每个机场的航班起落分布合 理。此外，在一些航班有延误等特殊情况下， 怎样作最合理的调整，这些都是离散数学的问 题。 对于城市的交通管理，交通规划，哪些地 方可能是阻塞要地，哪些地方应该设单行道， 立交桥建在哪里最合适，红绿灯怎样设定最合 理，如此等等，全是离散数学的问题。 关于离散数学的一些应用
关于离散数学的一些应用 离散数学中有一个著名问题:是否存在稳 定婚姻的问题。假如能找到两对夫妇(如张 (男)--李(女)和赵(男)-王(女)), 如果张(男)更喜欢王(女),而王(女)也 更喜欢张(男),那么这样就可能有潜在的不 稳定性。离散数学的方法可以找到一种婚姻的 安排方法,使得没有上述的不稳定情况出现 当然这只是理论上的结论)。这种离散数学 的方法却有二个实际的用途:美国的医院在确 定录取住院医生时,他们将考虑申请者的志愿 的先后次序,同时也给申请排序。按这样的次 序考虑出的总的方案将没有医院和申请者两者 同时后悔的情况。实际上,高考学生的最后录 取方案也可以用这种方法。 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 离散数学中有一个著名问题：是否存在稳 定婚姻的问题。假如能找到两对夫妇（如张 （男）--李（女）和赵（男）--王（女））， 如果张（男）更喜欢王（女），而王（女）也 更喜欢张（男），那么这样就可能有潜在的不 稳定性。离散数学的方法可以找到一种婚姻的 安排方法，使得没有上述的不稳定情况出现 （当然这只是理论上的结论）。这种离散数学 的方法却有一个实际的用途：美国的医院在确 定录取住院医生时，他们将考虑申请者的志愿 的先后次序，同时也给申请排序。按这样的次 序考虑出的总的方案将没有医院和申请者两者 同时后悔的情况。实际上，高考学生的最后录 取方案也可以用这种方法。 关于离散数学的一些应用
