下载文档原格式
离散数学教学大纲第一部分大纲说明一.课程的性质与任务《离散数学》是现代数学的一个重要分支，也是计算机计算机科学与技术一级学科及其相关专业必修的基础理论的核心课程。
它是学习后续专业课程不可缺少的数学工具。
该课程结合计算机学科的特点，主要研究离散量结构及相互关系，其研究对象一般是有限个或可数个元素，因此《离散数学》充分描述了计算机学科离散性的特点。
它是一门理论性较强，应用性较广的课程。
掌握集合论、数理逻辑、图论、整数、群、环、域、格、布尔代数以及语言与有限自动机等离散数学的基本概念和基本原理，为学习计算机专业各后续课程做好必要的知识准备。
并通过这些知识的学习进一步提高学生的抽象思维和逻辑推理能力，为从事计算机相关的理论研究与应用提供必要的描述工具和理论基础。
二《离散数学》的特点作为计算机科学与技术一级学科的一门课程，《离散数学》有与其他课程相同相似的地方，当然也有它自身的特点：1、义与定理多。
《离散数学》是建立在大量定义之上的逻辑推理学科，因此对概念的理解是我们学习这门课程的核心。
在学习这些概念的基础上，要特别注意概念之间的联系，而描述这些联系的实体则是大量的定理与性质。
2、法性强。
《离散数学》的许多证明题中，方法性是非常强的，如果知道题的证明方法，很容易就可以证出来，反之则事倍功半。
所以在学习该课程中要善于总结，勤于思考，这也是培养分析问题解决问题抽象思维能力的一个过程。
三与其他相关课程的关系先修课程：高等数学（包括数学分析、线性代数）后续课程：数据结构、数据库、编译原理等四课程的主要内容与基本要求本课程分为九部分：集合论基础、命题逻辑、谓词逻辑、图与网络、数论基础、群与环、多项式与有限域、格与布尔代数以及语言和有限自动机。
（一）集合论基础：在整个《离散数学》的知识体系中，集合论处于基础的地位，对于其所包含知识的掌握程度，直接关系到是否能学好图论和抽象代数问题。
本章主要讲述集合、关系和映射。
1. 掌握集合、子集、超集、空集、幂集、集合族的概念。
形式语言与自动机课后习题答案第二章4．找出右线性文法，能构成长度为1至5个字符且以字母为首的字符串。
答：G={N,T,P,S}其中N={S,A,B,C,D} T={x,y} 其中x∈{所有字母} y∈{所有的字符} P如下: S→x S→xA A→y A→yBB→y B→yC C→y C→yD D→y6．构造上下文无关文法能够产生L={ω/ω∈{a,b}*且ω中a的个数是b的两倍}答：G={N,T,P,S}其中N={S} T={a,b} P如下:S→aab S→aba S→baaS→aabS S→aaSb S→aSab S→SaabS→abaS S→abSa S→aSba S→SabaS→baaS S→baSa S→bSaa S→Sbaa7．找出由下列各组生成式产生的语言（起始符为S）(1)S→SaS S→b(2)S→aSb S→c(3)S→a S→aE E→aS答：（1）b(ab)n /n≥0}或者L={(ba)n b/n≥0}(2) L={a n cb n /n≥0}(3)L={a2n+1 /n≥0}第三章1．下列集合是否为正则集，若是正则集写出其正则式。
（1）含有偶数个a和奇数个b的{a,b}*上的字符串集合（2）含有相同个数a和b的字符串集合（3）不含子串aba的{a,b}*上的字符串集合答：（1）是正则集，自动机如下(2) 不是正则集，用泵浦引理可以证明，具体见17题（2）。
(3) 是正则集先看L’为包含子串aba的{a,b}*上的字符串集合显然这是正则集，可以写出表达式和画出自动机。
（略）则不包含子串aba的{a,b}*上的字符串集合L是L’的非。
根据正则集的性质，L也是正则集。
4．对下列文法的生成式，找出其正则式（1）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下：S→aA S→BA→abS A→bBB→b B→cCC→D D→bBD→d（2）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下：S→aA S→BA→cC A→bBB→bB B→aC→D C→abBD→d答：(1) 由生成式得：S=aA+B ①A=abS+bB ②B=b+cC ③C=D ④D=d+bB ⑤③④⑤式化简消去CD，得到B=b+c(d+bB)即B=cbB+cd+b =>B=(cb)*(cd+b) ⑥将②⑥代入①S=aabS+ab(cb)*(cd+b)+(cb)*(cd+b) =>S=(aab)*(ab+ε)(cb)*(cd+b) (2) 由生成式得：S=aA+B ①A=bB+cC ②B=a+bB ③C=D+abB ④D=dB ⑤由③得 B=b*a ⑥将⑤⑥代入④ C=d+abb*a=d+ab+a ⑦将⑥⑦代入② A=b+a+c(d+b+a) ⑧将⑥⑧代入① S=a(b+a+c(d+ab+a))+b*a=ab+a+acd+acab+a+b*a5.为下列正则集，构造右线性文法：(1){a,b}*(2)以abb结尾的由a和b组成的所有字符串的集合(3)以b为首后跟若干个a的字符串的集合(4)含有两个相继a和两个相继b的由a和b组成的所有字符串集合答：（1）右线性文法G=({S},{a,b},P,S)P: S→aS S→bS S→ε(2) 右线性文法G=({S},{a,b},P,S)P: S→aS S→bS S→abb(3) 此正则集为{ba*}右线性文法G=({S,A},{a,b},P,S)P: S→bA A→aA A→ε(4) 此正则集为{{a,b}*aa{a,b}*bb{a,b}*, {a,b}*bb{a,b}*aa{a,b}*}右线性文法G=({S,A,B,C},{a,b},P,S)P: S→aS/bS/aaA/bbBA→aA/bA/bbCB→aB/bB/aaCC→aC/bC/ε7.设正则集为a(ba)*(1)构造右线性文法(2)找出（1）中文法的有限自 b动机答：（1）右线性文法G=({S,A},{a,b},P,S)P: S→aA A→bS A→ε（2）自动机如下：(p2是终结状态)9.对应图（a）(b)的状态转换图写出正则式。
离散数学在自然语言处理中的应用自然语言处理是一门跨学科的领域，涉及语言学、计算机科学、人工智能等多个学科，旨在使计算机能够理解和处理人类的自然语言。
在自然语言处理领域中，离散数学是一个重要的分支，其应用广泛，包括语言模型、语法分析、词法分析等方面。
离散数学是数学中的一个分支，研究的是非连续的、离散的数学结构。
自然语言是连续的、离散的符号序列，其中的字符、单词、短语和句子等都可以表示为离散的对象。
因此，在自然语言处理中需要使用离散数学的理论和方法来处理文本数据。
在自然语言处理中，最常用的离散数学工具是自动机和形式语言。
自动机是一种能够对离散序列进行状态转移的计算模型，能够对文本进行自动识别和分类。
形式语言是一种能够对文本进行形式化描述和规范化的工具，包括正则表达式、上下文无关文法、正则文法和上下文有关文法等。
语言模型是自然语言处理中的一个重要概念，指的是对自然语言中的词序列进行建模。
在语言模型中，离散数学中的马尔可夫链是一个非常重要的工具。
马尔可夫链是一个随机过程，指的是当前状态只与前一个状态有关的模型。
在自然语言处理中，马尔可夫链可以被用来描述语言中的概率性质，例如某个单词出现在某个位置的概率，或者一个短语出现在一个句子中的概率。
语法分析和词法分析是自然语言处理中的两个重要任务，分别负责解析语言结构和单词的基本属性。
在语法分析和词法分析中，正则表达式和有限状态自动机是常用的离散数学工具。
正则表达式是一种用来描述文本模式的符号串，能够帮助分析语言中的基本符号，例如空格、标点符号和单词分隔符等。
有限状态自动机是一种能够对正则表达式进行编译的计算模型，能够有效地处理正则表达式匹配问题。
总之，离散数学在自然语言处理中的应用是非常广泛的，各种离散数学工具和理论都能够被用来解决自然语言处理中的具体问题。
离散数学的研究成果为解析语言结构、词法分析和语言模型等任务提供了基础和支持，使得自然语言处理的效率和准确性得以提升。
离散数学一、说明（一）课程性质离散数学是计算机专业重要的基础理论课程，以研究离散量的结构和相互间的关系为主要目标，其研究对象一般是有限个或可数个元素，因此它充分描述了计算机科学离散性的特点。
离散数学与计算机科学中的许多后继课联系紧密，能够提供为专业课服务的基本理论。
（二）教学目的对现实世界中被研究的对象进行抽象，建立必要的基本概念，运用数学工具和方法研究揭示对象发展变换的内在规律，为实验设计和工程设计实现提供方法和技术，并展开实验设计和实现工作是计算机科学的基本工作流程。
以离散数学为代表的构造性数学是描述学科理论、方法和技术的主要工具，本课程的目的在于使计算机专业的学生掌握必要的离散形式的数学概念和结构，培养学生的抽象概括能力和严谨的思维能力，为后继课程的学习和创新研究打下良好的基础。
（三）教学内容本课程包括计算机专业所需要的离散数学基础知识，主要内容由数理逻辑、集合论、代数系统与图论四部分组成。
数理逻辑是研究推理的科学，包括了命题逻辑和谓词逻辑，是计算机科学重要的逻辑基础；集合论包含了二元关系、函数、无限集合等；代数是对字母集合和字母组成的结构的计算，抽象代数是关于计算规则的学说，本课程主要讲述了群、布尔代数等；图论起源于欧拉对著名的哥尼斯堡七桥问题的研究，现实中的许多问题可以用图来表示。
上述概念在计算机科学中有着广泛的应用。
它们为数据结构和数据表示理论奠定了数学基础，同时为许多问题从算法的能行性角度提供了抽象和描述的重要方法和数学基础。
（四）教学时数教学时数为周4学时，共计72学时。
（五）教学方式采用课堂讲授与辅导答疑相结合的教学方式。
二、本文第一篇数理逻辑第一章命题逻辑教学要点：逻辑学是一门研究人类思维形式和思维规律的科学，思维的形式结构包括了概念、判断和推理之间的结构和联系，其中概念是思维的基本单位，通过概念对事物是否具有某种属性进行肯定或否定的回答就是判断；由一个或几个判断推出另一个判断的思维形式就是推理。
形式语言和自动机与离散数学的关系下载温馨提示:该文档是我店铺精心编制而成，希望大家下载以后，能够帮助大家解决实际的问题。
文档下载后可定制随意修改，请根据实际需要进行相应的调整和使用，谢谢!并且，本店铺为大家提供各种各样类型的实用资料，如教育随笔、日记赏析、句子摘抄、古诗大全、经典美文、话题作文、工作总结、词语解析、文案摘录、其他资料等等，如想了解不同资料格式和写法，敬请关注!Download tips: This document is carefully compiled by theeditor. I hope that after you download them,they can help yousolve practical problems. The document can be customized andmodified after downloading,please adjust and use it according toactual needs, thank you!In addition, our shop provides you with various types ofpractical materials,such as educational essays, diaryappreciation,sentence excerpts,ancient poems,classic articles,topic composition,work summary,word parsing,copy excerpts,other materials and so on,want to know different data formats andwriting methods,please pay attention!形式语言和自动机就是一种特殊的数学方式，它们和离散数学有很多关系哦。
