离散数学教学绪论.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为真。 根据题设条件，可得如下公式： R1P1Q2：如果商人和猜对的人戴的都是红帽子，那么另一个戴的就是黑帽子，因为红帽子只有两顶。 R1Q1P2：如果商人和另一个戴的都是红帽子，那么猜对的人戴的就是黑帽子。 P1P2：如果猜对的人戴的不是红帽子，那么他戴的就是黑帽子。 Q1Q2：如果另一个人戴的不是红帽子，那么他戴的就是黑帽子。 推演步骤如下： 设P1 （1）P1（根据假设）；（2）R1（根据题设） （3）R1P1（合取构成）；（4）R1P1Q2（根据题设） （5）Q2（3）（4）分离）。 这就是说，“另一个人戴黑帽子”这个判定是必然可以作出的，但是这与题设条件（即“另一个没有作出判定”）相矛盾，因此，P1为假，即P1为真，故可得： （6）P1；（7）P1P2（根据题设）； （8）P2（6）（7）分离）。 这就是说，“猜对的人戴着黑帽子”是真的，所以猜对的人肯定的说：“我戴的是黑帽子”。 返 回,理发师的头谁来剃的答案分析,如果理发师的头由别人给他理，即理发师自己不给自己理发，那么按规定这位理发师的头应该有自己理。如果理发师的头由他自己理，按规定他只给那些不给自己理发的人理发，那么理发师的头不能由他自己理，即理发师的头应该由别人来理。这就产生了矛盾: 理发师的头既不能由别人理，也不能由他自己理，所以这位理发师的规定是一个悖论。 返 回,聪明的囚徒的答案分析,聪明的囚徒所说的话，应使国王无论怎么处置他都带来矛盾，这句话就是“国王决定砍我的头”。如果这和国王规定一致，是说真话，因而按国王决定的处死方法，讲真话应处以绞刑，这样就造成了国王的规定（砍头）同国王决定的处死方法相矛盾。如果这和国王的规定不一致，是说的假话，因而按照国王决定的处死方法，讲假话予以砍头，这样