离散数学PPT教学绪论.ppt

《离散数学PPT教学绪论.ppt》由会员分享，可在线阅读，更多相关《离散数学PPT教学绪论.ppt（21页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、离离 散散 数数 学学主讲教师：程主讲教师：程 虹虹电电 话：话：67626第一章第一章 绪绪 论论课课 程程 简简 介介教教 学学 大大 纲纲教教 学学 目目 的的教教 学学 要要 求求参参 考考 教教 材材考考 核核 方方 式式 说说 明明离离 散散 与与 连连 续续名名 人人 名名 言言 趣趣 味味 数数 学学土耳其商人和帽子的故事土耳其商人和帽子的故事 理发师的头由谁来理理发师的头由谁来理?聪聪 明明 的的 囚囚 徒徒考考 试试 日日 程程 表表 的的 安安 排排课课 程程 简简 介介课程编号：课程编号：07ZB073116 课程性质：课程性质：必修必修 总学时：总学时：72学时学时

2、总学分：总学分：4分分 开课学期：开课学期：第三学期第三学期 适用专业：适用专业：计算机科学与技术计算机科学与技术 先修课程：先修课程：高等数学，线性代数高等数学，线性代数，计算机导论，计算机导论后续课程：后续课程：数据结构及算法，数字逻辑数据结构及算法，数字逻辑课程地位：课程地位：学位课程，非常重要学位课程，非常重要 教教 学学 大大 纲纲离散数学研究离散量的结构和相互间的关系。离散数学研究离散量的结构和相互间的关系。其研究对象一般是有限个或可数个元素。课程以其研究对象一般是有限个或可数个元素。课程以培养学生的抽象思维和缜密概括能力为主要教学培养学生的抽象思维和缜密概括能力为主要教学目标。课

3、程内容主要有：数理逻辑、集合论、二目标。课程内容主要有：数理逻辑、集合论、二元关系、代数系统、图论、形式语言和自动机。元关系、代数系统、图论、形式语言和自动机。离散数学能够为学生学习计算机专业知识与技术，离散数学能够为学生学习计算机专业知识与技术，从事计算机软、硬件开发和应用打下坚实的基础。从事计算机软、硬件开发和应用打下坚实的基础。教教 学学 目目 的的1、了解离散数学研究的内容以及它在计算机科学中的、了解离散数学研究的内容以及它在计算机科学中的地位和作用。地位和作用。2、理解和掌握命题逻辑和谓词逻辑的符号化和推导证、理解和掌握命题逻辑和谓词逻辑的符号化和推导证明方法。明方法。3、理解和掌握

4、集合与二元关系的性质和应用。、理解和掌握集合与二元关系的性质和应用。4、掌握代数系统（群、半群、格、环、域，布尔代数、掌握代数系统（群、半群、格、环、域，布尔代数等）的性质及主要应用。等）的性质及主要应用。5、掌握常用的判别图和树的方法。、掌握常用的判别图和树的方法。教教 学学 要要 求求1、理解命题逻辑和谓词逻辑的异同点和联系，掌握基本概念和推理证明方法。、理解命题逻辑和谓词逻辑的异同点和联系，掌握基本概念和推理证明方法。2、理解并掌握集合的基本运算和性质及其计算机科学中的应用。、理解并掌握集合的基本运算和性质及其计算机科学中的应用。3、了解二元关系和集合的笛卡儿积，掌握关系的运算和性质。、

5、了解二元关系和集合的笛卡儿积，掌握关系的运算和性质。4、理解函数的定义，并掌握不同种函数的性质。、理解函数的定义，并掌握不同种函数的性质。5、理解并掌握代数系统的性质，掌握几种典型的代数系统。、理解并掌握代数系统的性质，掌握几种典型的代数系统。6、了解图的基本概念，掌握它的存储表示，并理解最短路径和关键路径的求法。、了解图的基本概念，掌握它的存储表示，并理解最短路径和关键路径的求法。7、理解并掌握欧拉图和哈密尔顿图的定义及判定方法。、理解并掌握欧拉图和哈密尔顿图的定义及判定方法。8、了解树的基本概念及树的相关应用。、了解树的基本概念及树的相关应用。9、了解形式语言和有穷自动机。、了解形式语言和

6、有穷自动机。10、能够针对所学知识点，对每章后的习题做的覆盖率达到、能够针对所学知识点，对每章后的习题做的覆盖率达到60以上。以上。11、能够做题举一反三，尽量使用多种方法去解题，锻炼独立思考的能力。、能够做题举一反三，尽量使用多种方法去解题，锻炼独立思考的能力。12、能够从生活中、计算机课程学习中对应找到离散数学的实际应用实例，进而、能够从生活中、计算机课程学习中对应找到离散数学的实际应用实例，进而加深理解和掌握相关的知识点，并能提高学习的趣味性和积极性。加深理解和掌握相关的知识点，并能提高学习的趣味性和积极性。参参 考考 教教 材材推荐教材：推荐教材：离散数学离散数学，第二版，左孝凌、刘永

