離散數學

離散的數學是對可以視為“離散”的數學結構的研究（以與離散變量相似，具有與自然數的集合相似），而不是“連續”（類似於連續函數）。在離散數學中研究的對象包括邏輯中的整數，圖形和語句。相比之下，離散數學排除了“連續數學”中的主題，例如實數，微積分或歐幾里得幾何。整數通常可以列舉離散的對象；更正式的是，離散數學已被描述為數學的分支，該分支處理了可數集（有限集或具有與自然數相同的基數）。但是，“離散數學”一詞沒有確切的定義。

在離散數學中研究的對象集可以是有限的或無限的。有限數學一詞有時應用於涉及有限集的離散數學領域的一部分，尤其是與業務相關的領域。

在20世紀下半葉，離散數學的研究有所增加，部分原因是數字計算機的開發，這些計算機以“離散”的步驟運行，並將數據存儲在“離散”位中。離散數學的概念和符號可用於研究和描述計算機科學分支中的對象和問題，例如計算機算法，編程語言，密碼學，自動定理證明和軟件開發。相反，計算機實現在應用於離散數學到現實世界問題的想法方面具有重要意義。

儘管離散數學中的研究的主要對像是離散對象，但通常也採用了來自“連續”數學的分析方法。

在大學課程中，最初作為計算機科學支持課程出現了離散數學；當時它的內容有些偶然。此後，該課程與ACM和MAA的努力一起發展為一門課程，該課程基本上旨在發展一年級學生的數學成熟度；因此，如今，這也是一些大學中數學專業的先決條件。一些高中的離散數學教科書也出現了。在這個級別上，離散的數學有時被視為預備課程，例如在這方面的預處理。

富爾克森獎因離散數學的傑出論文而頒發。

離散數學的主題

理論計算機科學

理論計算機科學包括與計算相關的離散數學領域。它在圖形論和數學邏輯上很大程度上借鑒。理論計算機科學中包括算法和數據結構的研究。計算性研究原則上可以計算的內容，並且與邏輯有著密切的聯繫，而復雜性研究了計算所獲得的時間，空間和其他資源。自動機理論和正式語言理論與可計算性密切相關。培養皿網和工藝代數用於對計算機系統進行建模，並且使用離散數學的方法用於分析VLSI電子電路。計算幾何形狀將算法應用於幾何問題和幾何對象的表示，而計算機圖像分析將它們應用於圖像的表示。理論計算機科學還包括對各種連續計算主題的研究。

信息理論

信息理論涉及信息的量化。密切相關的是編碼理論，用於設計有效且可靠的數據傳輸和存儲方法。信息理論還包括連續主題，例如：模擬信號，模擬編碼，模擬加密。

邏輯

邏輯是對有效推理和推理的原理以及一致性，健全性和完整性的研究。例如，在大多數邏輯系統中（但在直覺邏輯中） Peirce定律（（（（ P → Q ）→ P ）→ P ）是一個定理。對於古典邏輯，可以通過真實表很容易驗證它。對數學證明的研究在邏輯中尤為重要，並且積累了自動化的定理，以證明和正式驗證軟件。

邏輯公式是離散的結構，就像證據一樣，形成有限樹或更一般的定向無環形結構（每個推進步驟組合一個或多個前提分支以得出一個結論）。邏輯公式的真實價值通常形成有限的集合，通常僅限於兩個值： true和false ，但是邏輯也可以連續值，例如，模糊邏輯。還研究了諸如無限掃描或無限衍生樹之類的概念，例如無限邏輯。

集理論

集合理論是研究設置的數學分支，它們是對象的集合，例如{藍色，白色，紅色}或所有質數的（無限）集。部分有序的集合和與其他關係的集合在多個領域都有應用。

在離散數學中，可計數集（包括有限集）是主要重點。集合理論作為數學的分支的開頭通常以喬治·坎托（Georg Cantor ）的作品為標誌，區分不同種類的無限集，以三角研究的研究和進一步的無限集合理論的進一步發展不在離散的範圍之內數學。的確，描述性集理論中的當代工作可以廣泛利用傳統的連續數學。

組合學

組合學研究可以將離散結構組合或佈置的方式進行研究。列舉組合學的集中於計算某些組合對象的數量 - 例如，十二倍的方式為計數排列，組合和分區提供了統一的框架。分析組合學涉及使用複雜分析和概率理論工具的組合結構的枚舉（即確定組合數）。與使用明確的組合公式和生成函數來描述結果的枚舉組合製劑相反，分析組合學旨在獲得漸近公式。拓撲組合學涉及在組合學中使用拓撲和代數拓撲/組合拓撲的技術。設計理論是對組合設計的研究，它們是具有某些相交特性的子集的集合。分區理論研究了與整數分區相關的各種枚舉和漸近問題，並且與Q系，特殊功能和正交多項式密切相關。分區理論最初是數字理論和分析的一部分，現在被認為是組合學或獨立領域的一部分。順序理論是對有限和無限的部分有序集的研究。

圖理論

圖理論是圖形和網絡的研究，通常被認為是組合學的一部分，但已經變得足夠大且足夠獨特，具有自己的問題，可以被視為本身的主題。圖是離散數學研究的主要對象之一。它們是自然和人為結構中最普遍的模型之一。他們可以在物理，生物和社會系統中建模多種類型的關係和過程動態。在計算機科學中，它們可以代表通信，數據組織，計算設備，計算流等網絡等。在數學中，它們在幾何和拓撲的某些部分中很有用，例如結節理論。代數圖理論與群體理論有密切的聯繫，拓撲圖理論與拓撲密切相關。也有連續的圖；但是，在大多數情況下，圖理論的研究屬於離散數學領域。

