离散数学

像这样的是离散数学的研究对象之一,它们拥有有趣的数学性质,可以作为现实世界用来解决问题的模型,而且还在计算机算法开发中有着举足轻重的作用。

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

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

隨著電腦科學的飛速發展,離散數學的重要性則日益彰顯。它為許多資訊科學課程提供了數學基礎,包括資料結構、演算法、資料庫理論、形式語言與作業系統等。如果沒有離散數學的相關數學基礎,學生在學習上述課程中,便會遇到較多的困難。此外,離散數學也包含了解決作業研究、化學、工程學、生物學等眾多領域的數學背景。由於運算對象是離散的,所以電腦科學的數學基礎基本上也是離散的。我們可以說電腦科學的數學語言就是離散數學。人們會使用離散數學裡面的槪念和表示方法,來研究和描述電腦科學下所有分支的對象和問題,如電腦運算程式語言密碼學自動定理証明軟件開發等。相反地,计算机的應用使離散數學的概念得以應用於日常生活當中(如運籌學)。

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

历史

图论领域中,大量研究的动机是企图证明在对所有的地图,譬如说此图,可以用不多于四种颜色上色,而且没有任意两个相接的区域会是同色。1976年,肯尼斯·阿佩尔沃尔夫冈·哈肯最终证明了四色定理。[5]

历史上,离散数学涉及了各个领域的一系列挑战性问题。在图论中,許多的研究动机是來自於嘗試证明四色定理。这些研究虽然从1852年开始,但是直至1976年四色定理才得到证明,是由肯尼斯·阿佩尔(Kenneth Appel)和沃尔夫冈·哈肯(Wolfgang Haken)藉由大量计算机辅助而完成的。[5]

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

第二次世界大戰盟軍破解納粹德軍密碼的需要,帶動了密碼學理論計算機科學的發展。英國的布萊切利園因而發明出第一部數位電子計算機——巨像電腦。與此同時,軍事上的需求亦帶動了運籌學的發展。直至冷戰時期,密碼學的地位依然重要,其後的幾十年間更發展出如公開密鑰加密等根本性的長進。隨著1950年代關鍵路徑方法的創立,運籌學則於商業項目管理上愈趨重要。電訊工業的出現亦助長了離散數學,特別是圖論信息論上的發展。數理邏輯敍述形式驗證至今已經成為安全關鍵系統軟件開發中必不可少的一環,自動定理證明的技術也因此而提高。

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