膜計(jì)算導(dǎo)論

內(nèi)容概要

　　《膜計(jì)算導(dǎo)論》是第一本系統(tǒng)全面介紹膜計(jì)算的中文譯著，本書的內(nèi)容涵蓋了膜計(jì)算研究領(lǐng)域的核心概念與結(jié)論，包括幾類重要的P系統(tǒng)以及它們的計(jì)算能力與計(jì)算效率、較為完備的參考文獻(xiàn)，以及一系列的公開問題和研究主題。原著出版于2002年，根據(jù)該領(lǐng)域的最新進(jìn)展，在中文譯著中增加了一章“膜計(jì)算最新進(jìn)展”。

作者簡介

膜計(jì)算領(lǐng)域的創(chuàng)始人，羅馬尼亞科學(xué)院院士、歐洲科學(xué)院院±、國際信息科學(xué)院院士，西班牙塞維利亞大學(xué)、德國馬格德堡大學(xué)、荷蘭萊頓大學(xué)、芬蘭計(jì)算機(jī)研究中心等歐洲知名大學(xué)與研究機(jī)構(gòu)特聘教授。
多年來從事形式語言理論及其應(yīng)用、DNA計(jì)算、膜計(jì)算等方面的研究工作，發(fā)表學(xué)術(shù)論文500余篇，出版專著11本，作為主題報(bào)告演講者參與國際會議100多次，兼任20多個(gè)國際期刊編委，自2009年起，進(jìn)入ISI學(xué)術(shù)高頻引用科學(xué)家名錄。

書籍目錄

第一章 緒論：膜計(jì)算—它是什么，它不是什么
第二章 預(yù)備知識
2.1 生物膜
2.1.1 質(zhì)膜的結(jié)構(gòu)
2.1.2 透膜運(yùn)輸
2.1.3 細(xì)胞分裂：有絲分裂
2.2 神經(jīng)元
2.3 可計(jì)算性初步
2.3.1 基本概念和符號
2.3.2 串和語言的運(yùn)算
2.3.3 Chomsky文法
2.3.4 語言的刻畫與必要條件
2.3.5 Lindenmayer系統(tǒng)
2.3.6 有窮自動機(jī)與圖靈機(jī)
2.3.7 受控重寫
2.3.8 關(guān)于CS和RE的差異
2.3.9 通用圖靈機(jī)和0型文法
2.3.10 剪接操作、插入-刪除操作、上下文鄰接操作
2.3.11 復(fù)雜性初步
2.3.12 多重集
2.4 文獻(xiàn)注釋
第三章 符號-對象膜系統(tǒng)
3.1 基本類型
3.2 兩個(gè)例子
3.3 基本類型的計(jì)算能力
3.4 基本擴(kuò)展
3.4.1 膜的溶解
3.4.2 進(jìn)化規(guī)則的優(yōu)先次序
3.4.3 兩個(gè)例子
3.4.4 帶規(guī)則優(yōu)先次序的膜系統(tǒng)的計(jì)算能力
3.4.5 具有同步特性膜系統(tǒng)的計(jì)算能力
3.5 形式化定義
3.6 進(jìn)一步擴(kuò)展
3.6.1 弱目標(biāo)命令
3.6.2 控制膜的滲透性
3.6.3 由濃度控制的通信
3.6.4 在計(jì)算過程中產(chǎn)生規(guī)則
3.6.5 使用促進(jìn)劑或抵制劑
3.7 帶外部輸出的系統(tǒng)
3.8 文獻(xiàn)注釋
第四章 通信取化進(jìn)化
4.1 同向/反向轉(zhuǎn)運(yùn)系統(tǒng)
4.2 計(jì)算通用性
4.3 控制規(guī)則使用
4.4 跟蹤對象的軌跡
4.5 帶載體的膜系統(tǒng)
4.6 文獻(xiàn)注釋
第五章 結(jié)構(gòu)化對象
5.1 重寫膜系統(tǒng)
5.2 若干變型系統(tǒng)及其計(jì)算能力
5.2.1 規(guī)則創(chuàng)建
5.2.2 條件重寫
5.2.3 條件通信
5.2.4 復(fù)制重寫
5.2.5 并行重寫
5.3 剪接膜系統(tǒng)
5.4 上下文膜系統(tǒng)
5.5 插入-刪除膜系統(tǒng)
5.6 文獻(xiàn)注釋
第六章 膜網(wǎng)絡(luò)
6.1 剪接情形
6.2 使用同向/反向轉(zhuǎn)運(yùn)規(guī)則
6.3 類神經(jīng)膜網(wǎng)絡(luò)
6.3.1 定義和實(shí)例
6.3.2 計(jì)算能力
6.3.3 計(jì)算效率
6.4 文獻(xiàn)注釋
第七章 以空間換取時(shí)間
7.1 膜系統(tǒng)的復(fù)雜類
7.2 膜分裂法
7.2.1 線性時(shí)間內(nèi)解決SAT問題
7.2.2 解決哈密爾頓路徑問題
7.2.3 使用協(xié)作規(guī)則
7.2.4 膜分裂是否必要
7.3 膜生成法
7.3.1 解決SAT問題
7.3.2 解決HPP問題
7.3.3 字符串-對象
7.4 字符串復(fù)制
7.5 預(yù)計(jì)算資源的使用
7.6 文獻(xiàn)注釋
第八章 更多探究結(jié)果
8.1 判定性結(jié)果
8.2 一元系統(tǒng)
8.3 上下文無關(guān)語言的刻畫
8.4 字符串-對象的評估
8.5 增強(qiáng)型膜處理系統(tǒng)
8.6 成果概覽
8.6.1 廣義串行膜系統(tǒng)
8.6.2 二維對象
8.6.3 膜系統(tǒng)與流X-機(jī)
8.6.4 膜系統(tǒng)與環(huán)境演算
8.6.5 通用系統(tǒng)的直接構(gòu)造
8.6.6 進(jìn)一步的研究課題
第九章 從抽象再到現(xiàn)實(shí)
9.1 細(xì)胞中的能量
9.2 細(xì)胞的芽生
9.3 細(xì)胞的雙層膜結(jié)構(gòu)
9.4 在電子計(jì)算機(jī)上的實(shí)現(xiàn)
9.5 人工生命的應(yīng)用
9.6 模擬光合作用
公開問題
通用性結(jié)論
參考文獻(xiàn)
索引
附錄 膜計(jì)算最新進(jìn)展
F.1 前面章 節(jié)中公開問題的跟蹤研究
F.2 脈沖神經(jīng)膜系統(tǒng)
F.2.1 非正式的介紹及例子
F.2.2 形式化定義
F.2.3 一些結(jié)果
F.3 分布式膜自動機(jī)
F.3.1 膜自動機(jī)計(jì)算能力的再研究
F.3.2 分布式膜自動機(jī)的計(jì)算能力
附錄參考文獻(xiàn)

