图1 为两相开关建立模型的有穷自动机3.4 离散数学与编译原理编译程序是计算机学科中比较高深的专业课，是计算机的一个十分复杂的系统程序。

一个典型的编译程序而论，一般都含有八个部分：词法分析程序，语法分析程序，语义分析程序，中间代码生成程序，代码优化程序，目标代码生成程序，错误检查和处理程序，各种信息表格的管理程序。

离散数学里的计算模型章节里就讲了三种类型的计算模型：文法、有限状态机和图灵机。

具知识有语言和文法，带输出的有限状态机，不带输出的有限状态机，语言的识别，图灵机等。

短语结构文法根据产生式类型来分类：0型文法，1 型文法，2型文法，3 型文法。

以上这些在离散数学里讲述到的知识点在编译原理的词法分析及语法分析中都会用到。

由于自然语言都极为复杂，对一个自然语言，看起来不大可能说出它的所有语法规则，因此，将一个语言自动翻译成另一个语言的研究，引出形式语言的概念。

与自然语言不同，形式语言是由一组意义明确的语法规则定义的，语法规则不仅对于语言学和自然语言的研究十分重要，而且对于程序设计语言的研究也很重要。

形式语言的句子是用语法来描述的。

在程序设计语言的应用中，经常出现两类问题：（1）怎么能够确定一组单词是否组合成了形式语言的一个有效句子？（2）怎么才能产生形式语言的一个有效句子。

在考虑这两类问题时，文法的使用十分有益。

离散数学里定义了短语结构文法。

G=（V,T,S,P）由下列四部分组成：词汇表V，由V 的所有终结符组成的V的子集合T,V的初始符S，和产生式集合P。

集合V-T , 记为N，N中的元素称为非终结符。

P中的每个产生式的左边必须至少包含一个非终结符。

编译原理中的词法分析运用了不确定的有穷自动机，确定的有穷自动机，从正规表达式到NFA。

在语法分析中运用了上下文无关文法，非上下文无关文法，LL(1)文法，LR 文法。

这些表达式与文法都在离散数学中有相关的描述。

因此，离散数学也是编译原理的前期基础课程。

3.5 离散数学与人工智能人工智能是以让机器完成那些如果由人来做则需要智能的事情的科学。

虽然人工智能已经发展到创造出各种实用的专家系统阶段，但是在早期发展阶段，人工智能还是以计算数学、图灵机为理论基础。

并且在人工智能初创的第一个10年中，人们着重的是问题求解和推理的过程。

在人工智能的研究与应用领域中，逻辑推理是人工智能研究中最持久的子领域之一。

逻辑是所有数学推理的基础，对人工智能有实际的应用。

定理证明的研究在人工智能方法的发展中曾经产生过重要的影响。

因此，人工智能的出现与发展是和离散分不开的。

我们知道，离散数学课程中有一部分讲述命题逻辑、谓词逻辑。

在这部分中讲解了命题的定义，命题的合取、析取等逻辑运算以及谓词和量词在命题中的应用。

我们知道专家系统是人工智能中一个正在发展正处在专家系统的研究领域。

专家系统（Expert-System）是一种智能计算机系统。

它是应用于某一专门领域，拥有该领域相当数量的专家级知识，能模拟专家的思维，能达到专家级水平，能像专家一样解决困难复杂的实际问题的计算机系统。

专家系统的主要组成部分是知识库和推理机。

不同的专家系统其功能和结构有可能不同，但一般完整的专家系统应包括人机接口、推理机、知识库、动态数据库、知识获取机构和解释机构这六部分。

各部分之间的关系如图2所示。

图2 专家系统的一般结构专家系统的核心是知识库和推理机，其工作过程是根据知识库中的知识和用户提供的事实进行推理，不断地由已知的前题推出未知的结论，即中间结果，并将中间结果放到数据库中，作为已知的新事实进行推理，从而把求解的问题由求知状态转换为已知状态。

在专家系统的运行过程中，会不断地通过人机接口与用户进行交互，向用户提问，并向用户作出解释。

知识库主要用来存放领域专家提供的专门知识。

知识库中的知识来源于知识获取机构，同时它又为推理机提供求解问题所需的知识。

知识表达方法有：一阶谓词逻辑表示法、产生式规则表示法、状态图表示法、框架表示法等。

推理机是模拟领域专家的思维过程，控制并执行对问题的解解。

根据已知的事实，利用知识库中的知识，按一定的推理方法和控制策略进行推理，直到得出相应的结论为止。

逻辑是所有数学推理的基础，对人工智能有实际的应用。

所以，采用谓词逻辑语言的演绎过程的形式化有助于我们更清楚地理解推理的某些子命题。

逻辑规则给出数学语句的准确定义。

离散数学中数学推理和布尔代数章节中的知识就为早期的人工智能研究领域打下了良好的数学基础。

许多非形式的工作，包括医疗诊断和信息检索都可以和定理证明问题一样加以形式化。

因此，在人工智能方法的研究中定理证明是一个极其重要的论题。

在这里，推理机就是实现机器推理的程序。

它既包括通常的逻辑推理，也包括基于产生式的操作。

推理机是使用知识库中的知识进行推理而解决问题的。

所以推理机也就是专家的思维机制，即专家分析问题、解决问题的方法的一种算法表示和机器实现。

3.6 离散数学在计算机体系结构中的应用在计算机体系结构中，指令系统的设计和改进内容占有相当重要的地位，指令系统的优化意味着整个计算机系统性能的提高。

指令系统的优化方法很多，一种方法是对指令的格式进行优化，一条机器指令是由操作码和地址码组成，指令格式的优化是指如何用最短的位数来表示指令的操作信息和地址信息，使程序中的指令的平均字长最短。

