当前课程知识点:Petri网:模型、理论与应用 >  第四章 网论 >  4-6 同步论 >  Video

返回《Petri网:模型、理论与应用》慕课在线视频课程列表

Video在线视频

Video

下一节:Video

返回《Petri网:模型、理论与应用》慕课在线视频列表

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

我不知道大家会不会问

说这个E2怎么可能反向发生

现在这个token在中间共享的那个

那个条件里面

他是这样的那么当E2发生以后

右边这个

条件里面就有个token了咱们从这个

情态

作为初始情态从这出发

这样一来E2的就可以反向发生

反向发生以后E1就可以正向发生

所以他是从一个情态就是右边的token

到另外一个情态就是左边的token

这个情态到情态的这个过程叫做一个

挠进程

挠进程是及于能够达到最大值也能达到最小值

这就是在文献里面曾经有过的定义

但是这个定义我觉得有点不太好接受啊

初学的人不太好接受所以我觉得还是咱们

还原它的本质它就是两个进程获得

同步距离是两个进程

跨进程的概念

不是在一个进程里面能够算出来的

现在我们看另外一个基本现场就是并发

这个图里面的E1或E2是并发的

这个并发呢

这里面这个大N没有写

其实不写大也家应该知道我们最初放大N的token

那么E1如果发生呢

这个就有n加1个token

在这个共享的虚线的这个观察窗口里面

就会有n加一个token

如果E1不发生E2发生

那么这个虚的就关上窗口里面

就会去掉一个token

这边的n减1个所以呢它的最大值

是n加1它的最小值是n减1

那结果也是2

它们的同步距离仍然是2

就是我刚才已经讲过了

比方说我们说话上嘴唇下嘴唇

拍手拍手左手E1或E2就是左手和右手

的动作要么缺一不可

所以E1或E2呢

你要么观察到两个都发生了

要么观察到一个也没有发生所以

你再加一个token的同时也要减掉一个token

所以它里面的token变化是没有的是不是等于0

所以这个同步距离就是零

那么现在问大家如果我两只手来拍桌子

这个同步距离是几呀

这个课程没时间让大家去思考

那么它同时就是并发

有我左手握右手时

互不依赖的是并发的

他的同步距离是几呢

刚才我看到了并发它的同步距离是2

怎么理解这个就是

在拍手的时候如果你用非常快的摄相机把它照下来

然后用非常慢的摄像放出来你就会发现

有可能一只手连续拍了两次桌子

中间没有另一手参加也就是说这样

右手后击的桌子抬起来以后右手先

左手后所以在左手两次击桌之间右手击

打击了这个桌子两次这就是同步距离为二

他们物理意义

所以并发它的同步距离是二

或者说说得更准确点是大于等于2

因为有的例子

我们可以看看并发的它是可能超过2的

咱们再看看这个例子

这个E1或E2那是不并发的

刚才我们例子里并发的时候

我们在上面加了两条弧

两个箭头

E1可以发生因为它只有一个输入

而且输入里面有token

E2不能发生因为E2现在我们加了一个

这个输入条件就是E1个后击里面

的s元素

所以它的发生规律是什么呢E1发生

然后E2发生然后E1又发生

然后这个E4发生

把这个系统里面E1

这些事件的发生规律了

就是用像这个公式所描述的一样

E1、E2、E4、E3

然后反复的这样发生

所以那个星号就表示

这个变迁序列是可以重复的

我们看到

它的规律是什么呀

E1发生两次E2发生一次

然后你看如果我们要把这个五个变迁

五个这个事件再重复一遍的话

我们就发现E1发生了四次而E2就发生了两次

如果我们再重复一次那么E1就发生了六次而

这个E2呢就发生了三次

所以这个最大值你看n里面的最大值是多少

一次就多下了一个再重复一遍

又多下了一个在重复一次又多下了一个

这个token可以无限的增长token数可以无限的增长

要多少个有多少个这就是刚才我说的

他的同步距离就是无穷了

但是这种无穷呢又是有规律的

因为它发生的次数始终是

2比1就是两次E1一次E2

所以我们体现这种规律虽然

一比一的规律是没有

但是一比二也是规律啊

我们怎么来描述这种规律呢

有加权的同步距离

来描述什么意思就是当E1发生的时候

我们往里面放一个token

当E2发生的时候我们从里面拿掉两个token

这样一来我们看这里面当

E1发生的时候token数变成n加1

当E2发生的时候这里面的token数变成n减1

然后E1再发生它又恢复了n

然后整个这五个事件

就这样循环就完了

所以在一次循环当中如果我们加权观察的话

观察窗口里面的token是没有变化

加一个减两个再加一个等于没有加没有减

所以这样一来它的同步距离呢

我们说它的加权同步距离就是2

写成什么样的就是写成底下这样

在这个第二个E2集合前面加上一个2

这就是它的权

然后后面的等于2这就是它的同步距离

所以加权同步距离体现的仍然是一种规律性

同步的就是事件发生

反复发生当中所呈现出来的规律性

什么叫异步刚才我们看过这个

