新型计算模型和顺序交互的数学计算机科学导论第九讲

《新型计算模型和顺序交互的数学计算机科学导论第九讲》由会员分享，可在线阅读，更多相关《新型计算模型和顺序交互的数学计算机科学导论第九讲（53页珍藏版）》请在金锄头文库上搜索。

1、新型计算模型和顺序交互的数学新型计算模型和顺序交互的数学计算机科学导论第九讲计算机科学导论第九讲计算机科学技术学院计算机科学技术学院陈意云陈意云0551-63607043, http:/ 程程 内内 容容课程内容课程内容围绕学科理论体系中的模型理论围绕学科理论体系中的模型理论, 程序理论和计算理论程序理论和计算理论1. 模型理论关心的问题模型理论关心的问题 给定模型给定模型M，哪些问题可以由模型，哪些问题可以由模型M解决解决；如何；如何比较模型的表达能力比较模型的表达能力2. 程序理论关心的问题程序理论关心的问题给定模型给定模型M，如何用模型，如何用模型M解决问题解决问题包括程序设计范型、程序

2、设计语言、程序设计、包括程序设计范型、程序设计语言、程序设计、形式语义、类型论、程序验证、程序分析等形式语义、类型论、程序验证、程序分析等3. 计算理论关心的问题计算理论关心的问题给定模型给定模型M和一类问题和一类问题, 解决该类问题需多少资源解决该类问题需多少资源2本讲座概要介绍交互计算的本讲座概要介绍交互计算的特点及相关的一些数学知识特点及相关的一些数学知识阶山示辩款滓鳖浙染弊膜本办琴属剔轧沥尼骚既娩妹贬阎翟蹬澜趴获淌诚新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲讲讲 座座 提提 纲纲基本知识基本知识人人 机机 物三元世界、云计算、未来网

3、、物联网、物三元世界、云计算、未来网、物联网、泛在网、图灵机计算模型、网域计算模型泛在网、图灵机计算模型、网域计算模型交互计算交互计算经典计算与交互计算、交互的特点、交互的机器经典计算与交互计算、交互的特点、交互的机器模型、能描述交互的演算模型、能描述交互的演算从归纳到余归纳从归纳到余归纳良基集、非良基集、余归纳、互模拟良基集、非良基集、余归纳、互模拟从代数到余代数从代数到余代数笛卡尔积笛卡尔积, 可区分并可区分并, 余代数余代数, 代数和余代数的区别代数和余代数的区别3纯胜眶给他哗凭休析惟伟难黔帽篱津浸劝獭贱境冶纯味妮稠恕旺挟路浚坯新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型

4、和顺序交互的数学计算机科学导论第九讲人人 机机 物三元世界物三元世界由由计计算算机机网网络络世世界界(也也称称计计算算世世界界, cyber world)、物物理理世世界界和和人人类类社社会会组组成成的的人人机机物物协协同同社社会会，是是多多人人、多多机机和和多多物物组组成成的的动动态态开开放放并并协协同同工工作作的的网络社会网络社会计计算算机机科科学学是是研研究究人人机机物物三三元元世世界界中中计计算算现现象象这这个共同主线的科学个共同主线的科学站站在在三三元元世世界界的的高高度度，有有助助于于理理解解云云计计算算、未未来来网网、物物联联网网、泛泛在在网网(ubiquitous networ

5、k)的的新新技技术趋势术趋势基基 本本 知知 识识4惹握踢砧软驼伎拦亢疏视房惯街纽评戍柒瞥硼死阁徊上筒椰捐供股激寄冈新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲云计算云计算把把资资源源集集中中于于互互联联网网上上的的数数据据中中心心，由由这这种种云云中中心提供应用层、平台层和基础设施层的心提供应用层、平台层和基础设施层的集中服务集中服务强强调调信信息息资资源源的的聚聚集集、优优化化、动动态态分分配配和和回回收收，通通过过提提高高数数据据中中心心的的效效率率，解解决决传传统统IT系系统统的的零零散性带来的低效率，降低信息化成本、降低能耗散性带来

6、的低效率，降低信息化成本、降低能耗向向公公众众提提供供一一种种新新的的高高效效计计算算模模式式，兼兼有有互互联联网网服务的便利与廉价和大型计算机的能力服务的便利与廉价和大型计算机的能力云云计计算算可可为为物物联联网网和和泛泛在在网网提提供供后后端端处处理理能能力力与与应用平台应用平台基基 本本 知知 识识5古用武滩惋怖浇拨梆崖肥昨颂卢游木缔婶己獭绵恳琐硒扛巴硼眷利式贺还新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲未来网（未来互联网，未来网（未来互联网，post-IP network）基基于于TCP/IP协协议议的的互互联联网网随随着着其其广广

7、泛泛应应用用，在在可可扩扩展展性性、移移动动性性、安安全全性性、服服务务质质量量和和可可靠靠性性等等方面都暴露出本质缺陷方面都暴露出本质缺陷近十多年来渐进式的改进未能从根本上解决问题近十多年来渐进式的改进未能从根本上解决问题美美国国和和欧欧盟盟等等已已开开展展“从从零零开开始始”的的革革命命方方式式研研究究未来互联网未来互联网未未来来网网可可为为云云计计算算、物物联联网网和和泛泛在在网网提提供供更更加加高高效安全的效安全的网络基础技术网络基础技术基基 本本 知知 识识6肩羔税顽殿友菜戈桃蛙楼魏豁昧热汪楷根抬旱暮姐诛旺汪清艳瞎左狂饲点新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和

