首页 >
离散数学
✍ dations ◷ 2025-04-02 13:39:40 #离散数学
离散数学(英语:Discrete mathematics)是数学的几个分支的总称,研究基于离散空间而不是连续的数学结构。与连续变化的实数不同,离散数学的研究对象——例如整数、图和数学逻辑中的命题——不是连续变化的,而是拥有不等、分立的值。因此离散数学不包含微积分和分析等“连续数学”的内容。离散对象经常可以用整数来枚举。更一般地,离散数学被视为处理可数集合(与整数子集基数相同的集合,包括有理数集但不包括实数集)的数学分支。 。但是,“离散数学”不存在准确且普遍认可的定义。实际上,离散数学经常被定义为不包含连续变化量及相关概念的数学,甚少被定义为包含什么内容的数学。离散数学中的对象集合可以是有限或者是无限的。有限数学一词通常指代离散数学处理有限集合的那些部分,特别是在与商业相关的领域。随着计算机科学的飞速发展,离散数学的重要性则日益彰显。它为许多信息学课程提供了数学基础,包括数据结构、算法、数据库理论、形式语言与操作系统等。如果没有离散数学的相关数学基础,学生在学习上述课程中,便会遇到较多的困难。此外,离散数学也包含了解决作业研究、化学、工程学、生物学等众多领域的数学背景。由于运算对象是离散的,所以计算机科学的数学基础基本上也是离散的。我们可以说计算机科学的数学语言就是离散数学。人们会使用离散数学里面的槪念和表示方法,来研究和描述计算机科学下所有分支的对象和问题,如电脑运算、编程语言、密码学、自动定理证明和软件开发等。相反地,计算机的应用使离散数学的概念得以应用于日常生活当中(如运筹学)。虽然离散数学的主要研究对象是离散对象,但是连续数学的分析方法往往也可以采用。数论就是离散和连续数学的交叉学科。同样的,有限拓扑(对有限拓扑空间的研究)从字面上可看作离散化和拓扑的交集。历史上,离散数学涉及了各个领域的一系列挑战性问题。在图论中,许多的研究动机是来自于尝试证明四色定理。这些研究虽然从1852年开始,但是直至1976年四色定理才得到证明,是由肯尼斯·阿佩尔(Kenneth Appel)和沃尔夫冈·哈肯(Wolfgang Haken)借由大量计算机辅助而完成的。在逻辑领域,大卫·希尔伯特(David Hilbert)于1900年提出的公开问题清单的第二个问题是要证明算术的公理是一致的。1931年,库尔特·哥德尔的第二不完备定理证明这是不可能的——至少算术本身不可能。大卫·希尔伯特的第十个问题是要确定某一整系数多项式丢番图方程是否有一个整数解。1970年,尤里·马季亚谢维奇证明这不可能做到。第二次世界大战时盟军有破解纳粹德军密码的需要,带动了密码学和理论计算机科学的发展。英国的布莱切利园因而发明出第一部数字电子计算机——巨像电脑。与此同时,军事上的需求亦带动了运筹学的发展。直至冷战时期,密码学的地位依然重要,其后的几十年间更发展出如公开密钥加密等根本性的长进。随着1950年代关键路径方法的创立,运筹学则于商业和项目管理上愈趋重要。电讯工业的出现亦助长了离散数学,特别是图论和信息论上的发展。数理逻辑上叙述的形式验证至今已经成为安全关键系统的软件开发中必不可少的一环,自动定理证明的技术也因此而提高。当今,理论计算机科学中最著名的开放问题之一是P/NP问题,P/NP问题中包含了复杂度类P与NP的关系。克雷数学研究所为此及其他6个千禧年大奖难题的第一个正确证明各悬赏100万美元。离散数学包含几个不同的主题,列举如下:逻辑是对有效推理和推理原则,及其连续性、合理性和完整性的研究。举一个简单的例子:在大多数逻辑系统中,皮尔士定律(((P→Q)→P)→P)是正确的,而且可以简易地利用真值表得到证明。数学证明在数理逻辑中十分重要,而且在自动定理证明和软件开发(如形式验证)有广泛应用。集合论是研究集合的数学分支。集合是指一定对象的总和,例如:{蓝色,白色,红色}是一个有限集合;所有素数组成一个无限集合。 偏序关系和拥有其他关系特征的集合在多个数学领域都有应用。信息论涉及信息量化。与此密切相关的编码理论则用来设计高效可靠的数据传输和数据储存方法。数论关注普通数字,特别是整数的特性。数论在密码学和密码分析中有应用,特别是关于素数和素性测试方面。在解析数论中,也使用连续数学的理论。组合数学研究对象进行排列或组合的途径,包含组合设计(Combinatorial design)、计数组合(enumerative combinatorics)、计数、组合几何(combinatorial geometry)、组合拓扑(Combinatorial topology)等主题。图论是组合数学的重要部分,有很多实际应用。在组合分析(analytic combinatorics)和代数图论(algebraic graph theory)中也使用连续数学的理论,而且代数图论还与群论有着紧密联系。图论是研究图和网络的数学分支,常被认为包含于组合数学中,但这一分支已经发展得足够庞大和有特点,并有自身领域所研究的问题,因此被视为一个独立的主题,在数学和科学的所有领域都有广泛的应用。例如:有名的七桥问题。代数结构既可以是离散的,也可以是连续的。离散代数包括逻辑门和编程中使用的逻辑代数、数据库中使用的关系代数、代数编码理论中重要的离散有限群、环和域、形式语言理论中的离散半群和幺半群。离散数学充分描述了计算机科学离散性的特点。理论计算机科学(Theoretical computer science)包含离散数学计算的领域,并特别注重图论和数理逻辑。理论计算机科学包括对计算数学结果的算法研究。可算性理论研究那些对象在原则上可被计算,和逻辑有密切联系。而复杂性则研究计算耗费的时间,自动机理论和形式语言理论与复杂性紧密联系。计算几何应用算法解决几何问题,而计算机图像分析则是应用算法在计算机中再现图像。虽然拓扑学是形式化和一般化物体“连续形变”的直觉概念的研究领域,其也包含很多离散主题,如拓扑变换时常取离散值,组合拓扑、拓扑图论、拓扑组合、计算拓扑、离散空间、有限拓扑空间等领域。运筹学的研究为解决一些商业上和其他范筹上实质的问题提供了方法。这些问题包括如何分配资源以使利润增至最高和如何为企划调度使风险减至最低等。运筹学的研究方向包括线性规划、最优化、等候理论、调度理论、网络理论,和一些正在增加的其他方面。运筹学的内容也会涉及一些连续主题,如连续时间马尔可夫过程、连续时间鞅、过程优化(英语:process optimization)以及连续混合控制理论。博弈论用于处理的问题比较复杂,通常这些选择成功与否取决于其他人的选择,因此如何作最好出一个最好的选择比较复杂。连续对策甚至也是存在的,如微分博弈。博弈论的主题包括拍卖理论和公平分配博弈。决策论是有关判定特定决策的价值、不确定性、合理性以及最终能够确定的最优决策的理论。效用理论的研究内容是由各种商品和服务评估相对经济满足程度,或是评估各种商品和服务的希求程度。社会选择理论是关于投票的理论。更近似于谜题的有关投票的问题是抽签问题(Bertrand's ballot theorem)。离散化关注将连续模型或等式转化为离散形式的过程,通常是基于简化计算的目的。数值分析是离散化一个重要实例。很多的连续数学概念都有离散数学的版本,例如:在应用数学中,离散模型是连续模型的离散近似。在离散模型中,离散方程由数据确定。使用递推关系是这种建模方式的一般方法。时标微积分是差分方程理论与微分方程理论的统一,应用在需要创建离散和连续同步数据模型的领域。
相关
- 炭疽炭疽病(英语:anthrax)是由炭疽杆菌感染造成的疾病,感染途径包括皮肤接触、呼吸道、消化道以及注射等四种,通常在感染一天至两个月后开始出现症状,经由皮肤接触的感染起初会出现小
- 白细胞减少症白细胞减少症是指外周血液中白细胞数持续低于4×109/升时的症状。嗜中性粒细胞减少症是白细胞减少症的一种。顾名思义,这种病的表现是嗜中性粒细胞(白细胞中最常见的种类)的数
- 6号染色体人类的6号染色体是23对染色体的其中之一,正常状况下每个细胞拥有两条。此染色体含有大约170百万个碱基对,占细胞内所有DNA的5.5%到6%。其中约有2000到2057个基因 ,依预测方式而
- 飞秒化学飞秒化学(femtochemistry)是物理化学的一支,研究在极小的时间内化学反应的过程和机理;这一领域涉及的时间间隔短至约10-15秒,即1飞秒,这也就是名称的来源。1999年,艾哈迈德·泽维尔
- 定序DNA测序(DNA sequencing,或译DNA定序)是指分析特定DNA片段的碱基序列,也就是腺嘌呤(A)、胸腺嘧啶(T)、胞嘧啶(C)与鸟嘌呤(G)的排列方式。快速的DNA测序方法的出现极大地推动了生物学和医
- 法国电视一台坐标:48°50′1.9″N 2°15′38.3″E / 48.833861°N 2.260639°E / 48.833861; 2.260639法国电视一台(TF1)是法国的一家民营电视台,隶属于TF1 Group。工业集团布依格对该媒体
- 埃因霍温埃因霍温(荷兰语:Eindhoven)又译埃因霍温、爱因荷芬,旧译名安恒,是一个位于荷兰南部北布拉班特省的市镇,是荷兰的第五大城市。埃因霍温是欧洲领先的科技中心之一,地处西欧悠久科技
- 化学气相沉积化学气相沉积(英语:chemical vapor deposition,简称CVD)是一种用来产生纯度高、性能好的固态材料的化学技术。半导体产业使用此技术来成长薄膜。典型的CVD工艺是将晶圆(基底)暴露
- 小词不当小词不当(Illicit minor)是一种形式谬误,是因三段论中的小词在结论周延,而在小前提中不周延,而导致论证无效。例句:推理规则:例句分析结果:有效性检验:其他检验:猫是猫科动物,猫是哺乳
- 玛莉·居里玛丽亚·斯克沃多夫斯卡-居里(波兰语:Maria Skłodowska-Curie,1867年11月7日-1934年7月4日),通常称为玛丽·居里(法语:Marie Curie)或居里夫人(Madame Curie),波兰裔法国籍物理学家、化