計算理論導引（第2版）

定　價：￥36.00

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

購買這本書可以去

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

內(nèi)容簡介

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

作者簡介

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

圖書目錄

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