离散数学在计算机中的应用-1.ppt

离散数学主要包括四个方面: 1数理逻辑. 2集合论. 3代数结构. 4图论. 离散数学是计算机的一个理论基础 计算科学的研究也离不开抽象代数的应用： 半群理论在自动机理论和形式语言中发挥了重要作用； 有限域理论是编码理论的数学基础，在通讯中起过重要的作用； 格和布尔代数则是电子线路设计、电子计算机硬件设计和通讯系统设的重要工具。 另外描述机器可计算的函数、研究算术计算的复杂性、刻画抽象数据结构、描述作为程序设计基础的形式语义学，都需要抽象代数知识。 1。集合论在计算机方面的应用 集合论是离散数学中极其重要的一部分,它在数据库中有着广泛的应用。我们可以利用关系理论使数据库从网络型、层次型转变成关系型,这样使数据库中的数据容易表示,并且易于存储和处理,使逻辑结构简单、数据独立性强、数据共享、数据冗余可控和操作简单。当数据库中记录较多时,集合中的笛卡儿积方便了记录的查询、插入、删除和修改。 还可以通过布尔运算关系运算得出真值表,应用到数字电子方面 在数据库方面的应用 在数字电子方面的应用 2。图论在计算机中的应用 在计算机网络原理里面，有一些路由选择算法,桶排序算法之类 的，像最短路径算法等，都是离散数学里图论的应用，都是一些经典的算法！！ 现在我们学的数据结构中的应用主要是图论部分在数据结构中的应用,树在图论中占着重要的地位。树是一种非线性数据结构,在现实生活中可以用树来表示某一家族的家谱或某公司的组织结构,也可以用它来表示计算机中文件的组织结构,树中二叉树在计算机科学中有着重要的应用。 简单的树 3。代数系统,群论在通信方面的应用 代数系统在计算机中的应用广泛,例如有限机,开关线路的计数等方面。但最常用的是在纠错码方面的应用。在计算机和数据通信中,经常需要将二进制数字信号进行传递,这种传递常常距离很远,所以难免会出现错误。通常采用纠错码来避免这种错误的发生,而设计的这种纠错码的数学基础就是代数系统。纠错码中的一致校验矩阵就是根据代数系统中的群概念来进行设计的,另外在群码的校正中,也用到了代数系统中的陪集。 简单来说纠错码就是通过关系运算后判断密码是否正确~ 二进制信号传递模型 * *