數字理論

數字理論通常與數字的屬性有關，尤其是整數。它在密碼學和密碼分析中具有應用，特別是在模塊化算術，二元方程，線性和二次的一致性，質量數和原始測試方面。數字理論的其他離散方麵包括數字的幾何形狀。在分析數理論中，還使用了連續數學的技術。超出離散對象的主題包括先驗數字，二元近似， P-ADIC分析和功能字段。

代數結構

代數結構以離散示例和連續示例出現。離散代數包括：邏輯門和編程中使用的布爾代數；數據庫中使用的關係代數；組，環和田地的離散版本和有限版本在代數編碼理論中很重要。離散的半群和單型物體出現在形式語言理論中。

連續數學的離散類似物

連續數學中有許多概念和理論，它們具有離散版本，例如離散演算，離散的傅立葉變換，離散的幾何，離散對數，離散差異幾何，離散的差異幾何，離散的外部計算，離散的MORSE理論，離散優化的優化理論，離散的概率理論，離散的概率理論，離散的概率理論，離散的概率理論分佈，差異方程，離散的動態系統和離散的向量度量。

有限差異，離散分析和離散演算的計算

在離散的演算和有限差的演算中，在整數間隔上定義的函數通常稱為序列。序列可以是來自數據源的有限序列，也可以是離散動力學系統的無限序列。這樣的離散函數可以通過列表（如果其域是有限的）或通用術語公式明確定義的，或者可以通過復發關係或差異方程來隱式地給出。差異方程與微分方程相似，但通過在相鄰術語之間取差來代替分化。它們可用於近似微分方程，或者（更經常）自行研究。有關微分方程的許多問題和方法都有差異方程式的對應物。例如，在研究連續函數或模擬信號的諧波分析中存在整體變換的情況下，有離散函數或數字信號的離散轉換。除了離散的度量空間外，還有更多一般的離散拓撲空間，有限的度量空間，有限的拓撲空間。

時間尺度的演算是差異方程理論與微分方程的統一，該方程的差異方程式具有應用於需要同時建模離散數據和連續數據的字段。建模這種情況的另一種方法是混合動力學系統的概念。

離散的幾何形狀

離散的幾何形狀和組合幾何形狀是關於幾何對象離散集合的組合特性。離散幾何形狀的一個長期主題是平面的瓷磚。

在代數幾何形狀中，可以將曲線的概念擴展到離散的幾何形狀，通過將多項式環的光譜置於有限磁場上，使其成為該田地上仿射空間的模型，並讓其他環的曲線提供在其他環上的曲線或光譜。那個空間。儘管曲線出現的空間具有有限數量的點，但曲線並不像連續設置中曲線的類似物那樣多。例如，可以研究（XC）的局部環的每個點的每個點，或者是局部環的頻譜，一個點與周圍的鄰域一起研究。代數品種還具有明確的切線空間概念，稱為Zariski切線空間，即使在有限的設置中也是如此適用的微積分特徵。

離散建模

在應用數學中，離散建模是連續建模的離散類似物。在離散建模中，離散公式適合數據。這種建模形式的一種常見方法是使用復發關係。離散化涉及將連續模型和方程式轉移到離散對應物中的過程，通常是為了通過使用近似值使計算更容易。數值分析提供了一個重要的例子。

挑戰

離散數學的歷史涉及許多具有挑戰性的問題，這些問題將注意力集中在該領域的領域。在圖理論中，許多研究的動機是通過試圖證明這四種顏色定理的動機，該定理於1852年首次指出，但直到1976年才證明（肯尼斯·阿佩爾（Kenneth Appel）和沃爾夫岡·哈肯（Wolfgang Haken），使用大量的計算機援助）。

在邏輯上，大衛·希爾伯特（David Hilbert）在1900年提出的開放問題清單上的第二個問題是證明算術的公理是一致的。戈德爾的第二個不完整定理在1931年證明，這表明這是不可能的 - 至少不在算術本身中。希爾伯特（Hilbert）的第十個問題是確定具有整數係數的給定多項式雙苯胺方程是否具有整數解決方案。 1970年， Yuri Matiyasevich證明了這是不可能的。

在第二次世界大戰中打破德國代碼的需求導致了密碼學和理論計算機科學的進步，在英格蘭的Bletchley Park開發了第一台可編程的數字電子計算機，並在Alan Turing和他的開創性工作的指導下，以可計算的數字進行了指導。冷戰意味著密碼學仍然很重要，在接下來的幾十年中，諸如公開密碼學之類的基本進展。電信行業還激發了離散數學的進步，尤其是在圖理論和信息理論方面。對於安全至關重要的系統的軟件開發，對邏輯上的語句的正式驗證是必要的，並且自動化定理的進步證明是由這種需求驅動的。

計算幾何形狀一直是現代視頻遊戲和計算機輔助設計工具中的計算機圖形的重要組成部分。

離散數學的幾個領域，尤其是理論計算機科學，圖理論和組合學，對於解決與理解生命之樹相關的具有挑戰性的生物信息學問題很重要。

當前，理論計算機科學中最著名的開放問題之一是P = NP問題，它涉及複雜性類P和NP之間的關係。克萊數學學院為第一個正確的證明提供了100萬美元的獎金，以及其他六個數學問題的獎品。

也可以看看

• 離散數學概述
• Cyber​​chase ，向兒童教授離散數學的節目