离散数学在计算机学科中的作用.docVIP

离散数学在计算机学科中的作用 　　摘要:离散数学和计算机科学关系密切,是计算机科学与技术的理论基础。作为有利的数学工具,对计算机的发展与计算机科学的研究起着重大的作用。本文阐述了离散数学在计算机学科不同领域中的应用,分析了离散数学与计算机专业其他学科间的关系,突出其在计算机学科中的作用。 　　Abstract: Discrete mathematics is closely related to computer science; it is the theory basis for computer science and technology. As favorable mathematical tool, it plays a major role in the development of computers and computer science research. In this paper, the application of discrete mathematics in computer science in different areas is described. the relationship among discrete mathematics and computer science and other disciplines is analyzed, highlighting its role in computer science. 　　关键词:离散数学;数据结构;编译原理;数据库原理;人工智能 　　Key words: discrete mathematics; data structure;compiler theory;database theory;artificial intelligence 　　中图分类号:TP3-05 文献标识码:A文章编号:1006-4311(2010)21-0215-01 　　 　　0引言 　　离散数学是计算机科学与技术专业的核心、骨干课程。一方面,它给后继课程,如数据结构、编译原理、数据库原理和人工智能等,提供必要的数学基础;另一方面,通过学习离散数学,可以培养和提高学生的抽象思维和逻辑推理能力,为其今后继续学习和工作,进行科学研究,打下扎实的数学基础。 　　离散数学主要研究离散量的结构和相互间的关系,其内容非常广泛,主要包括集合论、关系、映射、近世代数、图论、命题逻辑、谓词逻辑。该课程概念多、理论性强、高度抽象,学生学习起来困难很大,缺乏学习兴趣,因此从计算机专业的角度讨论离散数学在计算机学科中的作用,对后续计算机专业课程的影响,对调动学生学习积极性、提高学习兴趣将有很大帮助。 　　1离散数学在计算机学科中的作用 　　1.1 离散数学在数据结构中的应用数据结构研究的主要内容是数据的逻辑结构,存储结构以及基本运算操作。其中逻辑结构和基本运算操作来源于离散数学中的离散结构和逻辑思维。数据的逻辑结构分为四类:集合、线性结构、树形结构、图型结构,这正是离散数学中要研究的主要内容。如集合由元素组成,元素可理解为数据结构中的数据元素、记录、结点、顶点。关系是集合中元素之间都存在某种关系,例如学生表中班级同学之间的关系,家谱中祖先与子孙之间的关系。图论中的欧拉图解决了著名的哥尼斯堡七桥问题,还可以利用弗洛伊德算法解决交通网络中任意两个城市之间最短距离问题。树反映了数据对象之间的一对多关系,如组织机构图、家谱、资源管理器、通信中的哈夫曼编码都是以树为模型来讨论的。 　　1.2 离散数学在编译原理中的应用编译原理是计算机学科中比较高深的专业课,编译程序是计算机的一个十分复杂的系统程序。一个典型的编译程序一般都含有八个部分:词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、错误检查和处理程序、各种信息表格的管理程序。离散数学里的计算模型章节里就讲了三种类型的计算模型:文法、有限状态机和图灵机。具体知识有语言和文法、带输出的有限状态机、不带输出的有限状态机、语言的识别、图灵机等。短语结构文法根据产生式类型来分类:0型文法、1型文法、2型文法、3型文法。以上这些在离散数学里讲述到的知识点在编译原理的词法分析及语法分析中都会用到。因此,离散数学也是编译原理的前期基础课程,也为今后研究生课程――形式语言与自动机打下基础。 　　1.3 离散数学在数据库原理中的应用现代数据库技术广泛应用于社会各个领域,数据库是计算机管理数据的一种机构,关系数据库已经成为数据库的主流。离散数学中的笛卡儿积、关系是一个纯数学理论,是研究关系数据库的一种重要方法,不仅为其提供理论和方法上的支持,更重要的是推动了数据库技术的研究和发展。关