「离散数学」:修訂間差異
無編輯摘要 |
回退23.158.104.247(讨论)做出的出于善意的编辑:无来源 |
||
(未顯示由 32 位使用者於中間所作的 39 次修訂) | |||
第1行: | 第1行: | ||
{{NoteTA |
|||
* 點列項目 |
|||
⚫ | |||
{{Disputed|time=2012-11-16T08:38:23+00:00}} |
|||
|G2 = Math |
|||
{{原創研究|time=2010-08-28T16:27:14+00:00}} |
|||
⚫ | |||
{{primarysources|time=2010-08-28T16:27:14+00:00}} |
|||
[[File:6n-graf.svg|thumb|250px|像这样的[[图 (数学)|图]]是离散数学的研究对象之一,它们拥有有趣的[[图性质|数学性质]],可以作为现实世界用来解决问题的模型,而且还在计算机[[算法]]开发中有着举足轻重的作用。]] |
|||
'''离散数学'''({{lang-en|Discrete mathematics}})是[[数学]]的几个分支的总称,研究基于[[离散空间]]而不是[[连续函数|连续]]的数学结构。与連續变化的[[实数]]不同,离散数学的研究对象——例如[[整数]]、[[图 (数学)|图]]和[[数学逻辑]]中的命题<ref>Richard Johnsonbaugh, ''Discrete Mathematics'', Prentice Hall, 2008.</ref>——不是連續变化的,而是拥有不等、分立的值。<ref>{{cite mathworld|title=Discrete mathematics |urlname=DiscreteMathematics}}</ref>因此离散数学不包含[[微积分]]和[[数学分析|分析]]等「连续数学」的内容。 |
|||
离散对象经常可以用整数来[[枚举]]。更一般地,离散数学被视为处理[[可数集合]](与整数子集基数相同的集合,包括有理数集但不包括实数集)的数学分支。<ref>[[Norman L. Biggs]], ''Discrete mathematics'', Oxford University Press, 2002.</ref>但是,“离散数学”不存在准确且普遍认可的定义。<ref>Brian Hopkins, ''Resources for Teaching Discrete Mathematics'', Mathematical Association of America, 2008.</ref>实际上,离散数学经常被定义为不包含连续变化量及相关概念的数学,甚少被定义为包含什么内容的数学。 |
|||
离散数学中的对象集合可以是有限或者是无限的。'''有限数学'''一词通常指代离散数学处理有限集合的那些部分,特别是在与商业相关的领域。 |
|||
{{noteTA |
|||
⚫ | |||
⚫ | |||
隨著[[電腦科學]]的飛速發展,離散數學的重要性則日益彰顯。它為許多資訊科學課程提供了數學基礎,包括数据結構、演算法、数据库理論、形式語言與作業系統等。如果沒有離散數學的相關數學基礎,學生在學習上述課程中,便會遇到較多的困難。此外,離散數學也包含了解決作業研究、化學、工程學、生物學等眾多領域的數學背景。由於運算對象是離散的,所以電腦科學的數學基礎基本上也是離散的。我們可以說電腦科學的[[數學語言]]就是離散數學。人們會使用離散數學裡面的槪念和表示方法,來研究和描述電腦科學下所有分支的對象和問題,如電腦[[運算]]、[[编程語言]]、[[密碼學]]、[[自動定理証明]]和[[軟件開發]]等。相反地,计算机的應用使離散數學的概念得以應用於日常生活當中(如[[運籌學]])。 |
|||
[[File:6n-graf.svg|thumb|250px|[[圖形理論]]是离散数学的研究对象之一。]] |
|||
'''離散數學''' 就是「電腦用數學」;並不是一個新的東西。它只是蒐集計算機科學中用得著的數學,如[[邏輯]]、[[數論]]、[[集合論]]、[[圖論]]、...混合在一起;而且混合的比例也隨著計算機科學的發展而有不同。這件事是現在九年級生 (90 年代出生的人) 所不願意相信的事實,因為她們沒有看過電腦從無到有。她們沒有看過數學系的人不知道離散數學是甚麼的年代 <ref>丁致良, ''離散數學'',第三版,秀才書屋,2013。</ref>。 |
|||
虽然离散数学的主要研究对象是离散对象,但是连续数学的分析方法往往也可以采用。[[数论]]就是离散和连续数学的交叉学科。同样的,[[有限拓扑]](对有限拓扑空间的研究)从字面上可看作[[离散化]]和[[拓扑学|拓扑]]的交集。 |
|||
每個用得著數學的科系,大約大二都會有一門數學課,簡單說就是「本系常用數學」,但是通常被冠以各系名稱,如[[管理數學]]、[[工程數學]]、[[物理數學]]等等。其實,數學就是數學。因為電腦中只有「零」與「壹」所以相關的運算自然也就只有「零」與「壹」了。數學系裡「離散數學」通常教的是[[組合數學]]。不過離散數學包含得比這個廣。學物理的人稱「離散」的東西為「量子」;不過量子包含的意義比離散還多,在物理系中與離散數學比較像的是[[統計力學]]。這兩個學科都是教你計算東西的個數。 |
|||
== 历史 == |
== 历史 == |
||
[[File:Four Colour Map Example.svg|left|180px|thumb|在[[图论]]领域中,大量研究的动机是企图证明在对所有的地图,譬如说此图,可以用不多于[[四色定理|四种颜色]]上色,而且没有任意两个相接的区域会是同色。1976年,[[肯尼斯·阿佩尔]]和[[沃尔夫冈·哈肯]]最终证明了四色定理。<ref name="4colors">{{Citation |last=Wilson |first=Robin |authorlink=Robin Wilson (mathematician) |title=Four Colors Suffice |place=London |publisher=Penguin Books |year=2002 |isbn=0-691-11533-8}}</ref>]] |
[[File:Four Colour Map Example.svg|left|180px|thumb|在[[图论]]领域中,大量研究的动机是企图证明在对所有的地图,譬如说此图,可以用不多于[[四色定理|四种颜色]]上色,而且没有任意两个相接的区域会是同色。1976年,[[肯尼斯·阿佩尔]]和[[沃尔夫冈·哈肯]]最终证明了四色定理。<ref name="4colors">{{Citation |last=Wilson |first=Robin |authorlink=Robin Wilson (mathematician) |title=Four Colors Suffice |place=London |publisher=Penguin Books |year=2002 |isbn=0-691-11533-8}}</ref>]] |
||
历史上,离散数学涉及了各个领域的一系列挑战性问题。在[[图论]]中, |
历史上,离散数学涉及了各个领域的一系列挑战性问题。在[[图论]]中,許多的研究动机是來自於嘗試证明[[四色定理]]。这些研究虽然从1852年开始,但是直至1976年四色定理才得到证明,是由[[肯尼斯·阿佩尔]](Kenneth Appel)和[[沃尔夫冈·哈肯]](Wolfgang Haken)藉由大量计算机辅助而完成的。<ref name="4colors" /> |
||
在[[数理逻辑|逻辑]]领域,[[大卫·希尔伯特]](David Hilbert)於1900年提出的公开问题清单的第二个问题是要证明算术的[[公理]]是[[形式系统相容性|一致]]的。1931年,[[库尔特·哥德尔]]的[[哥德尔不完备定理|第二不完备定理]]证明这是不可能的——至少算术本身不可能。大卫·希尔伯特的第十个问题是要确定某一整系数多项式[[丢番图方程]]是否有一个整数解。1970年,[[尤里·马季亚谢维奇]]证明这不可能做到。 |
在[[数理逻辑|逻辑]]领域,[[大卫·希尔伯特]](David Hilbert)於1900年提出的公开问题清单的第二个问题是要证明算术的[[公理]]是[[形式系统相容性|一致]]的。1931年,[[库尔特·哥德尔]]的[[哥德尔不完备定理|第二不完备定理]]证明这是不可能的——至少算术本身不可能。大卫·希尔伯特的第十个问题是要确定某一整系数多项式[[丢番图方程]]是否有一个整数解。1970年,[[尤里·马季亚谢维奇]]证明这不可能做到。 |
||
第23行: | 第23行: | ||
[[第二次世界大戰]]時[[同盟國 (第二次世界大戰)|盟軍]]有[[密碼分析|破解]][[納粹德軍]]密碼的需要,帶動了[[密碼學]]和[[理論計算機科學]]的發展。英國的[[布萊切利園]]因而發明出第一部數位電子計算機——[[巨像電腦]]。與此同時,軍事上的需求亦帶動了[[運籌學]]的發展。直至[[冷戰]]時期,密碼學的地位依然重要,其後的幾十年間更發展出如[[公開密鑰加密]]等根本性的長進。隨著1950年代[[關鍵路徑|關鍵路徑方法]]的創立,運籌學則於[[商業]]和[[項目管理]]上愈趨重要。[[電訊]]工業的出現亦助長了離散數學,特別是[[圖論]]和[[信息論]]上的發展。[[數理邏輯]]上[[敍述]]的[[形式驗證]]至今已經成為[[安全關鍵系統]]的[[軟件開發]]中必不可少的一環,[[自動定理證明]]的技術也因此而提高。 |
[[第二次世界大戰]]時[[同盟國 (第二次世界大戰)|盟軍]]有[[密碼分析|破解]][[納粹德軍]]密碼的需要,帶動了[[密碼學]]和[[理論計算機科學]]的發展。英國的[[布萊切利園]]因而發明出第一部數位電子計算機——[[巨像電腦]]。與此同時,軍事上的需求亦帶動了[[運籌學]]的發展。直至[[冷戰]]時期,密碼學的地位依然重要,其後的幾十年間更發展出如[[公開密鑰加密]]等根本性的長進。隨著1950年代[[關鍵路徑|關鍵路徑方法]]的創立,運籌學則於[[商業]]和[[項目管理]]上愈趨重要。[[電訊]]工業的出現亦助長了離散數學,特別是[[圖論]]和[[信息論]]上的發展。[[數理邏輯]]上[[敍述]]的[[形式驗證]]至今已經成為[[安全關鍵系統]]的[[軟件開發]]中必不可少的一環,[[自動定理證明]]的技術也因此而提高。 |
||
当今,理 |
当今,[[理論計算機科學]]中最著名的开放问题之一是[[P/NP问题]],P/NP问题中包含了[[复杂度类]][[P (复杂度)|P]]与[[NP (复杂度)|NP]]的关系。[[克雷数学研究所]]为此及其他6个[[千禧年大奖难题]]的第一个正确证明各悬赏100万美元。<ref name="CMI千禧年大奖难题">{{cite web|title=千禧年大奖难题|url=http://www.claymath.org/millennium/|date=2000-05-24|accessdate=2008-01-12|archive-date=2008-01-08|archive-url=https://web.archive.org/web/20080108223641/http://www.claymath.org/millennium/|dead-url=no}}</ref> |
||
== |
== 主题 == |
||
[[File:WikipediaBinary.svg|thumb|150px| "Wikipedia" [[ASCII]]码的[[二进制]]表示。[[编码技术]]为[[信息论]]领域提供了一种表示语句和信息处理[[程序]]的途径。]] |
[[File:WikipediaBinary.svg|thumb|150px| "Wikipedia" [[ASCII]]码的[[二进制]]表示。[[编码技术]]为[[信息论]]领域提供了一种表示语句和信息处理[[程序]]的途径。]] |
||
离散数学包含几个不同的主题,列举如下: |
离散数学包含几个不同的主题,列举如下: |
||
第35行: | 第35行: | ||
=== 集合论 === |
=== 集合论 === |
||
{{main|集合论}} |
{{main|集合论}} |
||
集合论是研究[[集合]]的数学分支。集合是指一定对象的总和,例如:{蓝色,白色,红色}是一个[[有限集合]];所有[[素数]]组成一个[[无限集合]]。 [[偏序关系]]和拥有其他[[关系 (数学)|关系]]特征的集合在多个数学领域都有应用。 |
集合论是研究[[集合 (数学)|集合]]的数学分支。集合是指一定对象的总和,例如:{蓝色,白色,红色}是一个[[有限集合]];所有[[素数]]组成一个[[无限集合]]。 [[偏序关系]]和拥有其他[[关系 (数学)|关系]]特征的集合在多个数学领域都有应用。 |
||
=== 信息论 === |
=== 信息论 === |
||
{{main|信息论}} |
{{main|信息论}} |
||
[[File:Ulam 1.png|thumb|200px|right| |
[[File:Ulam 1.png|thumb|200px|right|[[质数螺旋图]],黑点为质数。]] |
||
信息论涉及[[信息]]量化。与此密切相关的[[编码理论]]则用来设计高效可靠的数据传输和数据储存方法。 |
信息论涉及[[信息]]量化。与此密切相关的[[编码理论]]则用来设计高效可靠的数据传输和数据储存方法。 |
||
第55行: | 第55行: | ||
=== 图论 === |
=== 图论 === |
||
{{main|图论}} |
{{main|图论}} |
||
图论是研究[[图]]和 |
图论是研究[[图 (数学)|图]]和[[网络理论|网络]]的数学分支,常被认为包含於组合数学中,但这一分支已经发展得足够庞大和有特点,并有自身领域所研究的问题,因此被视为一个独立的主题,在数学和科学的所有领域都有广泛的应用。例如:有名的七橋問題。<ref>[http://jhupbooks.press.jhu.edu/ecom/MasterServlet/GetItemDetailsHandler?iN=9780801866890&qty=1&viewMode=1&loggedIN=false&JavaScript=y Graphs on Surfaces] {{Wayback|url=http://jhupbooks.press.jhu.edu/ecom/MasterServlet/GetItemDetailsHandler?iN=9780801866890&qty=1&viewMode=1&loggedIN=false&JavaScript=y |date=20100611224850 }}, Bojan Mohar and Carsten Thomassen, Johns Hopkins University press, 2001</ref> |
||
=== 抽象代数 === |
=== 抽象代数 === |
||
第63行: | 第63行: | ||
=== 理论计算机科学 === |
=== 理论计算机科学 === |
||
{{main|理论计算机科学}} |
{{main|理论计算机科学}} |
||
[[File:Sorting quicksort anim.gif|thumb|150px|[[计算复杂性理论|复杂度]]研究[[程序]]耗费的时间,例如这个[[快速排序]]程序。]] |
[[File:Sorting quicksort anim.gif|thumb|150px|[[计算复杂性理论|复杂度]]研究[[计算机程序|程序]]耗费的时间,例如这个[[快速排序]]程序。]] |
||
离散数学充分描述了[[计算机科学]]离散性的特点。 |
离散数学充分描述了[[计算机科学]]离散性的特点。 |
||
第75行: | 第75行: | ||
=== 运筹学 === |
=== 运筹学 === |
||
{{main|运筹学}} |
{{main|运筹学}} |
||
[[File:Pert chart colored.gif|thumb|150px|像这样的[[计划评审技术|PERT]]图提供 |
[[File:Pert chart colored.gif|thumb|150px|像这样的[[计划评审技术|PERT]]图提供一个基于[[图论]]的商业管理技术。]]運籌學的研究為解決一些商業上和其他範籌上實質的問題提供方法。這些問題包括如何分配資源以使利潤增至最高和如何為企劃排程使風險減至最低等。運籌學的研究方向包括[[線性規劃]]、[[最优化]]、[[等候理論]]、[[调度理论]]、[[网络理论]],和一些正在增加的其他方面。运筹学的内容也会涉及一些连续主题,如连续时间[[马尔可夫过程]]、连续时间[[鞅 (概率论)|鞅]]、{{link-en|过程优化|process optimization}}以及连续混合[[控制理论]]。 |
||
=== 博弈论、决策论、效用理论、社会选择理论 === |
=== 博弈论、决策论、效用理论、社会选择理论 === |
||
第82行: | 第82行: | ||
1U = 合作 | UL = -1, -1 | UR = -10, 0 | |
1U = 合作 | UL = -1, -1 | UR = -10, 0 | |
||
1D = 背叛 | DL = 0, -10 | DR = -5, -5 }} |
1D = 背叛 | DL = 0, -10 | DR = -5, -5 }} |
||
[[博 |
[[博弈論]]用於處理的問題比較複雜,通常這些選擇成功與否取決於其他人的選擇,因此如何作最好出一個最好的選擇比較複雜。连续对策甚至也是存在的,如[[微分博弈]]。博弈論的主题包括[[拍卖理论]]和[[公平分配博弈]]。 |
||
[[决策论]]是有关判定特定决策的价值、不确定性、合理性以及最终能够确定的最优决策的理论。 |
[[决策论]]是有关判定特定决策的价值、不确定性、合理性以及最终能够确定的最优决策的理论。 |
||
第109行: | 第109行: | ||
在[[应用数学]]中,[[离散模型]]是[[连续模型]]的离散近似。在离散模型中,离散方程由[[数据]]确定。使用[[递推关系]]是这种建模方式的一般方法。 |
在[[应用数学]]中,[[离散模型]]是[[连续模型]]的离散近似。在离散模型中,离散方程由[[数据]]确定。使用[[递推关系]]是这种建模方式的一般方法。 |
||
=== 离散和连续混合数学 === |
|||
[[时标微积分]]是[[差分方程]]理论与[[微分方程]]理论的统一,应用在需要建立离散和连续同步数据模型的领域。 |
|||
== 参考文献 == |
== 参考文献 == |
||
第115行: | 第118行: | ||
== 延伸阅读 == |
== 延伸阅读 == |
||
{{Wikibooks|Discrete mathematics|离散数学|en}} |
{{Wikibooks|Discrete mathematics|离散数学|en}} |
||
⚫ | |||
* 丁致良, "離散數學'' 第三版 秀才書屋 ISBN 978-957-2928097. 網址 [http://www.nckubook.com.tw/index.php?pa=view_book&bid=6ve3sl9gh8vd4oi9bg416091379718032]. |
|||
⚫ | |||
* [[Ronald Graham]], [[Donald Knuth|Donald E. Knuth]], [[Oren Patashnik]], ''[[Concrete Mathematics]]'' |
* [[Ronald Graham]], [[Donald Knuth|Donald E. Knuth]], [[Oren Patashnik]], ''[[Concrete Mathematics]]'' |
||
* Richard Johnsonbaugh, ''Discrete Mathematics'' 6th ed. Macmillan. ISBN 0-13-045803- |
* Richard Johnsonbaugh, ''Discrete Mathematics'' 6th ed. Macmillan. ISBN 978-0-13-045803-2. Companion Web site: [http://wps.prenhall.com/esm_johnsonbau_discrtmath_6/] {{Wayback|url=http://wps.prenhall.com/esm_johnsonbau_discrtmath_6/ |date=20210427223112 }} |
||
* {{cite book | author=Klette |
* {{cite book | author=Reinhard Klette and Azriel Rosenfeld | title=Digital Geometry | publisher=Morgan Kaufmann | year=2004 | isbn=1-55860-861-3 | url=https://www.cs.auckland.ac.nz/~rklette/Books/MK2004/index.html | access-date=2020-05-25 | archive-date=2021-02-10 | archive-url=https://web.archive.org/web/20210210184341/https://www.cs.auckland.ac.nz/%7Erklette/Books/MK2004/index.html }} Also on (digital) topology, graph theory, combinatorics, axiomatic systems. |
||
* [[Donald Knuth|Donald E. Knuth]], ''[[The Art of Computer Programming]]'' |
* [[Donald Knuth|Donald E. Knuth]], ''[[The Art of Computer Programming]]'' |
||
* Kenneth H. Rosen, ''Handbook of Discrete and Combinatorial Mathematics'' CRC Press. ISBN 0-8493-0149- |
* 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 0-07-288008- |
* 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/ {{Wayback|url=http://highered.mcgraw-hill.com/sites/0072880082/information_center_view0/ |date=20130915092156 }} |
||
* [[Ralph Grimaldi|Ralph P. Grimaldi]], ''Discrete and Combinatorial Mathematics: An Applied Introduction'' 5th ed. Addison Wesley. ISBN 0-201-72634-3 |
* [[Ralph Grimaldi|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'' |
* C.L. Liu, ''Elements of Discrete Math'' |
||
* Neville Dean, ''Essence of Discrete Mathematics'' Prentice Hall. ISBN 0-13-345943- |
* 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 |
* Mathematics Archives, Discrete Mathematics links to syllabi, tutorials, programs, etc. http://archives.math.utk.edu/topics/discreteMath.html {{Wayback|url=http://archives.math.utk.edu/topics/discreteMath.html |date=20110829184228 }} |
||
* [[Jiří Matoušek (mathematician)|Jiří Matoušek]] & [[Jaroslav Nešetřil]], ''Invitation to Discrete Mathematics'', OUP. |
* [[Jiří Matoušek (mathematician)|Jiří Matoušek]] & [[Jaroslav Nešetřil]], ''Invitation to Discrete Mathematics'', OUP. |
||
== 外部連結 == |
== 外部連結 == |
||
* {{zh}}[http://episte.math.ntu.edu.tw/cgi/mathfield.pl?fld=dis 數學領域:離散數學 (Episte Math)] |
* {{zh}}[http://episte.math.ntu.edu.tw/cgi/mathfield.pl?fld=dis 數學領域:離散數學 (Episte Math)] {{Wayback|url=http://episte.math.ntu.edu.tw/cgi/mathfield.pl?fld=dis |date=20200703102106 }} |
||
{{应用数学}} |
|||
* {{zh}}[http://www.cis.nctu.edu.tw/~is83039/discret/discrete.html 主題網站:離散數學] |
|||
* {{zh}}[http://dm.net78.net/modules/newbb/ 主題網站:離散數學] |
|||
{{Computer Science}} |
{{Computer Science}} |
||
{{数学主要领域}} |
|||
[[Category:离散数学|*]] |
[[Category:离散数学|*]] |
於 2024年1月19日 (五) 10:30 的最新修訂
離散數學(英語: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) (頁面存檔備份,存於網際網路檔案館)
|
|
|