計算理論基礎

前言

　　自《計算理論基礎》問世以來，在這15年中許多東西變了，也有許多東西沒有變。計算機科學現(xiàn)在是一門成熟得多的公認的學科，在這個計算無處不在、信息全球化和復雜性迅速增長的世界上扮演越來越重要的角色，因此有更多的理由關心它的基礎?！队嬎憷碚摶A》的作者們自己現(xiàn)在更加成熟和忙碌——這是何以這么久才出第二版的原因。我們寫第二版，是因為我們感覺到有幾處可以說得更好些，有幾處可以簡單些，還有一些可以刪掉。更重要的是，我們希望本書反映計算理論和學它的學生在這些年的進步。雖然就絕對而言現(xiàn)在教計算理論的比過去多了，但是它在計算機科學教學計劃中的相對地位，例如與算法課程相比，沒有得到加強..

內(nèi)容概要

　　計算理論是計算機科學的理論基礎?！队嬎憷碚摶A》(第2版)介紹了計算理論最核心、最基本的內(nèi)容，包括形式語言與自動機、可計算性和計算復雜性三大部分。全書共分七章，分別為：集合、關系和語言；有窮自動機；上下文無關語言； Turing機；不可判定性；計算復雜性；NP完全性?！队嬎憷碚摶A》(第2版)突出了算法，從而使計算機專業(yè)的學生更易接受，也更有收益。

書籍目錄

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

編輯推薦

　　《計算理論基礎》(第2版)適合作為計算機專業(yè)及數(shù)學專業(yè)本科生或研究生的教材，也可供從事計算機科學的教學與研究人員參考。

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    計算理論基礎 PDF格式下載

---