00离散数学概述 1.pptVIP

Discrete Mathematics 主讲 刘遵雄 课程简介 离散数学，是现代数学的一个重要分支，计算机科学与技术一级学科的核心课程，是整个计算机学科的专业基础课。它是由于计算机理论研究和应用的发展而形成的学科 离散数学是以研究离散量的结构和相互间的关系为主要目标，其研究对象一般地是有限个或可数个元素，因此它充分描述了计算机科学离散性的特点。 离散数学是随着计算机科学的发展而逐步建立的，它形成于七十年代初期，是一门新兴的工具性学科。 通过本课程的学习，使学生具有现代数学的观点和方法，为提高专业理论水平打下坚实的基础，同时培养学生抽象思维和综合分析的能力 离散、连续的区别（引用清华大学马正华教授的说法） 南唐，李煜 问君能有几多愁，恰似一江春水向东流。 剪不断，理还乱，是离愁。 元代 马致远 枯藤 老树 昏鸦 小桥 流水 人家 古道 西风 瘦马 …… 与离散数学对应的学科连续数学，研究的是连续量，例如（1-100）之间有无数个研究对象 后续课程 为什么要学离散数学 计算机求解的基本模式是：实际问题 ? 数学建模 ? 算法设计 ? 编程实现 离散数学为数学建模打下知识基础、为算法设计提供具体指导 离散数学结构实际上就是通用的抽象的模式的集合。告诉你各种模式的本质特征和它们之间的关系，以及选用它们的策略；告诉你哪些问题是可解的，哪些是当前在图灵机模型上无（最优）解的，哪些是可以得到近似/较优解的。 简而言之，离散数学的作用就在于训练运用离散结构作为问题的抽象模型、构造算法、解决问题的能力。 离散数学的发展 18世纪以前, 数学基本上是研究离散对象的数量和空间关系的科学。 之后,因天文学,物理学的发展,如行星轨道,牛顿三大力学定律等研究,极大地推动了连续数学(以微积分,数学物理方程, 实、复变函数论为代表)的发展。离散对象的研究则处于停滞状态。 20世纪30年代, 图灵提出计算机的理论模型——图灵机。 这种模型早于实际制造计算机十多年,现实的计算机的计算能力, 本质上和图灵机的计算能力一样。 由于在计算机内,机器字长总是有限的, 它代表离散的数或其它离散对象，因此随着计算机科学和技术的迅猛发展,离散数学就显得重要。 离散数学的应用举例 关系型数据库的设计（关系代数） 表达式解析（树） 优化编译器的构造（闭包） 编译技术、程序设计语言（代数结构） Lisp和Prolog、人工智能、自动推理、机器证明（数理逻辑） 网络路由算法（图论） 游戏中的人工智能算法（图论、树、博弈论） 专家系统（集合论、数理逻辑—知识和推理规则的计算机表达） 软件工程—团队开发—时间和分工的优化（图论—网络、划分） (各种)算法的构造、正确性的证明和效率的评估（离散数学的各分支） 学习要求与成绩评定 教材 左孝凌，李为鉴，刘永才编著．离散数学．上海：上海科学技术文献出版社,1982 [美]Kenneth H.Rosen著．袁崇义，屈婉玲，王捍贫，刘田译．离散数学及其应用．北京：机械工业出版社，2002 数理逻辑简介 逻辑学是一门研究思维形式及思维规律的科学，也就是研究推理过程的规律的科学。逻辑规律就是客观事物在人的主观意识中的反映。 逻辑学分为辩证逻辑与形式逻辑两种，辩证逻辑是以辩证法认识论的世界观为基础的逻辑学，形式逻辑主要是对思维的形式结构和规律进行研究的类似于语法的一门工具性学科。 思维的形式结构包括了概念、判断和推理之间的结构和联系，其中概念是思维的基本单位，通过概念对事物是否具有某种属性进行肯定或否定的回答，这就是判断；由一个或几个判断推出另一判断的思维形式，就是推理。 用数学方法来研究推理的规律称为数理逻辑。这里所指的数学方法，就是引进一套符号体系的方法，在其中表达和研究推理的规律。 数理逻辑简介 通常认为数理逻辑是由莱布尼兹(Leibniz)创立的。 数理逻辑的内容包括：证明论、模型论、递归论、公理化集合论。 数理逻辑的应用 在形式语义学、程序设计方法学和软件工程领域。 在逻辑程序设计方面。 在数据库理论方面。 在程序自动生成、自动转换等的理论和技术研究中。 在形式语言理论、自动机理论、可计算理论、计算复杂性理论等方面。 在人工智能方面。 数理逻辑简介 一个土耳其商人想找一个十分聪明的助手协助他经商，有两人前来应聘，这个商人为了试试哪个更聪明些，就把两个人带进一间漆黑的屋子里，他打开灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的，现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在自己头上，在我开灯后，请你们尽快说出自己头上戴的帽子是什么颜色的。”说完后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了