7、才等编著，上海科学技术文献出版社，第二版，左孝凌、刘永才等编著，上海科学技术文献出版社参考教材：参考教材：1、离散数学离散数学，第三版，耿素云、屈婉玲等编，清华大学出版社，第三版，耿素云、屈婉玲等编，清华大学出版社 2、离散数学离散数学，刘学书、袁磊等编著，刘学书、袁磊等编著，武汉大学出版社武汉大学出版社3、离散数学导论离散数学导论，徐洁磐编，高等教育出版社徐洁磐编，高等教育出版社4、离散数学离散数学，陈莉、刘晓霞编著，高等教育出版社，陈莉、刘晓霞编著，高等教育出版社5、离散数学结构离散数学结构，第四版（影印版），第四版（影印版），Bernard Kolman等编，高等等编，高等教育出版社教育

8、出版社6、离散数学离散数学，朱一清编著，朱一清编著，电子工业出版社电子工业出版社7、离散数学离散数学，乔维声编，西安电子科技大学出版社，乔维声编，西安电子科技大学出版社8、离散数学离散数学，第四版，第四版，Richard Johnsonbaugh著，电子工业出版社著，电子工业出版社 考考 核核 方方 式式 说说 明明1、考查方式：、考查方式：笔试（闭卷）2、笔试时间：、笔试时间：120分钟3、成绩构成：、成绩构成：结业考试成绩（占70%）,平时成绩(占30%，包括作业、提问、测验等)4、主要题型：、主要题型：本课程命题范围涵盖课程的大部分章节。试题难易程度分为：较易占50%，中等难度占40%，

9、较难占10%。在题型结构上，主要由选择题、填空题、判断题、画图题和计算（综合）题，其中客观题（包括选择题、填空题、判断题等）占40%；主观题（包括画图题和计算（综合）题等）占60%。5、考核范围：、考核范围：第2章第11章离离 散散 与与 连连 续续“离散数学离散数学”是研究离散数量关系和离散结构数是研究离散数量关系和离散结构数学模型的数学分支的统称。学模型的数学分支的统称。“离散离散”与与“连续连续”是数量关系中一对极为深刻是数量关系中一对极为深刻的矛盾，它们之间的对立与统一是数学发展的重的矛盾，它们之间的对立与统一是数学发展的重要动力之一。要动力之一。“离散离散”是是“连续连续”的否定，即

10、的否定，即“不连续不连续”；“连续连续”则是指事物、数量的一种属则是指事物、数量的一种属性，这种属性使它们容易被分割或结合，并且不性，这种属性使它们容易被分割或结合，并且不会因此而丧失它们原有的本性。例如，实数是连会因此而丧失它们原有的本性。例如，实数是连续的，整数则是离散的；马铃薯是离散的，而马续的，整数则是离散的；马铃薯是离散的，而马铃薯羹则是连续的。铃薯羹则是连续的。近近50年来，数字电子计算机的飞速发展与广泛应用，年来，数字电子计算机的飞速发展与广泛应用，极大地冲击了现代数学。由于数字电子计算机是一个离散极大地冲击了现代数学。由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了

11、的数量关系，因此，结构，它只能处理离散的或离散化了的数量关系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临这样一些问题：如何高速、关的现代科学研究领域，都面临这样一些问题：如何高速、有效地处理离散的对象和离散的数量关系，如何对离散结有效地处理离散的对象和离散的数量关系，如何对离散结构建立离散数学模型，又如何将已用连续数量关系建立起构建立离散数学模型，又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。于是，来的数学模型离散化，从而可由计算机加以处理。于是，人们开始重新认识离散数量关系

12、的研究意义，重新重视讨人们开始重新认识离散数量关系的研究意义，重新重视讨论离散数量关系的数学分支，并取得新的发展。离散数学论离散数量关系的数学分支，并取得新的发展。离散数学学科的出现和发展是上述事实的逻辑结果。学科的出现和发展是上述事实的逻辑结果。名名 人人 名名 言言1、（绪论）宏伟的乐队里缺少不了乐器之王、（绪论）宏伟的乐队里缺少不了乐器之王钢琴，高钢琴，高耸入云的数学大厦里也缺少不了耸入云的数学大厦里也缺少不了“离散离散”（数学），（数学），“连连续续”和和“离散离散”像两支翅膀，像两支翅膀，它把人类从地上带向天堂！它把人类从地上带向天堂！“有限有限”与与“无穷无穷”象一把锋利的宝剑，它