8、顺序交互的数学计算机科学导论第九讲物联网物联网实现物物互联的网络实现物物互联的网络与与互互联联网网的的区区别别：物物物物互互联联，物物机机互互联联，而而不不是是局限于机机互联局限于机机互联实实现现对对物物理理世世界界（包包括括自自然然界界和和人人造造物物）的的精精准准感感知知，感感知知信信息息的的实实时时或或及及时时传传输输，针针对对物物理理世世界界限限制制的的处处理理与与决决策策，以以及及对对物物理理世世界界的的控控制制，提供高效智能的应用服务提供高效智能的应用服务更更高高层层次次：通通过过独独立立个个体体之之间间的的局局部部的的即即时时交交互互和和分分布布式式智智能能，使使物物体体具具有有

9、自自组组织织、自自计计算算和和自自反馈功能，实现反馈功能，实现物物之间的智能交互物物之间的智能交互基基 本本 知知 识识7除爹够草貉挡甩妓灿倾癣卞贱株似农弟升天烫喧吕内器萨袭惺应掌燃郊烛新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲基基 本本 知知 识识泛在网泛在网是是指指基基于于个个人人和和社社会会的的需需求求，实实现现人人与与人人、人人与与物物、物物与与物物之之间间按按需需进进行行的的信信息息获获取取、传传递递、存存储、认知、决策和使用等服务储、认知、决策和使用等服务具有超强的环境感知、内容感知及智能性具有超强的环境感知、内容感知及智能性环

10、境感知环境感知(environment perception)：指系统具有周围环境：指系统具有周围环境 参数的采集、语义表达、语义查询解析和语义推理的能力参数的采集、语义表达、语义查询解析和语义推理的能力内容感知内容感知(content aware)的网络服务：意在更细致地感知的网络服务：意在更细致地感知 终端（终端（PC、手机、平板电脑等）、手机、平板电脑等） 网络（网络（3G，Wifi等移动网络）等移动网络） 业务类型（游戏、视频、电子商务、微博等）业务类型（游戏、视频、电子商务、微博等） 的不同需求的不同需求, 提供更有针对性的解决方案和更有价值的服务提供更有针对性的解决方案和更有价值的

11、服务8驻拨量秃协芋沏镐郡剁扰会沃本啡狄渍就判媒费监啤姆扶约档鹤蚊捡簧城新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲基基 本本 知知 识识泛在网泛在网是是指指基基于于个个人人和和社社会会的的需需求求，实实现现人人与与人人、人人与与物物、物物与与物物之之间间按按需需进进行行的的信信息息获获取取、传传递递、存存储、认知、决策和使用等服务储、认知、决策和使用等服务具有超强的环境感知、内容感知及智能性具有超强的环境感知、内容感知及智能性通通过过多多种种联联网网的的智智能能人人机机交交互互设设备备，为为个个人人和和社社会提供无所不在的信息服务和应用会提供

12、无所不在的信息服务和应用9桌狱惧扼岂篇操电察春酿块介瘫粉拌厉顺从铀停突石寞拐衔柬盈脂韶褒锁新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲基基 本本 知知 识识区分性概括区分性概括未未来来网网：强强调调对对当当今今互互联联网网的的变变革革，是是未未来来信信息息化的网络基础化的网络基础云云计计算算：一一种种新新的的应应用用模模式式，强强调调应应用用层层信信息息的的综合处理，可作为物联网后端处理和应用平台综合处理，可作为物联网后端处理和应用平台物物联联网网：强强调调对对物物感感知知和和物物物物互互联联, 方方便便人人类类对对物物理世界的感知和控制，是

13、走向泛在网的重要一步理世界的感知和控制，是走向泛在网的重要一步泛泛在在网网：对对未未来来信信息息社社会会的的综综合合预预见见，是是上上述述这这些概念的集成些概念的集成10鸯睡曾捎者盼椽幢褐蛰岩临坝哈踊羚巾榴侣菇怨戚磺瘪疤绞堡尘鲸蹬溯奢新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲基基 本本 知知 识识图灵机计算模型图灵机计算模型把把物物理理世世界界数数字字化化，建建立立数数学学模模型型，通通过过计计算算和和数数据据处处理理方方法法，对对自自然然界界存存在在的的规规律律进进行行模模拟拟仿仿真真；计计算算类类应应用用和和数数据据处处理理应应用用都都

14、是是遵遵循循这这样样的的计算模型计算模型按按照照“输输入入 计计算算 输输出出”的的过过程程，产产生生的的所所有有结结果果都是可以预知的都是可以预知的它它是是一一个个计计算算世世界界（computation world），是是对对人人类类认认知知的的一一种种数数字字化化。这这个个数数字字世世界界与与人人类类社社会、物理世界是正交的会、物理世界是正交的11龟到屎条捷妥朱稼媚兹政叹汰闷桂群洒佬绘锋问辞佳皆我涌食硕愁且尉饰新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲基基 本本 知知 识识网域计算模型网域计算模型把信息化扩大到人类社会的一种计算模型把

15、信息化扩大到人类社会的一种计算模型通通过过移移动动数数据据的的方方式式，把把人人类类社社会会中中真真实实的的工工作作与与生生活活搬搬到到计计算算机机网网络络空空间间（cyberspace, 简简称称网网域），即网域可以看成是对人类社会的一个映射域），即网域可以看成是对人类社会的一个映射Cyberspace is the national environment in which communication over computer networks occurs.其其基基础础是是通通过过互互联联网网、上上网网本本(netbook)、智智能能手手机和网络设备等手段实现的人与人之间的通信机和网络

