離散數學(英語:Discrete mathematics)是數學的幾個分支的總稱,研究基於離散空間而不是連續的數學結構。與連續變化的實數不同,離散數學的研究對象——例如整數、圖和數學邏輯中的命題[1]——不是連續變化的,而是擁有不等、分立的值。[2]因此離散數學不包含微積分和分析等「連續數學」的內容。
離散對象經常可以用整數來枚舉。更一般地,離散數學被視為處理可數集合(與整數子集基數相同的集合,包括有理數集但不包括實數集)的數學分支。[3]但是,「離散數學」不存在準確且普遍認可的定義。[4]實際上,離散數學經常被定義為不包含連續變化量及相關概念的數學,甚少被定義為包含什麼內容的數學。
離散數學中的對象集合可以是有限或者是無限的。有限數學一詞通常指代離散數學處理有限集合的那些部分,特別是在與商業相關的領域。
隨著電腦科學的飛速發展,離散數學的重要性則日益彰顯。它為許多資訊科學課程提供了數學基礎,包括數據結構、演算法、數據庫理論、形式語言與作業系統等。如果沒有離散數學的相關數學基礎,學生在學習上述課程中,便會遇到較多的困難。此外,離散數學也包含了解決作業研究、化學、工程學、生物學等眾多領域的數學背景。由於運算對象是離散的,所以電腦科學的數學基礎基本上也是離散的。我們可以說電腦科學的數學語言就是離散數學。人們會使用離散數學裡面的槪念和表示方法,來研究和描述電腦科學下所有分支的對象和問題,如電腦運算、編程語言、密碼學、自動定理証明和軟件開發等。相反地,計算機的應用使離散數學的概念得以應用於日常生活當中(如運籌學)。
雖然離散數學的主要研究對象是離散對象,但是連續數學的分析方法往往也可以採用。數論就是離散和連續數學的交叉學科。同樣的,有限拓撲(對有限拓撲空間的研究)從字面上可看作離散化和拓撲的交集。
歷史
歷史上,離散數學涉及了各個領域的一系列挑戰性問題。在圖論中,許多的研究動機是來自於嘗試證明四色定理。這些研究雖然從1852年開始,但是直至1976年四色定理才得到證明,是由肯尼斯·阿佩爾(Kenneth Appel)和沃爾夫岡·哈肯(Wolfgang Haken)藉由大量計算機輔助而完成的。[5]
在邏輯領域,大衛·希爾伯特(David Hilbert)於1900年提出的公開問題清單的第二個問題是要證明算術的公理是一致的。1931年,庫爾特·哥德爾的第二不完備定理證明這是不可能的——至少算術本身不可能。大衛·希爾伯特的第十個問題是要確定某一整係數多項式丟番圖方程是否有一個整數解。1970年,尤里·馬季亞謝維奇證明這不可能做到。
第二次世界大戰時盟軍有破解納粹德軍密碼的需要,帶動了密碼學和理論計算機科學的發展。英國的布萊切利園因而發明出第一部數位電子計算機——巨像電腦。與此同時,軍事上的需求亦帶動了運籌學的發展。直至冷戰時期,密碼學的地位依然重要,其後的幾十年間更發展出如公開密鑰加密等根本性的長進。隨著1950年代關鍵路徑方法的創立,運籌學則於商業和項目管理上愈趨重要。電訊工業的出現亦助長了離散數學,特別是圖論和信息論上的發展。數理邏輯上敍述的形式驗證至今已經成為安全關鍵系統的軟件開發中必不可少的一環,自動定理證明的技術也因此而提高。
當今,理論計算機科學中最著名的開放問題之一是P/NP問題,P/NP問題中包含了複雜度類P與NP的關係。克雷數學研究所為此及其他6個千禧年大獎難題的第一個正確證明各懸賞100萬美元。[6]
主題
離散數學包含幾個不同的主題,列舉如下:
邏輯是對有效推理和推理原則,及其連續性、合理性和完整性的研究。舉一個簡單的例子:在大多數邏輯系統中,皮爾士定律(((P→Q)→P)→P)是正確的,而且可以簡易地利用真值表得到證明。數學證明在數理邏輯中十分重要,而且在自動定理證明和軟件開發(如形式驗證)有廣泛應用。
集合論是研究集合的數學分支。集合是指一定對象的總和,例如:{藍色,白色,紅色}是一個有限集合;所有素數組成一個無限集合。 偏序關係和擁有其他關係特徵的集合在多個數學領域都有應用。
數論關注普通數字,特別是整數的特性。數論在密碼學和密碼分析中有應用,特別是關於素數和素性測試方面。在解析數論中,也使用連續數學的理論。
組合數學研究對象進行排列或組合的途徑,包含組合設計(Combinatorial design)、計數組合(enumerative combinatorics)、計數、組合幾何(combinatorial geometry)、組合拓撲(Combinatorial topology)等主題。圖論是組合數學的重要部分,有很多實際應用。
在組合分析(analytic combinatorics)和代數圖論(algebraic graph theory)中也使用連續數學的理論,而且代數圖論還與群論有着緊密聯繫。
圖論是研究圖和網絡的數學分支,常被認為包含於組合數學中,但這一分支已經發展得足夠龐大和有特點,並有自身領域所研究的問題,因此被視為一個獨立的主題,在數學和科學的所有領域都有廣泛的應用。例如:有名的七橋問題。[7]
代數結構既可以是離散的,也可以是連續的。離散代數包括邏輯門和編程中使用的邏輯代數、數據庫中使用的關係代數、代數編碼理論中重要的離散有限群、環和域、形式語言理論中的離散半群和幺半群。
離散數學充分描述了計算機科學離散性的特點。
理論計算機科學(Theoretical computer science)包含離散數學計算的領域,並特別注重圖論和數理邏輯。理論計算機科學包括對計算數學結果的算法研究。可算性理論研究那些對象在原則上可被計算,和邏輯有密切聯繫。而複雜性則研究計算耗費的時間,自動機理論和形式語言理論與複雜性緊密聯繫。計算幾何應用算法解決幾何問題,而計算機圖像分析則是應用算法在計算機中再現圖像。
雖然拓撲學是形式化和一般化物體「連續形變」的直覺概念的研究領域,其也包含很多離散主題,如拓撲變換時常取離散值,組合拓撲、拓撲圖論、拓撲組合、計算拓撲、離散空間、有限拓撲空間等領域。
運籌學的研究為解決一些商業上和其他範籌上實質的問題提供方法。這些問題包括如何分配資源以使利潤增至最高和如何為企劃排程使風險減至最低等。運籌學的研究方向包括線性規劃、最優化、等候理論、調度理論、網絡理論,和一些正在增加的其他方面。運籌學的內容也會涉及一些連續主題,如連續時間馬爾可夫過程、連續時間鞅、過程優化以及連續混合控制理論。
合作 | 背叛 | |
合作 | -1, -1 | -10, 0 |
背叛 | 0, -10 | -5, -5 |
囚徒困境的支付矩陣 |
博弈論用於處理的問題比較複雜,通常這些選擇成功與否取決於其他人的選擇,因此如何作最好出一個最好的選擇比較複雜。連續對策甚至也是存在的,如微分博弈。博弈論的主題包括拍賣理論和公平分配博弈。
決策論是有關判定特定決策的價值、不確定性、合理性以及最終能夠確定的最優決策的理論。
效用理論的研究內容是由各種商品和服務評估相對經濟滿足程度,或是評估各種商品和服務的希求程度。
社會選擇理論是關於投票的理論。更近似於謎題的有關投票的問題是抽籤問題(Bertrand's ballot theorem)。
離散化關注將連續模型或等式轉化為離散形式的過程,通常是基於簡化計算的目的。數值分析是離散化一個重要實例。
很多的連續數學概念都有離散數學的版本,例如:
參考文獻
延伸閱讀
外部連結
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.