这个呢这个我们再重新看一遍

这个E1或E2刚刚不说了它是不同步的

因为这个E1

可以发任意多次E2不发生

E2也可以发生任意多次而E1不发生

所以它是不同步

这里面的这个观察窗口里同的token

可以任意的多也可以任意的少

那么他有没有规律呢我们能不能用加权

来体现它们之间的规律呢

那么这里面咱们可以很容易的看出来

没有权可以加它就是真的异步

没有规律

不像我们刚才那个是1:2这个没有这个规律

所以像这种呢

无论是同步距离或者加权同步距离

它都不能得到一个有限数这样的两组事件

就叫做异步的

所以这是真正的异步不能够同步

所以同步距离的定义就是这样

观察窗口所得到的最大值或最大最小值

之间的差叫做同步距离

这就是我们的定义

但是它那个形式化的定义那是比较复杂

所有的进程所有可能的进程

计算一个它的最大值

所有的进程计算一个最小值

然后最大值或最小值的差就是这个同步距离

那么这个公式我就不写了咱们书上有

嗯我想我到现在我就讲的已经很清楚了就是

最大值或最小值它有可能

是的两个不同的进程里面取得的

在进程里面要算一个最大值

在进程里面也算一个最小值

然后这个进程

这个最大值最小值之间差距同步距离

我们不能再一个同一个进程

说这里面最多发生多少次

最少发生多少次它的差是多少

这就错了

确实是分别计算进程的最大值

进程的最小值然后这两个差是这个同步距离

我不知道同学们会不会有这个疑问

为什么叫同步距离

那么我们是有道理的

这个有一个大家都知道这个距离公理

距离公理很简单

自己同一个点到自己的距离是零

就是第一条dxx等于0

另外距离的值任意两点的距离的值

就是大于等于0的第三条

然后这个距离是

这个对称的就从x点到y点的距离

或从y点到x点的距离

是相等的然后第四个

距离三角不等式

两点之间的距离小于这个

另外两段的和就是三角形

两边的和大于等于第三边

所以这就是这个三角不等式

距离公理就这些

那么很容易证明我们的同步距离的定义呢

是满足这个公理的

距离公理都是满足的

第一最大值减了最小值它当然大于等于0

如果你这个观察的E1或E2

是同一个集合那么当然

它的距离就是零了因为什么呢

你放进去一个就要拿出来一个

因为它既属于E1又属于E2

这就是为什么我一开始说

E1或E2的交是空集没有共同元素

所以很容易证明我这就不去重复的说了

他还有第五条性质

就是像我们说到的两个里面

公共元素去掉以后它的同步距离是一样的

然后第六个呢也很容易理解

根据这个定义的话这个很容易计算

我在这儿要是不写只是用嘴讲的大家不太容易

听得明白所以我就

省点事儿不说了你要有兴趣可以

自己去证明因为这个并不难

这就是同步距离

同步距离是同步论的核心概念

是它的核心概念怎么算呢

我们要不要一个进程一个进程把所有的进程

按照定义把所有的进程都找出来

然后一个一个算它的最大值

然后一个一个算它的最小值

需要不需要这样做呢

不需要如果这样做的话那这个

就太麻烦了当然你可以写个算法

让计算机来帮你算这个上面写的东西

我想说我刚才已经说过了我们不用挠进程

不用这个反向发生这个概念来定义

这就是挠进程的定义

一个反向发生我已经说过了咱们就不多说了

怎么计算在遇到具体的问题的时候

我们可以来

根据那个网系统的特点我们可以算

这里我有一个方法的就是可以借助p/t系统

来给大家介绍一下怎么个算法

我们知道

在我们讲这个网系统的性质

我们曾经介绍过这个有一个算法

叫做覆盖数字构造算法

怎么构造这个覆盖数

我们知道这个算法是已经成熟的了

你在网上

可能有机会能够下载这个算法

那么构造出来以后

构造出这个数以后这个数

是有限的然后我们可以把

相同的结局就是标识相同的

重叠起来就变成一个可搭图

那么在可搭图上呢我们来计算

构造出可搭图以后

在这可搭图上来计算这个同步距离

就是一件很容易的事情了

可搭树的根是什么

是m零初始标识

m0里面加上一列

第一列就是你那个观察窗口a

这个观察窗口的这个它的值

m0加上这一列的值那是n

就是我们一开始放进去的

N那么多个token

然后你就把a当做一个

普通库所以后我说现在是p/t系统

当事件发生的时候按照我们的观察规律

加一个token或者减一个token

加一个token减一个token这样来做

它跟这个库所不同的是什么呢

因为它不是系统的一部分

它是个观察窗口

所以它的值如果你一开始这个n

不够大的话他的值可以变成负的

而一般的这个

标识那是不允许库所里面有负的

说我这个是负级token不可能

但是观察窗口可以给观察窗口区别于

库所的地方就在于它的值这个分量

可以是正整数可以是零也可以是负整数

如果你要是加权同步距离呢

那么你就在变迁发生的时候

你就把那个权算上就行了

或者多加或者多减都可以了

