Video在线视频

下面我们讲信息流信息流系统

信息流系统里面的信息

不同于

之前讲到的数据结构和信息

那里是指完整的信息

这里讲的信息的是one bit information

是构成计算机系统的最基本的单元

就是只有一个字位one bit information

one bit information

它有两个状态一个成真一个不成真

它还有第三个状态没有信息

所谓信息它可能有也可能没有

有它的值要么是真要么是假

这就跟我们一位系统里面的条件有所不同

这个条件是要么成真要么不成真

比方说我们这个季节

要么在夏季要么不在夏季

夏季秋季冬季春季四个季节

要么里面有token要么里面没有token

这就是条件

它不存在不知道这个是不是夏季

我们现在肯定是知道是夏季

肯定不是冬季

条件成真还是不成真都是确定的

那么信息就有第三种状态

就是现在没有信息

用petri网来述描述一位信息

我们怎么描述呢

条件我们可以用一个s元素来表示

里面有token表示条件成真

里面没有token表示条件不成真

我们要想表示one bit information

我们不能用一个条件一个s元素来表示

因为一个s元素只有两种状态

有token或者没有token

我们用两个s元素来表示

s元素里面如果有token等于一

另外一个s元素里面如果有token表示a等于0

所以a等于1和a等于0如果有信息的话

就是分别在两个s元素里面分别有token

就代表了它的值是0或者是1

那么没有信息呢

就是两个s元素里面都没有token

这叫没有信息

这两个s元素

因为他表示的是

同一个信息同一个one bit information

因此他不可能两个s元素里面都有token

因为那就表示既成真又不成真

既等于0又等于1

所以我们用事实来表示

最后我们用两个s元素

用一个t元素

一个事实一个不能发生的事实

来描述它们之间的相关性

这三个元素构成的就叫做信息站

一个lnformation station

这个信息站代表的是一位信息

可以是零可以是1

可以是没有信息

t元素事实就排除了

同时为1或者为0的可能性

要注意信息流

关键在于信息的流动

和信息在流动当中的交互作用

所以在这个信息论里面有几种箭头函数

我这里统一写成n箭头函数

n可以是1可以是2可以是3

可以是任何一个正整数

n箭头函数是什么意思呢

前面n个信息x1到xn

在流动

在流动过程当中

他们同时都作用于

第n加一个信息就是那个y

我们这个表示的是

x1到xn都有一个黑点

可能看见的是个圆圈

是一个黑点

跟流动的箭头联系在一起

最后箭头指向

最后数的箭头

跟x1到xn都有黑点联系的

最后指向的是y

这个y那就是受影响的

被作用的信息

x1到xn都没有改变

y这个信息被n这个一位信息改变了

改变成什么呢

就是用后面这个公式来计算

改变u

u是y加上后面这些

x1到xn乘起来

然后来一个exclusive or

y要成真这两个里面只有一个成真

另外一个不成真的时候那是1

两个都成真或者两个都不成真那是0

运算符的符号这就是n箭头函数

n位信息作用在同一个信息上面

产生了一个新的信息

这就是信息的交互作用

另外还有一个箭头函数

叫做q函数

Q函数有三个流动的信息

one bit information组成的

中间的是b

abc这三个一位信息

作用是必定有一位信息作用在a和c上面

数改变的

改变的是a或c

不改变的b

b是流动过去

他要影响a或c

受影响以后的a或c怎么计算呢

就是片子上写的公式

如果我们仔细分析一下就知道

这个Q函数的作用就是

当b等于1的时候

交换a或c的值

a流动着的输出变成c了

c流动着的经过作用以后

Q作用以后变成a

这就是当b等于1的时候

他会交换a或c两个信息

输出就改变了

如果b要是等于0呢

那a或c不受影响

两个特例第一个特例是

a输入的是个零是个长信息

一个constant information是0

那我们知道它输出的

在c上面输出的是什么呢

就是c and b

我们得到了一个

and的运算符

我们可以用Q函数来做an的运算

如果这个c是constant1

那么我们得到的就是or这个运算符

所以Q函数可以表达来描述

逻辑运算上面的or还有and

那个not也很容易表示

所以从这里我就体会到

因为计算机里面的机器指令

无非就是not

or或者and

所以如果petri网能够正确的表达

and运算or运算not运算

那么岂不是就等价了吗

这就是一种证明的方式

有了这两种这个函数

这两种函数有什么性质呢

性质就是

它们都是可逆的

用Q来作用于a或c

如果你用Q作用两次

如果b等于1第一次把a和c交换了

在作用一次

又把a和c交换了

那岂不是交换回来了吗

所以作用两次等于不作用

所以这个是可以逆过来的

倒过来运算的

那么箭头函数也是

很容易就能够证明它是可逆的

这是第一个性质

两个函数都是可逆的

另外所有的箭头函数

都可以用p1

就是n等于1的时候的p1

或Q表示

于是乎如果我们能够把p1

或Q都用petri网来表示

