当前课程知识点:软件理论基础 >  第一章 基础知识 >  1.3 图 >  Video

返回《软件理论基础》慕课在线视频课程列表

Video在线视频

下一节:Video

返回《软件理论基础》慕课在线视频列表

Video课程教案、知识点、字幕

欢迎同学们来到《软件理论基础》Mooc课堂

现在介绍第三节:图

图实由两类元素构成

一类是顶点

顶点,也叫结点

用圆圈表示

像 a、b、c、d、e,是图的顶点

另一类是边

(a, b) 是有向边,从 a 指向 b

(b, c)、(b, e)、(c, e),等等

实际上,边

是顶点集合的一个关系

图中,边上标些数字

叫标记图

以后在自动机

经常要用到这种图

图中通路,也叫 walk

表示这样一些边连成的

由尾和首连接起来的边

像 (c, e)、(e, d)、(d, c)、(c, e)、(e, b)

构成的一个线路,叫做通路

在图中,有一种叫做路径

它是一种通路

没有重复的边

这个图中

从 e 开始,(e, d)(d, c)(c, e)(e, b)

是一条没有重复边的通路

称为路径

另外,这图中有一条路径

没有重复的顶点

像从 d 开始

(d, c)、(c, e)、 到 (e, b)

没有顶点重复

这样的路径,叫做简单路径

图中有一种,叫回路,也叫作环

是从某一点出发

譬如,从 e 开始出发,又回到它自己

这样一条路径叫做回路

在回路中

只有一点

从这点开始,譬如从 c 开始

c 到 e,e 到 b,再回到 c

只有这一点 c 出现重复

这样的回路叫做简单回路

图中有一类特殊的图

叫作树

有一个顶点或结点

没有入边连接它

叫作根结点

还有一些顶点,没有出边

这类顶点叫作叶结点

有些顶点,有进来的边,也有出去的边

是内部结点

在内部结点,像这个结点

是从这个顶点连接它

这结点叫做这个顶点的子结点

而这结点叫做这个结点的父结点

树中

的特点是没有环

树可以定义高度

这个结点,边的个数

是 0 个边,层数为 0

这个结点, 从根结点到它有一条边

它的层数是 一

这个结点,从根结点到它

通过两条边,是两层

而这个结点,从根结点到它

有三条边,是三层

这棵树

结点最高的层数

像这个结点

是这棵树最高的层数,三层

定义为树的高度

这节内容介绍完毕

谢谢大家!

软件理论基础课程列表:

第一章 基础知识

-1.1 概要

--第一节

-1.2 数学基础

--Video

-1.3 图

--Video

-1.4 证明方法

--Video

-1.5 语言基础

--Video

-1.6 语言运算

--Video

-习题--作业

第二章 确定有限自动机

-2.1 确定有限自动机的概念

--Video

-2.2 确定有限自动机的定义

--Video

-2.3 扩展转移函数

--Video

-2.4 正则语言

--Video

-2.5 DFA构造

--Video

-习题--作业

第三章 非确定有限自动机

-3.1 非确定有限自动机的概念

--Video

-3.2 e转移

--Video

-3.3 非确定有限自动机的定义

--Video

-3.4 扩展转移函数

--Video

-3.5 等价性证明

--Video

-3.6 文本搜索

--Video

-习题--作业

第四章 正则表示

-4.1 单一终结状态的NFA

--Video

-4.2 正则语言的运算性质

--Video

-4.3 正则表示和语言

--Video

-4.4 正则表示和正则语言

--Video

-4.5 正则语言的同态

--Video

-4.6 正则表示的代数定律

--Video

-习题--作业

第五章 正则文法和正则语言

-5.1 文法

--Video

-5.2 线性文法

--Video

-5.3 正则文法与正则语言

--Video

-5.4 自动机的积

--Video

-习题--作业

第六章 正则语言的性质与DFA优化

-6.1 基本问题

--Video

-6.2 泵引理

--Video

-6.3 非正则语言的判定 1

--Video

-6.4 非正则语言的判定 2

--Video

-6.5 DFA的优化 1

--Video

-6.6 DFA的优化 2

--Video

-习题--作业

第七章 上下文无关文法和推导

-7.1 上下文无关文法

--Video

-7.2 规约和推导

--Video

-7.3 语法分析树

--Video

-7.4 规约、推导和语法分析树之间的关系

--Video

-7.5 上下文无关语言

--Video

-习题--作业

第八章 CFG的应用与文法的二义性

-8.1 CFG的应用

--Video

-8.2 CFG的转化

--Video

-8.3 文法二义性

--Video

-8.4 二义性的消除方法

--Video

-8.5 CFG的构造方法

--Video

-8.6 CFG的构造实例

--Video

-第八章 CFG的应用与文法的二义性--习题

第九章 下推自动机

-9.1 PDA介绍

--Video

-9.2 PDA的定义

--Video

-9.3 PDA的即时描述

--Video

-9.4 PDA的语言

--Video

-9.5 PDA与CFG的关系

--Video

-习题--作业

第十章 下推自动机与CFG化简规范

-10.1 确定下推自动机

--Video

-10.2 DPDA与其他语言的关系

--Video

-10.3 终态型DPDA和空栈型DPDA

--Video

-10.4 消除无用符号

--Video

-10.5 消除e产生式

--Video

-10.6 消除单一产生式

--Video

-10.7 CFG的化简与Chomsky范式

--Video

-习题--作业

第十一章 上下文无关语言的性质

-11.1 CFL的必要条件

--Video

-11.2 CFL的Pumping引理

--Video

-11.3 CFL的闭运算性质

--Video

-11.4 CFL的同态性质

--Video

-11.5 CFL的交运算

--Video

-11.6 CFL的判定性质

--Video

-习题--作业

第十二章 Turing机

-12.1 图灵机的介绍

--Video

-12.2 图灵机的定义

--Video

-12.3 图灵机的即时描述

--Video

-12.4 图灵机的计算

--Video

-12.5 图灵机的编程技术

--Video

-习题--作业

第十三章 图灵机的扩展

-13.1 Turing理论

--Video

-13.2 图灵机带的扩展

--Video

-13.3 图灵机移动的扩展

--Video

-13.4 受限图灵机

--Video

-13.5 图灵机与其他自动机

--Video

-习题--作业

第十四章 不可判定问题

-14.1 图灵机编码

--Video

-14.2 对角线语言与通用语言

--Video

-14.3 图灵机语言的性质

--Video

-14.4 判定问题和语言

--Video

-14.5 计算复杂性问题

--Video

-第十四章 不可判定问题--习题

第十五章 自动机及应用

-15.1 时间自动机

--Video

-15.2 Buchi自动机

--Video

-15.3 软件形式化验证

--Video

-15.4 模型检测方法

--Video

-15.5 M3C模型检测系统

--Video

-习题--作业

期中考试

-期中考试

Video笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。