|
|
楼主 |
发表于 2008-5-5 04:15:42
|
显示全部楼层
part2
作者：
Michael Sipser麻省理工学院应用数学系教授，计算机科学和人工智能实验室(CSAIL)成员。他从事理论计算机科学与其他数学课程的教学工作25年，目前为数学系主任。他痴迷于复杂性理论，喜欢复杂性理论的教学工作。.
本書是計算理論領域的經典著作，被國外多所大學選用爲教材。本書以注重思路、深入引導爲特色，系統地介紹計算理論的三大主要內容：自動機與語言、可計算性理論和計算複雜性理論。同時，對可計算性和計算複雜性理論中的某些高級內容作了重點講解。全書通過啓發性的問題、精彩的結果和待解决問題來引導讀者挑戰此領域中的高層次問題。新版的一大亮點是增加了更多習題、教輔資料和部分習題解答，更加有利于教學。
全書叙述由淺入深、詳略得當，重點突出，不拘泥于技術細節。可作爲計算機專業高年級本科生和研究生的教材，也可作爲相關專業教師和研究人員的參考書。
出版者的話
專家指導委員會
譯者序
譯者簡介
第1版前言
第2版前言
第0章 緒論
0.1 自動機、可計算性與複雜性
0.2 數學概念和術語
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 交互式證明系統
10.5 幷行計算
10.6 密碼學
練習
問題
習題選解
參考文獻
索引 |
|
/2 
eetop公众号
创芯大讲堂
创芯人才网
发表于 2008-5-5 04:11:22
