《《可视化计算》第4章模型化(a)》由会员分享，可在线阅读，更多相关《《可视化计算》第4章模型化(a)（48页珍藏版）》请在金锄头文库上搜索。
1、第4章 模型化 PART A可视化计算1http:/学习目标 什么是模型?如何设计和应用有限状态机?为什么要讨论图灵机?什么是抽象数据类型?哪些抽象数据类型可以使用RAPTOR实现 或模拟?2http:/什么是模型? 模型（model）的定义：用以分析问题的概 念、数学关系、逻辑关系和算法序列的表 示体系人们依据研究的特定目的，在一定的假设 条件下，再现原型（antitype）客体的结构 、功能、属性、关系、过程等本质特征的 物质形式或思维形式。 3http:/模型的分类 1.物理模型，可分为实物模型和类比模型2数学模型用数学语言描述的一类模型。 3结构模型反映系统结构特点和因果关系的模型。
2、4仿真模型能够在数字计算机、模拟计算机或混合计算机 上运行的程序表达的模型4http:/如何建立模型? 数学建模和仿真建模是许多算法研究和开 发的基础数学建模是算法设计的重要基石，所有算 法的描述和算法分析无疑离不开数学建模d 的基础本章选取了在科学研究和算法研究上都十 分重要的有限状态机和图灵机作为主要的 案例，来说明建模和仿真的算法实现过程 5http:/什么是有限状态机? 有限状态机（finite-state machine， FSM ），又称有限状态自动机，简称状态机， 是刻画某项事物所具备的有限个状态以及 在这些状态之间的转移和动作等行为的数 学模型有限状态自动机在电子工程、语言学、
3、计 算机科学、哲学、生物学、数学和逻辑学 等领域中都是极为重要的 6http:/有限状态机的基本概念状态(state)存储关于过去的信息它反映从系统开始到现在时刻的输入变化转移(transition)指示状态变更用必须满足并促使转移发生的转移条件 (transition condition)或事件（event）来描述它动作（action）是在给定时刻要进行的活动 的描述7http:/动作的类型进入动作（entry action）在进入状态时发生退出动作(exit action)在退出状态时发生输入动作(input action)依赖于当前状态和输入条件进行转移动作(transition act
4、ion)在发生特定转移时进行 8http:/有限状态机的描述状态转移图状态转移表 当前状态/条件OpenedClosedClose doorClosedOpen doorOpened9http:/有限状态机的类型(1)1.接受器和识别器(Acceptors and recognizer)：也叫做序列检测器（ sequence detectors）产生一个二元输出，用“是”或“否”来回答输 入是否被机器接受10http:/序列检测器术语开始状态(Start state)：该状态通常用“没有 起点的箭头”指向它来表示；可接受（或最终状态）状态（Accept (or final) states）：该
5、状态是机器在报告到目 前为止处理的所有输入串都是可接受状态 语言的成员，它通常表示为双重圆圈11http:/序列检测器案例一个检测二进制数具有奇数或者偶数个0的 状态机该状态机可以接受的例子包括，空串、1、 11、11.、00、 010， 1010、10110等等12http:/有限状态机的类型(2)变换器(Transducers)变换器基于给定输入和状态(或对某个状态采取 某种动作)而生成输出。它们一般应用于控制装 置的设计中摩尔机（Moore machine）：其输出信号仅与 当前状态有关，即可以把Moore机的输出看成 是当前状态的函数米勒机（Mealy machine）：其输出信号不仅
6、 与当前状态有关，而且还与所有的输入信号有 关13http:/米勒机 vs 摩尔机14http:/有限状态机的数学定义接受器是五元组(，S，s0，F）这里的：是输入字母表（符号的非空有限集合）S是状态的非空有限集合s0是初始状态，它是S的元素是状态转移函数： SS。F是最终状态的集合，S的（可能为空）子集15http:/有限状态机的数学定义变换器是六元组(，S，s0，）， 这里的：是输入字母表（符号的非空有限集合）是输出字母表（符号的非空有限集合）S是状态的非空有限集合s0是初始状态，它是S的元素是状态转移函数：SS是输出函数16http:/有限状态机的数学定义如果输出函数是状态和输入字母表的
7、函数 (：S)，则定义对应于米勒模型，它 可以建模为米勒机如果输出函数只依赖于状态(：S)，则 定义对应于摩尔模型，它可建模为摩尔机17http:/如何设计和应用有限状态机?请设计一个算法实现一个运用了有限状态 机的电子宠物游戏，为了简化处理，设计 该宠物只有三种状态：当前状态/条件gladnormalsadtouchnormalplaygladignorenormalsad18http:/电子宠物状态机设计要求绘制该游戏的有限状态机的状态转移图。游戏的设计要求是，使用RAPTOR的图形 界面实现，使用三张图片来表示宠物的状 态，同时使用文字显示宠物所处状态的时 间（其中，glad和norma
8、l状态使用倒计数，计数值为0时，触发 ignore动作，进行状态变换；sad状态使用正计数）在图形界面上，设置两个操作区，分别接 收玩家输入的touch和play动作，进行状态 转换19http:/电子宠物状态机设计(状态图)20http:/可视化有限状态机的实现涉及到的指令问题包括：如何在图形界面中展示图片？如何在图形界面中显示文字？如何在图形界面中刷新文字（擦除原有的文字 ，在原地重新写入）？如何在图形界面下收集用户的输入？如何使用鼠标进行程序的输入？21http:/电子宠物状态机的技术解决方案22http:/电子宠物状态机的用户界面23http:/电子宠物游戏实现的一些说明用户输入，是通
9、过检查鼠标的光标所处的 区域来实现，在normal和sad两个状态，用 户只要将鼠标的光标指向相应的指令区域 ，程序循环到检查环节，就会接收指令， 然后进行状态转换；Normal状态设置的倒计数是从100，建议 读者在试运行时，降低RAPTOR的运行速 度，否则，状态转换的过程会非常模糊或 呈现中画面闪烁的情况；24http:/有限状态机的设计的启示有限状态机的状态转移表和状 态转移图是设计的基础与关键为每个状态设计一个子图，并 在子图中处理状态转换的各种 条件和事件按照有限状态机的状态转移图 对算法和程序进行测试，验证 状态转移是否符合要求25http:/为什么要讨论图灵机?阿兰图灵（Ala
10、n Turing）启发 与影响了他身后的整个计算机 发展史图灵在现代计算机出现之前， 就开始考虑用机器来模拟人们 用纸笔进行数学运算的过程26http:/图灵机的构造一条无限长的纸带(tape)一个读写头(head)一套控制规则(table)一个状态寄存器(register)27http:/将图灵机描述成机械装置28http:/图灵机的数学定义图灵机是一个七元组(Q， ，b，q0，F)，其中Q ，都是有限集合，且满足：Q是一个有限、非空的状态集合；是一个有限、非空字母（符号）集合；b，是一个空白符号（blank symbol），这是唯一 的一个可在计算任何步骤中出现无限次的符号； b是输入字母
11、(符号)的集合，其中不包含特殊的空 白符b；q0Q是起始状态；F Q是最终或可接受状态：QFQL，R是转移函数，其中L，R表示 读写头是向左移还是向右移；29http:/图灵机的简洁定义无限长的纸带上可以保证无限的记忆容量，纸带 上标有正方形中可以打印符号在任何时候，在机器里有一个符号，它被称为扫 描到的符号这台机器可以改变扫描到符号，而且其行为会部 分受到该符号的影响；但纸带上其他地方的符号，不影响机器的行为但是，纸带可以在机器上前后移动，这是这台机 器最基本的操作之一；因此，任何纸带上的符号，最终会对操作状况产 生影响。30http:/图灵机的关注要点这台机器的各个部分：状态：符号的集合动
12、作：打印、擦除、纸带移动都是有限的、离散的和可以区分的它拥有无限量的纸带，所以具有无限量的储存 空间31http:/图灵机的五项原子操作1.观察读写头下方纸带上的符号（判定当前状态）2.依据观察到的符号去寻找合适的指令序列并执行 （寻找行动或停机依据）3.打印符号Sj,或擦除，或无任何操作（一类动作）4.向左或向右移动读写头或静止不动（二类动作）5.进入该符号所在的终结格局（停机或其他循环状 态）32http:/图灵机的格局格局包括系统中的所有状态：内部状态（状态寄存器的内容）纸带上左右非零的部分状况读写头的位置33http:/图灵机应用（ab回文算法）34http:/ab回文算法运算(I)3
13、5http:/ab回文算法运算(II)36http:/ab回文算法运算(III)37http:/通用图灵机可以构造出一个特殊的图灵机，它接受任 意一个图灵机M的编码，然后模拟M的 运作，这样的图灵机称为通用图灵机 (Universal Turing Machine)现代电子计算机其实就是这样一种通用图 灵机的模拟，它可以接受一段描述其他图 灵机的程序，并运行程序实现该程序所描 述的算法38http:/用RAPTOR实现UTM的回文算法需要关注：这个图灵机可以接受哪些符号？如何模拟纸带？如何模拟纸带的左右移动？如何模拟空白符号（blank symbol需要多少个子图来实现算法？39http:/UT
