1、陈培芝离 散 数 学 13599901829 课程简介q 离散数学，是现代数学的一个重要分支，是整个计算机学科的专业基础课。q 离散数学是以研究 离散量 的结构和相互间的关系为主要目标，其研究对象一般地是有限个或可数个元素，因此它充分描述了计算机科学离散性的特点。q 离散数学是随着计算机科学的发展而逐步建立的，它形成于七十年代初期，是一门新兴的工具性学科。后续课程数据结构 操作系统编译理论 算法分析系统结构 容错判断机器定理证明 数据库原理人工智能 离散数学的发展q 18世纪以前 , 数学基本上是研究离散对象的数量和空间关系的科学。q 之后 ,因天文学 ,物理学的发展 ,如行星轨道 ,牛顿三大
2、力学定律等研究 ,极大地推动了连续数学 (以微积分 ,数学物理方程 , 实、复变函数论为代表 )的发展。q 离散对象的研究则处于停滞状态。q 20世纪 30年代 , 图灵提出计算机的理论模型 图灵机 。q 这种模型早于实际制造计算机十多年 ,现实的计算机的计算能力 , 本质上和图灵机的计算能力一样。q 由于在计算机内 ,机器字长总是有限的 , 它代表离散的数或其它离散对象，因此随着计算机科学和技术的迅猛发展 ,离散数学就显得重要。离散数学的内容q 数理逻辑 ： “证明 ”在计算科学的某些领域至关重要，构造一个证明和写一个程序的思维过程在本质上是一样的。q 组合分析 ：解决问题的一个重要方面就是
3、计数或枚举对象。q 离散结构 ：用来表示离散对象以及它们之间关系的抽象数学结构，包括：集合、排列、关系、树、图。q 算法化思维 ：许多问题都可以通过构造一个可以被程序实现的算法来解决。它的三个步骤是： 构造 （选择合适的离散模型和操作步骤）、 验证 （算法的正确性）、 评估 （时间和空间的复杂性）。q 应用和建模 ：在可以想到的任何研究领域都有离散数学的应用。计算科学、化学、植物学、动物学、语言学、地理、经济学等，构造离散模型都是极其有用的解决问题的方法。 教学内容集合论数理逻辑 图论代数结构为什么要学离散数学 q 计算机求解的基本模式是：实际问题 数学建模 算法设计 编程实现 q 离散数学为
4、数学建模打下知识基础、为算法设计提供具体指导q 离散数学结构实际上就是通用的抽象的模式的集合。告诉你各种模式的本质特征和它们之间的关系，以及选用它们的策略；告诉你哪些问题是可解的，哪些是当前在图灵机模型上无（最优）解的，哪些是可以得到近似 /较优解的。q 简而言之，离散数学的作用就在于训练运用离散结构作为问题的抽象模型、构造算法、解决问题的能力。离散数学的应用举例q 关系型数据库的设计（关系代数）q 表达式解析（树）q 优化编译器的构造（闭包）q 编译技术、程序设计语言（代数结构）q Lisp和 Prolog、人工智能、自动推理、机器证明（数理逻辑）q 网络路由算法（图论）q 游戏中的人工智能算法（图论、树、博弈论）q 专家系统（集合论、数理逻辑 知识和推理规则的计算机表达）q 软件工程 团队开发 时间和分工的优化（图论 网络、划分）q (各种 )算法的构造、正确性的证明和效率的评估（离散数学的各分支） 学习要求q 本课程特点定义 +定理 +例题q 多做习题，完成作业想的清楚，说的明白，写的工整教材 q 屈婉玲 ，耿素云编著 离散数学 (第二版 ) 北京：高等教育出版社 ,2004q 屈婉玲， 耿素云编著 离散数学学习指导与习题解析（第 2版） 北京：高等教育出版社 ,2005q http:/
