离散数学在计算机科学中的应用
首先简单介绍一下离散数学的定义及其在各学科领域的重要作用。离散数学(Discretemathematics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。
随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。
由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型；又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。
由此可见，离散数学在计算机科学中具有广泛的应用，下面我将一一陈述。
1离散数学在关系数据库中的应用
关系数据库中的数据管理系统向用户提供使用的数据库语言称为数据子语言，它是以关系代数或谓词逻辑中的方法表示。由于用这种数学的方法去表示，使得对这些语言的研究成为对关系代数或逻辑谓词的研究，优化语言的表示变成为对关系代数与谓词逻辑的化简问题。由于引入了数学表示方法，使得关系数据库具有比其它几种数据库较为优越的条件。正因为如此关系数据库迅速发展成为一种很有前途、很有希望的数据库。另外，离散数学中的笛卡儿积是一个纯数学理论，是研究关系数据库的一种重要方法，显示出不可替代的作用。不仅为其提供理论和方法上的支持，更重要的是推动了数据库技术的研究和发展。关系数据模型建立在严格的集合代数的基础上，其数据的逻辑结构是一个由行和列组成的二维表来描述关系数据模型。在研究实体集中的域和域之间的可能关系、表结构的确定与设计、关系操作的数据查询和维护功能的实现、关系分解的无损连接性分析、连接依赖等问题都用到二元关系理论。
2离散数学在数据结构中的应用
计算机要解决一个具体问题，必须运用数据结构知识。对于问题中所处理的数据，必须首先从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编出程序，进行测试、调整直至得到问题的最终解答。而寻求数学模型就是数据结构研究的内容。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。数据结构中将操作对象间的关系分为四类：集合、线性结构、树形结构、图状结构或网状结构。数据结构研究的主要内容是数据的逻辑结构，物理存储结构以及基本运算操作。其中逻辑结构和基本运算操作来源于离散数学中的离散结构和算法思考。离散数学中的集合论、关系、图论、树四个章节就反映了数据结构中四大结构的知识。如集合由元素组成，元素可理解为世上的客观事物。关系是集合的元素之间都存在某种关系。例如雇员与其工资之间的关系。图论是有许多现代应用的古老题目。伟大的瑞士数学家列昂哈德·欧拉在18世纪引进了图论的基本思想，他利用图解决了有名的哥尼斯堡七桥问题。还可以用边上带权值的图来解决诸如寻找交通网络里两城市之间最短通路的问题。而树反映对象之间的关系，如组织机构图、家族图、二进制编码都是以树作为模型来讨论。
3离散数学在编译原理中的应用
编译程序是计算机的一个十分复杂的系统程序。一个典型的编译程序一般都含有八个部分：词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、错误检查和处理程序、各种信息表格的管理程序。离散数学里的计算模型章节里就讲了三种类型的计算模型：文法、有限状态机和图灵机。具体知识有语言和文法、带输出的有限状态机、不带输出的有限状态机、语言的识别、图灵机等。短语结构文法根据产生式类型来分类：0型文法、1型文法、2型文法、3型文法。以上这些在离散数学里讲述到的知识点在编译原理的词法分析及语法分析中都会用到。因此，离散数学也是编译原理的前期基础课程。
4离散数学在人工智能中的应用
在人工智能的研究与应用领域中，逻辑推理是人工智能研究中最持久的子领域之一。逻辑是所有数学推理的基础，对人工智能有实际的应用。采用谓词逻辑语言的演绎过程的形式化有助于我们更清楚地理解推理的某些子命题。逻辑规则给出数学语句的准确定义。离散数学中数学推理和布尔代数章节中的知识就为早期的人工智能研究领域打下了良好的数学基础。许多非形式的工作，包括医疗诊断和信息检索都可以和定理证明问题一样加以形式化[8]。因此，在人工智能方法的研究中定理证明是一个极其重要的论题。在这里，推理机就是实现(机器)推理的程序。它既包括通常的逻辑推理，也包括基于产生式的操作。推理机是使用知识库中的知识进行推理而解决问题的。所以推理机也就是专家的思维机制，即专家分析问题、解决问题的方法的一种算法表示和机器实现。
5离散数学在计算机硬件设计中的应用
数字逻辑作为计算机的一个重要理论，在很大程度上起源于离散数学的数理逻辑中的命题与逻辑演算，其在计算机硬件设计中的应用更为突出。利用命题中各关联词的运算规律把又电平表示的各信号之间的运算于二进制数之间的运算联系起来，使得我们可以用与非门或者用或非门来解决电路设计问题，使得整个设计过程更加直观、系统化。数理逻辑在程序设计中起到花间的作用，当一个程序初稿拿出来以后，如果我们想分析一下其中是否有冗余存在，这时就用到了离散数学中命题演算的基本等式。
6.代数系统在通信方面的应用
代数系统在计算机中的应用广泛,例如有限机,开关线路的计数等方面。但最常用的是在纠错码方面的应用。在计算机和数据通信中,经常需要将二进制数字信号进行传递,这种传递常常距离很远,所以难免会出现错误。通常采用纠错码来避免这种错误的发生,而设计的这种纠错码的数学基础就是代数系统。纠错码中的一致校验矩阵就是根据代数系统中的群概念来进行设计的,另外在群码的校正中,也用到了代数系统中的陪集。
7离散数学在生物信息学中的应用
生物信息学是现代计算机科学中一个崭新的分支,它是计算机科学与生物学相结合的产物。目前,在美国有一个国家实验室Sandia国家实验室,主要进行组合编码理论和密码学的研究,该机构在美国和国际学术界有很高的地位。另外,由于DNA是离散数学中的序列结构,美国科学院院士,近代离散数学的奠基人Rota教授预言,生物学中的组合问题将成为离散数学的一个前沿领域。而且,IBM公司也将成立一个生物信息学研究中心。在1994年美国计算机科学家阿德勒曼公布了DNA计算机的理论,并成功地运用DNA计算机解决了一个有向哈密尔顿路径问题,这一成果迅速在国际产生了巨大的反响,同时也引起了国内学者的关注。DNA计算机的基本思想是:以DNA碱基序列作为信息编码的载体,利用现代分子生物学技术,在试管内控制酶作用下的DNA序列反应,作为实现运算的过程;这样,以反应前DNA序列作为输入的数据,反应后的DNA序列作为运算的结果,DNA计算机几乎能够解决所有的NP完全问题。
8结论
现在我国每一所大学的计算机专业都开设离散数学课程,正因为离散数学在计算机科学中的重要应用,可以说没有离散数学就没有计算机理论,也就没有计算机科学。所以,应努力学习离散数学,推动离散数学的研究,使它在计算机中有着更为广泛的应用。
参考文献：
《离散数学》——百度百科
《浅析离散数学在计算机科学中的应用》——齐齐哈尔大学学报
黄万徽《离散数学在关系数据库中的应用》
陶跃《离散数学在计算机纠错码中的应用》
陈敏，李泽民《离散数学在计算机科学中的应用》
王蕾，李永华《浅析离散数学在计算机科学中的应用》
耿素云，屈婉玲，《离散数学》高等教育出版社，1998
左孝凌，李永监，刘永才，《离散数学》上海科学技术文献出版社，2004
朱一清，《离散数学》电子工业出版社，2004
科学网—人工智能的基石是数学
中国科学院院士徐宗本：人工智能的基石是数学
■本报见习记者程唯珈
“人工智能的基石是数学，没有数学基础科学的支持，人工智能很难行稳致远。”近日，由联合国教科文组织和中国工程院联合主办的联合国教科文组织国际工程科技知识中心2019国际高端研讨会上，中国科学院院士、西安交通大学教授徐宗本在题为《AI与数学：融通共进》的主题报告上如是说。
在他看来，目前人工智能所面临的一些基础问题，其本质是来自数学的挑战。
数学家眼里的人工智能是什么？徐宗本给出的答案简洁明了：当下主要指机器学习。
如果给这个名词赋予一个说明，他认为这是人或者智能体，通过与环境的交互来提升自身行为和解决问题能力的智能化操作。“机器学习是把这种智能形式化为数学公式，转换成计算机可以操作的算法和软件。”他说。
进一步说，人工智能实际上是一个将数学、算法理论和工程实践紧密结合的领域。将其剖开来看，就是算法，也就是数学、概率论、统计学、各种数学理论的体现。
不过徐宗本认为，作为人工智能基石的数学，还存在五大核心问题待解，而这也是制约人工智能进一步发展的“绊脚石”。
第一是大数据的统计学基础。徐宗本认为，人工智能和大数据是一对“孪生姐妹”。人工智能更多指应用模式，强调与领域知识的结合。大数据则是最底层的信息技术，强调机器和机器、机器与人之间的内容交互与理解。但是当前，分析大数据的统计学基础面临颠覆，应用于复杂大数据分析的极限理论、统计推断方法、真伪判定等数学基础尚未完全建立起来。
第二是大数据计算基础算法。一般而言，理解和分析大数据都是通过数据处理或数据分析来实现的，而无论是数据处理还是数据分析，最终都归于求解一系列基本的数学问题，如线性方程组求解、图计算、最优化计算、高维积分等。不过，这些看似早已解决的问题在大数据情形下却成了“拦路虎”。
他以旅游为例，打了一个生动的比方来解释这种挑战。“比如从西安到北京，怎么走最近？过去地图分辨率不高，根据普通的地图可以获取基本的路线。但现在大数据背景下，地图的分辨率越来越高，不可能一次就涵盖西安至北京之间全部城市与道路的数据，只能一次一次地提供其中某些城市间的道路信息。到达北京需要多少时间，怎样走最近？要带多少钱？现在的机器还回答不了这些问题。这是由于在分布式图信息环境下，图计算的基础算法问题还没有解决。”徐宗本说。
第三是深度学习的数学理论。徐宗本认为，这个问题在当下尤为关键。新一轮的人工智能多以深度学习为基本模型，然而深度学习的设计基础在哪里，什么样的结构决定了什么样的性能，能不能有台劳公式和富里埃级数这样的数学表示理论，这些基本的理论问题还没有解决。正是由于这个原因，现在的人工智能还得靠“人工”来换“智能”，这也是造成当下“人工智能=人工+智能”的原因。
第四是非常规约束下的最优输运。人工智能的很多问题都可归纳为两个领域数据打通问题，即让两个对象在满足某一个特定的不变量情况下互相转移。“比如中英文互译，就是在保持语义的情况下将中文数据转换成英文数据。”
应用到现实，徐宗本畅想，将医院的CT和核磁共振图像相互转移或能很好地解决医疗诊断的信息不足问题。“因为照的是同一个人，这里人就是不变量。要解决这些问题，建立特定约束下实现最优传输的数学理论与方法是基本的。”
第五是关于学习方法论的建模与函数空间上的学习理论。徐宗本表示，研究生阶段学到的机器学习理论，需上升到方法论学习的阶段。
“从数学上说，无论函数空间上的学习理论怎么建立，本质是要适应不同的任务。由于任务本身是函数，是无穷的，那么就需要把过去机器学习中对样本、数据的选择、泛化，推广到对任务的选择、泛化中。”
如果辩证地看待数学和人工智能的关系，相辅相成可能是其最好的诠释。徐宗本表示，不仅数学可为人工智能提供基础，人工智能也为数学研究提供新的方法论。
“比如解偏微分方程，过去人们可能会使用计算机，现在用人工智能可以做得更好。”他认为，让数学中的模型方法与人工智能的数据方法结合，可将机器的深度学习应用得更加精确。
面对如今发展得如火如荼的人工智能产业，徐宗本也道出了自己对从业者的希冀。
“人工智能想要做得好，要靠数学问题尤其是算法的解决。”徐宗本再次强调，从业者应潜心从基础研究抓起，使我国的应用场景优势真正转化为技术优势和产业优势。
《中国科学报》(2019-11-04第4版综合)