計算理論導(dǎo)引

定　價：￥30.00

作　者：	（美）Michael Sipser著；張立昂，王捍貧，黃雄譯
出版社：	機(jī)械工業(yè)出版社
叢編項(xiàng)：	計算機(jī)科學(xué)叢書
標(biāo)　簽：	暫缺

購買這本書可以去

ISBN：	9787111075745	出版時間：	2002-01-01	包裝：	膠版紙
開本：	26cm	頁數(shù)：	284	字?jǐn)?shù)：

內(nèi)容簡介

　　本書由計算理論領(lǐng)域的知名權(quán)威Michael Sipser撰寫。他以獨(dú)特的視角，綜合地描述了計算機(jī)科學(xué)理論，并以清新的筆觸、生動的語言給出了寬泛的數(shù)學(xué)理論，而并非拘泥于某些低層次的技術(shù)細(xì)節(jié)。在證明之前，均有“證明思路”，幫助讀者理解數(shù)學(xué)形式下蘊(yùn)涵的概念。同樣，對于算法描述，均以直觀的文字，而非偽代碼給出，從而將注意力集中于算法本身，而不是某些模型。本書的內(nèi)容包括三個部分：自動機(jī)與語言、可計算性理論和計算復(fù)雜性理論。本書可作為計算機(jī)專業(yè)高年級本科生和研究生的教材，也可作為教師和研究人員的參考書。

作者簡介

　　譯者介紹張立昂，1941年2月出生，1965年畢業(yè)于北京大學(xué)數(shù)學(xué)力學(xué)系數(shù)學(xué)專業(yè)。現(xiàn)為北京大學(xué)計算機(jī)科學(xué)與技術(shù)系教授、博士生導(dǎo)師。主要研究方向：算法設(shè)計與分析、計算復(fù)雜性理論。著有《可計算性與計算復(fù)雜性導(dǎo)引》等。王捍貧，1964年7月出生，1993年畢業(yè)于北京師范大學(xué)數(shù)學(xué)系數(shù)理邏輯專業(yè)，獲博士學(xué)位?，F(xiàn)為北京大學(xué)計算機(jī)科學(xué)與技術(shù)系副教授。主要研究方向?yàn)閿?shù)理邏輯、計算復(fù)雜性、程序語義及正確性驗(yàn)證技術(shù)。著作有《數(shù)理邏輯》等。黃雄，1969年8月出生，北京大學(xué)計算機(jī)科學(xué)碩士，北京航空航天大學(xué)計算機(jī)科學(xué)博士?，F(xiàn)在中國科學(xué)院計算所做博士后。研究領(lǐng)域包括：算未能設(shè)計與分析、計算復(fù)雜性Web信息檢索。

圖書目錄