那么所有的信息流动

就可以用petri网来表示

我们看看这个图就是p1

第一箭头函数它的网表示

它的petri网表示

一个信息是有两个s元素来表示

所以a

有两个s元素一个是a等于0另一个是a等于1

那么这个b也是b等于0 b等于1

a是传递过去所以a一撇呢就等于a

a是流动的不受影响的

所以流动过去的是a一撇

a一撇等于1a等于1a一撇等于1

a等于0a一撇等于0

你就分析分析这个这个网

如果这个a里面有token

你最后不管这个b是什么

是b等于1有token还是b等于0有token

最后token都会流动到a一撇等于1里面去

b也是b也可能0也可能是1

所以a等于0a等于1两个里面有两个token

b等于0b等于1这两个有一个token

这时候我们这两个信息都有值了

就b1就可以交互了

这个图就是

p1这个第一箭头它的网表示

当a或b都有信息的时候

他们的交互

以及交互产生的结果

什么叫做a有信息

那就是a等于0或者a等于1里面

其中的一个有token

什么叫做b有信息

就是b等于1或b等于0两个里面

有一个有token

这样一来这4个变迁

有一个能够发生了

发生的结果你自己去分析一下

就可以看到如果a等于一

a一撇等于一里面会获得token

如果是a等于0那么a一撇等于0

这里面会有token

这表示a是在流动

它没有被改变

那么如果u是它的输出

所以u等于1表示什么呢

是表示a跟b这两个其中

有一个是0有一个1

不是那个exclusive or

两个里面有一个是1一个是0

它得到的就是1

两个都是0或者两个都是1得到那就是零

这就是b这条信息

受到了a的影响以后

得到的输出是u等于1

或者u等于0

这就是第一箭头函数

petri网的表示

为了让大家了解

信息流动底有什么作用

有个直观的印象

我们现在来讲一个故事

我上次已经讲了一个犯人在监狱里面

法官想要放他一条生路

让他猜一猜哪一天会处死他

结果他非常的自信

觉得法官处死不了他

结果就在那里等死了

这个问题呢还是一个犯人

还是关在监狱里

还是法官过来跟他说

这个法官也想放他一条生路

可能法官制造冤假错案比较多吧

就想放他一条生路

跟他说

你这个房间有两个门

一个门出去呢是一辆汽车

你就自由了

你如果从那个门出去

你就能自由了

可以有汽车送你回家

另一个门

外面是一层脚架

你如果从那个门出去马上就被处死

你要选择一个门出去

怎么选呢

这两个门口分别有一个卫兵把守

应该是a卫兵一个是b卫兵

这两个卫兵有一个人总说真话

不是真人啊不是真正的人总说真话的

还有一个人老说假话

也不是普通的人至少不是普通人吧

说这两个人一个老说真话一个老说假话

现在允许你问一个是非问题

这个卫兵只能回答你是还是不是还是非

你问了这个问题以后根据

卫兵的回答你选择一个门出去

然后是死是活看你选的对不对

我们的问题是什么呢

问题就是你能不能帮助这个犯人

设计一个是非题

然后让他根据这个回答

选出那个活门

让他出去就看见汽车

这个问题就是设计一个是非问题

帮助这个犯人

问卫兵问题

根据卫兵的回答选一个门出去

这里面有一个问题

有人很聪明说了

我去问卫兵a

说如果我问卫兵b

这个门是不是活门出去就活了

他会怎么回答

因为他肯定说的是反话

有一个说真话一个说假话吗

经过一正一反以后肯定是反

所有他觉得我很聪明我这就能出去了

但这不是一个是非题

什么是是非题

是非题就是有一个陈述句

我陈述一个事实

然后让你来回答判断

我陈述的这个事实成真还是不成真

这个叫做是非题

那个问题不是是非题

你可以问

任何一个是非题

但是就不能这样的问

一般人都会把这样的问题当做一个游戏题

我听到这个问题

就是我在多伦多大学

食堂里面吃饭的时候一个外国学生

他们在那讨论我听来的

这个题目大家有没有办法

帮他设计这个是非题

我告诉你

你如果把这个问题

用信息流动和信息交互作用的这个角度

来分析它

你就能够找到正确的答案

第一箭头函数

一位信息作用在另一个一位信息上面

我们现在有没有信息我们现在有两位信息

一位信息就是卫兵是说真话还是说假话

你去找一个卫兵问

这个卫兵

要么说真话要么说假话

所以这个信息是有值的

但是你不知道

另外这个门也是一位信息

他背后的门要么是活门

要么是死门

所以就有两位信息

我们这个是非题

必须要让这两个

信息交互作用

交互作用的结果是什么

正常流动的

让卫兵的信息正常的流动过来

我们听不到

反正他流动过来了

你说真话就说真话

说假话就说假话

这个信息我们听不到

我们要想听到的信息是什么呢

我希望得到这样的效果

就是你背后的那个门

是活门的话

你就说yes