16、设备等手段实现的人与人之间的通信例例如如，社社会会计计算算和和舆舆情情分分析析等等都都是是通通过过对对网网域域空空间的计算来发现人类社会的规律间的计算来发现人类社会的规律12碧芝宽借饭诵蛹按嚣摄只热共了多质污攫萍儿翻灯牟疥心皖墅盆延汛矿切新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲基基 本本 知知 识识网域计算模型网域计算模型网域空间的计算与图灵机计算有本质不同网域空间的计算与图灵机计算有本质不同不存在不存在“停机停机”问题问题算算法法不不是是独独立立的的, 而而是是交交互互算算法法的的网网络络(a network of interactin

17、g algorithms)存存在在涌涌现现现现象象(emergent phenomena)，即即在在混混沌沌的网上世界中能产生新的知识与智能的网上世界中能产生新的知识与智能13桓凸园尚镶捻刀预演申债戊弛埃蛮沤泡彻俩逸投秉落融汝剧鬼漂鸣督钝别新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲计算与交互计算与交互经典计算（简称计算）经典计算（简称计算）计计算算主主体体和和它它的的环环境境之之间间是是一一种种简简单单的的接接口口，即即按照按照“输入输入 计算计算 输出输出”的过程完成所规定任务的过程完成所规定任务计算体现出从输入到输出的函数性计算体现出从

18、输入到输出的函数性交互计算（简称交互）交互计算（简称交互）交交互互计计算算是是在在完完成成任任务务的的过过程程中中包包括括了了与与外外部部世世界通信的计算界通信的计算计计算算主主体体具具有有与与不不受受它它控控制制的的外外部部环环境境交交互互输输入入和输出的动作和输出的动作14洞晃崔晴牺蹭挫久酌泪齐插躇闲哉锚凡蟹镰命粉锥物编请奸嘎郝翟勘药训新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲交互的特点交互的特点基于交互的模型和基于图灵机的算法模型的区别基于交互的模型和基于图灵机的算法模型的区别交交互互任任务务并并非非都都能能简简化化为为函函数数，例例

19、如如永永远远运运行行的的操作系统不能由算法模拟的操作系统不能由算法模拟的在在交交互互模模型型中中，计计算算环环境境是是模模型型的的一一部部分分，并并且且通通过过动动态态地地向向计计算算系系统统或或计计算算主主体体提提供供输输入入并并消消费其输出值而体现为交互计算中活跃的一部分费其输出值而体现为交互计算中活跃的一部分在在交交互互模模型型中中，其其中中的的计计算算可可以以是是并并行行的的，一一个个计计算算主主体体可可以以和和它它的的环环境境以以及及其其他他计计算算主主体体并并行行工作工作计算与交互计算与交互15您坯转振由铭蓄止营袁瑰语运臭途椽翔挽辑送姨谊铱啪钱昏躲株测仔挨醋新型计算模型和顺序交互的

20、数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲交互的影响交互的影响交交互互为为计计算算现现象象提提供供一一种种新新的的概概念念模模型型, 它它强强调调交交互互而而不不是是算算法法。并并行行、分分布布、反反应应式式(reactive)、嵌嵌入入式式、面面向向部部件件、面面向向主主体体和和面面向向服服务务的的系系统统都是奠定此概念模型的重要范例都是奠定此概念模型的重要范例所所有有新新型型计计算算的的本本质质特特点点是是交交互互，交交互互是是现现代代计计算的问题和复杂性的根源算的问题和复杂性的根源交交互互与与计计算算的的统统一一理理论论是是计计算算机机科科学学的的基基础础，

21、以以支撑计算机科学的整套理论体系支撑计算机科学的整套理论体系如如何何为为经经典典计计算算和和现现代代计计算算建建立立统统一一的的理理论论框框架架?这是近几十年来计算机科学面临的重大挑战这是近几十年来计算机科学面临的重大挑战计算与交互计算与交互16脚鼎嘲骤浪宏要重躁钾崩诈消唾弹嘛交峦段谷芬俱虏拯推确鸵掐娄含谅筛新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲计算与交互计算与交互交互的机器模型交互的机器模型图灵机图灵机TM或冯或冯诺依曼计算机体系结构不适合作诺依曼计算机体系结构不适合作为交互的机器模型为交互的机器模型1. 顺序交互顺序交互机机SIM(

22、sequential interactive machine)SIM: M = (S, I, f ) S: 可枚举的状态集，可枚举的状态集，I: 可枚举的输入串集可枚举的输入串集 f : S I S O的的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

23、), (i3, o3), 刻画刻画17着林上郎启佬椎少辫义诺错吞矮釜纂营踏吐椒撞损触岸擂尺悯涕价巡镁杆新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲计算与交互计算与交互交互的机器模型交互的机器模型2. 持久图灵机持久图灵机PTM：，表达能力等价于，表达能力等价于SIM3. 多带交互机多带交互机MIM：，表达能力大于，表达能力大于SIM但都不足以作为先前提到的多种交互计算重要范但都不足以作为先前提到的多种交互计算重要范例的统一机器模型例的统一机器模型能描述交互的演算能描述交互的演算 演算是对前述挑战的最成功回应演算是对前述挑战的最成功回应 演演算

24、算的的两两个个重重要要特特色色：行行为为（或或观观察察）等等价价的的概概念，以及对交互行为模式分类的新的类型理论念，以及对交互行为模式分类的新的类型理论 演演算算已已经经被被应应用用到到编编程程语语言言设设计计、分分布布式式系系统统的的分析和验证等领域，产生了广泛的影响分析和验证等领域，产生了广泛的影响18幼若馁亦淋瘟藕锑码酥翱浸窥同漠芜椎沼连添先桂得工园歪溶林冠恼益导新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲顺序交互的数学模型顺序交互的数学模型在计算表达力上从算法到顺序交互的延伸在数学在计算表达力上从算法到顺序交互的延伸在数学上表现为一系