这样构造出来这个可搭图以后你去看一看

这个可搭图上面如果有圈有向圈

能在这个有向圈上面的图上面

会有变迁的名字

如果在这个这一圈的变迁

你算下来E1的变迁出现的数目

和E2变迁出现的数目如果不相等的话

那么这个同步距离就是无穷为什么呢因为你转一圈

就会净剩下或者净亏的几个token

因为他不相等

所以一般的来讲这个应该是

相等的如果不相同的同步距离就是无穷了

另外如果在构建可搭图或者可搭数的时候这个

观察窗口的分量变成∞了也就无穷了

那么当然它的同步距离

也就是无穷他的观察窗户的值不是无穷

而且每一个圈

E1变迁或者E2的变迁出现的数目是一样多

我们可以把这个圈去了

去了以后那就剩下一棵树了那么在这棵树上

这个观察窗口的最大值或最小值

很容易就找到了最大值和最小值之间的

这个差就是同步距离

因为这个EN系统是p/t系统的一个特例

它的全五分全都是一

这个容量函数都是一

所以这个算法也是EN系统这就是同步距离

同步距离我刚才说了

是通步论的核心概念

所以同步论第一让我们知道

什么是同步这个概念什么是系统的

同步系统什么是事件同步它是

事件反复发生当中体现出来的规律

而不是一次发生或另外一次发生之间的

关系所以从概念上来讲我们理解了同步

另外我们定义的同步距离这个定量的描述工具

那么要用那个同步论的应用的主要就是

同步距离的应用

所以我们下面就看这个同步距离的应用

下面我举几个例子

看看同步距离怎么样来

用到实践当中去

第一个例子就是评估双方

合同的这个最大损失

第二个是用于软件的规范

第三个用于系统的控制

我们一个一个来说

Petri网:模型、理论与应用课程列表:

第一章 概述

-概述

--Video

第二章 有向网

-有向网

--Video

第三章 Petri网

-3-1 Petri网定义

--Video

-3-2 Petri网层次系统

--Video

-3-3 基本网(EN)系统

--第一部分

--第二部分

--第三部分

--第四部分

-第三章 Petri网--3-3 基本网系统课后思考题

-3-4 条件-事件(C-E)系统

--Video

-第三章 Petri网--3-4 条件-事件系统课后习题

-3-5 库所-变迁(P-T)系统

--Video

--Video

--Video

--Video

--Video

-3-5 库所-变迁(P-T)系统课后习题--作业

-3-6 网系统层次

--Video

-3-7 高级网系统

--Video

-3-8 化简网系统

--Video

-3-9 非线性网系统

--Video

-3-10 小结

--Video

第四章 网论

-4-1 前言

--Video

-4-2 网拓扑

--Video

-4-3 并发论

--Video

-4-4 网逻辑

--Video

-4-5 信息流网

--Video

--Video

-4-6 同步论

--Video

--Video

-4-7 同步论-合同实例

--Video

-4-8 同步论-婚礼教堂实例

--Video

-4-9 同步论 同步器

--Video

-第四章 网论--思考题1

-4-10 实例与方法——电梯控制

--第一部分

--第二部分

--第三部分

--第四部分

-4-11 建模方法论

--Video

-4-12 汉诺塔问题

--第一部分

--第二部分

-第四章 网论--思考题2

第五章 业务流程管理

-5-1 工作流管理联盟

--Video

-5-2 工作流网(WF_net)

--Video

-5-3 Artifacts

--Video

-5-4 BPMN2.0

--Video

-5-5 学界

--Video

-5-6 业务流程管理(BPM)

--Video

-5-7 BPM建模

--A of ARM

--R of ARM:物理对象相关性

--R of ARM:同步器回顾

--R+M of ARM:业务逻辑

--M of ARM:化简规则

--R+M of ARM:案例语义

--R+M of ARM:管理逻辑

--M of ARM:BPMA

-5-8 流程举例

--第一部分

--第二部分

-5-9 流程之外

--Video

-Petri网小结

--Video

--Video

第六章 过程挖掘

-6.1 过程挖掘基础

--Video

--Video

--Video

--Video

--Video

--Video

--Video

--Video

--Video

--Video

--Video

--Video

--Video

--Video

-6.2 过程挖掘工具

--Video

--Video

-6.3 过程挖掘算法介绍

--Video

--Video

--Video

--Video

--Video

--Video

--Video

--Video

--Video

--Video

--Video

--Video

-6.4 未来研究方向

--Video

第七章 科研思考

-7.1 科研三要素

--Video

-7.2 Program today

--Video

-7.3 Program yesterday

--Video

-7.4 Theory of Programming

--Video

-7.5 A of ARM

--Video

-7.6 R of ARM

--Video

-7.7 M of ARM

--Video

-7.8 OESPA

--Video

-第七章 科研思考--习题

第八章 总结

-8.1 树个靶子

--Video

-8.2 八卦与自然

--Video

-8.3 结束语和感谢

--Video

-第八章 总结--习题

Video笔记与讨论

也许你还感兴趣的课程:

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