文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 信息与通信 > 计算的模型:图灵机与Petri网
侵权投诉

计算的模型:图灵机与Petri网

形式化的软件开发方法是建立在严格数学基础上的,其目标是通过严格的分析、验证发现软件设计及开发过程中的模糊性和不完备性,以达到对软件质量的有效控制。Petri网是形式化软件开发的一种很好的描述工具,它在描述异步并发的环境、模型验证等方面有着独到之处;图灵机是迄今为止计算能力最强的计算模型,在理论层面上有着其他模型不可替代的重要作用,它深刻地刻画了物理世界的可识别

第 3卷第 3期 1 Vo. . . 1 31 No 3

西华大学学报 (自然科学版 ) J u n lo h a U ie st Nau a S in e o r a f Xi u n v ri y t r l ce c

21 0 2年 5月 Ma 0 2 v2 1

文章编号:6 319 2 1 )30 0 - 17—5 X(0 2 0 -0 1 6 0

计算的模型:灵机与 P t网图 ei r 宋文,牟行军 (西华大学数学与计算机学院,四川成都 6 0 3 ) 1 09

摘

要:式化的软件开发方法是建立在严格数学基础上的,目标是通过严格的分析、形其验证发现软件设计及

开发过程中的模糊性和不完备性,以达到对软件质量的有效控制。P t网是形式化软件开发的一种很好的描述工 ei r具,它在描述异步并发的环境、模型验证等方面有着独到之处;图灵机是迄今为止计算能力最强的计算模型,在理论层面上有着其他模型不可替代的重要作用,它深刻地刻画了物理世界的可识别与可判定 2个重要的概念。文章

给出了这 2种计算模型的一些基本概念、结论以及解决问题的主要方法。最后,用交通管理系统为例说明形式化 方法的运用。

关键词:计算模型;图灵机;er网; Pt i计算;型模 中图分类号:P0 . T 3 16文献标志码: A

M o e f Co pu a i n:Tu i a hi n t iNe d lo m t to r ng M c ne a d Pe r t

S N n MO igjn O G We, U X n— u (colfMa e ts n o p t n i e n, i a U i rt,C eg u60 3 h a Sho o t mai dC m u r gn r g Xh n e i h ca eE ei u v sy hnd 109 C i ) n

Ab t a t F r l ot r e eo me tmeh d i a k n fmah ma ial— a e e h iu . I v i a h e e ef cie c n rlf r sr c: o ma f s wae d v l p n t o s i d o t e t l y b s d tc nq e t al c iv f t o t o c e v o t e s f a e q a i h o g g r u n lss e f ain t i d t e a iu t n n o l tn s f ot r e in a d d v lp n h ot r

u l y t r u h r oo s a ay i,v r i t o f h mb g i a d i c mp ee e so f w t i i c o n y s wae d s n e eo me t g

p o e s er e so e o o d d s r t n to st e r a ot a e d v lp n, ih h so vo sa v tg si ed s r t n r c s .P ti t n fg o e c p i o l me t m l s f r e eo me t wh c a b iu d a a e n t e c p i n i i o o o f w n h i o o s n h o o sc n u r n n i n n d mo e e f ai n u n c i e i a c c lt n mo e i h e t o u ig a i t s fa y c r n u o c r te v r me t e o n a d l r c t .T r g ma h n s a u ai d l t t e b s c mp t b l i vi i o i l o w h n ie

S r w ihejy nielcal r e thoeclee.Idpc epy h o m ot t ocps fdnialns addc - Of, hc n s rpaebe o er i v1 t eitde ltet pr n n eto et bees ei a o a r lat tal s w i a c i f i n d a i t n t e p y ia o l .I hs p p r o a i o c p s h i t o oo y t ov h r b e frt e t o k n so o b l y i h h sc lw r i d n t i a e,s me b sc c n e t,t e man meh d lg o s le t e p o l m w id f m— o h c p tt n lmo es a d c n l s n r r s n e .F rh r o e n e a l ft f c ma a e n y t m itd t x l i o s u a i a d l n o cu i s a ep e e td o o ute m r,a x mp e o af n g me ts se i l e o e p an h w t u e ri s s o t e frna t d . h l lmeho s o

Ke r s c mp t t n mo e;u i g ma h n; er n t c mp tt n; d l y wo d: o u ai d l

t r c i e P ti e; o ua i mo e o n o

从科学的角度看,代软件工程是关于形式化现软件开发方法的一门学科。形式化软件开发技术是

商品化产品的支撑工具和软件环境。虽然,大型对 复杂的系统进行完整的形式化验证不可能完全实

以严格的数学为工具,以模型为基础,使用准确的数 学语义表达方法,行严格的演绎推理的开发方法。进

现,把形式化技术应用于大型复杂系统的关键部但 分,行之有效的策略 J是。在理论研究层面,们不再受困于 N人 P问题的

2 O世纪 8 O年代末期,随着大规模程序开发的 出现,式化技术的学术研究及其工业应用得到了形长足的发展:立了较为容易理解的概念、语、建术规格技术及语言;建立了功能较为强大和完善的模型验证技术;开发出了一些与之适应的从研究原型到 收稿日期:0 2 . 2 1 ̄21 7

解决,高性能计算应运而生,行计算就是其中之并 一

。

同时人们提出了各种有别于图灵机的更加适合

描述并行环境的计算模型,得并行化的理论研究使有了较为坚实的根基。Pt网是并行计算的计算 ei r

基金项目:四川省教育厅应用基础研究项目( 9 20 0; 0 26 3 )西华大学计算机软件与理论重点学科建设( E 0 0 0 S D 8 2— 9—1 ) 作者简介:宋文 ( 96一),,授,导, C 15男教硕 C F高级会员,主要研究方向为 Pt网理论及应用、算理论。 er i计

计算的模型:图灵机与Petri网

第1页

TOP相关主题

热门文档

相关文档

  • 基本图灵机的Petri网建模研究

    1 基本图灵机及 Petri 网 1.1 基本图灵机图灵机是一种抽象的计算模型。 图灵机基本模型有一个有穷控制器,一条输入带和一个带头,输入带被分成许多单元,带头在...

  • Petri网模型的语用计算机

    —问题与探索; 我对计算机的认识—二元计算模型; 现阶段的研究与开发— 语用...络伊曼 结构 图灵机 Petri网 ? 状态元素 内存单元 变化元素 机器指令 关系 ...

  • Petri网模型

    Petri网模型_信息与通信_工程科技_专业资料。Petri网模型及应用Petri网基本概念 1960年德国Carl Adam Petri博士首次提 出 Petri网是一种图论工具,适于对离散事 件动...

  • Web1.0、_Web2.0、Web3.0、Web4.0、Web5.0及Web6.0的涵义

    语用网里,计算应用 界的人们所关心的是他们设计的软件模块和语用文章。前者是 图灵机模型的应用,关注于算法的可计算性和计算复杂度问题; 后者是Petri网理论的应用...

  • 小多项式时间万能Petri网

    小型通用Petri网的库所/变迁数(14,42)和(14,29)用模拟已知的小通用图 灵机...因此,构建UPN是有效的计算模型。 接下来,PolyUPN(15,29)网由UPN(14,29 )网...

  • 计算机学科的12个核心概念

    概念和形式模型主要采用数学方法进行研究。例如用于研究计算能力的 常用计算模型有图灵机、递归函数、λ 演算等;用于研究并行与分布式特性的 常用并发模型有 Petri 网...

  • 算法与图灵机模型

    ? ? ? ? 图灵机缘起 图灵机描述 计算“X+1”的图灵机 通用图灵机 图灵机模型的启示 01:00 2.2.1图灵机概念 ? 1900,德国数学家希尔伯特提出"23个数学难题...

  • Petri网模型参数化可达图研究(1)

    s∈S: 2 参数化模型性质检测相关工作由于一般的 Petri 网模型可达图都是根据初始标识计算 出来的,如果系统模型是参数化的,即初始标识的位置标记 数量是变量参数,...

  • 三划分问题可多项式归约为唯一可达向量Petri网可达性问题

    可计算 性和计算复杂性理论中几个相关的基本概念111J.用 不确定的图灵机在...扩展的三划分问题的Petri网模型算法1 归约为Petri网三的可达性问题,算法1详细...

  • 语用网的搜索原理

    这个计算哲学模型的地位,在计算机科学领域里,就相当于"图灵机"和"Petri 网" . 我希望 10 年后我能够表达出这个计算哲学的系统模型来. 分享到: X 分享到: ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email