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

《《可视化计算》第4章模型化.ppt》由会员分享，可在线阅读，更多相关《《可视化计算》第4章模型化.ppt（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第4章 模型化 PART A可视化计算1学习目标 什么是模型?如何设计和应用有限状态机?为什么要讨论图灵机?什么是抽象数据类型?哪些抽象数据类型可以使用RAPTOR实现或模拟?2什么是模型?模型（model）的定义：用以分析问题的概念、数学关系、逻辑关系和算法序列的表示体系人们依据研究的特定目的，在一定的假设条件下，再现原型（antitype）客体的结构、功能、属性、关系、过程等本质特征的物质形式或思维形式。3模型的分类 1.物理模型物理模型，可分为实物模型和类比模型2数学模型数学模型用数学语言描述的一类模型。3结构模型构模型反映系统结构特点和因果关系的模型。4仿真模型仿真模型能够在数字计算机

2、、模拟计算机或混合计算机上运行的程序表达的模型4如何建立模型?数学建模和仿真建模是许多算法研究和开发的基础数学建模是算法设计的重要基石，所有算法的描述和算法分析无疑离不开数学建模d的基础本章选取了在科学研究和算法研究上都十分重要的有限状态机和图灵机作为主要的案例，来说明建模和仿真的算法实现过程 5什么是有限状态机?有限状态机（finite-state machine，FSM），又称有限状态自动机，简称状态机，是刻画某项事物所具备的有限个状态以及在这些状态之间的转移和动作等行为的数学模型有限状态自动机在电子工程、语言学、计算机科学、哲学、生物学、数学和逻辑学等领域中都是极为重要的 6有限状态机的

3、基本概念状态(state)存储关于过去的信息它反映从系统开始到现在时刻的输入变化转移(transition)指示状态变更用必须满足并促使转移发生的转移条件(transition condition)或事件（event）来描述它动作（action）是在给定时刻要进行的活动的描述7动作的类型进入动作（entry action）在进入状态时发生退出动作(exit action)在退出状态时发生输入动作(input action)依赖于当前状态和输入条件进行转移动作(transition action)在发生特定转移时进行 8有限状态机的描述状态转移图状态转移表 当前状态当前状态/条件条件Opened

4、ClosedClose doorClosedOpen doorOpened9有限状态机的类型(1)1.接受器和接受器和识别器器(Acceptors and recognizer)：也叫做序列检测器（sequence detectors）产生一个二元输出，用“是”或“否”来回答输入是否被机器接受10序列检测器术语开始状开始状态(Start state)：该状态通常用“没有起点的箭头”指向它来表示；可接受（或最可接受（或最终状状态）状）状态（Accept(or final)states）：）：该状态是机器在报告到目前为止处理的所有输入串都是可接受状态语言的成员，它通常表示为双重圆圈11序列检测器案

