离散数学

北科百科,一部属于贝壳人的百科全书
跳转至: 导航搜索
Broom icon.png 此条目可能需要进行清理,以符合北科百科的质量标准。
请尽量协助改善这篇条目,详细信息请参见本条目的讨论页。
离散数学
Discrete mathematics cover.jpg
高等教育出版社《离散数学》

课程类别
专业基础课 数自计必
课程编号 050401
开设学院 数理学院
计算机与通信工程学院
设课专业 电子信息科学类
信息管理与信息系统
数学与应用数学
学分
学分 学时 类别
8 72

离散数学》(Discrete Mathematics)是北京科技大学开设的一门数学类专业基础必修课,课程对象为电子信息科学类信息管理与信息系统数学与应用数学专业的本科生。开设该课程的学院有数理学院计算机与通信工程学院

广义

离散数学是数学的几个分支的总称,研究基于离散空间而不是连续的数学结构,是计算机科学及相关专业本科生的一门必修基础课。与光滑变化的实数不同,离散数学的研究对象——例如整数、图和数学逻辑中的命题[1]——不是光滑变化的,而是拥有不等、分立的值。[2]因此离散数学不包含微积分和数学分析等“连续数学”的内容。离散对象经常可以用整数来枚举。更一般地,离散数学被视为处理可数集合的数学分支。[3] (与整数子集基数相同的集合,包括有理数集但不包括整数集)。但是,“离散数学”不存在准确且普遍认可的定义。[4]实际上,离散数学经常被定义为不包含连续变化量及相关概念的数学,甚少被定义为包含什么内容的数学。

离散数学中的对象集合可以是有限或者是无限的。有限数学一词通常指代离散数学处理有限集合的那些部分,特别是在与商业相关的领域。

离散数学近几十年来因为它在计算机科学上的应用备受关注。由于运算对象是离散的,所以计算机科学的数学基础基本上也是离散的。我们可以说计算机科学的数学语言就是离散数学。人们会使用离散数学里面的槪念和表示方法,来研究和描述计算机科学下所有分支的对象和问题,如计算机运算、程序语言、密码学、自动定理证明和软件开发等。相反地,计算机的应用使离散数学的意念(就如运筹学)得以应用于日常生活当中。

虽然离散数学的主要研究对象是离散对象,但是连续数学的分析方法往往也可以采用。数论就是离散和连续数学的交叉学科。同样的,有限拓扑(对有限拓扑空间的研究)从字面上可看作离散化和拓扑的交集。

历史

