离散数学的应用.pdf

离散数学在其他学科及现实生活中的应用 一、离散数学概论 离散数学是现代数学的一个重要分支，也是计算机专业课程体系中地位极为重要的专业 基础课之一。它以研究离散量的结构及相互关系为主要目标，充分描述了计算机科学离散性 的特点。该课程是数据结构、操作系统、计算机网络、算法设计与分析、软件工程、人工智 能、形式语言、编译原理等计算机本科阶段核心课程的基础，也是组合数学、遗传算法、数 据挖掘等计算机硕士研究生阶段相关课程的重要基础。 离散数学的主要内容包括集合论、数理逻辑、代数结构和图论四部分。数理逻辑与代数 结构的研究思想和研究方法在计算机科学中的许多研究领域得到了广泛的应用，解决了大量 的计算机科学问题。数理逻辑是研究推理的学科，在人工智能、程序理论和数据库理论等的 研究中有重要的应用。代数结构是关于运算或计算规则的学问，在计算机科学中，代数方法 被广泛应用于许多分支学科，如可计算性与计算复杂性、形式语言与自动机、密码学、网络 与通信理论、程序理论和形式语义学等。集合论和图论在计算机科学中也有广泛的应用，他 们为数据结构和算法分析奠定了数学基础，也为许多问题从算法角度如何加以解决提供了进 行抽象和描述的一些重要方法。 离散数学不仅是计算机技术迅猛发展的支撑学科，更是提高学生逻辑思维能力、创造性 思维能力以及形式化表述能力的动力源，为他们今后处理离散信息，从事计算机应用、信息 管理和计算机科研打下扎实的数学基础。中国科学院也已成立了离散数学研究中心，并得到 国家的重点资助。 二、应用 2.1 离散数学在计算机学科中的应用 计算机学科主要脱胎发源于数学学科，离散数学是现代数学的一个重要分支，是计算机 科学中基础理论的核心课程。由于计算机科学的迅速发展，与其有关的领域中，提出了许多 有关离散量的理论问题，需要用某些数学的工具做出描述和深化。离散数学把计算机科学中 所涉及到的研究离散量的数学综合在一起，进行较系统的、全面的论述，为研究计算机科学 的相关问题提供了有力的工具。计算机要解决一个具体问题，必须运用数据结构知识。对于 问题中所处理的数据，必须首先从具体问题中抽象出一个适当的数学模型，然后设计一个解 此数学模型的算法，最后编出程序，进行测试、调整直至得到问题的最终解答。而寻求数学 模型就是数据结构研究的内容。寻求数学模型的实质是分析问题，从中提取操作的对象，并 找出这些操作对象之间含有的关系，然后用数学的语言加以描述。数据结构中将操作对象间 的关系分为四类：集合、线性结构、树形结构、图状结构或网状结构。数据结构研究的主要 内容是数据的逻辑结构，物理存储结构以及基本运算操作。其中逻辑结构和基本运算操作来 源于离散数学中的离散结构和算法思考。离散数学中的集合论、关系、图论、树四个章节就 反映了数据结构中四大结构的知识。如集合由元素组成，元素可理解为世上的客观事物。关 系是集合的元素之间都存在某种关系。例如雇员与其工资之间的关系。图论是有许多现代应 用的古老题目。伟大的瑞士数学家列昂哈德·欧拉在18 世纪引进了图论的基本思想，他利 用图解决了有名的哥尼斯堡七桥问题。还可以用边上带权值的图来解决诸如寻找交通网络里 两城市之间最短通路的问题。而树反映对象之间的关系，如组织机构图、家族图、二进制编 码都是以树作为模型来讨论。 有时人们也把离散数学和图论加在一起算成是离散数学。作为计算机出现以后迅速发展 起来的一门数学分支。计算机科学就是算法的科学，而计算机所处理的对象是离散的数据， 所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是离散数学。 离散数学的发展改变了传统数学中分析和代数占统治地位的局面。现代数学可以分为两大 类：一类是研究连续对象的，如分析、方程等，另一类就是研究离散对象的离散数学。微积 分和近代数学的发展为近代的工业革命奠定了基础。而离散数学的发展则奠定了本世纪的计 算机革命的基础。计算机之所以被称为电脑，就是因为计算机被人编写了程序，而程序就是 算法，在绝大多数情况下，计算机的算法是针对离散的对象，而不是在作数值计算。正是因 为有了离散算法才使人感到计算机好像是有思维的。 2.2 离散数学在人工智能中的应用 人工智能是计算机学科中一个非常重要的方向,离散数学在人工智能中的应用主要是数 理逻辑部分在人工智能中的应用。数理逻辑包括命题逻辑和谓词逻辑,命题逻辑就是研究以 命题为单位进行前提与结论之间的推理,而谓词逻辑就是研究句子内在的联系。大家都知道, 人工智能共有两个流派,连接主义流派和符号主义流派。其中在符号主义流派里,他们认为现