浅析离散数学在计算机科学中的应用

全文字数:2946

浅析离散数学在计算机科学中的应用

 [摘 要]：离散数学作为有力的数学工具,对计算机的发展,计算机科学的研究起着重大的作用.计算机科学中普遍地采用离散数学中的一些基本概念,基本思想,基本方法,使得计算机科学越趋完善与成熟.本文简单介绍了离散数学在计算机科学的几个不同领域中的应用,指出了离散数学在从事计算机及相关科学工作中的重要性 ．
 
 [关键词]：  离散  编译  关系演算  死锁  递归
 
 离散数学是现代数学的一个重要分支,是计算机科学中基础理论的核心课程.与我们以往接触的连续数学的不同之处在于:离散数学研究的对象一般都是有限或可数个元素,并且是以研究离散量的结构和相互之间的关系为主要目标的①,因此,它充分描述了计算机科学的离散性特点.离散数学是随着计算机科学的发展而逐步建立的,形成于20世纪70年代初.离散数学与计算机科学中的数据结构操作系统编译理论算法分析,逻辑设计,系统结构,容错诊断,机器定理证明等课程联系紧密②.下面我们就从几个不同的方面简单分析一下离散数学在计算机科学中的应用．
 一、图论在计算机科学中的应用。
 图论是离散数学中引入的一个重要理论,由此引出了数据结构中两个重要概念:图和树.改变了以往只能对线性结构对象加以分析处理的状况;有了图论做理论基础,我们才可以在编译程序中用树来表示源程序语法结构,产生了自顶向下和自下向上这两种不同的语法分析树;也正因为有了图论,在数据库系统中,我们才可以用树来组织信息,从而把各信息结点间的复杂关系用一种清晰直观的方式表示出来;同样,图论在操作系统中也得到了充分应用,最典型的例子是我们可以用图论中的回路来判断并发进程中是否存在递归和死锁现象,采用这种方法我们可以把一项本来很复杂的工作通过判断一个有向图中是否存在回路来加以解决,大大提高了工作效率.
    例 1.已知有四个进程:P1,P2,P3,P4和四个资源:R1,R2,R3,R4,其分配情况如下: 
       P1占有资源 R4且申请资源 R1
       P2占有资源 R1且 申请资源 R2及 R3
       P3占有资源 R2且申请资源 R3
       P4占有资源 R3且申请资源 R1及 R4
       试分析在该过程中有无死锁现象发生 ．
    解：其资源分配图为图 1：
    由图1当中存在的回路我们很容易得出该过程中有死锁发生.
    1956年,N.乔姆斯基(Noam．Chomsky)提出 了一种文法的数学模型,该数学模型为有穷自动机奠定了理论基础.有穷自动机是实现程序编译过程的基础核心部分,它的主要任务是准确识别正规集(即识别正规文法所定义的语言和正规式所表示的集合)③,而正规集(也就是我们常说的单词)是编译程序的基本组成部分,这一过程为编译过程中的第一个步骤——词法分析程序的自动构造找到了特殊的方法和工具,并为接下来编译的其它五个步骤提供分析与操作对象.
 二、离散数学中的关系及关系运算在计算机科学中的应用。
关系及关系运算是数学领域中的一个基本概念,离散数学中所涉及到的关系及其运算对研究计算机科学中的许多问题如数据库,数据结构,情报检索等都是很好的分析工具.我们常见的关系数据

相关论文