离散数学（Discrete Mathematics）
目录 |
离散数学是研究离散量的结构及其相互关系的数学学科，离散数学是数学几个分支的总称，研究基于离散空间而不是连续的数学结构。更一般地，离散数学被视为处理可数集合（与整数子集基数相同的集合，包括有理数集但不包括整数集）的数学分支。与光滑变化的实数不同，离散数学的研究对象———例如整数、图和数学逻辑中的命题———不是光滑变化的，而是拥有不等、分立的值。离散数学中的对象集合可以是有限或者是无限的。特别是，有限数学一词通常指代离散数学处理有限集合的那些部分，特别是在与商业相关的领域。包括基本的概率论、线性规划、矩阵和行列式的理论。
离散数学的应用遍及现代科学技术的诸多领域，它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学等必不可少的科研基础。
历史上，离散数学涉及各个领域的一系列挑战性问题。在图论中，大量研究的动机是企图证明四色定理。这些研究虽然从1852年开始，但是直至1976年四色理论才得到证明，是由肯尼斯·阿佩尔和沃尔夫冈·哈肯大量使用计算机辅助来完成的。
在逻辑领域，大卫·希尔伯特于1900年提出的公开问题清单的第二个问题是要证明算术公理是一致的。1931年，库尔特·哥德尔的第二不完备定理证明这是不可能的———至少算术本身不可能。大卫·希尔伯特的第十个问题是要确定某一整系数多项式丢番图方程是否有一个整数解。1970年，尤里·马季亚谢维奇证明这不可能做到。
第二次世界大战时盟军基于破解纳粹德军密码的需要，带动了密码学和理论计算机科学的发展。英国的布莱切利园因而发明出第一部数字电子计算器———巨像计算机。与此同时，军事上的需求亦带动了运筹学的发展。直至冷战时期，密码学的地位依然重要，其后的几十年间更发展出如公开密钥加密等根本性的长进。随着20世纪50年代关键路径方法的创立，运筹学则于商业和项目管理上愈趋重要。电讯工业的出现亦助长了离散数学，特别是图论和信息论上的发展。数理逻辑上叙述的形式验证至今已经成为安全关键系统的软件开发中必不可少的一环，自动定理证明的技术也因此而提高。
1990年，中科院应用数学所研究员堵丁柱与美籍华人黄光明合作，证明了有关网络路线最短的一个猜想，在美国离散数学界引起轰动，被列为1989—1990年度美国离散数学界与理论计算机科学界的两项重大成果之一。此猜想持续22年，是贝尔实验室一直关注的难题，它在供电线路设计、计算机电路设计中都有应用，无怪乎解决后引起强烈反响。
计算机只能处理有限数和有限个数，无论什么问题都必须离散化后才能在计算机上进行数值计算，所以离散数学显得日益重要。离散数学包括传统的数理逻辑、集合论、信息论、数论、组合数学、图论、抽象代数、理论计算机科学、拓扑学、运筹学、博弈论、关系理论等，列举如下：
1、数理逻辑：数理逻辑是对有效推理和推理原则，及其连续性、合理性和完整性的研究。数学证明在数理逻辑中十分重要，而且在自动定理证明和软件开发（如形式验证）中有广泛应用。人的思维形式结构包括概念、判断和推理之间的结构与联系。其中概念是思维的基本单位；通过概念对事物描述是否具有某种属性进行肯定或否定的回答，这个过程就是判断；由一个或几个判断推出另一个判断的思维形式就是推理。研究推理的方法很多，用引进一套符号体系、简洁地表示出各种推理逻辑关系的数学方法研究就称为数理逻辑。
2、集合论：集合论是研究集合的数学分支。集合是指一定对象的总和，例如：｛蓝色，白色，红色｝是一个有限集合；所有素数组成一个无限集合。偏序关系和拥有其他关系特征的集合在多个数学领域都有应用。集合不仅可以用来表示数及其运算，还可以用于非数值信息的表示和处理（如数据的增加、删除、修改、排序及数据间关系的描述等）。集合论在信息科学的编译原理、开关理论、信息检索、形式语言、数据库与知识库、专家系统、CAD、CAI、人工智能等各个领域中有十分广泛的应用。
3、信息论：信息论涉及信息量化。与此密切相关的编码理论则用来设计高效可靠的数据传输和数据储存方法。编码技术为信息论领域提供了一种表示语句和信息处理程序的途径。
4、数论：数论关注普通数字，特别是整数的特性。数论在密码学和密码分
析中有应用，特别是关于素数和素性测试方面。在解析数论中，也使用连续数学的理论。
5、组合数学：组合数学研究对象进行排列或组合的途径，包含组合设计、计数组合、计数、组合几何、组合拓扑等主题。图论是组合数学的重要部分，有很多实际应用。在组合分析和代数图论中也使用连续数学的理论，而且代数图论还与群论有着紧密联系。
6、图论：图论是研究图和网络的数学分支，常被认为包含于组合数学中，但这一分支已经发展得足够庞大和有特点，并有自身领域所研究的问题，因此被视为一个独立的主题。
7、抽象代数：代数结构既可以是离散的，也可以是连续的。离散代数包括逻辑门和编程中使用的逻辑代数、数据库中使用的关系代数、代数编码理论中重要的离散有限群、环和域、形式语言理论中的离散半群和幺半群。代数的概念与方法是研究计算机科学和工程的重要数学工具。众所周知，在许多实际问题的研究中都离不开数学模型，而构造数学模型就要用到某种数学结构。因此抽象代数的基本概念、方法和结果已成为计算机科学与工程领域的基本工具。
8、理论计算机科学：离散数学充分描述了计算机科学离散性的特点。理论计算机科学包含离散数学计算的领域，并特别注重图论和数理逻辑。理论计算机科学包括对计算数学结果的算法研究。可算性理论研究哪些对象在原则上可被计算，和逻辑有密切联系。而复杂性则研究计算耗费的时间，自动机理论和形式语言理论与复杂性紧密联系。计算几何应用算法解决几何问题，而计算机图像分析则是应用算法在计算机中再现图像。
9、拓扑学：虽然拓扑学是形式化和一般化物体“连续形变”的直觉概念的研究领域，其也包含很多离散主题，如拓扑变换时常取离散值，组合拓扑、拓扑图论、拓扑组合、计算拓扑、离散空间、有限拓扑空间等领域。
10运筹学：运筹学的研究为解决一些商业上和其他范畴上实质的问题提供了方法。这些问题包括如何分配资源，以使利润增至最高以及如何为企划排程使风险减至最低等。运筹学的研究方向包括线性规划、最优化、等候理论、调度理论、网络理论，以及一些正在增加的其他方面。
11、博弈论、决策论、效用理论、社会选择理论：博弈论用于处理的问题比较复杂，通常这些选择成功与否取决于其他人的选择，因此如何作最好出一个最好的选择比较复杂。连续对策甚至也是存在的，如微分博弈。博弈论的主题包括拍卖理论和公平分配博弈。决策论是有关判定特定决策的价值、不确定性、合理性以及最终能够确定的最优决策的理论。效用理论的研究内容是由各种商品和服务评估相对经济满足程度，或是评估各种商品和服务的需求程度。
12、关系理论：关系是一种被广泛使用的概念，如日常生活中的父子关系、朋友关系、债主与债户关系，自然科学中的函数关系、相似关系、对称关系。我们介绍集合时，并不关心集合的成员之间有什么关系。而事实上客观世界是由各种各样的事物组成的，事物之间存在着一定的相互作用、相互联系和相互制约的关系。集合的元素并不是乌合之众。因此我们既有必要研究集合元素的个性、共性，更有必要研究元素之间的关系。
13、离散化：离散化关注将连续模型或等式转化为离散形式的过程，通常是基于简化计算的目的。数值分析是离散化一个重要实例。
14、连续数学的离散近似：在应用数学中，离散模型是连续模型的离散近似。在离散模型中，离散方程由数据确定。使用递推关系是这种建模方式的一般方法。
15、离散和连续混合数学：时标微积分是差分方程理论与微分方程理论的统一，应用在需要建立离散和连续同步数据模型的领域。