离散数学

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

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

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

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

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

离散数学的主题
"Wikipedia" ASCII码的二进制表示。编码技术为信息论领域提供了一种表示语句和信息处理程序的途径。

离散数学包含几个不同的主题，列举如下：

数理逻辑
主条目：数理逻辑

逻辑是对有效推理和推理原则，及其连续性、合理性和完整性的研究。举一个简单的例子：在大多数逻辑系统中，皮尔士定律（((P→Q)→P)→P）是正确的，而且可以简易地利用真值表得到证明。数学证明在数理逻辑中十分重要，而且在自动定理证明和软件开发（如形式验证）有广泛应用。

集合论
主条目：集合论

集合论是研究集合的数学分支。集合是指一定对象的总和，例如：{蓝色，白色，红色}是一个有限集合；所有素数组成一个无限集合。 偏序关系和拥有其他关系特征的集合在多个数学领域都有应用。

信息论
主条目：信息论
质数螺旋图，黑点为质数。

信息论涉及信息量化。与此密切相关的编码理论则用来设计高效可靠的数据传输和数据储存方法。

数论
主条目：数论

数论关注普通数字，特别是整数的特性。数论在密码学和密码分析中有应用，特别是关于素数和素性测试方面。在解析数论中，也使用连续数学的理论。

组合数学
主条目：组合数学
代数图论与群论有着紧密联系。此截角四面體图与交错群A4有关。

组合数学研究对象进行排列或组合的途径，包含组合设计（Combinatorial design）、计数组合（enumerative combinatorics）、计数、组合几何（combinatorial geometry）、组合拓扑（Combinatorial topology）等主题。图论是组合数学的重要部分，有很多实际应用。

在组合分析（analytic combinatorics）和代数图论（algebraic graph theory）中也使用连续数学的理论，而且代数图论还与群论有着紧密联系。

图论
主条目：图论

图论是研究图和网络的数学分支，常被认为包含於组合数学中，但这一分支已经发展得足够庞大和有特点，并有自身领域所研究的问题，因此被视为一个独立的主题，在数学和科学的所有领域都有广泛的应用。例如：有名的七橋問題。[3]

抽象代数
主条目：抽象代数

代数结构既可以是离散的，也可以是连续的。离散代数包括逻辑门和编程中使用的逻辑代数、数据库中使用的关系代数、代数编码理论中重要的离散有限群、环和域、形式语言理论中的离散半群和幺半群。

理论计算机科学
复杂度研究程序耗费的时间，例如这个快速排序程序。

离散数学充分描述了计算机科学离散性的特点。

理论计算机科学（Theoretical computer science）包含离散数学计算的领域，并特别注重图论和数理逻辑。理论计算机科学包括对计算数学结果的算法研究。可算性理论研究那些对象在原则上可被计算，和逻辑有密切联系。而复杂性则研究计算耗费的时间，自动机理论和形式语言理论与复杂性紧密联系。计算几何应用算法解决几何问题，而计算机图像分析则是应用算法在计算机中再现图像。

拓扑学
主条目：拓扑学

虽然拓扑学是形式化和一般化物体“连续形变”的直觉概念的研究领域，其也包含很多离散主题，如拓扑变换时常取离散值，组合拓扑、拓扑图论、拓扑组合、计算拓扑、离散空间、有限拓扑空间等领域。

运筹学
主条目：运筹学
像这样的PERT图提供了一个基于图论的商业管理技术。

運籌學的研究為解決一些商業上和其他範籌上實質的問題提供了方法。這些問題包括如何分配資源以使利潤增至最高和如何為企劃排程使風險減至最低等。運籌學的研究方向包括線性規劃、最优化、等候理論、调度理论、网络理论，和一些正在增加的其他方面。运筹学的内容也会涉及一些连续主题，如连续时间马尔可夫过程、连续时间鞅、过程优化以及连续混合控制理论。

博弈论、决策论、效用理论、社会选择理论
合作 背叛
合作 -1, -1 -10, 0
背叛 0, -10 -5, -5
囚徒困境的支付矩阵

博弈論用於處理的問題比較複雜，通常這些選擇成功與否取決於其他人的選擇，因此如何作最好出一個最好的選擇比較複雜。连续对策甚至也是存在的，如微分博弈。博弈論的主题包括拍卖理论和公平分配博弈。

决策论是有关判定特定决策的价值、不确定性、合理性以及最终能够确定的最优决策的理论。

效用理论的研究内容是由各种商品和服务评估相对经济满足程度，或是评估各种商品和服务的希求程度。

社会选择理论是关於投票的理论。更近似於谜题的有关投票的问题是抽签问题（Bertrand's ballot theorem）。

离散化
主条目：离散化

离散化关注将连续模型或等式转化为离散形式的过程，通常是基于简化计算的目的。数值分析是离散化一个重要实例。

连续数学的离散近似
计算几何将计算机算法应用於几何物体的描绘

很多的连续数学概念都有离散数学的版本，例如:

在应用数学中，离散模型是连续模型的离散近似。在离散模型中，离散方程由数据确定。使用递推关系是这种建模方式的一般方法。

离散和连续混合数学

时标微积分是差分方程理论与微分方程理论的统一，应用在需要建立离散和连续同步数据模型的领域。

参考文献
  1. Wilson, Robin, , London: Penguin Books, 2002, ISBN 0-691-11533-8
  2. . 2000-05-24 [2008-01-12]. （原始内容存档于2008-01-08）.
  3. 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:
  • Reinhard Klette and Azriel Rosenfeld. . Morgan Kaufmann. 2004. ISBN 1-55860-861-3. 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.

外部連結
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.