离散数学概论

随着大数据时代的到来，信息呈现多元化和差异化，有价值的数据提取、挖掘和价值关联日益受到重视。从工业革命时代以来，以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。

离散数学（discrete mathematics）是研究离散量的结构及其相互关系的数学学科，离散数学是数学几个分支的总称，研究基于离散空间而不是连续的数学结构。更一般地，离散数学被视为处理可数集合（与整数子集基数相同的集合，包括有理数集但不包括整数集）的数学分支。与光滑变化的实数不同，离散数学的研究对象——例如整数、图和数学逻辑中的命题——不是光滑变化的，而是拥有不等、分立的值。

离散数学中的对象集合可以是有限或者是无限的。特别是，有限数学一词通常指代离散数学处理有限集合的那些部分，特别是在与商业相关的领域。包括基本的概率论、线性规划、矩阵和行列式的理论。

离散数学的应用遍及现代科学技术的诸多领域，它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学等必不可少的科研基础。

历史上，离散数学涉及各个领域的一系列挑战性问题。在图论中，大量研究的动机是企图证明四色定理。这些研究虽然从1852年开始，但是直至1976年四色理论才得到证明，是由肯尼斯·阿佩尔（Kenneth Appel）和沃尔夫冈·哈肯（Wolfgang Haken）大量使用计算机辅助来完成的。

在逻辑领域，大卫·希尔伯特（David Hilbert）于1900年提出的公开问题清单的第二个问题是要证明算术公理是一致的。1931年，库尔特·哥德尔的第二不完备定理证明这是不可能的——至少算术本身不可能。大卫·希尔伯特的第十个问题是要确定某一整系数多项式丢番图方程是否有一个整数解。1970年，尤里·马季亚谢维奇证明这不可能做到。

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

1990年，中科院应用数学所研究员堵丁柱与美籍华人黄光明合作，证明了有关网络路线最短的一个猜想（Pollak－Gilbert猜想，1968年提出），在美国离散数学界引起轰动，被列为1989—1990年度美国离散数学界与理论计算机科学界的两项重大成果之一。此猜想持续22年，是贝尔实验室一直关注的难题，它在供电线路设计、计算机电路设计中都有应用，无怪乎解决后引起强烈反响。

离散数学在国外早已成为十分重要的学科，如IBM，AT&T都有全世界最强的离散数学研究中心。美国政府成立了离散数学及理论计算机科学中心DIMACS（与Princeton大学、Rutgers大学、AT&T联合创办的，设在Rutgers大学），该中心已是离散数学及理论计算机科学的重要研究阵地。Thomson Science公司创刊的一份电子刊物《离散数学和理论计算机科学》即是一个很好的说明。它的内容涉及离散数学和计算机科学的众多方面。Microsoft的比尔·盖茨近来也在提倡和支持计算机科学的基础研究。例如，Bell实验室的有关线性规划算法的实现，以及有关计算机网络的算法，由于有明显的商业价值，显然是没有对外公开的。

总的来说，离散数学不仅在基础数学研究中具有极其重要的地位，在其他学科中同样有着重要的应用。微积分和近代数学的发展为近代工业革命奠定了基础，离散数学的发展则奠定了计算机与信息科学革命的基础。离散数学在当代经济领域更是有着极其广泛的应用，在企业管理、交通规划、战争指挥、金融分析等方面都有重要应用。