5、例一个检测二进制数具有奇数或者偶数个0的状态机该状态机可以接受的例子包括，空串、1、11、11.、00、010，1010、10110等等12有限状态机的类型(2)变换器器(Transducers)变换器基于给定输入和状态(或对某个状态采取某种动作)而生成输出。它们一般应用于控制装置的设计中摩摩尔机（机（Moore machine）：）：其输出信号仅与当前状态有关，即可以把Moore机的输出看成是当前状态的函数米勒机（米勒机（Mealy machine）：）：其输出信号不仅与当前状态有关，而且还与所有的输入信号有关13米勒机 vs 摩尔机14有限状态机的数学定义接受器接受器是五元组(，S，s0，

6、F）这里的：是输入字母表（符号的非空有限集合）S是状态的非空有限集合s0是初始状态，它是S的元素是状态转移函数：SS。F是最终状态的集合，S的（可能为空）子集15有限状态机的数学定义变换器器是六元组(，S，s0，），这里的：是输入字母表（符号的非空有限集合）是输出字母表（符号的非空有限集合）S是状态的非空有限集合s0是初始状态，它是S的元素是状态转移函数：SS是输出函数16有限状态机的数学定义如果输出函数是状态和输入字母表的函数(：S)，则定义对应于米勒米勒模型，它可以建模为米勒米勒机如果输出函数只依赖于状态(：S)，则定义对应于摩摩尔模型，它可建模为摩摩尔机17如何设计和应用有限状态机?请设

7、计一个算法实现一个运用了有限状态机的电子宠物游戏，为了简化处理，设计该宠物只有三种状态：当前状态当前状态/条件条件gladnormalsadtouchnormalplaygladignorenormalsad18电子宠物状态机设计要求绘制该游戏的有限状态机的状态转移图。游戏的设计要求是，使用RAPTOR的图形界面实现，使用三张图片来表示宠物的状态，同时使用文字显示宠物所处状态的时间（其中，glad和normal状态使用倒计数，计数值为0时，触发ignore动作，进行状态变换；sad状态使用正计数）在图形界面上，设置两个操作区，分别接收玩家输入的touch和play动作，进行状态转换19电子宠物

8、状态机设计(状态图)20可视化有限状态机的实现涉及到的指令问题包括：如何在图形界面中展示图片？如何在图形界面中显示文字？如何在图形界面中刷新文字（擦除原有的文字，在原地重新写入）？如何在图形界面下收集用户的输入？如何使用鼠标进行程序的输入？21电子宠物状态机的技术解决方案22电子宠物状态机的用户界面23电子宠物游戏实现的一些说明用户输入，是通过检查鼠标的光标所处的区域来实现，在normal和sad两个状态，用户只要将鼠标的光标指向相应的指令区域，程序循环到检查环节，就会接收指令，然后进行状态转换；Normal状态设置的倒计数是从100，建议读者在试运行时，降低RAPTOR的运行速度，否则，状态

9、转换的过程会非常模糊或呈现中画面闪烁的情况；24有限状态机的设计的启示有限状态机的状态转移表和状态转移图是设计的基础与关键为每个状态设计一个子图，并在子图中处理状态转换的各种条件和事件按照有限状态机的状态转移图对算法和程序进行测试，验证状态转移是否符合要求25为什么要讨论图灵机?阿兰图灵（Alan Turing）启发与影响了他身后的整个计算机发展史图灵在现代计算机出现之前，就开始考虑用机器来模拟人们用纸笔进行数学运算的过程26图灵机的构造一条无限长的纸带(tape)一个读写头(head)一套控制规则(table)一个状态寄存器(register)27将图灵机描述成机械装置28图灵机的数学定义图

10、灵机是一个七元组(Q，b，q0，F)，其中Q，都是有限集合，且满足：Q是一个有限、非空的状态集合；是一个有限、非空字母（符号）集合；b，是一个空白符号（blank symbol），这是唯一的一个可在计算任何步骤中出现无限次的符号；b是输入字母(符号)的集合，其中不包含特殊的空白符b；q0Q是起始状态；F Q是最终或可接受状态：QFQL，R是转移函数，其中L，R表示读写头是向左移还是向右移；29图灵机的简洁定义无限长的纸带上可以保证无限的记忆容量，纸带上标有正方形中可以打印符号在任何时候，在机器里有一个符号，它被称为扫描到的符号这台机器可以改变扫描到符号，而且其行为会部分受到该符号的影响；但纸带

11、上其他地方的符号，不影响机器的行为但是，纸带可以在机器上前后移动，这是这台机器最基本的操作之一；因此，任何纸带上的符号，最终会对操作状况产生影响。30图灵机的关注要点这台机器的各个部分：状态：符号的集合动作：打印、擦除、纸带移动都是有限的、离散的和可以区分的它拥有无限量的纸带，所以具有无限量的储存空间31图灵机的五项原子操作1.观察读写头下方纸带上的符号（判定当前状态）2.依据观察到的符号去寻找合适的指令序列并执行（寻找行动或停机依据）3.打印符号Sj,或擦除，或无任何操作（一类动作）4.向左或向右移动读写头或静止不动（二类动作）5.进入该符号所在的终结格局（停机或其他循环状态）32图灵机的格

12、局格局包括系统中的所有状态：内部状态（状态寄存器的内容）纸带上左右非零的部分状况读写头的位置33图灵机应用（ab回文算法）34ab回文算法运算(I)35ab回文算法运算(II)36ab回文算法运算(III)37通用图灵机可以构造出一个特殊的图灵机，它接受任意一个图灵机M的编码，然后模拟M的运作，这样的图灵机称为通用图灵机(Universal Turing Machine)现代电子计算机其实就是这样一种通用图灵机的模拟，它可以接受一段描述其他图灵机的程序，并运行程序实现该程序所描述的算法38用RAPTOR实现UTM的回文算法需要关注：这个图灵机可以接受哪些符号？如何模拟纸带？如何模拟纸带的左右移

13、动？如何模拟空白符号（blank symbol需要多少个子图来实现算法？39UTM回文算法的设计思想（I）这个图灵机可以接受a，b两种符号（小写的ASCII码：a、b）如果遇到了字符集以外的符号，系统的状态图没有定义，也就不可接受！输入部分是否需要校验？绝对需要，对输入的字符串，逐个扫描，遇到非法字符，立刻退出系统（因为状态图没有定义如何处理非法输入）40UTM回文算法的设计思想（II）如何模拟纸带？使用字符串变量保存输入的字符串，可以按照下标访问，这就等于将字符放在编号的格子中如何模拟纸带的左右移动？由于使用了字符串和字符串中字符访问的下标，只要设置字符串的下标变量，通过增1和减1，就可以模

14、拟纸带的右移和左移41UTM回文算法的设计思想（III）如何模拟空白符号（blank symbol）？使用“#”号，在用户输入字符串时，自动在字符串尾加上一个“#”符号，机器检测到该符号，就知道是空白符号。同样，需要按照状态图(在纸带上)写入空白符号的时候，也是使用“#”写入42TM回文算法的子图调用关系43有限状态机 vs 图灵机相同之相同之处：二者都可以使用状态图和状态表，进行状态转移的描述。不同之不同之处：图灵机可以接受写入；而有限状态机则不可以图林机有寄存器；而有限状态机则没有44图灵机的意灵机的意义与思想内涵与思想内涵1、它证明了通用计算理论，肯定了计算机实现的可能性，同时它给出了计

15、算机应有的主要架构；2、图灵机模型引入了读写、算法和程序语言的概念，在很大程度上突破了在他之前的计算机的设计理念；3、图灵机模型理论是计算机学科最核心的理论，因为计算机的极限计算能力就是通用图灵机的计算能力45图灵机与现代计算机现代计算机主要构成（如冯诺依曼体系结构）存储器（相当于纸带）中央处理器（控制器及其状态，并且其字母表可以仅有0和1两个符号）I/O系统（相当于纸带上的符号扫描（输入）和结果写入（输出）现代计算机，其内存的组织在逻辑上也是一维数组，与“纸带”的形式相似46数据与线性化由于计算机内存系统的一维数组的组织形式，导致无论何种现实世界中的数据格式必须处理成为“线性化”的格式才能保存在计算机中这就是本章第二部分的主要内容:抽象数据类型47End of ch4-148