浅析《离散数学》在计算机学科中的应用.pdf

浅析 离散数学 在计算机学科中的应用 贺玉珍 张海江 1 运城学院计算机科学与技术系 运城0 4 4 0 0 0 2 运城供电分公司 运城0 4 4 0 0 0 摘要 离散数 学是计算机科 学和计算机应用的理论基础和数学工具 介绍离散数学的每一部 分分别在计算机不同领域 中的应用 分析离散数学作为计算机专业其他课程理论基础 的作用 指出离散数 学在从事计算机及相关科学工作 中的重要性 关键词 离散数学 数理逻辑 图论 数据库 人工智能 0 引言 离散数学 是现代数学 的一个重要分支 也是 计算机科学与技术的理论技术 又称为计算机数学 它是 以研究 离散性 的结 构 和相 互 间的关 系 为主要 目 标 其研究对象一般是有 限个或可数个元素 离散 数学 作为计算机科学与技术专业的一 门必修的骨 干专业 基础课 程 一方 面 它充分 描述 了计算 机科 学 离散性的特点 而且给后继课程例如 数据结构 操作系统 数据库原理 人工智能 编译原 理 计算机网络 信息安全 算法分析 等课程 提供必要的数学基础 另一方面 它所提供 的训练十 分有利于学生概括抽象能力 逻辑思维能力 归纳构 造能力的提高 以及学生严谨 完整 规范的科学态 度的培养 这些能力与态度是一切软 硬件计算机科 学工作者所不可缺少的 为学生将来从事计算机科 研或 工程 技术奠 定理 论基 础 因此 在 离 散数 学 课 程的教学过程中 我们应该在讲解分析理论基础上 结合计算机学科应用 以提高学生的学习兴趣和对 该课程 的重 视 1 数理逻辑在计算机学科中的应用 离散数学 中的数理逻辑是一门研究推理的逻 辑学科 它与计算机学科有着非常密切的关系 在计 算机理论 程序设计和计算机硬件系统发挥着重要 而广 泛 的应用 1 1数理逻辑在计算机计算中的应用 从计算模型和可计算性 的研究来看 可计算函 数和可计算谓词是等价的 因此计算可 以用 函数演 算来表达 也可以用逻辑系统来表达 作为计算模型 可以计算的函数恰好与可计算谓词是等价的 而逻 辑 系统又 能通 过 自身 的无矛 盾 性保证 这样 一 种计 算 模 型是合 理 的 由此可 见 作 为一种 数学 形式 系 统 图灵机及其与它等价的计算模型的逻辑基础是坚实 的 人工智能领域的一个重要方 向就是基于逻辑的 人工智能 1 2 数理逻辑在计算机设计和制造 中的应用 实际计算机的设计和制造中 使用数字逻辑技 术实现计算机的各种运算的理论基础是代数和布尔 代数 布尔代数只是在形式演算方面使用 了代数的 方法 其 内容的实质仍然是逻辑 1 3 数理逻辑在计算机程序设计语 言中的应用 从计算机程序设计语言方面来考察 语言的理 论基础是形式语 言 自动机与形式语义学 而形式语 言 自动机与形式语义学所采用的主要研究思想和 基金项目 运城学院科研基金项 Ifl No 2 0 0 6 0 4 0 5 收稿 日期 2 0 1 0 0 3 0 4 修稿 E l 期 2 0 1 0 0 3 1 8 作者 简介 贺 玉珍 1 9 7 1 女 山西运 城人 硕 士 副教 授 研 究方 向为数 据 库与教 据挖 掘 现代计算机2 0 1 0 0 3 方法来源于数理逻辑和代数 程序设计语言中的许 多机制和方法 例如子程序调用的参数 的代换 赋值 等都出自数理逻辑的方法 此外 在语言的语义研究 中 四种语义方法最终可归结为代数和逻辑的方法 而且 程序的语义及其正确性理论基础仍然是数理 逻辑和进一步的模型论 1 4 数理逻辑在数据库管理 系统中的应用 在数据库理论中 逻辑是比不可少的 在关系模 型中 以属性来描述事物 属性的取值范围称为域 一 个对象有一个或多个关 系 例如一个描述学生的 关系模 式为 S t u d e n t n a m e n u mb e r s e x b i r t h d e p a r t me n t 可用 t 来表示每个元组 关系演算就是 以关系 为变量 若以为谓词逻辑来表示关系的操作 则关系 演算的一般形式为 t I P t l P 1 为 t 应满足的谓词 若要查询计算机系某男 大学生的姓名 则关系演算 的表达式应为 t 1 t s t u d e n t AN D t s e x m AN D t d e p a 一 me n t c o mp u t e r 可以看出 这种 以关系演算表示的操作 只要署 明所要得到的结果 不必表明操作 的过程 2 集合论在计算机学科中的应用 离散数学 中的集合论被应用在计算机学科的 各个方面 集合是构造离散结构的基础 离散结构是 计算机的基本结构 从集合构造而来的离散结构包 括 计数时广泛使用的组合 即无序对象集 表示对 象之间相互关系 即序偶集合 图 顶点集合 以及边 的集合 以及用户模拟计算机的有限状态机等 集合 论在数据结构 数据库 人工智能领域及程序设计语 言等都有重要的应用 数据库技术被广泛应用于社会各个领域 关系 数据库已经成为数据库的主流 集合中的笛卡儿积 是一个纯数学理论 是研究关系数据库的一种重要 方法 显示出不可替代的作用 不仅为其提供 了理论 和方法上的支持 更重要 的是推动 了数据库技术的 研究和发展 关系数据模型建立在严格的集合代数 现代计算机2 0 1 0 0 3 的基础上 其数据的逻辑结构是一个由行和列组成 的二维表来描述关系数据模型 在研究实体集中的 域和域之间的可能关 系 表结构的确定与设计 关系 操 作 的数据 查询 和维护 功能 的实 现 关 系分解 的无 损连接性分析 连接依赖等问题都用到笛卡儿积的 理 论 3 图论计算机学科中的应用 图论对计算机制图 操作系统 程序设计语言的 编译系统以及信息的组织与检索起重要作用 其平 面图 树的研究对集成 电路的布线 网络线路的铺 设 网络 信息 流量 的分析 等的实用 价值 显而易见 有 了图论作理论基础 才可以在编译程序中用树来表 示源程序语法结构 产生了自顶向下和自下向上这 两种不同的语法分析树 也正因为有了图论 在数据 库系统中 才可以用树来组织信息 从而把各信息结 点间的复杂关系用一种清晰直观的方式表示 出来 同样 图论在操作系统中也得到了充分应用 最典型 的例子是可以用图论 中的回路来判断并发进程中是 否存在递归和死锁现象 可以把一项本来很复杂的 工作通过判断一个有 向图中是否存在回路来加以解 决 大大提高了工作效率 在计算机体系结构中 指令系统的优化意味着 整个计算机系统性能的提高 指令系统的优化的一 种方法是对指令的格式进行优化 指令格式的优化 是指如何用最短的位数来表示指令的操作信息和地 址信息 使程序中的指令的平均字长最短 为此可以 用 到 哈夫曼 的压缩算 法 构 造 出哈夫曼树 方 法是将 指令系统的所有指令 的使用频度进行统计 并按使 用 频度 由小 到大排 序 每次选 择其 中最 小 的两个 频 度合并成一个频度是它们两者之和的新结点 再按 该频度大小插人余下未参与结合的频度值中 如此 继续进行 直到全部频度结合完毕形成根结点为止 之后 对每个结点向下延伸的两个分支 分别标注 1 或 0 从根结点开始 沿线到达各频度结点所经 过的代码序列就构成了该指令 的哈夫曼编码 这样 得到 的编码序列使指令使用概率低的指令编 以长 码 指令使用概率高的指令编以短码 竺 4 代数系统在计算中学科中的应用 5 结语 代数结构是关于运算或计算规则 的学问 在计 算机科学中 代数方法被广泛应用于许多分支学科 例如可计算性与计算复杂性 形式语言与自动机 密 码学 网络与通信理论 程序理论和形式语义学等 格与布尔代数理论成为电子计算机硬件设计和通信 系统设计 中的重要工具 关系数据库系统通过关 系数据语言 c 例如 S Q L 语言 进行数据查询和操作 S Q L语言是一种非过程 化的语言 在查询时只需说明需要的数据 而不说明 通 过何种 存取路 径 去存 取数 据 即用 户 只需提 出干 什么 不必提出怎么干 怎么干由关系数据库管理系 统 自动进行 它必须选择高效的方法来完成用户的 查询 这个过程为查询优化 关系数据库管理系统首 先将用户的 S Q L语句转化为等价的关 系代 数表达 式 然后利用系统信息和上面介绍的运算律进行优 化 例如选择运算与广义笛卡尔积运算满足交换律 则选 择运 算应该 尽可 能先 执行 因为选 择运 算 减少 了数据 而广义笛卡尔积尽可能后执行 因为广义笛 卡尔积会产生大量的组合数据 在计算机科学领域中很多地方都采用 了离散数 学的概念思想和方法 从科学计算到信息处理 计算 机体系结构到计算机应用技术 计算机软件到计算 机硬件 人工智能到分布式系统 无不与离散数学密 切相关 离散数学已经成为计算机专业学生必须掌 握的理论基础和数学工具 作为一名计算机专业的 学生 掌 握 好 离 散 数 学 这 门课 程 才 能 更 加深 入 全面地掌握计算机学科中的其他课程 参考文 献 f I I 傅彦 王立杰 尚明生 顾小丰 离散数学实验与习题解 析 高等教育出版社 2 0 0 7 2 1 傅彦 顾小丰 王庆先 刘启和 离散数学及其应用 高 等教育 出版社 2 0 0 7 3 1 耿素云 屈婉玲 离散数学 高等教育出版社 2 0 0 3 4 1 陈敏 李泽军 离散数学在计算机学科 中的应用 电脑 知识与技术 2 0 0 9 1 2 5 1 2 5 2 f 5 1 龚静 王青川 数理逻辑在计算机科学中的应用浅析 青海科技 2 0 0 4 6 5 3 5 5 Di s c u s s i o n o n t h e Ap p l ic a t i o n o f Di s c r e t e Ma t h e ma t i c s i n Co mp u t e r Sc i e n c e HE Y u z h e n Z H AN G Ha i j i a n g D e p a r t me n t o f C o mp u t e r S c i e n c e T e c h n o l o g y Y u n c h e n g Un i v e r s i t y Yu n c h e n g 0 4 4 0 O 0 Ab s t r a c t Di s c r e t e Ma t h e ma t i c s i s a t h e o r y b a s i s a n d ma t h e ma t i c al t o o l i n c o mp u t e r s c i e n c e fi e l d s I n t r o d u c e s t h e a p p l i c a t i o n o f e v e r y p a r t s o f Di s c r e t e Ma t h e ma t i c s i n d i ff e r e n t f i e l d s o f c o mp u t e r s c i e n c e a n a l y z e s t h e t h e o ry b asi s o f D i s c r e t e Ma t h e ma t i c s i n o t h e r s u b j e c t s o f c o mp u t e r s p e c i a l t y a n d p o i n t s o u t t h e i mp o r t a n c e o f Di s c r e t e Ma t h e ma t i