13、无往不胜，无象一把锋利的宝剑，它无往不胜，无坚不摧！坚不摧！2、学习数学吧！即便你还是一个孩童，学习它能培养你的、学习数学吧！即便你还是一个孩童，学习它能培养你的耐性，更能发挥你的思考力及创造力！耐性，更能发挥你的思考力及创造力！3、(集合论技术集合论技术)连续的形象：连续的形象：“剪不断，理还乱，是离愁，剪不断，理还乱，是离愁，恰似一江春水向东流。恰似一江春水向东流。”南唐，李后主词南唐，李后主词4、离散的形象：、离散的形象：“枯藤老树昏鸦，小桥流水人家，古道西枯藤老树昏鸦，小桥流水人家，古道西风瘦马，夕阳西下，断肠人在天涯。风瘦马，夕阳西下，断肠人在天涯。”元元.马致远马致远5、(图论图论

14、)“现在应该使用图的概念渗入所有的数学教学，图现在应该使用图的概念渗入所有的数学教学，图表示了一个系统的可能状态以及连接这些状态的算子。表示了一个系统的可能状态以及连接这些状态的算子。离散数学的趣味应用离散数学的趣味应用1、土耳其商人和帽子的故事、土耳其商人和帽子的故事一个土耳其商人，想找一个十分聪明的助手协助他经商，有一个土耳其商人，想找一个十分聪明的助手协助他经商，有两个人前来应聘，这个商人为了试一试哪一个聪明些，就把两个两个人前来应聘，这个商人为了试一试哪一个聪明些，就把两个人带进一间漆黑的屋子里，他打开电灯后：人带进一间漆黑的屋子里，他打开电灯后：“这张桌子上有五顶这张桌子上有五顶帽子

15、，两顶是红色的，三顶是黑色的。现在，我把灯关掉，而且帽子，两顶是红色的，三顶是黑色的。现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在头上，把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在头上，在我开灯后，请你们尽快的说出自己头上戴的帽子是什么颜色的。在我开灯后，请你们尽快的说出自己头上戴的帽子是什么颜色的。”说完之后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头说完之后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来，接着把电灯打开，这上，同时商人将余下的两顶帽子藏了起来，接着把电灯打开，这时，那两个有应试者看到商人头上戴的是一

16、顶红帽子，过了一会时，那两个有应试者看到商人头上戴的是一顶红帽子，过了一会儿，其中一个人便喊到：儿，其中一个人便喊到：“我戴的是黑帽子。我戴的是黑帽子。”请问这个人猜得对吗？是怎么推导出来的？请问这个人猜得对吗？是怎么推导出来的？答案分析答案分析2、理发师的头由谁来理、理发师的头由谁来理?在一个小镇上，有一个理发师公开在一个小镇上，有一个理发师公开宣布：他给而且只给小镇上所有不给宣布：他给而且只给小镇上所有不给自己理发的人理发，现在要问自己理发的人理发，现在要问:这位理这位理发师的头由谁来理发师的头由谁来理?答案分析答案分析3、聪、聪 明明 的的 囚囚 徒徒古希腊有个国王，对处死囚徒的方法作了

17、两种规定：古希腊有个国王，对处死囚徒的方法作了两种规定：一种是砍头，一种是绞刑。并且他自恃聪明的做出一种规一种是砍头，一种是绞刑。并且他自恃聪明的做出一种规定：囚徒可以说一句话，并且这句话是马上可以验证其真定：囚徒可以说一句话，并且这句话是马上可以验证其真假。如果囚徒说的是真话，那么处以绞刑，如果囚徒说的假。如果囚徒说的是真话，那么处以绞刑，如果囚徒说的是假话，那么处以砍头。许多囚徒或者是因为说了假话而是假话，那么处以砍头。许多囚徒或者是因为说了假话而被砍头或者因为说了真话而被处以绞刑。被砍头或者因为说了真话而被处以绞刑。有一位极其聪明的囚徒，当轮到他来选择处死方法时，有一位极其聪明的囚徒，当

18、轮到他来选择处死方法时，他说出一句巧妙的话，结果使这个国王按照哪种方法处死他说出一句巧妙的话，结果使这个国王按照哪种方法处死他，都违背自己的决定，只得将他放了。他，都违背自己的决定，只得将他放了。试问：这囚徒说的是句什么话？试问：这囚徒说的是句什么话？答案分析答案分析4、考试日程表的安排、考试日程表的安排考虑七天安排七门考试的问题，要使同考虑七天安排七门考试的问题，要使同一教员举行的任何两门考试不要安排在接一教员举行的任何两门考试不要安排在接连的两天内进行。假如每个教员最多举行连的两天内进行。假如每个教员最多举行四次考试，证明安排这样的考试日程表总四次考试，证明安排这样的考试日程表总是可能的。