25、列的延伸上表现为一系列的延伸在集合表达力上：在集合表达力上：从良基集到非良基集的延伸从良基集到非良基集的延伸 非良基集作为无限流的顺序行为的形式模型非良基集作为无限流的顺序行为的形式模型在数学对象定义的表达力上：在数学对象定义的表达力上：从归纳到余归纳的从归纳到余归纳的延伸延伸 例例如如，表表达达了了从从字字符符串串到到无无限限字字符符流流的的转转变变，这是算法到交互转变的基础这是算法到交互转变的基础在代数表达力上：在代数表达力上：从代数到余代数的延伸从代数到余代数的延伸 余代数为无限流的演算提供工具余代数为无限流的演算提供工具从归纳到余归纳从归纳到余归纳19舀窘及箍掺呜诚尧提访困猜夏碱劝榨胡

26、爪镑惕涨儒荫缅挝巡抨屿剥涅亚条新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲非良基集非良基集良基关系良基关系集合集合A A上的一个关系上的一个关系 是是良基的良基的，若不存在，若不存在A A上元上元素的无穷递减序列素的无穷递减序列a0 a1 a2 （a b iff b a）良基集良基集直观解释：直观解释：不存在无穷递减序列的集合不存在无穷递减序列的集合非良基关系非良基关系集合集合A A上的一个关系是非上的一个关系是非良基的良基的，若存在，若存在A A上元上元素的无穷递减序列素的无穷递减序列非良基集非良基集直观解释：不遵守上述对良基集的限制的集合

27、直观解释：不遵守上述对良基集的限制的集合从归纳到余归纳从归纳到余归纳20咒籍碾半稚痢吕镍宰箔界南脖雹狸匝虽苇爬更盲斧津结秘惫阶瞥割擦锡坎新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲从归纳到余归纳从归纳到余归纳解释两个记号：笛卡尔积解释两个记号：笛卡尔积对两个集合对两个集合X和和Y，其笛卡儿积是如下的序对集合，其笛卡儿积是如下的序对集合X Y x, y | x X , y Y 射影函数射影函数Proj1: X Y X和和Proj2: X Y Y满足满足等式等式(1) Proj1( x, y ) = x(2) Proj2( x, y ) = y2

28、1镊兼泼恐咯始牌党蚜彭无番底藻候感剩侨期惮竿臃曰薯黍钠轮硫筒驱赁谎新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲从归纳到余归纳从归纳到余归纳解释两个记号：可区分并（又称和、余积）解释两个记号：可区分并（又称和、余积）对两个集合对两个集合X和和Y，其可区分并是如下的序对集合，其可区分并是如下的序对集合X +Y 0, x | x X 1, y | y Y 内射函数内射函数(又称余射影函数又称余射影函数)InLeft : X X +Y和和InRight : Y X +Y 满足等式满足等式 InLeft(x) = 0, x InRight(y) = 1

29、, y 22爷裳绣傻钙然硒夫元财筋报卿嗣爱嗽赌鹃僧谤菇伐织挫揍怖酋鼎凑冤焙法新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲集合方程的最小解与最大解集合方程的最小解与最大解下面集合方程的最小解是下面集合方程的最小解是A上的字符串集上的字符串集t unit + (A t) t, A和和unit分别是集合变量分别是集合变量, 字符集和某个特殊字符集和某个特殊元素的集合；元素的集合；unit的元素代表空集的元素代表空集 “ ”表示两边同构而不是相等表示两边同构而不是相等下面集合方程的最大解是下面集合方程的最大解是A上的无限字符流集上的无限字符流集t (

30、A t)(与上面方程比较与上面方程比较, 没有没有unit )体现出延伸出来的概念与原来概念的对偶性体现出延伸出来的概念与原来概念的对偶性对偶性在代数和余代数上体现得最清楚对偶性在代数和余代数上体现得最清楚从归纳到余归纳从归纳到余归纳23抬磁粕戈倡顶伞词润考擦蘸妇狮各扎穿锦变怪募刮同廓廖炉吁澳达犯萎瓢新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲从归纳到余归纳从归纳到余归纳归纳与余归纳的比较归纳与余归纳的比较1. 归纳归纳是构造主义的方法，用它定义数据时，可是构造主义的方法，用它定义数据时，可分解成分解成三个基本步骤：基本情况、迭代规则和最小化

31、条件三个基本步骤：基本情况、迭代规则和最小化条件 例如，数据集例如，数据集A上的有限表集可归纳地定义如下上的有限表集可归纳地定义如下 (1) 基础情况：基础情况：nil(空表空表)是有限表是有限表(2) 迭代规则：若迭代规则：若a A且且 是有限表，则是有限表，则cons(a, )是有限表是有限表(3) 最小化条件：此外最小化条件：此外, 有限表集中不含其它元素有限表集中不含其它元素 最小化规则指所定义的集合是满足最小化规则指所定义的集合是满足(1)和和(2)两条两条约束的最小集合，无任何垃圾在其中约束的最小集合，无任何垃圾在其中24傅赵实眶伸详程农灾涉羚渤躇洗琵忻通谎恶炼匙末炊晦哗匠捻烫剁洛

32、敛睫新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲从归纳到余归纳从归纳到余归纳归纳与余归纳的比较归纳与余归纳的比较1. 归纳归纳可计算函数可计算函数 f :X Y 在两个层次上是归纳的在两个层次上是归纳的 (1) 归纳定义的静态值域：归纳定义的静态值域： X是归纳定义的是归纳定义的 例：字符串集的定义例：字符串集的定义: t unit + (A t)的最小解的最小解 (2) 归纳定义的动态计算：归纳定义的动态计算： f 的计算过程是归纳的计算过程是归纳定义的定义的图灵机也是类似地通过归纳定义的状态转换步骤图灵机也是类似地通过归纳定义的状态转换步