目錄
譯者序
前言
第1章   導(dǎo)引
1.1   自動機(jī). 可計算性與復(fù)雜性
1.1.1   計算復(fù)雜性理論
1.1.2   可計算性理論
1.1.3    自動機(jī)理論
1.2   數(shù)學(xué)概念和術(shù)語
1.2.1   集合
1.2.2   序列和多元組
1.2.3   函數(shù)和關(guān)系
1.2.4   圖
1.2.5   字符串和語言
1.2.6   布爾邏輯
1.2.7    數(shù)學(xué)名詞匯總
1.3    定義. 定理和證明
1.4    證明的類型
1.4.1    構(gòu)造性證明
1.4.2   反證法
1.4.3   歸納法
練習(xí)
問題
第一部分    自動機(jī)與語言
第2 章   正則語言
2.1   有窮自動機(jī)
2.1.1    有窮自動機(jī)的形式定義
2.1.2    有窮自動機(jī)舉例
2.1.3    計算的形式定義
2.1.4   設(shè)計有窮自動機(jī)
2.1.5   正則運(yùn)算
2.2   非確定性
2.2.1   非確定型有窮自動機(jī)的形式定義
2.2.2    NFA與DFA的等價性
2.2.3    在正則運(yùn)算下的封閉性
2.3    正則表達(dá)式
2.3.1    正則表達(dá)式的形式定義
2.3.2    與有窮自動機(jī)的等價性
2.4    非正則語言
練習(xí)
問題
第3章   上下文無關(guān)語言
3.1    上下文無關(guān)文法
3.1.1    上下文無關(guān)文法的形式定義
3.1.2    上下文無關(guān)文法舉例
3.1.3    設(shè)計上下文無關(guān)文法
3.1.4     歧義性
3.1.5     喬姆斯基范式
3.2    下推自動機(jī)
3.2.1    下推自動機(jī)的形式定義
3.2.2    下推自動機(jī)舉例
3.2.3     與上下文無關(guān)文法的等價性
3.3     非上下文無關(guān)語言
練習(xí)
問題
第二部分   可計算性理論
第4章    丘奇—圖靈論題
4.1   圖靈機(jī)
4.1.1    圖靈機(jī)的形式定義
4.1.2    圖靈機(jī)的例子
4.2    圖靈機(jī)的變形
4.2.1    多帶圖靈機(jī)
4.2.2     非確定型圖靈機(jī)
4.2.3     枚舉器
4.2.4    與其他模型的等價性
4.3     算法的定義
4.3.1    希爾伯特問題
4.3.2    描述圖靈機(jī)的術(shù)語
練習(xí)
問題
第5章   可判定性
5.1    可判定語言
5.1.1     與正則語言相關(guān)的可判定性問題
5.1.2    與上下文無關(guān)語言相關(guān)的可判定問題
5.2    停機(jī)問題
5.2.1    對角化方法
5.2.2    停機(jī)問題是不可判定的
5.2.3    一個圖靈不可識別語言
練習(xí)
問題
第6章    可歸約性
6.1    語言理論中的不可判定問題
6.2     一個簡單的不可判定問題
6.3     映射可歸約性
6.3.1   可計算函數(shù)
6.3.2    映射可歸約性的形式定義
練習(xí)
問題
第7 章    可計算性理論的高級專題
7.1    遞歸定理
7.1.1    自引用
7.1.2    應(yīng)用遞歸定理的術(shù)語
7.1.3   應(yīng)用
7.2    邏輯理論的可判定性
7.2.1    一個可判定的理論
7.2.2    一個不可判定的理論
7.3     圖靈可歸約性
7.4     信息的定義
7.4.1    極小長度的描述
7.4.2    定義的優(yōu)化
7.4.3    不可壓縮的串和隨機(jī)性
練習(xí)
問題
第三部分   復(fù)雜性理論
第8章   時間復(fù)雜性
8.1    度量復(fù)雜性
8.1.1    大O和小o記法
8.1.2    分析算法
8.1.3     模型間的復(fù)雜性關(guān)系
8.2   P 類
8.2.1   多項(xiàng)式時間
8.2.2   P 中的問題舉例
8.3    NP類
8.3.1   NP中的問題舉例
8.3.2   P與NP問題
8.4    NP完全性
8.4.1     多項(xiàng)式時間可歸約性
8.4.2     NP完全性的定義
8.4.3    庫克—列文定理
8.5    幾個NP完全問題
8.5.1    頂點(diǎn)覆蓋問題
8.5.2    哈密頓路徑問題
8.5.3    子集和問題
練習(xí)
問題
第9章    空間復(fù)雜性
9.1    薩維奇定理
9.2    PSPACE類
9.3   PSPACE完全性
9.3.1     問題TQBF
9.3.2    博奕的必勝策略
9.3.3     廣義地理學(xué)
9.4     L類和NL學(xué)
9.5    NL 完全性
9.6    NL等于coNL
練習(xí)
問題
第10章    難解性
10.1   層次定理
10.2    相對化
10.3    電路復(fù)雜性
練習(xí)
問題
第 11章    復(fù)雜性理論中的高級專題
11.1    近似算法
11.2    概率算法
11.2.1    BPP類
11.2.2    素數(shù)性
11.2.3    只讀一次的分支程序
11.3    交錯式
11.3.1    交錯式時間與交錯式空間
11.3.2    多項(xiàng)式時間層次
11.4     交互式證明系統(tǒng)
11.4.1    圖的非同構(gòu)
11.4.2    模型的定義
11.4.3    IP=PSPACE
11.5   并行計算
11.5.1    一致布爾電路
11.5.2    NC類
11.5.3    P完全性
11.6     密碼學(xué)
11.6.1     密鑰
11.6.2    公鑰密碼系統(tǒng)
11.6.3    單向函數(shù)
11.6.4     天窗函數(shù)
練習(xí)
問題
參考文獻(xiàn)
索引