內容簡介
計算理論導引本書系統地介紹了計算理論的三個主要內容：自動機與語言、可計算性和計算複雜性。絕大部分內容是基本的，同時對可計算性和計算複雜性理論中的某些高級內容作了重點介紹。作者以清閒的筆觸、生動的語言給出了寬泛的數學原理，而沒有拘泥於某些低層次的細節。本書可作為計算機專業高年級本科生和研究生的教材，也可作為教師和研究人員的參考書。
媒體推薦
書評
本書由計算理論領域的知名權威Michael Sipser撰寫。他以獨特的視角，綜合地描述了計算機科學理論，並以清新的筆觸，生動的語言給出了寬泛的數學原理，而並非拘泥於某些低層次的技術細節。在證明之前，均有“證明思路”，幫助讀者理解數學形式下蘊含的概念。同樣，對於算法描述，均以直觀的文字，而非偽代碼給出，從而將注意力集中於算法本身，而不是某些模型。
本書的內容包括三個部分：自動機與語言、可計算性理論和計算複雜性理論。
目錄
譯者序
前言
第1章 導引
1.1 自動機、可計算性與複雜性
1.1.1 計算複雜性理論
1.1.2 可計算性理論
1.1.3 自動機理論
1.2 數學概念和術語
1.2.1 集合
1.2.2 序列和多元組
1.2.3 函式和關係
1.2.4 圖
1.2.5 字元串和語言
1.2.6布爾邏輯.
1.2.7 數學名辭彙總
1.3 定義、定理和證明
1.4 證明的類型
1.4.1 構造性證明
1.4.2 反證法
1.4.3 歸納法
練習
問題
第一部分 自動機與語言
第2章 正則語言
2.1 有窮自動機
2.1.1 有窮自動機的形式定義
2.1.2 有窮自動機舉例
2.1.3 計算的形式定義
2.1.4 設計有窮自動機
2.1.5正則運算
2.2 非確定性
2.2.1 非確定型有窮自動機的形式定義
2.2.3 在正則運算下的封閉性
2.3 正則表達式
…………
