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

《离散数学在计算机科学中作用与应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、离散数学在计算机科学中作用与应用　　摘要：离散数学是计算机专业的一门专业基础课，在计算机科学中有重要而广泛的应用，是计算机专业课《数据结构》、《操作系统》、《编译原理》、《数据库系统原理》和《数字逻辑》等课的先导课程，因此离散数学是掌握计算机科学理论基础的重要数学工具。本文介绍了离散数学在计算机科学中的重要应用和应用。关键词：离散数学计算机科学数据结构离散数学是计算机应用必不可少的工具，例如数理逻辑在数据模型、计算机语义、人工智能等方面的应用，集合论在数据库技术中的应用，代数系统在信息安全中的密码学方面的应

2、用，图论在信息检索、网络布线、指令系统优化等方面的应用。1.离散数学与其他课程的关系1.1离散数学与数据结构的关系5离散数学与数据结构的关系非常紧密，数据结构课程描述的对象有四种，分别是线形结构、集合、树形结构和图结构，这些对象都是离散数学研究的内容。线形结构中的线形表、栈、队列等都是根据数据元素之间关系的不同而建立的对象，离散数学中的关系这一章就是研究有关元素之间的不同关系的内容；数据结构中的集合对象及集合的各种运算都是离散数学中集合论研究的内容；离散数学中的树和图论的内容为数据结构中的树形结构对象和图结

3、构对象的研究提供很好的知识基础。1.2离散数学与数据库原理的关系目前数据库原理主要研究的数据库类型是关系数据库。关系数据库中的关系演算和关系模型需要用到离散数学中的谓词逻辑的知识；关系数据库的逻辑结构是由行和列构成的二维表，表之间的连接操作需要用到离散数学中的笛卡儿积的知识，表数据的查询、插入、删除和修改等操作都需要用到离散数学中的关系代数理论和数理逻辑中的知识。1.3离散数学与数字逻辑的关系数字逻辑为计算机硬件中的电路设计提供了重要理论，而离散数学中的数理逻辑部分为数字逻辑提供了重要的数学基础。在离散数学

4、中命题逻辑中的连结词运算可以解决电路设计中的由高低电平表示的各信号之间的运算以及二进制数的位运算等问题。1.4离散数学与编译原理的关系5编译原理和技术是软件工程技术人员很重要的基础知识，编译程序是非常复杂的系统程序，包括词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成、依赖机器的代码优化7个阶段。离散数学中的计算模型[2]这一章的语言和文法、有限状态机、语言的识别和图灵机等知识点为编译程序中的词法分析和语法分析提供了基础。2.离散数学在计算机学科中的应用2.1数理逻辑在人工智能中的应用人工

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

6、的家谱或某公司的组织结构，也可以用它来表示计算机中文件的组织结构，树中二叉树在计算机科学中有着重要的应用。二叉树共有三种遍历方法：前序遍历法、中序遍历法和后序遍历法。通过访问不同的遍历序列，可以得到不同的节点序列，通常在计算机中利用不同的遍历方法读出代数表达式，以便在计算机中对代数表达式进行操作。2.3集合论在数据库系统理论中的应用5集合论是离散数学中极其重要的一部分，它在数据库中有广泛的应用。我们可以利用关系理论使数据库从网络型、层次型转变成关系型，这样使数据库中的数据容易表示，并且易于存储和处理，使逻辑

7、结构简单、数据独立性强、数据共享、数据冗余可控和操作简单。当数据库中记录较多时，集合中的笛卡儿积方便了记录的查询、插入、删除和修改。2.4代数系统在通信方面的应用代数系统在计算机中的应用广泛，例如有限机，开关线路的计数等方面。但最常用的是在纠错码方面的应用。在计算机和数据通信中，经常需要将二进制数字信号进行传递，这种传递常常距离很远，所以难免出现错误。通常采用纠错码避免这种错误的发生，而设计的这种纠错码的数学基础就是代数系统。2.5离散数学在生物信息学中的应用生物信息学是现代计算机科学中一个崭新的分支，它是

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