你背后的门是死门的话

你就是说No

这个tf就是卫兵

t里面有token说明这个卫兵说真话

F里面有token说明这个卫兵说假话

l里面有token说明他背后的门是活门

D里面有token说明他背后的门是死门

我们期待的结果是什么

就是u等于1卫兵后面的门是活门

我们看这个活门

活门参与两个变迁

一个是跟t第一个

一个是第三个

第一个是说真话的卫兵守着活门

他要说yes

就是u等于1

第二个呢

是说假话的人

守着活门

他会说1如果我们从信息流动

信息交互的这个角度来分析这个问题

那么就可以迎刃而解了

我们期待的效果是什么

u回答1的时候就是卫兵回答yes

u等于1的时候

他的背后是活门

回答是u等于0就是No的时候

他就背后是死门

能够产生u等于1的一共有两个变迁

第二个变迁和第三个变迁

第一个变迁是什么呢

这个说真话的卫兵

看守他的背后是什么是死门

d得到的是u等于1

还有第三个变迁

输出也是u等于1这是什么呢

就是说假话的那个卫兵守的是死门

什么样的问题能够使得

说真话的说yes

说假话的也说yes

说真话的守着死门

说假话的守着活门是不是一回事

说真话的守着死门

说假话的当然要守着活门

你就问这个

说真话的卫兵是守着死门吗

这个时候说真话的人

他会说yes

因为他守着的就是死门

这个问题大家把它当做一个游戏来玩

好像是凭自己的聪明才智

想出一个来

拍脑袋

聪明人想出来了

我就这么问

如果信息流系统

能够给我们启发

如果我们用信息流动

信息交互的作用来思考这个环境

这个卫兵和门的关系

就能够

第一箭头函数就能和他联系起来

第一箭头函数就能帮助我们

找到这个是非题

今天我先不往下讲

下次我来帮大家分析

你回去以后

自己想想看第一箭头函数

怎么帮助你想出是非题

得到一个正确的是非问题

帮助这个犯人找到一条生路

所以关键就是

对应用题有个环境的理解和分析

从信息流动信息交互的

角度来理解分析

当时我还在数学所

当时解决了这个问题以后

有一次有一个机会

我跟另外一个同事有一次交流

他告诉我在Knuth

他是个计算机的神童

曾经在很年轻的时候就

号称在上个世纪的70年代吧

他要写七本书

来讲算法

他已经出了三本

我通过调查

计算机发展实在太快了

他写不出来这几本书了

他写了三本就不写了

这是个名人

你们可能年纪轻的人不知道

Knuth

这是他的姓

在他的书上有一个练习题

他打了两个星号说是很难很难的一个题

我为什么提到这个题目

就是因为我刚才说了我跟我的同事

有一次交流的机会

他看了这个题目他跟我说

这个题目出错了

我要来证明这个题目是无解的

你这个题目是个什么题目呢

他跟我讲

说有一个朋友接待他的一位客人

领着这个客人就到当地的一个饭馆去吃饭

正好看见有一张圆桌子上面坐了三个人

这三个人在当地是家喻户晓的名人

主人就跟客人介绍了

说你看见这三个人没有

这三个人是我们当地的名人

他们三个当中

有一个

老说真话从来不说假话

有一个总说假话从来不说真话

他们三个里面只有一个普通人

有时候说真话有时候说假话

你看看能不能够用三个是非题

判断出这三个人谁说真话

谁说假话谁是一个普通人

设计这回是三个是非题

那我这个同事呢

认为他思考了很长时间

觉得这是无解的

是不可能有解的

他想要做的事

就是证明这个题目错了

但是这个题目没有错

这个题目是有解的

而且关键就在一步

迈出了成功的第一步第二步第三步

都不是问题了

第一步是什么

就是用信息流动

或信息交互作用来理解这个问题

来分析这个问题

我们这里有几位信息

有三个人

刚才我们那个问题

有一个犯人

有两个门

有两个卫兵

从人的角度来讲也是三个

我们能不能够把它联系起来

把这三个人就桌子上的三个人

一个说真话一个说假话

还有个普通人

能不能把他联系起来

跟我们刚才讲的第一个问题联系起来

如果你的第一个问题有解了

这三个人的问题

你能够正确的对应

那么就很容易

把这个问题

给出他的答案了

我提示一下

今天这个问题我是以后也不会给解的

你自己去想

我就提示一下

你把那个普通人

当成是门

这样就剩下两个人

一个说真话一个说假话

然后你的头两个问题要做的是什么

就是把这个普通人找出来

你如果两个问题能够

把这个普通人也就是这个门找出来

剩下那两个人

一个说真话一个说假话

你想判断还不容易吗

这是桌子吗

他说是那是说真话

他说不是他说假话

所以关键是有两个是非问题

把那个普通人可以找出来

这两个问题怎么设计

你就把这个普通人当成那个门就行了

守卫关系

卫兵跟门有一个看守的关系

谁守着那个门

有这个关系