历史上,离散数学涉及了各个领域的一系列挑战性问题。在图论中,大量研究的动机是企图证明四色定理。这些研究虽然从1852年开始,但是直至1976年四色理论才得到证明。(由Kenneth Appel和Wolfgang Hake,大量使用计算机辅助。[5]

在数理逻辑领域,David Hilbert于1900年提出的公开问题清单的第二个问题是要证明算术的公理是一致的。1931年,库尔特·哥德尔的第二不完备定理证明这是不可能的——至少算术本身不可能。David Hilbert的第十个问题是要确定某一整系数多项式丢番图方程是否有一个整数解。1970年,Yuri Matiyasevich证明这不可能做到。

第二次世界大战时盟军有破解纳粹德军密码的需要,带动了密码学和理论计算机科学的发展。英国的布莱切利园因而发明出第一部数位电子计算机——巨像计算机。与此同时,军事上的需求亦带动了运筹学的发展。直至冷战时期,密码学的地位依然重要,其後的几十年间更发展出如公开密钥加密等根本性的长进。随着1950年代关键路径方法的创立,运筹学则于商业和项目管理上愈趋重要。电讯工业的出现亦助长了离散数学,特别是图论和信息论上的发展。数理逻辑上敍述的形式验证至今已经成为安全关键系统的软件开发中必不可少的一环,自动定理证明的技术也因此而提高。

当今,理论计算机科学中最着名的开放问题之一是P/NP问题,P/NP问题中包含了复杂度类P与NP的关系。克雷数学研究所为此及其他6个千禧年大奖难题的第一个正确证明各悬赏100万美元。[6]

离散数学的主题

离散数学包含几个不同的主题,列举如下:

数理逻辑

逻辑是对有效推理和推理原则,及其连续性、合理性和完整性的研究。举一个简单的例子:在大多数逻辑系统中,皮尔士定律(((PQ)→P)→P)是正确的,而且可以简易地利用真值表得到证明。数学证明在数理逻辑中十分重要,而且在自动定理证明和软件开发(如形式验证)有广泛应用。

集合论

集合论是研究集合的数学分支。集合是指一定对象的总和,例如:{蓝色,白色,红色}是一个有限集合;所有素数组成一个无限集合。 偏序关系和拥有其他关系特征的集合在多个数学领域都有应用。

信息论

信息论涉及信息量化。与此密切相关的编码理论则用来设计高效可靠的数据传输和数据储存方法。

数论

数论关注普通数字,特别是整数的特性。数论在密码学和密码分析中有应用,特别是关于素数和素性测试方面。在解析数论中,也使用连续数学的理论。

组合数学

组合数学研究对象进行排列或组合的途径,包含组合设计(Combinatorial design), 计数组合(enumerative combinatorics), 计数、组合几何(combinatorial geometry), 组合拓扑(Combinatorial topology)等主题。图论是组合数学的重要部分,有很多实际应用。

在组合分析(analytic combinatorics)和代数图论(algebraic graph theory)中也使用连续数学的理论,而且代数图论还与群论有着紧密联系。

图论

图论是研究图和网络的数学分支,常被认为包含于组合数学中,但这一分支已经发展得足够庞大和有特点,并有自身领域所研究的问题,因此被视为一个独立的主题,在数学和科学的所有领域都有广泛的应用。[7]

抽象代数

代数结构既可以是离散的,也可以是连续的。离散代数包括逻辑门和编程中使用的逻辑代数、数据库中使用的关系代数、代数编码理论中重要的离散有限群、环和域、形式语言理论中的离散半群和幺半群。

理论计算机科学

理论计算机科学(Theoretical computer science)包含离散数学计算的领域,并特别注重图论和数理逻辑。理论计算机科学包括对计算数学结果的算法研究。可算性理论研究那些对象在原则上可被计算,和逻辑有密切联系。而计算复杂性理论|复杂性则研究计算耗费的时间,自动机理论和形式语言理论与复杂性紧密联系。计算几何应用算法解决几何问题,而计算机图像分析则是应用算法在计算机中再现图像。

拓扑学

虽然拓扑学是形式化和一般化物体“连续形变”的直觉概念的研究领域,其也包含很多离散主题,如拓扑变换时常取离散值,组合拓扑、拓扑图论、拓扑组合、计算拓扑、离散空间、有限拓扑空间等领域。

运筹学

运筹学的研究为解决一些商业上和其他范筹上实质的问题提供了方法。这些问题包括如何分配资源以使利润增至最高和如何为企划排程使风险减至最低等。运筹学的研究方向包括线性规划、最优化、等候理论、调度理论、网络理论,和一些正在增加的其他方面。运筹学的内容也会涉及一些连续主题,如连续时间马尔可夫过程、连续时间鞅、过程优化以及连续混合控制理论。

博弈论、决策论、效用理论、社会选择理论

博奕论用于处理的问题比较复杂,通常这些选择成功与否取决于其他人的选择,因此如何作最好出一个最好的选择比较复杂。连续对策甚至也是存在的,如微分博弈。博奕论的主题包括拍卖理论和公平分配博弈。

决策论是有关判定特定决策的价值、不确定性、合理性以及最终能够确定的最优决策的理论。

效用理论的研究内容是由各种商品和服务评估相对经济满足程度,或是评估各种商品和服务的希求程度。

社会选择理论是关于投票的理论。更近似于谜题的有关投票的问题是抽签问题(Bertrand's ballot theorem)。

离散化

离散化关注将连续模型或等式转化为离散形式的过程,通常是基于简化计算的目的。数值分析是离散化一个重要实例。

连续数学的离散近似

很多的连续数学概念都有离散数学的版本,例如:

  • 离散微积分
  • 离散概率分布
  • 离散傅里叶转换
  • 离散几何
  • 离散对数
  • 离散微分几何
  • 离散外微分
  • 离散莫尔斯理论
  • 差分方程
  • 离散动力系统。

在应用数学中,离散模型是连续模型的离散近似。在离散模型中,离散方程由数据确定。使用递推关系是这种建模方式的一般方法。

离散和连续混合数学

时标微积分是差分方程理论与微分方程理论的统一,应用在需要建立离散和连续同步数据模型的领域。

国内课程设置

  • 第一部分 数理逻辑
    • 第一章 命题逻辑的基本概念
      • 1.1 命题与联结词
      • 1.2 命题公式及其赋值
    • 第二章 命题逻辑等值演算
      • 2.1 等值式
      • 2.2 析取范式与合取范式
      • 2.3 联结词的完备集
      • 2.4 可满足性问题与消解法
    • 第三章 命题逻辑的推理理论
      • 3.1 推理的形式结构
      • 3.2 自然推理系统P
    • 第四章 一阶逻辑基本概念
      • 4.1 一阶逻辑命题符号化
      • 4.2 一阶逻辑公式及其解释
    • 第五章 一阶逻辑等值演算与推理
      • 5.1 一阶逻辑等值式与置换规则
      • 5.2 一阶逻辑前束范式
      • 5.3 一阶逻辑的推理理论
  • 第二部分 集合论
    • 第六章 集合代数
      • 6.1 集合的基本概念
      • 6.2 集合的运算
      • 6.3 有穷集的计数
      • 6.4 集合恒等式
    • 第七章 二元关系
      • 7.1 有序对与笛卡儿积
      • 7.2 二元关系
      • 7.3 关系的运算
      • 7.4 关系的性质
      • 7.5 关系的闭包
      • 7.6 等价关系与划分
      • 7.7 偏序关系
    • 第八章 函数
      • 8.1 函数的定义与性质
      • 8.2 函数的复合与反函数
      • 8.3 双射函数与集合的基数
      • 8.4 一个电话系统的描述实例
  • 第三部分 代数结构
    • 第九章 代数系统
      • 9.1 二元运算及其性质
      • 9.2 代数系统
      • 9.3 代数系统的同态与同构
    • 第十章 群与环
      • 10.1 群的定义及其性质
      • 10.2 子群与群的陪集分解
      • 10.3 循环群与置换群
      • 10.4 环与域
    • 第十一章 格与布尔代数
      • 11.1 格的定义与性质
      • 11.2 分配格、有补格与布尔代数
  • 第四部分 组合数学
    • 第十二章 基本的组合计数公式
      • 12.1 加法法则与乘法法则
      • 12.2 排列与组合
      • 12.3 二项式定理与组合恒等式
      • 12.4 多项式定理
    • 第十三章 递推方程与生成函数
      • 13.1 递推方程的定义及实例
      • 13.2 递推方程的公式解法
      • 13.3 递推方程的其他解法
      • 13.4 生成函数及其应用
      • 13.5 指数生成函数及其应用
      • 13.6 Cata1an数与Stir1ing数
  • 第五部分 图论
    • 第十四章 图的基本概念
      • 14.1 图
      • 14.2 通路与回路
      • 14.3 图的连通性
      • 14.4 图的矩阵表示
      • 14.5 图的运算
    • 第十五章 欧拉图与哈密顿图
      • 15.1 欧拉图
      • 15.2 哈密顿图
      • 15.3 最短路问题与货郎担问题
    • 第十六章 树
      • 16.1 无向树及其性质
      • 16.2 生成树
      • 16.3 根树及其应用
    • 第十七章 平面图
      • 17.1 平面图的基本概念
      • 17.2 欧拉公式
      • 17.3 平面图的判断
      • 17.4 平面图的对偶图
    • 第十八章 支配集、覆盖集、独立集、匹配与着色
      • 18.1 支配集、点覆盖集与点独立集
      • 18.2 边覆盖集与匹配
      • 18.3 二部图中的匹配
      • 18.4 点着色
      • 18.5 地图着色与平面图的点着色
      • 18.6 边着色
  • 第六部分 初等数论
    • 第十九章 初等数论
      • 19.1 素数
      • 19.2 最大公约数与最小公倍数
      • 19.3 同余
      • 19.4 一次同余方程
      • 19.5 欧拉定理和费马小定理
      • 19.6 初等数论在计算机科学技术中的几个应用

参考文献

  1. Richard Johnsonbaugh, Discrete Mathematics, Prentice Hall, 2008.
  2. Eric W. Weisstein, Discrete mathematics, MathWorld.
  3. Norman L. Biggs, Discrete mathematics, Oxford University Press, 2002.
  4. Brian Hopkins, Resources for Teaching Discrete Mathematics, Mathematical Association of America, 2008.
  5. Wilson, Robin (2002), Four Colors Suffice, London: Penguin Books, ISBN 0-691-11533-8
  6. 千禧年大奖难题(2000年5月24日)
  7. Graphs on Surfaces, Bojan Mohar and Carsten Thomassen, John Hopkins University press, 2001

外部链接