19、是可能的。答案分析答案分析土耳其商人和帽子的答案分析土耳其商人和帽子的答案分析设P1表示“猜对的人戴红帽子”；P2表示“猜对的人戴黑帽子”；Q1表示“另一个人戴红帽子”；Q2表示“另一个人戴黑帽子”；R1表示“商人戴红帽子”。现在知道R1为真，又知道另一个人没有作出断定，即既不能断定Q1为真，也不能断定Q2为真。根据题设条件，可得如下公式：R1P1Q2：如果商人和猜对的人戴的都是红帽子，那么另一个戴的就是黑帽子，因为红帽子只有两顶。R1Q1P2：如果商人和另一个戴的都是红帽子，那么猜对的人戴的就是黑帽子。P1P2：如果猜对的人戴的不是红帽子，那么他戴的就是黑帽子。Q1Q2：如果另一个人戴的不是

20、红帽子，那么他戴的就是黑帽子。推演步骤如下：设P1（1）P1（根据假设）；（2）R1（根据题设）（3）R1P1（合取构成）；（4）R1P1Q2（根据题设）（5）Q2（3）（4）分离）。这就是说，“另一个人戴黑帽子”这个判定是必然可以作出的，但是这与题设条件（即“另一个没有作出判定”）相矛盾，因此，P1为假，即P1为真，故可得：（6）P1；（7）P1P2（根据题设）；（8）P2（6）（7）分离）。这就是说，“猜对的人戴着黑帽子”是真的，所以猜对的人肯定的说：“我戴的是黑帽子”。返返 回回理发师的头谁来剃的答案分析理发师的头谁来剃的答案分析如果理发师的头由别人给他理，即理发师自如果理发师的头由别人

21、给他理，即理发师自己不给自己理发，那么按规定这位理发师的头应己不给自己理发，那么按规定这位理发师的头应该有自己理。如果理发师的头由他自己理，按规该有自己理。如果理发师的头由他自己理，按规定他只给那些不给自己理发的人理发，那么理发定他只给那些不给自己理发的人理发，那么理发师的头不能由他自己理，即理发师的头应该由别师的头不能由他自己理，即理发师的头应该由别人来理。这就产生了矛盾人来理。这就产生了矛盾:理发师的头既不能由理发师的头既不能由别人理，也不能由他自己理，所以这位理发师的别人理，也不能由他自己理，所以这位理发师的规定是一个悖论。规定是一个悖论。返返 回回 聪明的囚徒的答案分析聪明的囚徒的答案

22、分析聪明的囚徒所说的话，应使国王无论怎么处置他都聪明的囚徒所说的话，应使国王无论怎么处置他都带来矛盾，这句话就是带来矛盾，这句话就是“国王决定砍我的头国王决定砍我的头”。如果这。如果这和国王规定一致，是说真话，因而按国王决定的处死方和国王规定一致，是说真话，因而按国王决定的处死方法，讲真话应处以绞刑，这样就造成了国王的规定（砍法，讲真话应处以绞刑，这样就造成了国王的规定（砍头）同国王决定的处死方法相矛盾。如果这和国王的规头）同国王决定的处死方法相矛盾。如果这和国王的规定不一致，是说的假话，因而按照国王决定的处死方法，定不一致，是说的假话，因而按照国王决定的处死方法，讲假话予以砍头，这样又造成了

23、国王的规定（绞刑）同讲假话予以砍头，这样又造成了国王的规定（绞刑）同国王决定的处死方法相矛盾。国王处于进退维谷的处境，国王决定的处死方法相矛盾。国王处于进退维谷的处境，只好免于处死，将囚徒放掉。只好免于处死，将囚徒放掉。返返 回回考试日程表的答案分析考试日程表的答案分析如果将七次（或七天）考试作为七个顶如果将七次（或七天）考试作为七个顶点，做一个图点，做一个图G，若两个顶点对应的考试是，若两个顶点对应的考试是由不同的教员举行的，则这两个顶点连一由不同的教员举行的，则这两个顶点连一条边，实际上就是判定图条边，实际上就是判定图G是否有哈密尔顿是否有哈密尔顿通路问题。通路问题。返返 回回课课 后后 思思 考考请同学们课后通过查阅资料或上网搜索的方式，列举出离散数学的其他一些趣味应用问题！