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