为此可以用到哈夫曼的压缩概念，哈夫曼(Huffman)压缩是一种无损压缩法。

Huffman压缩概念的基本思想是，当各种事件发生的概率不均等时，采用优化技术对发生概率最高的事件用最短的位数(时间)来表示(处理)，而对出现概率较低的允许用较长的位数(时间)来表示(处理)，就会导致表示(处理)的平均位数(时间)的缩短。

利用哈夫曼算法，构造出哈夫曼树。

方法是将指令系统的所有指令的使用频度进行统计，并按使用频度由小到大排序，每次选择其中最小的两个频度合并成一个频度是它们二者之和的新结点。

再按该频度大小插入余下未参与结合的频度值中。

如此继续进行，直到全部频度结合完毕形成根结点为止，之后，对每个结点向下延伸的两个分支，分别标注“1”或“0”，从根结点开始，沿线到达各频度结点所经过的代码序列就构成了该指令的哈夫曼编码。

这样得到的编码系列就符合了指令使用概率低的指令编以长码，指令使用概率高的指令编以短码的初衷。

3.7 离散数学在计算机其他学科中的应用离散数学在计算机研究中的作用越来越大，计算机科学中普遍采用离散数学中的一些基本概念、基本思想、基本方法，使得计算机科学越趋完善与成熟。

离散数学在计算机科学和技术中有着广泛应用，除了在上述提到的领域中发挥了重要作用外，在其他领域也有着重要的应用，如离散数学中的数理逻辑部分在计算机硬件设计中的应用尤为突出，数字逻辑作为计算机科学的一个重要理论，在很大程度上起源于离散数学的数理逻辑中的命题与逻辑演算。

利用命题中各关联词的运算规律把由高低电平表示的各信号之间的运算与二进制数之间的运算联系起来，使得我们可以用数学的3方法来解决电路设计问题，使得整个设计过程变得更加直观，更加系统化。

集合论在计算机科学中也有广泛的应用，它为数据结构和算法分析奠定了数学基础，也为许多问题从算法角度如何加以解决提供了进行抽象和描述的一些重要方法，在软件工程和数据库中也会用到。

代数结构是关于运算或计算规则的学问，在计算机科学中，代数方法被广泛应用于许多分支学科，如可计算性与计算复杂性、形式语言与自动机、密码学、网络与通信理论、程序理论和形式语义学等，格与布尔代数理论成为电子计算机硬件设计和通讯系统设计中的重要工具，图论对开关理论与逻辑设计、计算机制图、操作系统、程序设计语言的编译系统以及信息的组织与检索起重要作用，其平面图、树的研究对集成电路的布线、网络线路的铺设、网络信息流量的分析等的实用价值显而易见。

4 结论离散数学不仅是计算机技术迅猛发展的支撑学科，更是提高学生逻辑思维能力、创造性思维能力以及形式化表述能力的动力源，离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到分布式系统，无不与离散数学密切相关。

在现代计算机科学中，如果不了解离散数学的基本内容，则在计算机科学中就寸步难行了。

参考文献［1］耿素云，屈婉玲，张立昂离散数学（第二版）［M］北京：清华大学出版社，1999:1-224［2］洪帆& 离散数学基础（第二版）［M］武汉：华中理工大学出版社，1995(8):232-376［3］严蔚敏，吴伟民数据结构（C语言版）［M］北京：清华大学出版社，1997:118-150［4］蒋立源，康慕宁编译原理（第二版）［M］西安：西北工业大学出版社，2001:41-104［5］ John E. Hopcroft Rajeev Motwani Jeffrey 自动机理论、语言和计算导论［M］北京：机械工业出版社，2002:115-148［6］蔡自兴，徐光佑人工智能及其应用［M］北京：清华大学出版社，1996:174-221［7］廉师友人工智能原理与应用基础教程［M］昆明：云南科技出版社，1998:21-61[8] 徐洁磐、朱怀宏、宋方敏离散数学及其在计算机中的应用［M］北京：人民邮电出版社，2008:1-323[9] 许曼苓离散数学的方法和挑战[J] 计算研究与发展, 2002:1771-1772[10] 赵淑群、李小英、黄高昂计算机本科专业《离散数学》的教学改革与实践[J] 东华理工学院学报, 2007,26(2):194-197[11] 李盘林、赵铭伟、徐喜荣离散数学［M］第二版北京:人民邮电出版社,2009:1-2495致谢：四年的本科生涯一晃而过，在此本科论文即将完成之际，有着许多的感慨，从论文的选题、写作、反复修改直至终稿，得到了众多老师和同学热心和真诚的帮助，在此一并表示感谢。

首先感谢我的指导老师梁莉莉老师。

作为一个大四的学生，真正体会了时间是多么的紧张，辅修第二专业，忙于上课、实习和找工作，时间很难安排过来，内心充满了恐惧，由于这种种原因，我对论文的完成几乎丧失了信心。

但是梁老师不仅给了我们充裕的时间准备，而且对于我论文中出现的问题，都给予了孜孜不倦的指导，梁老师这种对待学生认真负责的态度值得我终身学习，深深感谢梁老师给予我的教诲、关怀和帮助！在进广西民族大学直至今天，有很多老师都对我的成长给予了真诚而无私的关爱，在唐国吉老师、张树美老师等治学严谨的态度，让我收获颇多，从他们的循循善诱中让我学到了很多东西。

在此我很感激他们的教导之恩，也希望他们能带出一届又一届优秀的毕业生。

而在我完成毕业论文的过程中，我也得到了很多同学、朋友的帮助，特别是我的舍友，四年时间里，总有他们的支持与鼓励，与他们的愉快相处让我感受人与人之间的真诚友谊和温暖情怀，感谢他们。