計算理論導(dǎo)引（第2版）

定　價：￥36.00

作　者：	唐常杰
出版社：	機械工業(yè)
叢編項：	計算機科學(xué)叢書
標(biāo)　簽：	暫缺

購買這本書可以去

ISBN：	9787111190288	出版時間：	2006-07-01	包裝：	膠版紙
開本：	16開	頁數(shù)：	269	字?jǐn)?shù)：

內(nèi)容簡介

　　本書是計算理論領(lǐng)域的經(jīng)典著作，被國外多所大學(xué)選用為教材。本書以注重思路、深入引導(dǎo)為特色，系統(tǒng)地介紹計算理論的三大主要內(nèi)容：自動機與語言、可計算性理論和計算復(fù)雜性理論。同時，對可計算性和計算復(fù)雜性理論中的某些高級內(nèi)容作了重點講解。全書通過啟發(fā)性的問題、精彩的結(jié)果和待解決問題來引導(dǎo)讀者挑戰(zhàn)此領(lǐng)域中的高層次問題。新版的一大亮點是增加了更多習(xí)題、教輔資料和部分習(xí)題解答，更加有利于教學(xué)。.全書敘述由淺人深、詳略得當(dāng)，重點突出，不拘泥于技術(shù)細(xì)節(jié)?？勺鳛橛嬎銠C專業(yè)高年級本科生和研究生的教材，也可作為相關(guān)專業(yè)教師和研究人員的參考書。..本書由計算理論領(lǐng)域的知名權(quán)威Michael Sipser所撰寫。他以獨特的視角，系統(tǒng)地介紹了計算理論的三個主要內(nèi)容：自動機與語言、可計算性理論和計算復(fù)雜性理論。絕大部分內(nèi)容是基本的，同時對可計算性和計算復(fù)雜性理論中的某些高級內(nèi)容進(jìn)行了重點介紹。作者以清新的筆觸、生動的語言給出了寬泛的數(shù)學(xué)原理，而沒有拘泥于某些低層次的細(xì)節(jié)。在證明之前，均有“證明思路”，幫助讀者理解數(shù)學(xué)形式下蘊涵的概念。同樣，對于算法描述，均以直觀的文字而非偽代碼給出，從而將注意力集中于算法本身，而不是某些模型。新版根據(jù)多年來使用本書的教師和學(xué)生的建議進(jìn)行了改進(jìn)，并對課堂測試題進(jìn)行了全面的更新，每章末均有樣例解答。...

作者簡介

　　作者：Michael SipserMichael Sipser麻省理工學(xué)院應(yīng)用數(shù)學(xué)系教授，計算機科學(xué)和人工智能實驗室（CSAIL）成員。他從事理論計算機科學(xué)與其他數(shù)學(xué)課程的教學(xué)工作25年，目前為數(shù)學(xué)系主任。他癡迷于復(fù)雜性理論，喜歡復(fù)雜性理論的教學(xué)工作。.

圖書目錄

出版者的話
專家指導(dǎo)委員會
譯者序
譯者簡介
第1版前言
第2版前言
第0章緒論
0.1    自動機、可計算性與復(fù)雜性
0.2    數(shù)學(xué)概念和術(shù)語
0.3    定義、定理和證明
0.4    證明的類型
練習(xí)
問題
習(xí)題選解
第一部分自動機與語言
第1章正則語言
1.1    有窮自動機
1.2    非確定性
1.3    正則表達(dá)式
1.4    非正則語言
練習(xí)
問題
習(xí)題選解
第2章上下文無關(guān)文法
2.1    上下文無關(guān)文法概述
2.2    下推自動機
2.3    非上下文無關(guān)語言
練習(xí)
問題
習(xí)題選解
第二部分可計算性理論
第3章丘奇-圖靈論題
3.1    圖靈機
3.2    圖靈機的變形
3.3    算法的定義
練習(xí)
問題
習(xí)題選解
第4章可判定性
4.1    可判定語言
4.2    停機問題
練習(xí)
問題
習(xí)題選解
第5章可歸約性
5.1    語言理論中的不可判定問題
5.2    一個簡單的不可判定問題
5.3    映射可歸約性
練習(xí)
問題
習(xí)題選解
第6章可計算性理論的高級專題
6.1    遞歸定理
6.2    邏輯理論的可判定性
6.3    圖靈可歸約性
6.4    信息的定義
練習(xí)
問題
習(xí)題選解
第三部分復(fù)雜性理論
第7章時間復(fù)雜性
7.1    度量復(fù)雜性
7.2    P類
7.3    NP類
7.4    NP完全性
7.5    幾個NP完全問題
練習(xí)
問題
習(xí)題選解
第8章空間復(fù)雜性
8.1    薩維奇定理
8.2    PSPACE類
8.3    PSPACE完全性
8.4    L類和NL類
8.5    NL完全性
8.6    NL等于coNL
練習(xí)
問題
習(xí)題選解
第9章難解性
9.1    層次定理
9.2    相對化
9.3    電路復(fù)雜性
練習(xí)
問題
習(xí)題選解
第10章復(fù)雜性理論高級專題
10.1    近似算法
10.2    概率算法
10.3    交錯式
10.4    交互式證明系統(tǒng)
10.5    并行計算
10.6    密碼學(xué)
練習(xí)
問題
習(xí)題選解
參考文獻(xiàn)
索引