離散數學

出自 MBA智库百科(https://wiki.mbalib.com/)

離散數學（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、離散和連續混合數學：時標微積分是差分方程理論與微分方程理論的統一，應用在需要建立離散和連續同步數據模型的領域。

• 徐晉著,《大數據經濟學》,上海交通大學出版社,2014.06,第45頁