33、骤,对归纳定义的串进行变换，图灵机的局限也是源于对归纳定义的串进行变换，图灵机的局限也是源于其基于归纳其基于归纳25浊并罚豫登黍裹绸尸蕴哨吟绢旧库硝柜翅逗霉督勃恶覆授部霍芭骗事饰适新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲从归纳到余归纳从归纳到余归纳归纳与余归纳的比较归纳与余归纳的比较2. 余归纳余归纳用用余余归归纳纳定定义义数数据据时时，可可分分解解成成两两个个基基本本步步骤骤：迭代规则和最大化条件。与归纳相比，它删去基迭代规则和最大化条件。与归纳相比，它删去基础情况，修改迭代规则，用最大化取代最小化础情况，修改迭代规则，用最大化取代最小

34、化 例如例如, 数据集数据集A上的无限表集可余归纳地定义如下上的无限表集可余归纳地定义如下 (1) 迭代规则：若迭代规则：若a A且且 是无限表，则是无限表，则cons(a, )是无限表是无限表(2) 最大化条件：数据集最大化条件：数据集A上的无限表集是满足迭上的无限表集是满足迭代规则的最大集合代规则的最大集合26如扰忧伺奢焕歧蜗缺侮商嚷雁搐痊轻售们癸几葬塑青秧堪蜗舔邪岛票嫁涎新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲从归纳到余归纳从归纳到余归纳归纳与余归纳的比较归纳与余归纳的比较2. 余归纳余归纳最大化条件表示所有未被迭代规则最大化条件表

35、示所有未被迭代规则(1)排除的元素排除的元素都被包含在所定义的集合中，即该集合中任何无限都被包含在所定义的集合中，即该集合中任何无限表都可以通过应用规则表都可以通过应用规则(1)若干次而得到若干次而得到交互计算在两个层次上是余归纳的交互计算在两个层次上是余归纳的 (1) 余归纳定义的静态值域余归纳定义的静态值域 例，无限字符流集的定义：例，无限字符流集的定义：t (A t)的最大解的最大解 (2) 余归纳定义的动态下一步动作余归纳定义的动态下一步动作(后面有例子后面有例子)27糙锁涣洪乙淫晓委蛹适惊株芯畸画蘸影驱尊扭育刹膀慨钠虎卓碟肾贷步面新型计算模型和顺序交互的数学计算机科学导论第九讲新型计

