膜计算导论

2012-6  

华中科技大学出版社  

Gheorghe Paun  

398  

572000  

无  

　　《膜计算导论》是第一本系统全面介绍膜计算的中文译著，本书的内容涵盖了膜计算研究领域的核心概念与结论，包括几类重要的P系统以及它们的计算能力与计算效率、较为完备的参考文献，以及一系列的公开问题和研究主题。原著出版于2002年，根据该领域的最新进展，在中文译著中增加了一章“膜计算最新进展”。

膜计算领域的创始人，罗马尼亚科学院院士、欧洲科学院院±、国际信息科学院院士，西班牙塞维利亚大学、德国马格德堡大学、荷兰莱顿大学、芬兰计算机研究中心等欧洲知名大学与研究机构特聘教授。
多年来从事形式语言理论及其应用、DNA计算、膜计算等方面的研究工作，发表学术论文500余篇，出版专著11本，作为主题报告演讲者参与国际会议100多次，兼任20多个国际期刊编委，自2009年起，进入ISI学术高频引用科学家名录。

第一章 绪论：膜计算—它是什么，它不是什么
第二章 预备知识
2.1 生物膜
2.1.1 质膜的结构
2.1.2 透膜运输
2.1.3 细胞分裂：有丝分裂
2.2 神经元
2.3 可计算性初步
2.3.1 基本概念和符号
2.3.2 串和语言的运算
2.3.3 Chomsky文法
2.3.4 语言的刻画与必要条件
2.3.5 Lindenmayer系统
2.3.6 有穷自动机与图灵机
2.3.7 受控重写
2.3.8 关于CS和RE的差异
2.3.9 通用图灵机和0型文法
2.3.10 剪接操作、插入-删除操作、上下文邻接操作
2.3.11 复杂性初步
2.3.12 多重集
2.4 文献注释
第三章 符号-对象膜系统
3.1 基本类型
3.2 两个例子
3.3 基本类型的计算能力
3.4 基本扩展
3.4.1 膜的溶解
3.4.2 进化规则的优先次序
3.4.3 两个例子
3.4.4 带规则优先次序的膜系统的计算能力
3.4.5 具有同步特性膜系统的计算能力
3.5 形式化定义
3.6 进一步扩展
3.6.1 弱目标命令
3.6.2 控制膜的渗透性
3.6.3 由浓度控制的通信
3.6.4 在计算过程中产生规则
3.6.5 使用促进剂或抵制剂
3.7 带外部输出的系统
3.8 文献注释
第四章 通信取化进化
4.1 同向/反向转运系统
4.2 计算通用性
4.3 控制规则使用
4.4 跟踪对象的轨迹
4.5 带载体的膜系统
4.6 文献注释
第五章 结构化对象
5.1 重写膜系统
5.2 若干变型系统及其计算能力
5.2.1 规则创建
5.2.2 条件重写
5.2.3 条件通信
5.2.4 复制重写
5.2.5 并行重写
5.3 剪接膜系统
5.4 上下文膜系统
5.5 插入-删除膜系统
5.6 文献注释
第六章 膜网络
6.1 剪接情形
6.2 使用同向/反向转运规则
6.3 类神经膜网络
6.3.1 定义和实例
6.3.2 计算能力
6.3.3 计算效率
6.4 文献注释
第七章 以空间换取时间
7.1 膜系统的复杂类
7.2 膜分裂法
7.2.1 线性时间内解决SAT问题
7.2.2 解决哈密尔顿路径问题
7.2.3 使用协作规则
7.2.4 膜分裂是否必要
7.3 膜生成法
7.3.1 解决SAT问题
7.3.2 解决HPP问题
7.3.3 字符串-对象
7.4 字符串复制
7.5 预计算资源的使用
7.6 文献注释
第八章 更多探究结果
8.1 判定性结果
8.2 一元系统
8.3 上下文无关语言的刻画
8.4 字符串-对象的评估
8.5 增强型膜处理系统
8.6 成果概览
8.6.1 广义串行膜系统
8.6.2 二维对象
8.6.3 膜系统与流X-机
8.6.4 膜系统与环境演算
8.6.5 通用系统的直接构造
8.6.6 进一步的研究课题
第九章 从抽象再到现实
9.1 细胞中的能量
9.2 细胞的芽生
9.3 细胞的双层膜结构
9.4 在电子计算机上的实现
9.5 人工生命的应用
9.6 模拟光合作用
公开问题
通用性结论
参考文献
索引
附录 膜计算最新进展
F.1 前面章 节中公开问题的跟踪研究
F.2 脉冲神经膜系统
F.2.1 非正式的介绍及例子
F.2.2 形式化定义
F.2.3 一些结果
F.3 分布式膜自动机
F.3.1 膜自动机计算能力的再研究
F.3.2 分布式膜自动机的计算能力
附录参考文献

版权页： 插图： 另一种定义图灵机所接受语言的方式也是一种比较自然的方式：它所接受语言中的每个输入串W∈T，都能使图灵机从初始格局soW出发，并最终进入终止格局（不能进一步转移的格局）。这时终止状态集F就不再有意义了。上述两种定义L（M）的方式是等价的，它们识别的语言集合也是等价的，称为递归可枚举语言，记为RE。确定性图灵机与非确定性图灵机接受的语言也是等价的，都是RE。 如果在图灵机上使用多条带，其中一条作为执行字符读写操作的输入带，其他的带作为工作带，并且对于所有的工作带都用相同的工作控制，这种变型并不能提高图灵机的计算能力。但是这种多带图灵机可以用来处理复杂的计算过程（参见2.3.11节），因为它可以实现分别记录读取字符消耗的时间与识别、处理字符所消耗的时间。 从图形的角度来看，标准图灵机（只有一条输入带）可以利用类似于描述有穷状态自动机的方式（见图2.7）进行表示。它们在功能上有两点区别：一是图灵机的读写头可以左右移动，而有穷状态自动机只能向左移动：二是图灵机可以读取并改写（包括擦除，即改写为空字符）输入带上的字符，而有穷状态自动机仅仅可以读取输入带上的字符。其中第二点是影响两者计算能力大小至关重要的区别。 图灵机不仅仅是一个定义语言的装置，它也是一个定义映射的装置，在这里我们不详细介绍它作为定义映射装置的工作过程。简单地讲，映射的功能是通过两个瞬时描述，即输入瞬时描述与终止瞬时描述，计算给定函数的值。同样，可以利用输入带描述自变量，输出带描述当前自变量下的函数值，有时计算过程也会用到其他的工作带。 对于某个输入字符串，图灵机允许使用多条带来识别这个字符串，而有穷状态自动机则只能在字符串写入的带上进行读取操作。如果限制图灵机的每条工作带为有限长度，这样则限制了图灵机的计算空间，因此它只能识别长度有限的字符串。这个特殊形式的图灵机被称为线性界限自动机，它刻画的语言族是上下文有关语言，记为CS。 在计算机科学领域中有许多与图灵机等价的计算模型，但是由于图灵机具有杰出的计算能力与稳定性（没有什么计算模型能够超越图灵机的计算能力），它是人们公认的理想计算模型的标准形式。事实上，根据图灵一丘奇论题，任何可以通过算法计算的问题都可以由图灵机进行求解。

《世界科技名著译丛:膜计算导论》是第一本系统全面介绍膜计算的中文译著，适合从事相关研究工作的人员参考阅读。

无

膜计算导论 PDF格式下载

一本有关细胞，计算，与算法的书。很有启发性。作者是欧洲科学院院士，译者也是国内大牛。

看完此书有很大的收获，每一个计算机专业的人，都值得读一读。