計(jì)算理論基礎(chǔ)（第2版）

定　價(jià)：￥29.00

作　者：	（美）[H.R.劉易斯]Harry R.Lewis，（美）[C.H.帕帕季米特里烏]Christos H.Papadimitriou著；張立昂，劉田譯；張立昂譯
出版社：	清華大學(xué)出版社
叢編項(xiàng)：	世界著名計(jì)算機(jī)教材精選
標(biāo)　簽：	算法

購買這本書可以去

當(dāng)當(dāng)網(wǎng) (￥24.70)

ISBN：	9787302039488	出版時(shí)間：	2002-07-01	包裝：
開本：	26cm	頁數(shù)：	256	字?jǐn)?shù)：

內(nèi)容簡介

　　計(jì)算理論是計(jì)算機(jī)科學(xué)的理論基礎(chǔ)。本書介紹了計(jì)算理論最核心、最基本的內(nèi)容，包括形式語言與自動(dòng)機(jī)、可計(jì)算性和計(jì)算復(fù)雜性三大部分。全書共分七章，分別為：集合、關(guān)系和語言；有窮自動(dòng)機(jī)；上下文無關(guān)語言；Turing機(jī)；不可判定性；計(jì)算復(fù)雜性；NP完全性。本書突出了算法，從而使計(jì)算機(jī)專業(yè)的學(xué)生更易接受，也更有收益。本書適合作為計(jì)算機(jī)專業(yè)及數(shù)學(xué)專業(yè)本科生或研究生的教材，也可供從事計(jì)算機(jī)科學(xué)的教學(xué)與研究人員參考。

作者簡介

暫缺《計(jì)算理論基礎(chǔ)（第2版）》作者簡介

圖書目錄

譯者序
第一版序言
第二版序言
導(dǎo)言
第1章  集合. 關(guān)系和語言
1. 1  集合
1. 2  關(guān)系與函數(shù)
1. 3  特殊類型的二元關(guān)系
1. 4  有窮集合與無窮集合
1. 5  三個(gè)基本的證明技術(shù)
1. 6  閉包與算法
1. 7  字母表與語言
1. 8  語言的有窮表示
參考文獻(xiàn)
第2章有窮自動(dòng)機(jī)
2. 1  確定型有窮自動(dòng)機(jī)
2. 2  非確定型有窮自動(dòng)機(jī)
2. 3  有窮自動(dòng)機(jī)與正則表達(dá)式
2. 4  正則語言與非正則語言
2. 5  狀態(tài)最小化
2. 6  關(guān)于有窮自動(dòng)機(jī)的算法
參考文獻(xiàn)
第3章  上下文無關(guān)語言
3. 1  上下文無關(guān)文法
3. 2  語法分析樹
3. 3  下推自動(dòng)機(jī)
3. 4  下推自動(dòng)機(jī)與上下文無關(guān)文法
3. 5  上下文無關(guān)語言與非上下文無關(guān)語言
3. 6  關(guān)于上下文無關(guān)文法的算法
3. 7  確定性與語法分析
參考文獻(xiàn)
第4章  Turing機(jī)
4. 1  Turing機(jī)的定義
4. 2  用Turing機(jī)計(jì)算
4. 3  Turing機(jī)的擴(kuò)充
4. 4  隨機(jī)存取Turing機(jī)
4. 5  非確定型Turing機(jī)
4. 6  文法
4. 7  數(shù)值函數(shù)
參考文獻(xiàn)
第5章  不可判定性
5. 1  Church-Turing論題
5. 2  通用Turing機(jī)
5. 3  停機(jī)問題
5. 4  與Turing機(jī)有關(guān)的不可判定問題
5. 5  與文法有關(guān)的不可解問題
5. 6  不可解的鋪磚問題
5. 7  遞歸語言的性質(zhì)
參考文獻(xiàn)
第6章  計(jì)算復(fù)雜性
6. 1  P類
6. 2  若干問題
6. 3  布爾可滿足性
6. 4  NP類
參考文獻(xiàn)
第7章  NP完全性
7. 1  多項(xiàng)式時(shí)間歸約
7. 2  Cook定理
7. 3  其他的NP完全問題
7. 4  對(duì)付NP完全性
參考文獻(xiàn)
中英對(duì)照名詞索引