《可视化计算》第4章模型化(A).ppt

电子宠物状态机的技术解决方案 * 电子宠物状态机的用户界面 * 电子宠物游戏实现的一些说明 用户输入，是通过检查鼠标的光标所处的区域来实现，在normal和sad两个状态，用户只要将鼠标的光标指向相应的指令区域，程序循环到检查环节，就会接收指令，然后进行状态转换； Normal状态设置的倒计数是从10→0，建议读者在试运行时，降低RAPTOR的运行速度，否则，状态转换的过程会非常模糊或呈现中画面闪烁的情况； * 有限状态机的设计的启示 有限状态机的状态转移表和状态转移图是设计的基础与关键 为每个状态设计一个子图，并在子图中处理状态转换的各种条件和事件 按照有限状态机的状态转移图对算法和程序进行测试，验证状态转移是否符合要求 * 为什么要讨论图灵机? 阿兰·图灵（Alan Turing）启发与影响了他身后的整个计算机发展史 图灵在现代计算机出现之前，就开始考虑用机器来模拟人们用纸笔进行数学运算的过程 * 图灵机的构造 一条无限长的纸带(tape) 一个读写头(head) 一套控制规则(table) 一个状态寄存器(register) * 将图灵机描述成机械装置 * 图灵机的数学定义 图灵机是一个七元组(Q， Γ，b，Σ，δ，q0，F)，其中Q，Σ，Γ都是有限集合，且满足： Q是一个有限、非空的状态集合； Γ是一个有限、非空字母（符号）集合； b∈Γ，是一个空白符号（blank symbol），这是唯一的一个可在计算任何步骤中出现无限次的符号； Σ Γ\{b}是输入字母(符号)的集合，其中不包含特殊的空白符b； q0∈Q是起始状态； F Q是最终或可接受状态 δ：Q\F×「→Q×Γ×{L，R}是转移函数，其中L，R表示读写头是向左移还是向右移； * 图灵机的简洁定义 无限长的纸带上可以保证无限的记忆容量，纸带上标有正方形中可以打印符号 在任何时候，在机器里有一个符号，它被称为扫描到的符号 这台机器可以改变扫描到符号，而且其行为会部分受到该符号的影响； 但纸带上其他地方的符号，不影响机器的行为 但是，纸带可以在机器上前后移动，这是这台机器最基本的操作之一； 因此，任何纸带上的符号，最终会对操作状况产生影响。 * 图灵机的关注要点 这台机器的各个部分： 状态：符号的集合 动作：打印、擦除、纸带移动 都是有限的、离散的和可以区分的 它拥有无限量的纸带，所以具有无限量的储存空间 * 图灵机的五项原子操作 观察读写头下方纸带上的符号（判定当前状态） 依据观察到的符号去寻找合适的指令序列并执行（寻找行动或停机依据） 打印符号Sj,或擦除，或无任何操作（一类动作） 向左或向右移动读写头或静止不动（二类动作） 进入该符号所在的终结格局（停机或其他循环状态） * 图灵机的格局 格局包括系统中的所有状态： 内部状态（状态寄存器的内容） 纸带上左右非零的部分状况 读写头的位置 * 图灵机应用（ab回文算法） * ab回文算法运算(I) * ab回文算法运算(II) * ab回文算法运算(III) * 通用图灵机 可以构造出一个特殊的图灵机，它接受任意一个图灵机M的编码M，然后模拟M的运作，这样的图灵机称为通用图灵机(Universal Turing Machine) 现代电子计算机其实就是这样一种通用图灵机的模拟，它可以接受一段描述其他图灵机的程序，并运行程序实现该程序所描述的算法 * 用RAPTOR实现UTM的回文算法 需要关注： 这个图灵机可以接受哪些符号？ 如何模拟纸带？ 如何模拟纸带的左右移动？ 如何模拟空白符号（blank symbol 需要多少个子图来实现算法？ * UTM回文算法的设计思想（I） 这个图灵机可以接受a，b两种符号（小写的ASCII码：a、b） 如果遇到了字符集以外的符号，系统的状态图没有定义，也就不可接受！ 输入部分是否需要校验？ 绝对需要，对输入的字符串，逐个扫描，遇到非法字符，立刻退出系统（因为状态图没有定义如何处理非法输入） * UTM回文算法的设计思想（II） 如何模拟纸带？ 使用字符串变量保存输入的字符串，可以按照下标访问，这就等于将字符放在编号的格子中 如何模拟纸带的左右移动？ 由于使用了字符串和字符串中字符访问的下标，只要设置字符串的下标变量，通过增1和减1，就可以模拟纸带的右移和左移 * UTM回文算法的设计思想（III） 如何模拟空白符号（blank symbol）？ 使用“#”号，在用户输入字符串时，自动在字符串尾加上一个“#”符号，机器检测到该符号，就知道是空白符号。 同样，需要按照状态图(在纸带上)写入空白符号的时候，也是使用“#”写入 * TM回文算法的子图调用关系 * 有限状态机 vs 图灵机 相同之处： 二者都可以使用状态图和状态表