新書推薦：
《
形似神异：什么是中日传统政治文化的结构性差异
》
售價：NT$
254.0
《
养育不好惹的小孩
》
售價：NT$
352.0
《
加加美高浩的手部绘画技法 II
》
售價：NT$
407.0
《
卡特里娜（“同一颗星球”丛书）
》
售價：NT$
398.0
《
伟大民族：从路易十五到拿破仑的法国史（方尖碑）
》
售價：NT$
857.0
《
古今“书画同源”论辨——中国书法与中国绘画的关系问题兼中国画笔墨研究
》
售價：NT$
602.0
《
《日本文学史序说》讲演录
》
售價：NT$
332.0
《
无尽的海洋：美国海事探险与大众文化（1815—1860）
》
售價：NT$
454.0
|
| 內容簡介： |
替式下推自动机是当前并行与分布式计算环境的数学模型，而墨水点是对移动智能体在宿主机器上写入信息的一种模拟，交替式下推自动机的研究对于解明基于互联网的并行与分布式计算的复杂性具有重要的理论意义。
交替式是由Chandra、Kozen和Stockmeyer提出来的一个并行与分布式计算的理论模型。交替式图灵机（Alternating Turing Machine）是对非确定性图灵机的一个扩展，它的有穷状态被分为全称状态（Universal State）和存在状态（Existential State）两种不同的计算状态。交替式图灵机采用交替的方式，不断采用存在和全称两种计算方式进行计算，已经证明，这种交替式计算模式有效地提高了计算能力，交替式下推自动机则是比交替式图灵机更为简单的计算模型。关于亚对数空间限定的交替式图灵机的研究取得了较大进展，但是，目前国际上关于多墨水点交替式下推自动机的研究还比较少。替式下推自动机是当前并行与分布式计算环境的数学模型，而墨水点是对移动智能体在宿主机器上写入信息的一种模拟，交替式下推自动机的研究对于解明基于互联网的并行与分布式计算的复杂性具有重要的理论意义。
交替式是由Chandra、Kozen和Stockmeyer提出来的一个并行与分布式计算的理论模型。交替式图灵机（Alternating Turing Machine）是对非确定性图灵机的一个扩展，它的有穷状态被分为全称状态（Universal State）和存在状态（Existential State）两种不同的计算状态。交替式图灵机采用交替的方式，不断采用存在和全称两种计算方式进行计算，已经证明，这种交替式计算模式有效地提高了计算能力，交替式下推自动机则是比交替式图灵机更为简单的计算模型。关于亚对数空间限定的交替式图灵机的研究取得了较大进展，但是，目前国际上关于多墨水点交替式下推自动机的研究还比较少。
本书引入两种类型的机器模型，即具有亚对数空间的2方向交替式下推自动机和具有多个墨水点的交替式下推自动机，并对这两种类型自动机模型的一些重要性质进行了深入研究，并提出了多墨水点交替式下推自动机的概念；研究了在亚对数空间下，墨水点个数对仅有全称状态的多墨水点交替式下推自动机计算能力的影响；证明了亚对数空间限定的仅有全称状态的多墨水点交替式下推自动机计算能力随着墨水点个数的增加而增强，研究了在亚对数空间下，仅有全称状态和仅有存在状态的多墨水点交替式下推自动机计算能力的关系，证明了它们的计算能力是不可比较的；论证了在亚对数空间下，仅有全称状态的多墨水点交替式下推自动机所识别的语言族，以及仅有存在状态的多墨水点交替式下推自动机所识别语言族的闭包属性，证明了这些语言族在补、与正则语言的连接、星号及保持长度的同态运算下是不封闭的；引入自验证的1墨水点2方向非确定性下推自动机，证明了在亚对数空间下，具有1墨水点的非确定性下推自动机计算能力比具有1墨水点的自验证非确定性下推自动机的计算能力强。本书*后讨论了相关的几个尚待研究解决的问题，提出了今后研究的方向。
|
| 目錄：
|
第1章引言1
第2章形式语言与自动机11
21抽象代数知识准备11
22形式语言与自动机12
221字符串和语言12
222有穷状态自动机13
23图灵机形式化定义15
24下推自动机及其模型18
25分布式计算和并行计算19
26自动机理论基础21
261自动机定义22
262自动机理论22
263有限自动机理论22
264无限自动机理论23
265概率自动机理论23
266细胞自动机理论23
267抽象自动机理论24
27自动机理论与其他学科的关系24
271与数学学科的关系24
272与形式语言的关系24
273与控制论的关系24
274与生物领域的关系25
28交替式下推自动机与网格25
281网格计算兴起25
282网格定义26
283网格信息处理原理27
284交替式下推自动机与网格计算27
29自动机理论与先进计算28
291并行计算28
292分布式计算29
293集群计算29
294网格计算30
295云计算31
210本章小结33
第3章交替式下推自动机34
312方向交替式下推自动机的定义与性质34
32强loglog n空间限定的2DPDA识别性证明37
33本章小结40
第4章多墨水点交替式下推自动机的计算复杂性研究41
41定义和标识约定41
42多墨水点交替式下推自动机的墨水点层次性42
43全称状态与存在状态计算方式的不可比较性46
44本章小结51
第5章多墨水点交替式下推自动机的闭包属性53
51多墨水点非确定性下推自动机的闭包属性53
52仅有全称状态的多墨水点交替式下推自动机的闭包属性56
53本章小结61
第6章交替式下推自动机语言运算的封闭性62
61格局相关的有穷控制器的状态62
62连接、星号和保持长度的同态等的运算封闭性63
632方向交替式下推自动机闭包属性的结果69
第7章自验证的1墨水点非确定性下推自动机70
71自验证的1墨水点非确定性下推自动机的概念70
72有无墨水点的非确定性下推自动机之间的关系71
73本章小结74
第８章亚对数空间限定的多墨水点交替式下推自动机的闭包属性75
81具有k个墨水点的图灵机75
82多墨水点交替式下推自动机的闭包属性76
83语言族m2UPDAkLn运算的不封闭性79
第9章总结和展望81
91研究总结81
92研究展望82
参考文献84
附录符号及术语表90
|
|
購物車/收銀台(0) | 在線留言板
| 付款方式
| 聯絡我們
| 運費計算
| 幫助中心 |
加入書簽
HOME
新書上架
