離散數學
離散數學（英語：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）。
離散化
[編輯]離散化關注將連續模型或等式轉化為離散形式的過程，通常是基於簡化計算的目的。數值分析是離散化一個重要實例。
連續數學的離散近似
[編輯]
很多的連續數學概念都有離散數學的版本，例如:
在應用數學中，離散模型是連續模型的離散近似。在離散模型中，離散方程由數據確定。使用遞歸關係是這種建模方式的一般方法。
離散和連續混合數學
[編輯]時標微積分是差分方程理論與微分方程理論的統一，應用在需要建立離散和連續同步數據模型的領域。
參考文獻
[編輯]- ^ Richard Johnsonbaugh, Discrete Mathematics, Prentice Hall, 2008.
- ^ Weisstein, Eric W. (編). Discrete mathematics. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英語）.
- ^ Norman L. Biggs, Discrete mathematics, Oxford University Press, 2002.
- ^ Brian Hopkins, Resources for Teaching Discrete Mathematics, Mathematical Association of America, 2008.
- ^ 5.0 5.1 Wilson, Robin, Four Colors Suffice, London: Penguin Books, 2002, ISBN 0-691-11533-8
- ^ 千禧年大奖难题. 2000-05-24 [2008-01-12]. （原始內容存檔於2008-01-08）.
- ^ Graphs on Surfaces （頁面存檔備份，存於互聯網檔案館）, Bojan Mohar and Carsten Thomassen, Johns Hopkins University press, 2001
延伸閱讀
[編輯]
- Norman L. Biggs, Discrete Mathematics 2nd ed. Oxford University Press. ISBN 978-0-19-850717-8. Companion Web site: includes questions together with solutions.
- Ronald Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics
- Richard Johnsonbaugh, Discrete Mathematics 6th ed. Macmillan. ISBN 978-0-13-045803-2. Companion Web site: [1] （頁面存檔備份，存於互聯網檔案館）
- Reinhard Klette and Azriel Rosenfeld. Digital Geometry. Morgan Kaufmann. 2004 [2020-05-25]. ISBN 1-55860-861-3. （原始內容存檔於2021-02-10）. Also on (digital) topology, graph theory, combinatorics, axiomatic systems.
- Donald E. Knuth, The Art of Computer Programming
- Kenneth H. Rosen, Handbook of Discrete and Combinatorial Mathematics CRC Press. ISBN 978-0-8493-0149-0.
- Kenneth H. Rosen, Discrete Mathematics and Its Applications 6th ed. McGraw Hill. ISBN 978-0-07-288008-3. Companion Web site: http://highered.mcgraw-hill.com/sites/0072880082/information_center_view0/ （頁面存檔備份，存於互聯網檔案館）
- Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction 5th ed. Addison Wesley. ISBN 978-0-201-72634-3
- C.L. Liu, Elements of Discrete Math
- Neville Dean, Essence of Discrete Mathematics Prentice Hall. ISBN 978-0-13-345943-2. Not as in depth as above texts, but a gentle intro.
- Mathematics Archives, Discrete Mathematics links to syllabi, tutorials, programs, etc. http://archives.math.utk.edu/topics/discreteMath.html （頁面存檔備份，存於互聯網檔案館）
- Jiří Matoušek & Jaroslav Nešetřil, Invitation to Discrete Mathematics, OUP.
外部連結
[編輯]- （中文）數學領域：離散數學 (Episte Math) （頁面存檔備份，存於互聯網檔案館）
