新型计算模型和顺序交互的数学计算机科学导论第九讲ppt课件.ppt
《新型计算模型和顺序交互的数学计算机科学导论第九讲ppt课件.ppt》由会员分享,可在线阅读,更多相关《新型计算模型和顺序交互的数学计算机科学导论第九讲ppt课件.ppt(53页珍藏版)》请在三一文库上搜索。
1、新型计算模型和顺序交互的数学 计算机科学导论第九讲,计算机科学技术学院 陈意云 0551-63607043, http:/ 程 内 容,课程内容 围绕学科理论体系中的模型理论, 程序理论和计算理论 1. 模型理论关心的问题 给定模型M,哪些问题可以由模型M解决;如何比较模型的表达能力 2. 程序理论关心的问题 给定模型M,如何用模型M解决问题 包括程序设计范型、程序设计语言、程序设计、形式语义、类型论、程序验证、程序分析等 3. 计算理论关心的问题 给定模型M和一类问题, 解决该类问题需多少资源,2,本讲座概要介绍交互计算的特点及相关的一些数学知识,讲 座 提 纲,基本知识 人机物三元世界、
2、云计算、未来网、物联网、泛在网、图灵机计算模型、网域计算模型 交互计算 经典计算与交互计算、交互的特点、交互的机器模型、能描述交互的演算 从归纳到余归纳 良基集、非良基集、余归纳、互模拟 从代数到余代数 笛卡尔积, 可区分并, 余代数, 代数和余代数的区别,3,人机物三元世界 由计算机网络世界(也称计算世界, cyber world)、物理世界和人类社会组成的人机物协同社会,是多人、多机和多物组成的动态开放并协同工作的网络社会 计算机科学是研究人机物三元世界中计算现象这个共同主线的科学 站在三元世界的高度,有助于理解云计算、未来网、物联网、泛在网(ubiquitous network)的新技术
3、趋势,基 本 知 识,4,云计算 把资源集中于互联网上的数据中心,由这种云中心提供应用层、平台层和基础设施层的集中服务 强调信息资源的聚集、优化、动态分配和回收,通过提高数据中心的效率,解决传统IT系统的零散性带来的低效率,降低信息化成本、降低能耗 向公众提供一种新的高效计算模式,兼有互联网服务的便利与廉价和大型计算机的能力 云计算可为物联网和泛在网提供后端处理能力与应用平台,基 本 知 识,5,未来网(未来互联网,post-IP network) 基于TCP/IP协议的互联网随着其广泛应用,在可扩展性、移动性、安全性、服务质量和可靠性等方面都暴露出本质缺陷 近十多年来渐进式的改进未能从根本上
4、解决问题 美国和欧盟等已开展“从零开始”的革命方式研究未来互联网 未来网可为云计算、物联网和泛在网提供更加高效安全的网络基础技术,基 本 知 识,6,物联网 实现物物互联的网络 与互联网的区别:物物互联,物机互联,而不是局限于机机互联 实现对物理世界(包括自然界和人造物)的精准感知,感知信息的实时或及时传输,针对物理世界限制的处理与决策,以及对物理世界的控制,提供高效智能的应用服务 更高层次:通过独立个体之间的局部的即时交互和分布式智能,使物体具有自组织、自计算和自反馈功能,实现物物之间的智能交互,基 本 知 识,7,基 本 知 识,泛在网 是指基于个人和社会的需求,实现人与人、人与物、物与物
5、之间按需进行的信息获取、传递、存储、认知、决策和使用等服务 具有超强的环境感知、内容感知及智能性 环境感知(environment perception):指系统具有周围环境 参数的采集、语义表达、语义查询解析和语义推理的能力 内容感知(content aware)的网络服务:意在更细致地感知 终端(PC、手机、平板电脑等) 网络(3G,Wifi等移动网络) 业务类型(游戏、视频、电子商务、微博等) 的不同需求, 提供更有针对性的解决方案和更有价值的服务,8,基 本 知 识,泛在网 是指基于个人和社会的需求,实现人与人、人与物、物与物之间按需进行的信息获取、传递、存储、认知、决策和使用等服务
6、具有超强的环境感知、内容感知及智能性 通过多种联网的智能人机交互设备,为个人和社会提供无所不在的信息服务和应用,9,基 本 知 识,区分性概括 未来网:强调对当今互联网的变革,是未来信息化的网络基础 云计算:一种新的应用模式,强调应用层信息的综合处理,可作为物联网后端处理和应用平台 物联网:强调对物感知和物物互联, 方便人类对物理世界的感知和控制,是走向泛在网的重要一步 泛在网:对未来信息社会的综合预见,是上述这些概念的集成,10,基 本 知 识,图灵机计算模型 把物理世界数字化,建立数学模型,通过计算和数据处理方法,对自然界存在的规律进行模拟仿真;计算类应用和数据处理应用都是遵循这样的计算模
7、型 按照“输入计算输出”的过程,产生的所有结果都是可以预知的 它是一个计算世界(computation world),是对人类认知的一种数字化。这个数字世界与人类社会、物理世界是正交的,11,基 本 知 识,网域计算模型 把信息化扩大到人类社会的一种计算模型 通过移动数据的方式,把人类社会中真实的工作与生活搬到计算机网络空间(cyberspace, 简称网域),即网域可以看成是对人类社会的一个映射 Cyberspace is the national environment in which communication over computer networks occurs. 其基础是通过
8、互联网、上网本(netbook)、智能手机和网络设备等手段实现的人与人之间的通信 例如,社会计算和舆情分析等都是通过对网域空间的计算来发现人类社会的规律,12,基 本 知 识,网域计算模型 网域空间的计算与图灵机计算有本质不同 不存在“停机”问题 算法不是独立的, 而是交互算法的网络(a network of interacting algorithms) 存在涌现现象(emergent phenomena),即在混沌的网上世界中能产生新的知识与智能,13,计算与交互,经典计算(简称计算) 计算主体和它的环境之间是一种简单的接口,即按照“输入计算输出”的过程完成所规定任务 计算体现出从输入到输
9、出的函数性 交互计算(简称交互) 交互计算是在完成任务的过程中包括了与外部世界通信的计算 计算主体具有与不受它控制的外部环境交互输入和输出的动作,14,交互的特点 基于交互的模型和基于图灵机的算法模型的区别 交互任务并非都能简化为函数,例如永远运行的操作系统不能由算法模拟的 在交互模型中,计算环境是模型的一部分,并且通过动态地向计算系统或计算主体提供输入并消费其输出值而体现为交互计算中活跃的一部分 在交互模型中,其中的计算可以是并行的,一个计算主体可以和它的环境以及其他计算主体并行工作,计算与交互,15,交互的影响 交互为计算现象提供一种新的概念模型, 它强调交互而不是算法。并行、分布、反应式
10、(reactive)、嵌入式、面向部件、面向主体和面向服务的系统都是奠定此概念模型的重要范例 所有新型计算的本质特点是交互,交互是现代计算的问题和复杂性的根源 交互与计算的统一理论是计算机科学的基础,以支撑计算机科学的整套理论体系 如何为经典计算和现代计算建立统一的理论框架?这是近几十年来计算机科学面临的重大挑战,计算与交互,16,计算与交互,交互的机器模型 图灵机TM或冯诺依曼计算机体系结构不适合作 为交互的机器模型 1. 顺序交互机SIM(sequential interactive machine) SIM: M = (S, I, f ) S: 可枚举的状态集,I: 可枚举的输入串集 f
11、 : SI SO的TM可计算函数,即(s, i) (s, o) 从sk-1到sk的状态转移:原子的I/O序对(ik, ok) 输入的不确定性: 动态输入ik不可预测(依赖于ok-1) 输出的确定性: ok由ik确定(很容易扩展到ok不确定) SIM的行为由I/O流(i1, o1), (i2, o2), (i3, o3), 刻画,17,计算与交互,交互的机器模型 2. 持久图灵机PTM:,表达能力等价于SIM 3. 多带交互机MIM:,表达能力大于SIM 但都不足以作为先前提到的多种交互计算重要范 例的统一机器模型 能描述交互的演算 演算是对前述挑战的最成功回应 演算的两个重要特色:行为(或观察
12、)等价的概念,以及对交互行为模式分类的新的类型理论 演算已经被应用到编程语言设计、分布式系统的分析和验证等领域,产生了广泛的影响,18,顺序交互的数学模型 在计算表达力上从算法到顺序交互的延伸在数学 上表现为一系列的延伸 在集合表达力上:从良基集到非良基集的延伸 非良基集作为无限流的顺序行为的形式模型 在数学对象定义的表达力上:从归纳到余归纳的 延伸 例如,表达了从字符串到无限字符流的转变,这是算法到交互转变的基础 在代数表达力上:从代数到余代数的延伸 余代数为无限流的演算提供工具,从归纳到余归纳,19,非良基集 良基关系 集合A上的一个关系是良基的,若不存在A上元 素的无穷递减序列a0 a1
13、 a2 (a b iff b a) 良基集 直观解释:不存在无穷递减序列的集合 非良基关系 集合A上的一个关系是非良基的,若存在A上元 素的无穷递减序列 非良基集 直观解释:不遵守上述对良基集的限制的集合,从归纳到余归纳,20,从归纳到余归纳,解释两个记号:笛卡尔积 对两个集合X和Y,其笛卡儿积是如下的序对集合 X Y x, y | xX , yY 射影函数Proj1: X Y X和Proj2: X Y Y满足 等式 (1) Proj1( x, y) = x (2) Proj2( x, y) = y,21,从归纳到余归纳,解释两个记号:可区分并(又称和、余积) 对两个集合X和Y,其可区分并是如
14、下的序对集合 X +Y 0, x | xX 1, y | yY 内射函数(又称余射影函数)InLeft : X X +Y和 InRight : Y X +Y 满足等式 InLeft(x) = 0, x InRight(y) = 1, y,22,集合方程的最小解与最大解 下面集合方程的最小解是A上的字符串集 t unit + (A t) t, A和unit分别是集合变量, 字符集和某个特殊 元素的集合;unit的元素代表空集 “”表示两边同构而不是相等 下面集合方程的最大解是A上的无限字符流集 t (A t) (与上面方程比较, 没有unit ) 体现出延伸出来的概念与原来概念的对偶性 对偶性在
15、代数和余代数上体现得最清楚,从归纳到余归纳,23,从归纳到余归纳,归纳与余归纳的比较 1. 归纳 是构造主义的方法,用它定义数据时,可分解成 三个基本步骤:基本情况、迭代规则和最小化条件 例如,数据集A上的有限表集可归纳地定义如下 (1) 基础情况:nil(空表)是有限表 (2) 迭代规则:若aA且是有限表,则cons(a, )是有限表 (3) 最小化条件:此外, 有限表集中不含其它元素 最小化规则指所定义的集合是满足(1)和(2)两条 约束的最小集合,无任何垃圾在其中,24,从归纳到余归纳,归纳与余归纳的比较 1. 归纳 可计算函数 f :X Y 在两个层次上是归纳的 (1) 归纳定义的静态
16、值域: X是归纳定义的 例:字符串集的定义: t unit + (A t)的最小解 (2) 归纳定义的动态计算: f 的计算过程是归纳 定义的 图灵机也是类似地通过归纳定义的状态转换步骤, 对归纳定义的串进行变换,图灵机的局限也是源于 其基于归纳,25,从归纳到余归纳,归纳与余归纳的比较 2. 余归纳 用余归纳定义数据时,可分解成两个基本步骤:迭代规则和最大化条件。与归纳相比,它删去基 础情况,修改迭代规则,用最大化取代最小化 例如, 数据集A上的无限表集可余归纳地定义如下 (1) 迭代规则:若aA且是无限表,则cons(a, )是无限表 (2) 最大化条件:数据集A上的无限表集是满足迭代规则
17、的最大集合,26,从归纳到余归纳,归纳与余归纳的比较 2. 余归纳 最大化条件表示所有未被迭代规则(1)排除的元素 都被包含在所定义的集合中,即该集合中任何无限 表都可以通过应用规则(1)若干次而得到 交互计算在两个层次上是余归纳的 (1) 余归纳定义的静态值域 例,无限字符流集的定义:t (A t)的最大解 (2) 余归纳定义的动态下一步动作(后面有例子),27,从归纳到余归纳,归纳与余归纳的比较 3. 例: 有限表的构造算子(constructor)有nil和cons 无限表的构造算子仅有cons 两种表都有观察算子head和运算算子tail,合称为 解构算子(destructor) 并且
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 新型 计算 模型 顺序 交互 数学 计算机科学 导论 第九 ppt 课件
链接地址:https://www.31doc.com/p-3389170.html