隐藏信息检测与还原技术课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《隐藏信息检测与还原技术课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 隐藏 信息 检测 还原 技术 课件
- 资源描述:
-
1、1第二部分第二部分 分布式算法分布式算法汪炀汪炀第二次课第二次课中国科学技术大学计算机系中国科学技术大学计算机系 国家高性能计算中心(合肥)国家高性能计算中心(合肥)22.1.1 系统系统2.异步系统异步系统n 异步:异步:msg传递的时间和一个处理器的两个相继步骤之间的传递的时间和一个处理器的两个相继步骤之间的时间无固定上界时间无固定上界例如,例如,Internet中,中,email虽然常常是几秒种到达,但也可能虽然常常是几秒种到达,但也可能要数天到达。当然要数天到达。当然msg延迟有上界,但它可能很大,且随时延迟有上界,但它可能很大,且随时间而改变。间而改变。因此异步算法设计时,须使之独立
2、于特殊的计时参数,不能因此异步算法设计时,须使之独立于特殊的计时参数,不能依赖于该上界。依赖于该上界。n 执行片断执行片断一个异步一个异步msg传递系统的一个执行片断传递系统的一个执行片断是一个有限或无限是一个有限或无限的序列:的序列: C0, 1, C1, 2, C2, 3, , (C0不一定是初始配置不一定是初始配置)这里这里Ck是一个配置,是一个配置, k是一个事件。若是一个事件。若是有限的,则它是有限的,则它须结束于某个配置,且须满足下述条件:须结束于某个配置,且须满足下述条件:32.1.1 系统系统v若若k =del(i,j,m),则,则m必是必是Ck-1里的里的outbufill的
3、一个元素,这的一个元素,这里里ll是是pi的信道的信道pi,pj的标号的标号从从Ck-1到到Ck的唯一变化是将的唯一变化是将m从从Ck-1里的里的outbufill中删去,并将中删去,并将其加入到其加入到Ck里的里的inbufjh h中,中,h是是pj的信道的信道pi,pj的标号。的标号。即:传递事件将即:传递事件将msg从发送者的输出缓冲区移至接收者的输入从发送者的输出缓冲区移至接收者的输入缓冲区。缓冲区。v若若k =comp(i),则从,则从Ck-1到到Ck的变化是的变化是改变状态:转换函数在改变状态:转换函数在pi的可访问状态的可访问状态(在配置在配置Ck-1里里)上进行上进行操作,清空
4、操作,清空inbufill,(1llr)发送发送msg:将转换函数指定的消息集合加到:将转换函数指定的消息集合加到Ck里的变量里的变量outbufi上。上。(Note:发送发送send,传递,传递delivery之区别之区别)即:即: pi以当前状态以当前状态(在在Ck-1中中)为基础按转换函数改变状态并发为基础按转换函数改变状态并发出出msg。42.1.1 系统系统n 执行:执行:一个执行是一个执行片断一个执行是一个执行片断C0, 1, C1, 2, ,这里这里C0是一个初始配置。是一个初始配置。n 调度:调度:一个调度一个调度(或调度片段或调度片段)总是和执行总是和执行(或执行片或执行片断
5、断)联系在一起的,它是执行中的事件序列:联系在一起的,它是执行中的事件序列:1, 2, 。并非每个事件序列都是调度。例如,并非每个事件序列都是调度。例如,del(1,2,m)不不是调度,因为此事件之前,是调度,因为此事件之前,p1没有步骤发送没有步骤发送(send)m。若局部程序是确定的,则执行若局部程序是确定的,则执行(或执行片断或执行片断)就由初就由初始配置始配置C0和调度和调度(或调度片断或调度片断)唯一确定,可表示为唯一确定,可表示为exec(C0 , )。52.1.1 系统系统n 容许执行:容许执行:(满足活跃性条件满足活跃性条件)异步系统中,若某个处理器有无限个计算事件,每异步系统
6、中,若某个处理器有无限个计算事件,每个发送的个发送的msg都最终被传递,则执行称为容许的。都最终被传递,则执行称为容许的。Note: 无限个计算事件是指处理器没有出错无限个计算事件是指处理器没有出错,但它,但它不蕴含处理器的局部程序必须包括一个无限循环不蕴含处理器的局部程序必须包括一个无限循环非形式地说:非形式地说:一个算法终止是指在某点后转换函数一个算法终止是指在某点后转换函数不改变处理器的状态。不改变处理器的状态。n 容许的调度:容许的调度:若它是一个容许执行的调度。若它是一个容许执行的调度。62.1.1 系统系统3.同步系统同步系统在同步模型中,处理器按锁步骤在同步模型中,处理器按锁步骤
7、(lock-step)执行:执行:执行被划分为轮,每轮里,执行被划分为轮,每轮里,每个处理器能够发送一个每个处理器能够发送一个msg到每个邻居,这些到每个邻居,这些msg被传递。被传递。每个处理器一接到每个处理器一接到msg就进行计算。就进行计算。虽然特殊的分布系统里一般达不到,但这种模型对于设虽然特殊的分布系统里一般达不到,但这种模型对于设计算法非常方便,因为无需和更多的不确定性打交道。当计算法非常方便,因为无需和更多的不确定性打交道。当按此模型设计算法后,能够很容易模拟得到异步算法。按此模型设计算法后,能够很容易模拟得到异步算法。n 轮:轮:在同步系统中,配置和事件序列可以划分成不相交的在
8、同步系统中,配置和事件序列可以划分成不相交的轮,每轮由一个传递事件轮,每轮由一个传递事件(将将outbuf的消息传送到信道上使的消息传送到信道上使outbuf变空变空),后跟一个计算事件,后跟一个计算事件(处理所有传递的处理所有传递的msg)组组成。成。72.1.1 系统系统n 容许的执行:容许的执行:指无限的执行。指无限的执行。因为轮的结构,所以因为轮的结构,所以每个处理器执行无限数目的计算步,每个处理器执行无限数目的计算步,每个被发送的每个被发送的msg最终被传递最终被传递n 同步与异步系统的区别同步与异步系统的区别在一个无错的同步系统中,一个算法的执行只取决在一个无错的同步系统中,一个算
9、法的执行只取决于初始配置于初始配置但在一个异步系统中,对于相同的初始配置及无错但在一个异步系统中,对于相同的初始配置及无错假定,因为处理器步骤间隔及消息延迟均不确定,假定,因为处理器步骤间隔及消息延迟均不确定,故同一算法可能有不同的执行。故同一算法可能有不同的执行。82.1.2 复杂性度量复杂性度量n 分布式算法的性能:分布式算法的性能:v消息复杂度消息复杂度v时间复杂度时间复杂度v空间复杂度空间复杂度v性能衡量:最坏性能、期望性能性能衡量:最坏性能、期望性能n 终止:终止:假定每个处理器的状态集包括终止状态子集,假定每个处理器的状态集包括终止状态子集,每个的每个的pi的转换函数对终止状态只能
10、映射到终止状的转换函数对终止状态只能映射到终止状态态当所有处理机当所有处理机均处于终止状态且没有均处于终止状态且没有msg在传输时在传输时,称系统称系统(算法算法)已终止。已终止。92.1.2 复杂性度量复杂性度量n 算法的算法的msg复杂性复杂性(最坏情况最坏情况):算法在所有算法在所有容许容许的的执行上发送执行上发送msg总数的最大值总数的最大值(同步和异步系统同步和异步系统)n 消息复杂度度量消息复杂度度量v消息复杂度:消息总数消息复杂度:消息总数/消息中总的位数长度消息中总的位数长度v消息总数:消息总数:4/4v消息位数总长度消息位数总长度(位复杂度位复杂度):14/8102.1.2
11、复杂性度量复杂性度量n 时间复杂度时间复杂度同步系统:最大轮数,即算法的任何容许执行直到终止的同步系统:最大轮数,即算法的任何容许执行直到终止的最大轮数。最大轮数。异步系统:假设:异步系统:假设:节点计算任何有限数目事件的时间为节点计算任何有限数目事件的时间为0;一条消息发送和接收之间的时间至多为一条消息发送和接收之间的时间至多为1个时间单位,定义个时间单位,定义为:所有计时容许执行中直到终止的最大时间。为:所有计时容许执行中直到终止的最大时间。n 计时执行计时执行(timed execution)指:指:每个事件关联一个非负实数每个事件关联一个非负实数,表示事件发生的时间。时,表示事件发生的
12、时间。时间起始于零,且须是非递减的。但对间起始于零,且须是非递减的。但对每个单个的处理器而言每个单个的处理器而言是严格增的是严格增的。若执行是无限的,则执行的时间是无界的。因此执行中若执行是无限的,则执行的时间是无界的。因此执行中的事件可根据其发生时间来排序的事件可根据其发生时间来排序不在同一处理器上的多个事件可以同时发生,在任何有不在同一处理器上的多个事件可以同时发生,在任何有限时间之前只有有限数目的事件发生。限时间之前只有有限数目的事件发生。112.1.2 复杂性度量复杂性度量n 消息的延迟消息的延迟v 发送发送msg的计算事件和处理该的计算事件和处理该msg的计算事件之间所逝去的时间的计
13、算事件之间所逝去的时间v 它主要由它主要由msg在发送者的在发送者的outbuf中的等待时间和在接收者的中的等待时间和在接收者的inbuf中的等待时间所构成中的等待时间所构成n 异步算法的时间复杂性异步算法的时间复杂性定义中,每个定义中,每个msg延时至多为延时至多为1,但,但实际中,至多实际中,至多1个时间个时间单位会很难计算,因此修改假设:单位会很难计算,因此修改假设: 一条消息发送和接收之间时间恰好为一条消息发送和接收之间时间恰好为1个时间单位个时间单位 一条消息发送和接收之间时间介于一条消息发送和接收之间时间介于和和1之间之间(0 1) 假设消息传递的延迟满足某种概率分布,并由此来计算
展开阅读全文