离散数学PPT教学绪论.ppt

离 散 数 学 主讲教师： 程 虹 电 话： 67626 第一章 绪 论 课 程 简 介 教 学 大 纲 教 学 目 的 教 学 要 求 参 考 教 材 考 核 方 式 说 明 离 散 与 连 续 名 人 名 言 趣 味 数 学 土耳其商人和帽子的故事 理发师的头由谁来理 ? 聪 明 的 囚 徒 考 试 日 程 表 的 安 排 课 程 简 介 课程编号： 07ZB073116 课程性质： 必修 总学时： 72学时 总学分： 4分 开课学期： 第三学期 适用专业： 计算机科学与技术 先修课程： 高等数学，线性代数 ，计算机导论 后续课程： 数据结构及算法，数字逻辑 课程地位： 学位课程，非常重要 教 学 大 纲 离散数学研究离散量的结构和相互间的关系。 其研究对象一般是有限个或可数个元素。课程以 培养学生的抽象思维和缜密概括能力为主要教学 目标。课程内容主要有：数理逻辑、集合论、二 元关系、代数系统、图论、形式语言和自动机。 离散数学能够为学生学习计算机专业知识与技术， 从事计算机软、硬件开发和应用打下坚实的基础。 教 学 目 的 1、了解离散数学研究的内容以及它在计算机科学中的 地位和作用。 2、理解和掌握命题逻辑和谓词逻辑的符号化和推导证 明方法。 3、理解和掌握集合与二元关系的性质和应用。 4、掌握代数系统（群、半群、格、环、域，布尔代数 等）的性质及主要应用。 5、掌握常用的判别图和树的方法。 教 学 要 求 1、理解命题逻辑和谓词逻辑的异同点和联系，掌握基本概念和推理证明方法。 2、理解并掌握集合的基本运算和性质及其计算机科学中的应用。 3、了解二元关系和集合的笛卡儿积，掌握关系的运算和性质。 4、理解函数的定义，并掌握不同种函数的性质。 5、理解并掌握代数系统的性质，掌握几种典型的代数系统。 6、了解图的基本概念，掌握它的存储表示，并理解最短路径和关键路径的求法。 7、理解并掌握欧拉图和哈密尔顿图的定义及判定方法。 8、了解树的基本概念及树的相关应用。 9、了解形式语言和有穷自动机。 10、能够针对所学知识点，对每章后的习题做的覆盖率达到 60以上。 11、能够做题举一反三，尽量使用多种方法去解题，锻炼独立思考的能力。 12、能够从生活中、计算机课程学习中对应找到离散数学的实际应用实例，进 而加深理解和掌握相关的知识点，并能提高学习的趣味性和积极性。 参 考 教 材 推荐教材： 离散数学 ，第二版，左孝凌、刘永才等编著，上海科学技术文献出版社 参考教材： 1、 离散数学 ，第三版，耿素云、屈婉玲等编，清华大学出版社 2、 离散数学 ，刘学书、袁磊等编著， 武汉大学出版社 3、 离散数学导论 ， 徐洁磐编，高等教育出版社 4、 离散数学 ，陈莉、刘晓霞编著，高等教育出版社 5、 离散数学结构 ，第四版（影印版）， Bernard Kolman等编，高等 教育出版社 6、 离散数学 ， 朱一清编著， 电子工业出版社 7、 离散数学 ，乔维声编，西安电子科技大学出版社 8、 离散数学 ，第四版， Richard Johnsonbaugh著，电子工业出版社 考 核 方 式 说 明 1、考查方式： 笔试（闭卷） 2、笔试时间： 120分钟 3、成绩构成： 结业考试成绩（占 70%） ,平时成绩 (占 30%， 包括作业、提问、测验等 ) 4、主要题型： 本课程命题范围涵盖课程的大部分章节。试 题难易程度分为：较易占 50%，中等难度占 40%，较难占 10%。在题型结构上，主要由选择题、填空题、判断题、 画图题和计算（综合）题，其中客观题（包括选择题、填 空题、判断题等）占 40%；主观题（包括画图题和计算 （综合）题等）占 60%。 5、考核范围： 第 2章第 11章 离 散 与 连 续 “离散数学”是研究离散数量关系和离散结构数 学模型的数学分支的统称。 “离散”与“连续”是数量关系中一对极为深刻 的矛盾，它们之间的对立与统一是数学发展的重 要动力之一。“离散”是“连续”的否定，即 “不连续”；“连续”则是指事物、数量的一种 属性，这种属性使它们容易被分割或结合，并且 不会因此而丧失它们原有的本性。例如，实数是 连续的，整数则是离散的；马铃薯是离散的，而 马铃薯羹则是连续的。 近 50年来，数字电子计算机的飞速发展与广泛应用， 极大地冲击了现代数学。由于数字电子计算机是一个离散 结构，它只能处理离散的或离散化了的数量关系，因此， 无论计算机科学本身，还是与计算机科学及其应用密切相 关的现代科学研究领域，都面临这样一些问题：如何高速、 有效地处理离散的对象和离散的数量关系，如何对离散结 构建立离散数学模型，又如何将已用连续数量关系建立起 来的数学模型离散化，从而可由计算机加以处理。于是， 人们开始重新认识离散数量关系的研究意义，重新重视讨 论离散数量关系的数学分支，并取得新的发展。离散数学 学科的出现和发展是上述事实的逻辑结果。 名 人 名 言 1、（绪论）宏伟的乐队里缺少不了乐器之王 钢琴，高 耸入云的数学大厦里也缺少不了“离散”（数学），“连 续”和“离散”像两支翅膀， 它把人类从地上带向天堂！ “有限”与“无穷”象一把锋利的宝剑，它无往不胜，无 坚不摧！ 2、学习数学吧！即便你还是一个孩童，学习它能培养你的 耐性，更能发挥你的思考力及创造力！ 3、 (集合论技术 )连续的形象：“剪不断，理还乱，是离愁， 恰似一江春水向东流。” 南唐，李后主词 4、离散的形象：“枯藤老树昏鸦，小桥流水人家，古道西 风瘦马，夕阳西下，断肠人在天涯。” 元 .马致远 5、 (图论 )“现在应该使用图的概念渗入所有的数学教学，图 表示了一个系统的可能状态以及连接这些状态的算子。 离散数学的趣味应用 1、土耳其商人和帽子的故事 一个土耳其商人，想找一个十分聪明的助手协助他经商，有 两个人前来应聘，这个商人为了试一试哪一个聪明些，就把两个 人带进一间漆黑的屋子里，他打开电灯后：“这张桌子上有五顶 帽子，两顶是红色的，三顶是黑色的。现在，我把灯关掉，而且 把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在头上， 在我开灯后，请你们尽快的说出自己头上戴的帽子是什么颜色 的。”说完之后，商人将电灯关掉，然后三人都摸了一顶帽子戴 在头上，同时商人将余下的两顶帽子藏了起来，接着把电灯打开， 这时，那两个有应试者看到商人头上戴的是一顶红帽子，过了一 会儿，其中一个人便喊到：“我戴的是黑帽子。” 请问这个人猜得对吗？是怎么推导出来的？ 答案分析 2、理发师的头由谁来理 ? 在一个小镇上，有一个理发师公开 宣布：他给而且只给小镇上所有不给 自己理发的人理发，现在要问 : 这位理 发师的头由谁来理 ? 答案分析 3、聪 明 的 囚 徒 古希腊有个国王，对处死囚徒的方法作了两种规定： 一种是砍头，一种是绞刑。并且他自恃聪明的做出一种规 定：囚徒可以说一句话，并且这句话是马上可以验证其真 假。如果囚徒说的是真话，那么处以绞刑，如果囚徒说的 是假话，那么处以砍头。许多囚徒或者是因为说了假话而 被砍头或者因为说了真话而被处以绞刑。 有一位极其聪明的囚徒，当轮到他来选择处死方法 时，他说出一句巧妙的话，结果使这个国王按照哪种方法 处死他，都违背自己的决定，只得将他放了。 试问：这囚徒说的是句什么话？ 答案分析 4、考试日程表的安排 考虑七天安排七门考试的问题，要使同 一教员举行的任何两门考试不要安排在接 连的两天内进行。假如每个教员最多举行 四次考试，证明安排这样的考试日程表总 是可能的。 答案分析 土耳其商人和帽子的答案分析 设 P1表示“猜对的人戴红帽子”； P2表示“猜对的人戴黑帽子”； Q1表示“另一个人戴红帽子”； Q2表示“另一个人戴黑帽子”； R1表示“商人戴 红帽子”。 现在知道 R1为真，又知道另一个人没有作出断定，即既不能断定 Q1为真，也不能断定 Q2为真。 根据题设条件，可得如下公式： R1 P1Q2 ：如果商人和猜对的人戴的都是红帽子，那么另一个戴的就是黑帽子， 因为红帽子只有两顶。 R1 Q1P2 ：如果商人和另一个戴的都是红帽子，那么猜对的人戴的就是黑帽子。 P1P2 ：如果猜对的人戴的不是红帽子，那么他戴的就是黑帽子。 Q1Q2 ：如果另一个人戴的不是红帽子，那么他戴的就是黑帽子。 推演步骤如下： 设 P1 （ 1） P1（根据假设）；（ 2） R1（根据题设） （ 3） R1 P1（合取构成）；（ 4） R1 P1Q2 （根据题设） （ 5） Q2（ 3）（ 4）分离）。 这就是说，“另一个人戴黑帽子”这个判定是必然可以作出的，但是这与题设条件 （即“另一个没有作出判定”）相矛盾，因此， P1为假，即 P1为真，故可得： （ 6） P1；（ 7） P1P2 （根据题设）； （ 8） P2（ 6）（ 7）分离）。 这就是说，“猜对的人戴着黑帽子”是真的，所以猜对的人肯定的说：“我戴的是黑 帽子”。 返 回 理发师的头谁来剃的答案分析 如果理发师的头由别人给他理，即理发师自 己不给自己理发，那么按规定这位理发师的头应 该有自己理。如果理发师的头由他自己理，按规 定他只给那些不给自己理发的人理发，那么理发 师的头不能由他自己理，即理发师的头应该由别 人来理。这就产生了矛盾 : 理发师的头既不能由 别人理，也不能由他自己理，所以这位理发师的 规定是一个悖论。 返 回 聪明的囚徒的答案分析 聪明的囚徒所说的话，应使国王无论怎么处置他都 带来矛盾，这句话就是“国王决定砍我的头”。如果这 和国王规定一致，是说真话，因而按国王决定的处死方 法，讲真话应处以绞刑，这样就造成了国王的规定（砍 头）同国王决定的处死方法相矛盾。如果这和国王的规 定不一致，是说的假话，因而按照国王决定的处死方法， 讲假话予以砍头，这样又造成了国王的规定（绞刑）同 国王决定的处死方法相矛盾。国王处于进退维谷的处境， 只好免于处死，将囚徒放掉。 返 回 考试日程表的答案分析 如果将七次（或七天）考试作为七个 顶点，做一个图 G，若两个顶点对应的考试 是由不同的教员举行的，则这两个顶点连 一条边，实际上就是判定图 G是否有哈密尔 顿通路问题。 返 回 课 后 思 考 请同学们课后通过查阅资料或上网搜索 的方式，列举出离散数学的其他一些趣味 应用问题！