36、算模型和顺序交互的数学计算机科学导论第九讲从归纳到余归纳从归纳到余归纳归纳与余归纳的比较归纳与余归纳的比较3. 例：例：有限表的有限表的构造算子构造算子(constructor)有有nil和和cons无限表的构造算子仅有无限表的构造算子仅有cons两种表都有观察算子两种表都有观察算子head和运算算子和运算算子tail，合称为，合称为解构算子解构算子(destructor)并且都有性质并且都有性质 head(cons(a, ) = a tail(cons(a, ) = 两者分别对应两者分别对应 集合方程集合方程t unit + (A t)的最小解的最小解 集合方程集合方程t (A t)的最大解

37、的最大解28秦臂狸洱哇排码矽债卖样徽败鲸巫重聂热需湾咕好翔灭挡摈沿暂枷汝哩赴新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲从归纳到余归纳从归纳到余归纳归纳和余归纳定义的函数的比较归纳和余归纳定义的函数的比较1. 归纳定义的函数归纳定义的函数在计算有限表表长的函数在计算有限表表长的函数length的归纳定义中，的归纳定义中，需要定义需要定义length作用于所有构造算子的值：作用于所有构造算子的值： length(nil) = 0 length(cons(a, ) = 1 + length( )怎样给出一个函数在余归纳定义集合上的余归纳怎样给出一

38、个函数在余归纳定义集合上的余归纳定义？定义？29竖幼仿幢梨恃树胃敌肇匹析做纯耳化穿恬遇赎拆莫张峙吐慎帝荣俘嵌闺疤新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲从归纳到余归纳从归纳到余归纳归纳和余归纳定义的函数的比较归纳和余归纳定义的函数的比较2. 余归纳定义的函数余归纳定义的函数考虑字符集考虑字符集A上的无限表，现在有函数上的无限表，现在有函数f : A A定义定义f 的拓展函数的拓展函数ext(f )，它把，它把f 应用到无限表应用到无限表 的的每个每个元素，得到新的无限表元素，得到新的无限表ext(f )( )余归纳定义即定义解构算子在每个

39、余归纳定义即定义解构算子在每个ext(f )( )上的值上的值 head(ext(f )( ) = f (head( ) tail(ext(f )( ) = ext(f )(tail( )在这些等式的左边，在这些等式的左边，f 出现在解构算子的出现在解构算子的“里面里面”在归纳定义中，在归纳定义中，length出现在构造算子的出现在构造算子的“外面外面”：length(nil) = 0, length(cons(a, ) = 1 + length( )30列雷铬痉寻陪呸仲租请寄跋毛术际殴靴嗜酌凤酌滁出苍褒剐付掸闽唱雇郧新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学

40、计算机科学导论第九讲从归纳到余归纳从归纳到余归纳互模拟互模拟例：无限表上的例：无限表上的odd运算运算 odd：忽略所有偶数位置的元素后构成的无限表：忽略所有偶数位置的元素后构成的无限表 head(odd( ) = head( ) tail(odd( ) = odd(tail(tail( ) 用等式演算可得用等式演算可得 head(tail(odd( ) = head(odd(tail(tail( ) = head(tail(tail( ) 不难证明，对所有的自然数不难证明，对所有的自然数n head(tail(n) (odd( ) = head(tail(2n) ( )31群酉籽荣歧续互乐鲍

41、永弗操再乍花切逻绢敝铺拒账来问囊箔秦钢负悄仍嘉新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲从归纳到余归纳从归纳到余归纳互模拟互模拟例：无限表上的例：无限表上的odd运算运算 odd：忽略所有偶数位置的元素后构成的无限表：忽略所有偶数位置的元素后构成的无限表 head(odd( ) = head( ) tail(odd( ) = odd(tail(tail( ) 顺便说一句：顺便说一句： 从计算的角度，欲求从计算的角度，欲求head(odd( ) 的结果，不能的结果，不能等等odd( )的结果算出后，再交给的结果算出后，再交给head函数函数

42、(不终止不终止) 须用惰性计算的方法：须用惰性计算的方法：在在head函数需要下一个数函数需要下一个数据时，据时，odd才计算下一个数据并提供给才计算下一个数据并提供给head32督密素盼粕自弛枫盐畦八泽玛辱装秧纪猾铜西子前熔仑丑怒籽裸抠饿株妹新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲从归纳到余归纳从归纳到余归纳互模拟互模拟怎样证明余归纳定义的数据和函数的性质怎样证明余归纳定义的数据和函数的性质1、某些性质可以用归纳法来证明，例如证明、某些性质可以用归纳法来证明，例如证明head(tail(n) (odd( ) = head(tail(2n

43、) ( )2、互模拟、互模拟余归纳证明专用方法余归纳证明专用方法从数学上刻画系统（如对象、进程等）行为等价从数学上刻画系统（如对象、进程等）行为等价这个直观概念这个直观概念指两个系统从观测者角度看，可以互相模拟对方指两个系统从观测者角度看，可以互相模拟对方的行为的行为33前很涧走洼纤溢猴迹湿摄验爸态诛沾泊鞘攫孩责坷微演娇蛆雌腕较辱抉王新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲从归纳到余归纳从归纳到余归纳互模拟互模拟 通过无限表上的例子来解释通过无限表上的例子来解释 先前已定义先前已定义oddhead(odd( ) = head( )tail

44、(odd( ) = odd(tail(tail( ) 定义定义eveneven = odd tail 定义定义mergehead(merge( , ) = head( )tail(merge( , ) = merge( , (tail( )34讨具奉猛屋鸽枷座通宪埂赤骡打赶圣葱纱杀卵噎锻幅起蜜焙勃殊骡吠腾够新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲从归纳到余归纳从归纳到余归纳互模拟互模拟基于互模拟证明基于互模拟证明merge(odd( ), even( ) = 互模拟是满足下面条件的关系互模拟是满足下面条件的关系R： 若若 , R，则，则

45、head( ) = head( ) 并且并且 tail( ), tail( ) R基于互模拟的余归纳证明原理是：基于互模拟的余归纳证明原理是： 对互模拟关系对互模拟关系R，若，若 , R，则，则 = 按上述原理，先定义关系按上述原理，先定义关系 R = merge(odd( ), even( ), | 是无限表是无限表 只要证明只要证明R是互模拟关系即可是互模拟关系即可 35桩遂译菊群汐眼靡倒举屡座养往坐懈郁氓鸿走和孰皆荫皋剿罐胸垛主踩栖新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲从归纳到余归纳从归纳到余归纳互模拟互模拟第一个条件的证明第一个

46、条件的证明 head(merge(odd( ), even( ) = head(odd( ) = head( )第二个条件的证明第二个条件的证明 需证需证 tail(merge(odd( ), even( ), tail( ) 也在也在R中中1. tail(merge(odd( ), even( ) = merge(even( ), tail(odd( )36根据根据tail(merge( , ) = merge( , (tail( )掠郭凳荒哼浸统式搀炭闪岸初釉效娠樱诫槛剃葵分柬饮鞭冶谭撰摹叶棋浅新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲

47、从归纳到余归纳从归纳到余归纳互模拟互模拟第一个条件的证明第一个条件的证明 head(merge(odd( ), even( ) = head(odd( ) = head( )第二个条件的证明第二个条件的证明 需证需证 tail(merge(odd( ), even( ), tail( ) 也在也在R中中1. tail(merge(odd( ), even( ) = merge(even( ), tail(odd( ) = merge(odd(tail( ), odd(tail(tail( )37 根据根据even = odd tail 和和 tail(odd( ) = odd(tail(tai

48、l( )靶斥殷篆儿蔗妒怨宾寞竿缔贝壕蚕皋傀旗贪朝抒拌唤蜘迟份溉籽臼蔬柔尺新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲从归纳到余归纳从归纳到余归纳互模拟互模拟第一个条件的证明第一个条件的证明 head(merge(odd( ), even( ) = head(odd( ) = head( )第二个条件的证明第二个条件的证明 需证需证 tail(merge(odd( ), even( ), tail( ) 也在也在R中中1. tail(merge(odd( ), even( ) = merge(even( ), tail(odd( ) = mer

49、ge(odd(tail( ), odd(tail(tail( ) = merge(odd(tail( ), even(tail( )38根据根据even = odd tail 图槐蝇朋忻醚履炬罕固恢聋阿梁氖劈嚷薄瓣跟本扬仗楚橱郎邻警牙恶撕磕新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲从归纳到余归纳从归纳到余归纳互模拟互模拟第一个条件的证明第一个条件的证明 head(merge(odd( ), even( ) = head(odd( ) = head( )第二个条件的证明第二个条件的证明 需证需证 tail(merge(odd( ), even

50、( ), tail( ) 也在也在R中中1. tail(merge(odd( ), even( ) = merge(even( ), tail(odd( ) = merge(odd(tail( ), odd(tail(tail( ) = merge(odd(tail( ), even(tail( )2. merge(odd(tail( ), even(tail( ), tail( ) 在在R中中, 故故 tail(merge(odd( ), even( ), tail( ) 也在也在R中中39因为因为 merge(odd( ), even( ), 在在R中中, 把把 代换成代换成tail( )

51、可得可得蜒萤铰臀只例挖闭帐纷豹拧最多嚷洪账扒掐慑拂掳放婪假崭踌藉罪赐弗亿新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲从归纳到余归纳从归纳到余归纳互模拟互模拟 利用归纳和等式演算，也可以证明利用归纳和等式演算，也可以证明merge(odd( ), even( ) = 但没有这么简洁但没有这么简洁 需用归纳法先证明下面几个等式：需用归纳法先证明下面几个等式：head(tail(n)(odd( ) = head(tail(2n)( )head(tail(2n)(merge( , ) = head(tail(n)( )head(tail(2n+1)(

52、merge( , ) = head(tail(n)( ) 然后利用等式演算证明然后利用等式演算证明head(tail(n)(merge(odd( ), even( ) = head(tail(n)( )40拜奔熔左咸揩陕匈瞒浚愧水椿泪颖寞柴对将舌取纶蓝耻残盎曙服挣房附臂新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲从代数到余代数从代数到余代数笛卡尔积（先前已给出）笛卡尔积（先前已给出）对两个集合对两个集合X和和Y，其笛卡儿积是如下的序对集合，其笛卡儿积是如下的序对集合X Y x, y | x X , y Y 射影函数射影函数Proj1: X Y

53、 X和和Proj2: X Y Y满足满足等式等式 Proj1( x, y ) = x Proj2( x, y ) = y41斩遍腹郝烩廊屁舔冯扰斗枚拾仁越戮逐食房领馆作凌硫房登宿骡晚长薯笼新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲从代数到余代数从代数到余代数笛卡尔积笛卡尔积对任意函数对任意函数f : Z X和和g : Z Y, 存在唯一的存在唯一的“配配对对”函数函数 f, g : Z X Y 使得使得Proj1 f, g = f 且且Proj2 f, g = g即对即对z Z， f, g (z) = f (z), g(z) X Y注：注：

54、 f, g 看成函数名看成函数名二元积的这些性质在范畴论中二元积的这些性质在范畴论中可以用交换图表可以用交换图表(右图右图)表示表示可推广到可推广到n元积的情况元积的情况YZ f, g X YXProj1gfProj242俯落姥笋卷笛盒婿玩贺鼎山奎旅古等浮屠间罗杉瘪镍练安槛起寻炉缴簿牲新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲从代数到余代数从代数到余代数可区分并（又称和、余积）可区分并（又称和、余积） （先前已给出）（先前已给出）对两个集合对两个集合X和和Y，其可区分并是如下的序对集合，其可区分并是如下的序对集合X +Y 0, x | x

55、X 1, y | y Y 内射函数内射函数(又称余射影函数又称余射影函数)InLeft : X X +Y和和InRight : Y X +Y 满足等式满足等式 InLeft(x) = 0, x InRight(y) = 1, y 43隋几瓮取黑烛伴刑诺兢车衣敦爷浚强失逢瘸糜墙戍欲滇掘择重蕴寅脖人确新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲从代数到余代数从代数到余代数可区分并（又称和、余积）可区分并（又称和、余积）对任意函数对任意函数f : X Z和和g : Y Z, 存在唯一的余配存在唯一的余配对函数对函数f, g: X +Y Z使得使得

56、f, g InLeft = f 且且f, g InRight = g即对即对w X +Y, f, g(w) = 二元和的这些性质在范畴论中二元和的这些性质在范畴论中可以用交换图表可以用交换图表(右图右图)表示表示可推广到可推广到n元和的情况元和的情况注注: f, g看成函数名看成函数名YZf, gX + YXInLeftgfInRight f (x), w = 0, x g(y), w = 1, y 44败跟洽芽皖麻气麓敛弦存晶跺者唇宅糖展纬蠢弊喘淡喻抿腿狮春涵像潮干新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲从代数到余代数从代数到余代数笛卡

57、尔积和可区分并笛卡尔积和可区分并它们交换图表的区别是：箭头正好相反它们交换图表的区别是：箭头正好相反可区分并用于描述代数可区分并用于描述代数, 笛卡尔积用来描述余代数笛卡尔积用来描述余代数从从它它们们交交换换图图表表的的对对偶偶性性来来体体会会代代数数和和余余代代数数的的关系关系这是介绍这部分的目的这是介绍这部分的目的YZf, gX + YXInLeftgfInRightYZ f, g X YXProj1gfProj245永舶壮路程挠榷眨选豆蒲论晦棕婪桂酷红插栈老匠亲嗓疯皑谤颐沂永割扬新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲从代数到余代数

58、从代数到余代数自然数代数自然数代数自然数自然数N N 上的零和后继函数上的零和后继函数0 : unit N N （0是归纳定义的基础情况）是归纳定义的基础情况）S : N N N N （S是构造算子）是构造算子）构成函子构成函子F的的代数代数 N N , 0, S : F(N N ) N N , 其中其中N N 称为载体，称为载体，F(N N ) = unit+N N 。函数。函数0, S称为该代称为该代数的代数结构数的代数结构 函子是范畴之间保结构的函子是范畴之间保结构的的映射，深入了解需要的映射，深入了解需要范畴论的知识范畴论的知识N NN N0, Sunit+N NunitInLeftS

59、0InRight46皋而篆肢臭穴泛扁苞赁副咽阳哲邑藏氏左冷菠霄转抽纷勘礁勘去绣畅缚合新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲从代数到余代数从代数到余代数一个简单的余代数一个简单的余代数两个集合两个集合U (状态集状态集)和和 A(可观察数据集可观察数据集) 和函数和函数value : U A （value是观察算子）是观察算子）next : U U （next是运算算子）是运算算子）构成函子构成函子G的的余代数余代数 U , value, next : U G(U) ,其中其中U称为该余代数的载体，称为该余代数的载体， G(U) = A

60、U。函数。函数 value, next 称为该余代数的称为该余代数的余代数结构余代数结构 由于余代数经常描述由于余代数经常描述动态系统，载体也叫做动态系统，载体也叫做状态空间状态空间UU value, next A UAProj1nextvalueProj247泄泪滑患悠医锋涧搪灌喉肝峪粹甥淹氏伙叫还婴君季咬竣狂持埂铲忻柏束新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲从代数到余代数从代数到余代数例：例：有两个按键有两个按键value和和next的机器的机器 按按value键时不影响机器内部状态，并产生数据集键时不影响机器内部状态，并产生数据集

61、A的某个元素的某个元素(可见属性可见属性)，连续按，连续按value键产生同样键产生同样的结果的结果 按按next键时机器转移到另一个状态，该状态的性键时机器转移到另一个状态，该状态的性质可通过按质可通过按value键来观察键来观察 该机器可以用状态空间该机器可以用状态空间U上的下述余代数来描述上的下述余代数来描述 value, next : U A U 其中其中 value, next 由两个函数由两个函数value : U A和和next : U U组成组成48颇舌列统昌系碌吨播假驱咯夯锨眺航可柳什审怀溪希棚味畸害咀滓怜炭卯新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序

62、交互的数学计算机科学导论第九讲从代数到余代数从代数到余代数例：例：有两个按键有两个按键value和和next的机器的机器 该机器可以用状态空间该机器可以用状态空间U上的下述余代数来描述上的下述余代数来描述 value, next : U A U其中其中 value, next 由由 value: U A和和next: U U组组成成 连续地交替按连续地交替按next键和键和value键，可以产生无限序键，可以产生无限序列列(a1, a2, ) 它可以看成它可以看成N N A上的一个函数，其中上的一个函数，其中ai = value(next(i)(u) A 若若u1, u2 U给出同样的可观察序

63、列，则给出同样的可观察序列，则u1和和u2从观从观察角度不可区分察角度不可区分49臀眩隙泽郎寂坊级往赏燃本拆斋瓮饵溯拷费灿既硼忘裤勾篱耍纳烈柱浑殆新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲从代数到余代数从代数到余代数余代数和代数的区别余代数和代数的区别本质上这是构造和观察之间的区别本质上这是构造和观察之间的区别 代数由载体集合代数由载体集合U和射入和射入U的函数的函数a : F(U) U 组组成，它告知怎样构造成，它告知怎样构造U的元素的元素 余代数由载体集合余代数由载体集合U和逆向的函数和逆向的函数c : U F(U)组组成，此时不知道怎

64、样形成成，此时不知道怎样形成U的元素，仅有作用在的元素，仅有作用在U上上的操作，它给出关于的操作，它给出关于U的某些信息的某些信息50豪苏浴倍营洞筒篇路艺财贿殆疫偏挂假乔活戏恫迂揖斯逐楼照域玻聋得赎新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲小小 结结本讲座小结本讲座小结从从三三元元世世界界的的高高度度概概述述地地介介绍绍云云计计算算、未未来来网网、物联网和泛在网及计算模型物联网和泛在网及计算模型强强调调现现代代计计算算与与经经典典计计算算最最主主要要的的区区别别之之一一是是交交互性互性介绍顺序交互的数学模型介绍顺序交互的数学模型研究方向研究

65、方向如何为经典计算与新型计算建立统一的理论框架如何为经典计算与新型计算建立统一的理论框架各种交互计算的机器模型各种交互计算的机器模型各种交互计算的数学模型各种交互计算的数学模型51衍援券演鳞框拟徐嘿蹄沙擎蹄竟匡踌末头涝呻帮染发玖杠淘生递卑瘤现冠新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲小小 结结参考文献参考文献孙凝晖等，海计算：物联网的新型计算模型，中孙凝晖等，海计算：物联网的新型计算模型，中国计算机学会通讯，国计算机学会通讯，6(7)，2010.7曹爱文等译曹爱文等译, 计算机数学计算机数学, 清华大学出版社清华大学出版社, 2010林惠

66、民等译，移动与通信系统：林惠民等译，移动与通信系统： 演算，清华大学演算，清华大学出版社，出版社，2009Goldin, D; Smolka, S. A; Wegner, P.(Eds.),Interactive Computation: The New Paradigm, 2006Bart Jacobs and Jan Rutten. A Tutorial on Coalgebras and Coinduction. The Hyper bulletin of the European Association for Theoretical ComputerScience, 62: 222-259 （本讲座的理论部分源于此）（本讲座的理论部分源于此）52淖饺终裤主遂腔柒劲辫凑吨诈父存兹恰腺束哭埂清豪茬擎齐盼命狸抿经堑新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲小小 结结相关课程相关课程网络计算与高效算法（研）、高级计算机体系结网络计算与高效算法（研）、高级计算机体系结构（研）、程序设计语言理论（研）构（研）、程序设计语言理论（研）53苑肛名叭饶默稚稼笔誓反冤捻遏卵华烂校刺很汰栋致剥抿痒玫便江侧檄肢新型计算模型和顺序交互的数学计算机科学导论第九讲新型计算模型和顺序交互的数学计算机科学导论第九讲