《简论计算机与离散数学.doc》由会员分享，可在线阅读，更多相关《简论计算机与离散数学.doc（3页珍藏版）》请在金锄头文库上搜索。
1、简论计算机与离散数学离散数学: 离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。 数学和计算机的关系非常密切。一直到二三十年以前，
2、计算机科学本身还是数学学科的一个分支，最早研究计算机的专家也都是数学家。在计算机进行运算的基本原理中，处处渗透着数学的各种思想。而现在，计算机科学已经深受人们的关注，成为了一个独立的学术领域，这之间离不开数学理论的推动；反之，从数学的发展来看，不仅可以利用计算机解决大量人工无法实现的巨量计算问题，很多难以证明的定理还可以通过计算机完成证明；程序，作为数学与计算机之间的一座重要桥梁，在数学的发展，计算机的应用方面起着双重的推动作用。 随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。离散数学课程所传授的思想和方法，广泛地体现在计算
3、机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。 由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系， 因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型；又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。 离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业
4、课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。以下是计算机与离散数学之间最为突出的六个联系1 离散数学在关系数据库中的应用2 离散数学在数据结构中的应用3 离散数学在编译原理中的应用4 离散数学在人工智能中的应用5 离散数学在计算机硬件设计中的应用6 离散数学在计算机纠错码中的应用1 离散数学在关系数据库中的应用 关系数据库中的数据管理系统
5、向用户提供使用的数据库语言称为数据子语言，它是以 关系代数或谓词逻辑中的方法表示。由于用这种数学的方法去表示，使得对这些语言的研究成为对关系代数或逻辑谓词的研究，优化语言的表示变成为对关系代数与谓词逻辑的化简问题。由于引入了数学表示方法，使得关系数据库具有比其它几种数据库较为优越的条件。正因为如此关系数据库迅速发展成为一种很有前途、很有希望的数据库。 另外，离散数学中的笛卡儿积是一个纯数学理论，是研究关系数据库的一种重要方法，显示出不可替代的作用。不仅为其提供理论和方法上的支持，更重要的是推动了数据库技术的研究和发展。关系数据模型建立在严格的集合代数的基础上，其数据的逻辑结构是一个由行和列组成
6、的二维表来描述关系数据模型。在研究实体集中的域和域之间的可能关系、表结构的确定与设计、关系操作的数据查询和维护功能的实现、关系分解的无损连接性分析、连接依赖等问题都用到二元关系理论。 2 离散数学在数据结构中的应用 计算机要解决一个具体问题，必须运用数据结构知识。对于问题中所处理的数据，必须首先从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编出程序，进行测试、调整直至得到问题的最终解答。而寻求数学模型就是数据结构研究的内容。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。 数据结构中将操作对象间的关系分为
7、四类：集合、线性结构、树形结构、图状结构或 网状结构。数据结构研究的主要内容是数据的逻辑结构，物理存储结构以及基本运算操作。其中逻辑结构和基本运算操作来源于离散数学中的离散结构和算法思考。离散数学中的集合论、关系、图论、树四个章节就反映了数据结构中四大结构的知识。如集合由元素组成，元素可理解为世上的客观事物。关系是集合的元素之间都存在某种关系。例如雇员与其工资之间的关系。 3 离散数学在编译原理中的应用 编译程序是计算机的一个十分复杂的系统程序。一个典型的编译程序一般都含有八个部分：词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、错误检查和处理程序、
8、各种信息表格的管理程序。 离散数学里的计算模型章节里就讲了三种类型的计算模型：文法、有限状态机和图灵机。具体知识有语言和文法、带输出的有限状态机、不带输出的有限状态机、语言的识别、图灵机等。短语结构文法根据产生式类型来分类：0 型文法、1 型文法、2 型文法、3 型文法。以上这些在离散数学里讲述到的知识点在编译原理的词法分析及语法分析中都会用到。因此，离散数学也是编译原理的前期基础课程。 4 离散数学在人工智能中的应用 在人工智能的研究与应用领域中，逻辑推理是人工智能研究中最持久的子领域之一。逻辑是所有数学推理的基础，对人工智能有实际的应用。采用谓词逻辑语言的演绎过程的形式化有助于我们更清楚地
9、理解推理的某些子命题。逻辑规则给出数学语句的准确定义。离散数学中数学推理和布尔代数章节中的知识就为早期的人工智能研究领域打下了良好的数学基础。许多非形式的工作，包括医疗诊断和信息检索都可以和定理证明问题一样加以形式化. 因此，在人工智能方法的研究中定理证明是一个极其重要的论题。在这里，推理机就是实现(机器)推理的程序。它既包括通常的逻辑推理，也包括基于产生式的操作。推理机是使用知识库中的知识进行推理而解决问题的。所以推理机也就是专家的思维机制，即专家分析问题、解决问题的方法的一种算法表示和机器实现。 5 离散数学在计算机硬件设计中的应用 数字逻辑作为计算机的一个重要理论，在很大程度上起源于离散
10、数学的数理逻辑中的命题与逻辑演算，其在计算机硬件设计中的应用更为突出。利用命题中各关联词的运算规律把又电平表示的各信号之间的运算于二进制数之间的运算联系起来，使得我们可以用与非门或者用或非门来解决电路设计问题，使得整个设计过程更加直观、系统化。数理逻辑在程序设计中起到花间的作用，当一个程序初稿拿出来以后，如果我们想分析一下其中是否有冗余存在，这时就用到了离散数学中命题演算的基本等式。 6 离散数学在计算机纠错码中的应用 计算机中，常常需要将二进制数字信号进行传递。这种传递的距离近则数米、数毫米，远则超过数千公里。在传递过程中，由于存在各种干挠，常常会使二进制信号产生失真现象。而利用离散数学的集
11、合论、群论和数理逻辑来分析研究计算机纠错码的纠错能力，是离散数学在计算机科学中的一个重要应用方面。 综上所述，离散数学不仅是计算机技术迅猛发展的支撑学科，更是提高学生逻辑思维能力、创造性思维能力以及形式化表述能力的动力源，离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到分布式系统，无不与离散数学密切相关。在现代计算机科学中，如果不了解离散数学的基本内容，则在计算机科学中就寸步难行了。书名:离散数学及其在计算机中的应用(第4次修订) 作者:徐洁磐 出版社：人民邮电出版社离散数学及其在计算机中的应用(第4次修订)系统地介绍了离散数学的基础理论，阐述了各个分支之间的联系，还说明了它在计算机中的应用。主要内容包括：集合论、关系、映射和无限集、近世代数、图论、命题逻辑、谓词逻辑、命题逻辑和谓词逻辑的公理化理论、离散数学在计算机中的应用。章末附有复习提纲及习题，书末附有各章习题解答。离散数学和计算机科学关系密切。
