摘 要： 20世纪中叶以来, 随着计算机的诞生及其对科学与社会日渐显现的影响力, 离散数学的思想和方法迅速发展, 展现出了更为多样和充满活力的知识形态。离散数学的知识创新具有典型的数学范式革命性。作为对微积分范式的一种突破, 离散数学超越了传统数学的知识界线, 展现出在数学本体论、认识论与方法论上的新的哲学特征。与计算机与信息科学的发展相得益彰, 离散数学范式具有离散化、算法化、计算性、复杂性以及与科学更为紧密的交互性等显着的当代科学革命特征, 并显现出学科知识群与复杂性科学等独特的意蕴。
关键词： 离散数学; 范式革命; 图灵计算; 量子计算; 计算复杂性;
Abstract： Since the middle of 20 thcentury, with the birth of computer and its increase effect on science and society, the thought and method of discrete mathematics have developed rapidly and new forms of knowledge with more multiple, tensions and vigor were emerged. The knowledge innovation of discrete mathematics has representative paradigm revolutionary character. As a breakthrough and transcending of the paradigm of calculus, the discrete mathematics has gone beyond the bound of traditional mathematics and showed new philosophical features in ontology, epistemology and methodology of mathematics. Complement with the development of computer and information science each other, the discrete mathematics demonstrated the contemporary scientific revolution features such as discretization, algorithmization, complexity and more tightly interaction with science, as well as the unique implication of group of disciplinary knowledge and complex science.
Keyword： discrete mathematics; paradigm revolution; turing machine; quantum computation; computational complexity;
20世纪中叶以来, 随着计算机的迅猛发展, 核心数学呈现出新的迹象。一种异于微积分的数学新范式———离散数学喷薄而出, 成为推动当代数学与科学发展的一种主导力量。离散数学是数学研究范式的一次重大转向。与20世纪的科学进步和革命相互辉映, 在离散数学领域中持续发生的数学知识创新与革命性突破书写了20世纪以来绚丽多彩、恢宏壮观的科学画卷, 成为当代科学革命的重要标志之一, 具有重要的科学里程碑意义。
1、 离散数学的知识创造及其发展
20世纪中叶以来, 数学的知识进步呈现出新的特征, 它从单纯的知识量的积累转变为产生一系列具有革命性意义的知识变革。而突破传统的微积分范式的知识创造也正在悄然发生。其中尤其是以离散数学的崛起和兴盛最具范式革命性意义。
离散数学是数学中若干分支的总称, 研究的对象是基于离散空间而不是连续空间的数学结构。离散数学的基本内容包括集合与数据结构、代数结构、计数理论、数值分析、数理逻辑、图论、自动机理论、递归函数、数论、组合数学、离散概率、计算群论、计算组合学、计算图论等。更一般地说, 离散数学可以被视为建立在可数集合之上的数学分支。与连续型数学模型相比, 由于计算机的运算在本质上是离散型的, 因而直接从实际问题建立离散的数学模型, 比传统上先建立连续的模型再予以离散化更为便捷。如此, 离散数学就创制了一种迥然不同于微积分连续数学的新范式———离散数学的知识范式。
1.1、 离散数学的理论准备与计算机时代“算法”的涵义
离散数学的异军突起与计算机的诞生密不可分。计算机的发明是人类科技史上一次重大的创造。受到计算机迅猛发展的影响, 20世纪后半叶以来, 数学发展开始从较为单一的微积分主线中分离出来, 离散数学的思想方法由于其与计算机的紧密联系而日益受到数学共同体的青睐。因为无论是具有多么强大功能的计算机, 也只能进行有限的计算和处理有限的数据。而不能完成实在无限的过程。这样, 微积分的思想和理论就不能直接用于计算机, 而必须做离散化的处理, 才能发挥其效力。离散数学的兴起, 是数学知识创新与当代科学发展交互作用的共同结果。作为一种新的数学范式, 离散数学在知识构成中有两个必备的数学理论条件。
第一个是集合论的语言与方法。19世纪末集合论的诞生, 使得数学研究对象获得了极大的扩展。在微积分范式中, 实数系 (最多到复数系) 构成了所有理论的基础性平台。在复变函数范式中, 复数系构成了其知识建构的平台。20世纪以来, 集合论替代了以前的各种平台, 成为几乎所有新的数学分支的主要平台。“对20世纪数学的另一个重大影响, 是康托尔在19世纪末把无穷集引入数学词汇。许多长期存在的问题, 可以用集论提供的丰富语言来重新描绘或重新解决”[1]。任何抽象的对象所构成的集合, 只要满足一定的条件、关系、规则和法则, 都可以成为数学的研究对象。因此, 集合论堪称数学知识范式的一场革命。集合论在离散数学具有特别重要的基础地位。
第二个是理论计算机的科学基础, 特别是其数学基础的形成、发展与成熟。值得注意的是, 计算机科学中许多重要的理论基础是从曾被认为是极为抽象和缺乏现实意义的数理逻辑和形式主义数学的研究中逐步发展起来的。例如数理逻辑, 20世纪30年代后, 随着哥德尔定理的诞生, 数理逻辑等纯粹数学研究出现了一些与理论计算机的诞生紧密相关的新的语境。其中一个重要的方向就是对“算法”的研究。“算法”有许多不同的定义, 其最朴素的含义是“一步接一步的方法”[2]。在计算机时代, “算法”特指的是与计算机的程序运行相关的计算方法1。
1.2、“计算”作为离散数学核心概念的革命性演进:从可计算到超级计算
20世纪后半叶以来, 以计算机的理论发展和应用为平台的离散数学体系开始迅猛发展, 并对传统的以连续数学为核心的数学知识结构与体系造成了巨大的挑战。由于计算机本质上是离散型的机器, 因此, 随着计算机的发明, 离散数学的思想、观念和方法的重要性开始在20世纪中叶以来的数学研究中日益显现出来。数学的核心领域发生的持续的知识更新与创造可谓日新月异。以下就以离散数学中最核心的概念之一———“计算”概念作为其知识范例, 对离散数学的革命性演进予以分析。
如果一个函数可以在规定的程序内通过有限步计算达到所需要的结果, 那么这样的函数就被称为“可计算”的。在这方面, 英国数学家图灵 (A.M.Turing) 的工作是开创性的和最为引人注目的。1936年, 剑桥大学国王学院年仅23岁的图灵发表了影响深远的论文“论可计算数及其在判定问题中的应用” (on computable numbers, with an application to the Entscheidungsproblem) 在这篇论文中, 图灵首次定义了“可计算数”的概念:“‘可计算’数可以简要地描述为其小数表达式可以通过有限方法加以计算的实数”[3]。图灵可计算性 (Turing computability) 和图灵机 (Turing machine) 的概念由此诞生2。图灵所研究的“可计算性” (computability) 以及图灵机TM (是Turing’s machines的缩写) 概念, 作为假想的理想机器, 图灵机奠定了最终导致计算机发明的理论基础。
随着理论计算机科学的不断发展, 人们又提出了“超计算” (hypercomputation) 的概念。所谓“超计算”是指“无法在图灵意义 (即一个计算者用纸和笔在有限步骤里进行的有效计算) 上进行计算的函数和数的计算”[5]。而以超级计算概念设计的超级计算机 (hypercomputer) 则超越了图灵机的范围, 能够进行更多的函数、数、问题解决和任何任务的计算。
1.3、 量子计算与量子计算机引领离散数学发展的新方向
近数十年来, 量子计算和量子计算机的概念开始逐步成为理论计算机科学研究的一个前沿。英国数学家阿迪亚 (M.Atiyah) 在着名的“20世纪的数学”一文中曾预测说:“21世纪将会是怎样的?我已经说了21世纪将会是量子数学的时代。……量子数学可能意味着我们能够尽我们所能地理解分析、几何、拓扑和各种各样的非线性函数空间的代数”[6]。这一预测可谓具有很好的前瞻性。在量子数学中, 一个迅猛发展的领域就是量子计算的概念。与电子计算机中的计算概念不同, 量子计算的概念与量子计算机紧密相关。量子计算机是建立在量子力学所使用的计算模型基础上的计算机[7]。
与“超级计算”的概念相比, “量子计算”具有更奇特的威力。量子计算的思想是物理学、数学与计算机科学的一个结合, 其想法源自于量子力学理论[8]。1982年, 在着名的“模拟物理与计算机”一文中, 量子计算机的开创者之一费因曼 (R.P.Feynman) 提出了依据量子力学公设获得量子计算的数学框架的设想[9]。1985年, 牛津大学的多伊奇 (D.Deutsch) 提出量子图灵机 (quantum Turing machine) 的概念, 量子计算开始具备了数学的基本型式[10]。
与传统的计算机不同, “潜在的量子计算机的核心是微观系统的能力, 一个原子或一个单个光子, 会同时处于超过一个的量子态———叠加的状态”[11]。一束激光可以把一个原子激发到一种兼具原态和激发态的叠加状态。如果这两种状态分别表示二进制的1和0, 叠加状态就可以立刻同时作用于两种值。一个量子计算机在叠加态时如果有n个原子, 就可以同时完成2n次运算, 这种并行度是传统电子计算机所无法比拟的。在量子计算中发展出了各种量子算法。其中, 量子绝热算法是一个研究热点。量子绝热算法 (quantum adiabatic algorithm) 以及量子绝热超级计算机 (The quantum adiabatic hypercomputer) 是近年来发展迅猛的量子计算领域。在量子计算中, 利用绝热量子演化原理进行计算的过程称为绝热量子计算。量子绝热进化算法可以有效地解决若干NP完全问题[12]。“绝热量子计算与传统量子计算在处理Hamilton量上本质的区别:前者并不以显式的酉变换改变系统Hamilton量来控制量子计算的过程, 而是设定绝热量子演化条件, 让系统在物理定律的支配下自行进行时间演化”[13]。
量子计算促进了数学与物理学更紧密的结合。量子计算的思想作为物理学、数学与计算机科学的一个美妙结合, 体现了数学、计算机和物理学的内在本质联系。量子计算作为一种新型算法, 体现了量子力学的基本思想在计算当中的威力。数学与物理学相互之间都给对方提供必要的方法 (包括算法) , 这是数学与物理学相互关系达到更高境界的基本标志。可以期待的是, 量子计算将成为未来数学知识的重要形态。
2 、离散数学的范式革命性及其特征
如何看待离散数学在当代数学中所扮演的角色?与之相应的一个首要问题是如何评价经典微积分范式在当代数学中的地位。拉尔斯顿 (A.Ralston) 在“离散数学会在重要性上超越微积分吗?”一文中给出的判断是:“随着纯数学在20世纪的快速增长, ‘数学之树’中根植于微积分的比例显着地下降了”[14]。拉尔斯顿特别强调了数值分析、算法、图论、多值逻辑、快速傅里叶变换、数理逻辑、计算复杂性等离散数学分支在当代数学和计算机科学中日益增长的重要性。概括起来, 离散数学有以下一些重要的革命性指向需要特别予以关注。
2.1 、离散数学具有突破并超越微积分范式的革命性指征
与微积分范式相比, 离散数学范式具有以下三个显着的革命性特征:第一, 从数学的应用性看, 离散数学具有与当代社会生产力形态更好的匹配力和适应性。“正如古典分析是在第一次工业革命中培育并得到发展的, 离散数学则是由第二次工业革命所支撑并得到进步的”[14]。第一次工业革命的对象是物质世界, 而第二次工业革命处理的是非物质———知识、通讯、信息等。相对来看, 微积分的应用对象是第一自然, 而离散数学的应用领域则更多的是人工自然。因此, 如果说与微积分相比, 离散数学处于数学发展的更高阶段, 这一判断是合理的。
第二, 离散数学范式具有与微积分范式迥然有别的思想方法、知识领域和知识结构。微积分用连续变化的观念去对客体做出一种刻画, 在许多情况下只是一种简单化和理想化。微积分假设了研究对象的许多理想的属性, 如连续, 可微, 光滑, 收敛, 一致收敛, 可积等。如果对象不具有这样的属性, 微积分思想方法就会出现散焦现象, 难以对这些对象进行很好的理论描绘。与微积分相比, 离散数学的突出特征之一就是离散化的思想与方法。而离散数学仅能处理有限对象, 或通过近似或逼近的方式接近潜在无限。这就使得离散数学具有可以直接处理客观对象的特征, 因为任何客观事物都是有限性的存在。从严格性和证明的角度看, 在离散数学中, 其严格性的标准与构造性和计算性紧密相关。比如, 在离散数学中对证明性的要求 (尤其是纯粹的存在性证明) 大幅降低, 而构造性的要求则大大提高。
第三, 在离散数学中, 猜测、算法、试错和计算机实验成为基本的方法, 这是数学方法论的重大转变, 具有典型的方法论革命意义。计算机辅助化成为做数学的基本方法, 如1976年阿佩尔和哈肯对四色定理的计算机证明, 就颠覆了传统数学手工证明的观念。计算机还有助于更多的数学发现, 典型的例子是对孤立子的研究。计算机实验也逐渐成为做数学的一种基本方式。贝克 (Alan Baker) 在“实验数学”一文中, 把“使用计算机”和“归纳支撑”作为“实验数学”的两个基本特征[15]。贾弗和奎因在“‘推测数学’:走向数学和理论物理的文化综合”一文中提出, 应该借鉴物理学中理论物理和实验物理的各自分工, 把数学分为“证明数学”和“假设数学”, 从而允许“推测数学”的存在[16]。
2.2、 离散数学与连续数学的范式差异性与可通约性
离散数学的诞生, 彻底改变了连续数学 (包括微积分理论以及与之密切相关的古典应用数学) 一统数学天下的格局。在计算机诞生之前, 连续数学在数学世界里可谓独一无二的王者。20世纪下半叶以来也许是连续数学 (以微积分为核心) 范式一枝独秀局面让位于与离散数学范式分庭抗礼的重要时期, 更准确地说是在范式的差异与转换中走向了两种范式的相互辉映。虽然在数学的发展中, 由于问题、理论、研究对象和方法的不同, 数学曾被分成纯粹数学和应用数学两大类。尽管在纯粹数学范式中, 连续数学依然占据着某些领域的统治地位, 但它们之间又不是截然分割和孤立的。
在离散数学与连续数学的范式关联性中, 库恩在科学革命的语境中所表达的范式之间的不可通约性遭受了挑战。表面上看起来, 离散数学范式似乎是对连续数学范式的一种远离或背离。然而, 这种背离却并不是沿着与连续数学完全相反的思想逻辑和方法路径行进的, 而是与之具有了一种范式可通约性。“连续的经典数学的世界与离散的当代计算是互补的”[17]。事实上, 纯粹数学从应用中获得的动力, 与应用数学从抽象理论中获得灵感, 都是有大量的案例的。正如有学者论证的, “纯粹数学与应用数学是不可分割地缠绕在一起的”[18]。连续数学的离散近似就是这样一种相互结合的知识典型。离散化关注将连续模型或等式转化为离散形式的过程, 通常是基于简化计算的目的。很多的连续数学概念都有离散数学的版本。
可以预见的是, 未来的数学发展必将使得连续数学与离散数学获得更为紧密和高层次的结合。已出现了许多把两者结合起来的数学理论创新。例如:离散微积分;离散概率分布;离散傅里叶变换;离散几何;离散对数;离散微分几何;离散外微分;离散莫尔斯理论;差分方程;离散动力系统等。在应用数学中, 离散模型是连续模型的离散近似。在离散模型中, 离散方程由数据所确定。使用递推、递归迭代等关系是这种建模的一般方法。由此, 传统意义上的微积分范式亦获得了计算机时代特有的离散数学思想方法的新内涵。因此, 两者之间进一步形成的张力和相互融合是未来数学发展值得期待的一个方向。
2.3 、计算机科学的发展推动传统数学并催生新的数学知识分支
计算机的广泛使用对数学研究具有积极的推动作用。例如着名难题四色问题就是被计算机证明的。在问题的求解过程中, 许多具有实用价值的数学分支如数论、分析几何、小波分析、仿生计算、数值计算中的有限单元方法等等都是与计算机和人工智能紧密相关的。以复动力系统来看, “近十多年来非常活跃的一个数学分支—复动力系统, 其研究起源于1920年前后法国数学家法图 (P.J.L.Fatou) 与朱里亚 (G.Julia) 的工作。当时, 他们已经对有理函数的动力系统作了很完整的研究, 然而没有电子计算机, 也缺乏数学上的一些准备, 这个领域沉寂了60年。1980年以后, 复动力系统引起了许多数学家的兴趣, 成为研究的热点之一。发生这样大变化的一个原因就是计算机的功用。借助于计算机, 可以将有理函数的朱里亚集完全描绘出来, 而朱里亚集是复动力系统里的一个最重要和基本的概念。当有理函数作一点微小的变化, 其朱里亚集就会产生很大的改变。许多实际对象, 比如一片树叶, 我们可以找到一个函数, 其朱里亚集与这片树叶的形状是一样的”[19]。我国着名数学家、科学院院士王梓坤教授把数学内部各分支间的相互渗透、数学与其他科学 (如控制论) 的相互渗透、电子计算机的出现看作是当代数学三个新的特点[20]。这一判断是准确和全面的。
离散数学不仅推动传统数学的发展, 而且催生了大量新的数学分支。例如, 在离散数学知识群中, AI (人工智能) 是一个近年来愈加活跃的领域。与计算机相比, 一般来说, 人脑具有处理模糊信息的能力, 善于判断和处理模糊现象。但计算机对模糊现象识别能力较差, 为了提高计算机识别模糊现象的能力, 就需要把人们常用的模糊语言设计成机器能接受的指令和程序, 以便机器能像人脑那样简洁灵活地做出相应的判断, 从而提高自动识别和控制模糊现象的效率。这就需要寻找一种描述和加工模糊信息的数学工具, 进而推动数学家深入研究模糊集合、模糊逻辑和模糊数学。
3 、离散数学知识创新的意义
离散数学的知识创新具有不同于连续数学的独特、深刻和显着的意义。作为一种数学家的工作哲学, 离散数学的哲学是活生生的、充满生机的与当下科技进步紧密相关的数学哲学。这种具有实践哲学倾向的数学范式缩小了数学与数学哲学的距离, 改变了传统数学哲学与实际数学研究脱节的局面, 堪称当代数学哲学实践转向的一个范例。
3.1 、离散数学开创了“学科群”知识新范式并赋予数学新的统一性
与传统数学相对孤立的学科类型相比, 离散数学具有数学不同分支的学科交互性。这种交互性体现在离散数学不是一个孤立的分支, 而是一个“学科群”, 即由一簇相互紧密关联的学科组成的知识集合。
数学的统一性是数学保持生命活力的一个基本前提。在离散数学范式获得主流数学地位之后, 一种新的数学统一性亦开始形成。这种统一性既不是依照“逻辑主义”或“元数学”的基础, 甚至也不是按照“结构主义”或“经验主义 (包括拟经验主义) ”的标准来获得的, 而是以不同学科的相互渗透、相互交叉为特点。阿迪亚这样描述了20世纪后半叶以来的数学发展特征:“20世纪的后半叶更多地是我愿意称之为‘统一的时代’。在这个时代里, 各个领域之间的界限被打破, 各种技术可以从一个领域转移到另一个领域, 不同事物的交叉性达到了空前的范围”[6]。在离散数学学科群中, 学科之间壁垒被打破, 不同学科之间相互交织、相互映衬, 学科之间没有严格的知识界线。离散数学范式不仅拓展了数学研究的领域和范围, 而且在更高的层次上实现了与以微积分为主体的连续数学的相得益彰和互补平衡, 使得数学在不同“子范式”和“学科群”的有机多样联系中实现了新的统一。
3.2 、对传统数学哲学本体论、认识论和方法论的突破与挑战
在离散数学范式中, 关注现实的数学、计算机、信息科学等前沿科学问题与其高度的、广覆盖率的应用性是其鲜明的特色。平考克 (C.Pincock) 在“走向应用数学哲学”一文中写道:“如果在当代数学哲学中有什么新的趋势可以称得上是‘新浪潮’的, 那肯定就是把注意力转向了对被工作数学家所热捧的实践与优先发展领域的呼唤”[21]。由于与计算机科学和信息科学等领域天然的和紧密的学科间性, 在离散数学范式及其共同体中, 许多传统的、形而上学色彩浓厚的数学哲学认识论话题、难点和焦点都变得不再重要或不再被关注。如数学哲学家贝纳塞拉夫在“数不可能是什么”一文中所提出的着名的“贝纳塞拉夫论证” (Benacerraf’s argument) , 已经很少有数学家关注, 因为他们在做数学时并没有担心数可能是什么这样的问题。再比如, 在柏拉图主义者和唯名论者之间的长期争论, 以及与人们关于数学知识的认识论困惑有关的话题, 都对“数学实践”没有什么影响[21]。
在数学本体论上, 离散数学的思想与方法超越了整体主义、形式主义和结构主义等思想所设定的阈值, 呈现出局部化、构造性、复杂性等学科特征。例如, 整体主义的一个基本假设是部分与整体的相似性;形式主义试图割裂语言与意义的丰富隐喻;而结构主义就认为复杂事物之间的层次关系是明晰的和可分离的。但在复杂性科学中, 情形常常并非如此。复杂性科学的一个基本观点就是认为, 事物之间具有复杂的关联, 这种关联不是完全可分解的。这种不可分解性表明, 事物之间的复杂关联未必能呈现出局部与整体的相似性。而形式语言的表征之丰富性亦正是语言与外部世界多样性隐喻的一个基本特征。
在方法论上, 离散数学的体系显现出对于“决定论”“还原论”和“整体论”思想的高度超越。在微积分范式中, 无论是在基础主义还是结构主义的各自主张中, 都有浓厚的“决定论”“还原论”和“整体论”色彩。比如, 在微积分范式中, 实数理论被看作是所有知识的基础。而在离散数学中, 即使是像最基本的算法和计算等概念, 也是随着知识创新被不断赋予新的含义的动态概念。离散数学的方法并不拘泥于任何既有的思想限定和方法论教条, 而是以可计算性、实效性和综合性为依归。
3.3、 计算复杂性具有典型的信息科学和复杂性科学思想特征
在离散数学中含有信息科学和复杂性科学的核心性概念和思想, 并且构成了信息科学和复杂性科学的一个知识范例。例如在可计算性理论中, 逐步发展出了计算复杂性理论。计算复杂性是计算机科学的复杂性理论和数值计算的复杂性理论的总称。参数化复杂性的开创者唐尼和菲洛斯认为, 计算复杂性的主题在当代科学中扮演着意义深远甚至是核心的角色[22]。在近年来日益炙手可热的大数据、云计算、互联网+的技术背景下整个科学研究范式的剧烈变革中, 计算复杂性的思想正扮演着越来越重要的角色。
计算复杂性的概念源自于图灵机 (TM) 在采用一种算法进行计算时的运算时间问题。有时候为了得到一个答案, 即使TM运行得足够快, 也仍然会出现TM会花费不切实际的运行时间的可能。比如, 假如你想去参观遍布于世界各地的50个旅游目的地。并且你也知道从一个目的地到另一个目的地所需的费用。具体取决于你从哪一个地方开始, 以及下一个目的地去哪里。这样, 你就有50! (即50的阶乘) 种旅游方案可以选择, 并可从中选取总费用最便宜的一种。而各种不同可能性的数目将是一个巨大的数字, 50!>10025。如果计算每次旅行这50个地点所需花销的时间仅需十亿分之一秒 (这已是相当快的了) , 那么要确定那次旅行的费用最低, 将用掉不少于1025次一个人一生的时间。因此, 仅仅满足于算法可解性是远远不够的, 还需要考虑实际可解性。这就涉及到TM所采用的计算模式以及TM运行的时间和空间。这正是计算复杂性所要考虑的问题[23]。
在计算机科学的复杂性理论中, 与时间复杂性相关的一个基本问题是复杂度类P与NP是否不相等3。显然, P?NP, 但P与NP是否相等, 却一直是一个没有解决的难题[24]。与之相关的还有NP难问题 (NP-hard) 和NP完全问题 (NP-completeness) 4。如果P=NP获证, 则NP完全的问题也能轻松获解;所有基于密钥的安全系统将失灵;数学证明也可以完全交给计算机来处理;所有的人工智能问题都将得到解决, 并且机器人能够完美地模拟人类的行为。无疑, 计算复杂性作为一种基本的复杂性现象, 是理解复杂性科学的一个很好的范本。
复杂性科学所引发的科学革命包含着一个重要的转换, 即“从线性的、可逆的、可还原的动力学的数学模型向非线性的、不可逆的、功能上不可还原的复杂的动力学模型 (特别是包括所有生命系统在内的复杂的适应系统) 的转换”[25]。富特 (R.Foote) 预测, “数学与物理的发展将会深刻地超越它们的历史源头。在更大的意义上, 数学自身的研究, 正在不断地超越研究者‘用手’验证的能力, 将会是根本的复杂系统”[26]。进而, 与自然科学的飞速进步相互辉映, 离散数学在这一场伟大的科学革命中所扮演的角色不可小觑。
参考文献
[1] Steen L A. The science of patterns[J]. Science, New Series, 1988, 240 (4852) :611-616.
[2] Jenkyns T, Stephenson B. Fundamentals of Discrete Math for Computer Science[M]. Springer, 2013, 4.
[3] Turing A M. On computable numbers, with an application to the Entscheidungsproblem[J]. Proceedings of the London Mathematical Society, Series 2, 1936, 42:230-265.
[4] Offermanns D S, Rosenthal D W. Encyclopedia of Molecular Pharmacology[M]. Springer, 1252.
[5] Copeland B J. Hypercomputation:Philosophical issues[J]. Theoretical Computer Science, 2004, 317 (1-3) , 251-267.
[6] Atiyah M. Mathematics in the 20th Century[J]. The American Mathematical Monthly, 2001, 108 (7) :654-666.
[7] Akama S. Elements of Quantum Computing[M].Springer International Publishing, Switzerland, 2015:1.
[8] Hagar A, Korolev A. Quantum hypercomputation—hype or computation?[J]. Philosophy of Science, 2007, 74 (3) :347-363.
[9] Feynman R P. Simulating physics with computers[J].International Journal of Theoretical Physics, 1982, 21 (6-7) :467-488.
[10] Ohya M, Volovich I. Mathematical Foundations of Quantum Information and Computation and Its Applications to Nano-and Bio-systems[M]. Springer, 2011:313.
[11] Taubes G. All together for quantum computing[J]. Science, New Series, 1996, 273 (5279) :1164.
[12] Kaynak O, Alpaydin E, Oja E, et al. Artificial Neural Networks and Neural Information Processing—ICANN/ICONIP 2003[M]. Springer, 2003, 951.
[13]吴楠, 宋方敏, 绝热量子计算[J].南京邮电大学学报 (自然科学版) , 2011, 31 (2) :19-26.
[14] Ralston A. Will discrete mathematics surpass calculus in importance?[J]. The College Mathematics Journal, 1984, 15 (5) :371-373.
[15] Baker A. Experimental mathematics[J]. Erkenn, 2008, 68 (3) :331-344.
[16] Jaffe A, Quinn F.“Theoretical mathematics”:Toward a cultural synthesis of mathematics and theoretical physics[J]. Bulletin (New Series) of the American Mathematical Society, 1993, 29 (1) :1-13.
[17] Tall D. Continuous mathematics and discrete computing are complementary, not alternatives[J]. The College Mathematics Journal, 1984, 15 (5) :389-391.
[18] Nishii R, et al. A Mathematical Approach to Research Problems of Science and Technology[M]. Springer, Japan, 2014:399.
[19]杨乐.数学与当代科技发展的关系[J].了望, 1994, (6) :37.
[20]中国科学院数学物理学部.今日数学及其应用[J].自然辩证法研究, 1994, 10 (1) :5.
[21] Bueno O, Linnebo?. New Waves in Philosophy of Mathematics[M]. Palgrave Macmillan, 2009:173.
[22] Downey R G, Fellows M R. Parameterized Complexity[M]. Springer, 1999:2.
[23] Singh A. Elements of Computation Theory[M]. Springer, 2009:327.
[24] Loebl M. Discrete Mathematics in Statistical Physics[M]. Germany, Vieweg+Teubner, 2010:5-6.
[25] Siegel H. Hooker’s revolutionary regulatory realism[J]. Study in History and Philosophy of Science, 1998, 29 (1) :129-141.
[26] Foote R. Mathematics and complex systems[J]. New Series, 2007, 318 (5849) :410-412.
注释
1 对算法的研究早在中国古代数学典籍《九章算术》中就开始了。在9世纪, 波斯数学家Al-Khowarizimi设计了一些做算术的方法。现代数学被开创以来, 算法被赋予了与数学知识特征相关的特点, 如微分与积分的计算方法、微分方程的计算方法、黎曼流形的计算方法等。在1900年在巴黎召开的国际数学家大会上, 着名数学家希尔伯特的23个着名问题中, 第10个就是一个关于算法的问题, 即能否通过有限步骤来判定丢番图方程 (即不定方程) 是否存在有理整数解? 1970年, 数学家Yuri Matiyasevich给出了否定答案, 即丢番图方程是图灵不可解的。
2 图灵计算, 亦称图灵计算机 (即TM) , 是一种具有理想装置的数学模型, 随着其内部状态、读取方式、书写方式的改变, 以及一个具有潜在无限带宽的变动, 都与其当前状态相互一致[4]。
3 P表示所有在多项式时间内可计算函数的类; NP则被定义为那些可以判断或验证的类。
4 NP难问题 (NP-hard) :如果每一语言L'∈NP都在多项式时间下可化约为L, 则语言L就被称为NP难的。和NP完全问题 (NPcompleteness) :如果一个语言L'∈NP且是NP难的, 则被称为NP完全的[23]。
