离散数学在计算机科学中的作用和应用

胡平芳 肖超

摘 要： 离散数学是计算机专业的一门专业基础课，在计算机科学中有重要而广泛的应用，是计算机专业课《数据结构》、《操作系统》、《编译原理》、《数据库系统原理》和《数字逻辑》等课的先导课程，因此离散数学是掌握计算机科学理论基础的重要数学工具。本文介绍了离散数学在计算机科学中的重要应用和应用。

关键词： 离散数学 计算机科学 数据结构

离散数学是计算机应用必不可少的工具，例如数理逻辑在数据模型、计算机语义、人工智能等方面的应用，集合论在数据库技术中的应用，代数系统在信息安全中的密码学方面的应用，图论在信息检索、网络布线、指令系统优化等方面的应用。

1.离散数学与其他课程的关系

1.1离散数学与数据结构的关系

离散数学与数据结构的关系非常紧密，数据结构课程描述的对象有四种，分别是线形结构、集合、树形结构和图结构，这些对象都是离散数学研究的内容。线形结构中的线形表、栈、队列等都是根据数据元素之间关系的不同而建立的对象，离散数学中的关系这一章就是研究有关元素之间的不同关系的内容；数据结构中的集合对象及集合的各种运算都是离散数学中集合论研究的内容；离散数学中的树和图论的内容为数据结构中的树形结构对象和图结构对象的研究提供很好的知识基础。

1.2离散数学与数据库原理的关系

目前数据库原理主要研究的数据库类型是关系数据库。关系数据库中的关系演算和关系模型需要用到离散数学中的谓词逻辑的知识；关系数据库的逻辑结构是由行和列构成的二维表，表之间的连接操作需要用到离散数学中的笛卡儿积的知识，表数据的查询、插入、删除和修改等操作都需要用到离散数学中的关系代数理论和数理逻辑中的知识。

1.3离散数学与数字逻辑的关系

数字逻辑为计算机硬件中的电路设计提供了重要理论，而离散数学中的数理逻辑部分为数字逻辑提供了重要的数学基础。在离散数学中命题逻辑中的连结词运算可以解决电路设计中的由高低电平表示的各信号之间的运算以及二进制数的位运算等问题。

1.4离散数学与编译原理的关系

编译原理和技术是软件工程技术人员很重要的基础知识，编译程序是非常复杂的系统程序，包括词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成、依赖机器的代码优化7个阶段。离散数学中的计算模型[2]这一章的语言和文法、有限状态机、语言的识别和图灵机等知识点为编译程序中的词法分析和语法分析提供了基础。

2.离散数学在计算机学科中的应用

2.1数理逻辑在人工智能中的应用

人工智能是计算机学科中一个非常重要的方向，离散数学在人工智能中的应用主要是数理逻辑部分在人工智能中的应用。人类的自然语言可以用符号进行表示。语言的符号化就是数理逻辑研究的基本内容，计算机智能化的前提就是将人类的语言符号化成机器可以识别的符号，这样计算机才能进行推理，才能具有智能。由此可见数理逻辑中重要的思想、方法及内容已贯穿人工智能的整个学科。

2.2图论在数据结构中的应用

离散数学在数据结构中的应用主要是图论部分在数据结构中的应用，树在图论中具有重要的地位。树是一种非线性数据结构，在现实生活中可以用树表示某一家族的家谱或某公司的组织结构，也可以用它来表示计算机中文件的组织结构，树中二叉树在计算机科学中有着重要的应用。二叉树共有三种遍历方法：前序遍历法、中序遍历法和后序遍历法。

通过访问不同的遍历序列，可以得到不同的节点序列，通常在计算机中利用不同的遍历方法读出代数表达式，以便在计算机中对代数表达式进行操作。

2.3集合论在数据库系统理论中的应用

集合論是离散数学中极其重要的一部分，它在数据库中有广泛的应用。我们可以利用关系理论使数据库从网络型、层次型转变成关系型，这样使数据库中的数据容易表示，并且易于存储和处理，使逻辑结构简单、数据独立性强、数据共享、数据冗余可控和操作简单。当数据库中记录较多时，集合中的笛卡儿积方便了记录的查询、插入、删除和修改。

2.4代数系统在通信方面的应用

代数系统在计算机中的应用广泛，例如有限机，开关线路的计数等方面。但最常用的是在纠错码方面的应用。在计算机和数据通信中，经常需要将二进制数字信号进行传递，这种传递常常距离很远，所以难免出现错误。通常采用纠错码避免这种错误的发生，而设计的这种纠错码的数学基础就是代数系统。

2.5离散数学在生物信息学中的应用

生物信息学是现代计算机科学中一个崭新的分支，它是计算机科学与生物学相结合的产物。由于DNA是离散数学中的序列结构，美国科学院院士，近代离散数学的奠基人Rota教授预言，生物学中的组合问题将成为离散数学的一个前沿领域。DNA计算机的基本思想是：以DNA碱基序列作为信息编码的载体，利用现代分子生物学技术，在试管内控制酶作用下的DNA序列反应，作为实现运算的过程；这样，以反应前DNA序列作为输入的数据，反应后的DNA序列作为运算的结果，DNA计算机几乎能够解决所有的NP完全问题。

3.结语

现在我国每一所大学的计算机专业都开设离散数学课程，正因为离散数学在计算机科学中的重要性，可以说没有离散数学就没有计算机理论，也就没有计算机科学。所以，应努力学习离散数学，推动离散数学的研究，使它在计算机中有更广泛的应用。

参考文献：

[1]朱家义，苗国义等.基于知识关系的离散数学教学内容设计[J].计算机教育，2010（18）：98-100.

[2]方世昌.离散数学.西安电子科技大学出版社，1985.

[3]陈敏，李泽军.离散数学在计算机学科中的应用[J].电脑知识与技术，2009，5（1）：251-252.

[4]B.Kolman，R.Busby&S.Ross.Discrete Mathematical Structure.

[5]李大友.离散数学.清华大学出版社，2001.

[6]龚静，王青川.数理逻辑在计算机科学中的应用浅析[J].青海科技，2004，（6）：53-54..