章節(jié)摘錄

版權(quán)頁：   插圖：   另一種定義圖靈機(jī)所接受語言的方式也是一種比較自然的方式：它所接受語言中的每個(gè)輸入串W∈T，都能使圖靈機(jī)從初始格局soW出發(fā)，并最終進(jìn)入終止格局（不能進(jìn)一步轉(zhuǎn)移的格局）。這時(shí)終止?fàn)顟B(tài)集F就不再有意義了。上述兩種定義L（M）的方式是等價(jià)的，它們識別的語言集合也是等價(jià)的，稱為遞歸可枚舉語言，記為RE。確定性圖靈機(jī)與非確定性圖靈機(jī)接受的語言也是等價(jià)的，都是RE。 如果在圖靈機(jī)上使用多條帶，其中一條作為執(zhí)行字符讀寫操作的輸入帶，其他的帶作為工作帶，并且對于所有的工作帶都用相同的工作控制，這種變型并不能提高圖靈機(jī)的計(jì)算能力。但是這種多帶圖靈機(jī)可以用來處理復(fù)雜的計(jì)算過程（參見2.3.11節(jié)），因?yàn)樗梢詫?shí)現(xiàn)分別記錄讀取字符消耗的時(shí)間與識別、處理字符所消耗的時(shí)間。 從圖形的角度來看，標(biāo)準(zhǔn)圖靈機(jī)（只有一條輸入帶）可以利用類似于描述有窮狀態(tài)自動機(jī)的方式（見圖2.7）進(jìn)行表示。它們在功能上有兩點(diǎn)區(qū)別：一是圖靈機(jī)的讀寫頭可以左右移動，而有窮狀態(tài)自動機(jī)只能向左移動：二是圖靈機(jī)可以讀取并改寫（包括擦除，即改寫為空字符）輸入帶上的字符，而有窮狀態(tài)自動機(jī)僅僅可以讀取輸入帶上的字符。其中第二點(diǎn)是影響兩者計(jì)算能力大小至關(guān)重要的區(qū)別。 圖靈機(jī)不僅僅是一個(gè)定義語言的裝置，它也是一個(gè)定義映射的裝置，在這里我們不詳細(xì)介紹它作為定義映射裝置的工作過程。簡單地講，映射的功能是通過兩個(gè)瞬時(shí)描述，即輸入瞬時(shí)描述與終止瞬時(shí)描述，計(jì)算給定函數(shù)的值。同樣，可以利用輸入帶描述自變量，輸出帶描述當(dāng)前自變量下的函數(shù)值，有時(shí)計(jì)算過程也會用到其他的工作帶。 對于某個(gè)輸入字符串，圖靈機(jī)允許使用多條帶來識別這個(gè)字符串，而有窮狀態(tài)自動機(jī)則只能在字符串寫入的帶上進(jìn)行讀取操作。如果限制圖靈機(jī)的每條工作帶為有限長度，這樣則限制了圖靈機(jī)的計(jì)算空間，因此它只能識別長度有限的字符串。這個(gè)特殊形式的圖靈機(jī)被稱為線性界限自動機(jī)，它刻畫的語言族是上下文有關(guān)語言，記為CS。 在計(jì)算機(jī)科學(xué)領(lǐng)域中有許多與圖靈機(jī)等價(jià)的計(jì)算模型，但是由于圖靈機(jī)具有杰出的計(jì)算能力與穩(wěn)定性（沒有什么計(jì)算模型能夠超越圖靈機(jī)的計(jì)算能力），它是人們公認(rèn)的理想計(jì)算模型的標(biāo)準(zhǔn)形式。事實(shí)上，根據(jù)圖靈一丘奇論題，任何可以通過算法計(jì)算的問題都可以由圖靈機(jī)進(jìn)行求解。

編輯推薦

《世界科技名著譯叢:膜計(jì)算導(dǎo)論》是第一本系統(tǒng)全面介紹膜計(jì)算的中文譯著，適合從事相關(guān)研究工作的人員參考閱讀。

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    膜計(jì)算導(dǎo)論 PDF格式下載

---