《离散数学》理论在计算机科学中的应用浅析

崔艳荣,陈 勇,黄艳娟

(长江大学计算机科学学院,湖北荆州434023)

《离散数学》是计算机科学核心基础课程,包含数理逻辑、集合论、代数系统和图论4部分,这4部分从不同的角度出发,研究各种离散量之间数与形的关系[1]。计算机科学解决的正是离散量的问题,因而 《离散数学》在计算机科学发展中起作不可替代的作用。许多学生在学习 《离散数学》的时候,只把 《离散数学》当成一门纯数学来对待,不了解其与计算机科学的关系。为此,笔者从数理逻辑、集合论、代数系统和图论4个方面阐述 《离散数学》与计算机科学的联系及其在计算机科学中的应用。

1 数理逻辑在计算机科学中的应用

数理逻辑是一门研究推理的逻辑学科,它为确定一个给出的论证是否有效提供各种法则和技巧,在计算机科学里用来检验程序的正确性和证明定理,同时在计算机科学的计算理论、算法分析与设计、程序设计、人工智能、计算机硬件系统等方面有着重要作用[2]。具体包括如下几方面:

1)为计算机模型和可计算性的研究提供依据 数理逻辑中的可计算谓词和计算模型中的可计算函数是等价的,互相可以转化,计算可以用函数演算来表达,也可以用逻辑系统来表达。逻辑系统能通过自身的无矛盾性保证这样一种计算模型是合理的,这就为图灵机及与它等价的计算模型提供了坚实的逻辑基础。

2)为计算机的设计与制造提供依据 计算机的各种运算是通过数字逻辑技术实现的,而代数和布尔代数是数字逻辑的理论基础,布尔代数在形式演算方面虽然使用了代数的方法,但其内容的实质仍然是逻辑。

3)为计算机程序设计语言提供主要思想 计算机程序设计语言的理论基础是形式语言、自动机与形式语义学,数理逻辑的代数为形式语言、自动机和形式语义学提供了主要思想和方法,程序设计语言中的许多机制和方法,如子程序调用中的参数代换、赋值等都出自数理逻辑的方法。

此外,在语言的语义研究中,4种语义方法最终可归结为代数和逻辑的方法,而且,程序的语义及其正确性的理论基础仍然是数理逻辑或者进一步的模型论。另外,在计算机体系结构的研究中,像容错计算机系统、Transputer计算机、阵列式向量计算机、可变结构的计算机系统结构及其计算模型等都直接或间接与逻辑及其代数密不可分。

2 集合论在计算机科学中的应用

集合论包括集合、关系和函数3部分。

1)集合 集合不仅可以表示数,而且可以像数一样进行运算,还可以用于非数值信息的表示和处理,如数据的增加、删除、排序以及数据间关系的描述,有些很难用传统的数值计算来处理的问题,却可以用集合来处理。因此,集合论在程序语言、数据结构、数据库与知识库、形式语言和人工智能等领域得到了广泛应用。

2)关系 关系也广泛地应用于计算机科学技术中,例如计算机程序的输入和输出关系、数据库的数据特性关系和计算机语言的字符关系等,是数据结构、情报检索、数据库、算法分析、计算机理论等计算机领域中的良好数据工具。另外,关系中划分等价类的思想也可用于求网络的最小生成树等图的算法中。

3)函数 函数可以看成是一种特殊的关系,计算机中把输入、输出间的关系看成是一种函数。类似地,在开关理论、自动机原理和可计算性理论等领域中,函数都有极其广泛的应用,其中双射函数是密码学中的重要工具。

3 代数系统在计算机科学中的应用

代数系统是一种数学结构,代数的概念和方法是研究计算机科学的重要数学工具。在利用计算机科学解决实际问题时都离不开数学模型,而构造一个现象或过程的数学模型就需要某种数学结构,而代数结构就是最常用的数学结构之一。如描述机器可计算的函数、研究算法计算的复杂性、刻画抽象数据结构、程序设计语言的语义学基础、逻辑电路设计和编码理论等都需要代数知识。代数系统中的群论在计算机安全领域得到广泛关注,比如有名的椭圆曲线算法,半群在形式语言与自动机中都有具体的应用。另外,计算机科学中的有限自动机理论、开关网络理论、计算机逻辑设计等领域都直接地应用了布尔代数的结论。

4 图论在计算机科学中的应用

图论在计算机科学中扮演中重要的角色,为计算机科学中的形式语言、数据结构、分布式系统、操作系统、计算机网络等提供了有力的数学工具。特别是图论中的最小支撑树、最短通路、最大匹配、网络流、中国邮递员问题和旅行售货员等问题在计算机科学中都有着广泛的应用[3]。

5 结 语

数理逻辑、集合论、代数系统和图论是 《离散数学》的4大部分,笔者分析了上述内容在计算机科学中的应用。在 《离散数学》的教学中,应根据不同的知识点,给学生分析与讲解 《离散数学》在计算机科学中的重要作用,改变学生把 《离散数学》当纯数学学习的想法,进一步地提高学生的学习兴趣,从而取得良好的教学效果。

[1]傅彦,顾小丰,王庆先,等.离散数学及其应用[M].北京:高等教育出版社,2007.

[2]傅彦,王丽杰,尚明生,等.离散数学实验与习题解析[M].北京:高等教育出版社,2007.

[3]周强,孙树朴.图论及其在计算机科学中的应用[M].北京:中国矿业大学出版社,1995.