計算理論基礎（第2版）

定　價：￥29.00

作　者：	（美）劉易斯、（希）帕帕蒂米特里奧
出版社：	清華大學出版社
叢編項：	世界著名計算機教材精選
標　簽：	暫缺

購買這本書可以去

ISBN：	9787302132882	出版時間：	2006-07-01	包裝：	平裝
開本：	16開	頁數(shù)：	244	字數(shù)：

內容簡介

　　計算理論是計算機科學的理論基礎。本書介紹了計算理論最核心、最基本的內容，包括形式語言與自動機、可計算性和計算復雜性三大部分。全書共分7章，分別為：集合、關系和語言；有窮自動機；上下文無關語言；Turing機；不可判定性；計算復雜性；NP完全性。本書突出了算法，從而使計算機專業(yè)的學生更易于接受，也更有收益。　.本書適合作為計算機專業(yè)及數(shù)學專業(yè)本科生或研究生的教材，也可供從事計算機科學的教學與研究人員參考。...

作者簡介

暫缺《計算理論基礎（第2版）》作者簡介

圖書目錄

譯者序(Ⅲ)
第一版序言(Ⅴ)
第二版序言(Ⅶ)
導言(Ⅸ)
第1章集合、關系和語言(１)
１.１集合(１)
１.2關系與函數(shù)(４)
１.３特殊類型的二元關系(７)
１.４有窮集合與無窮集合(１１)
１.５三個基本的證明技術(１３)
１.６閉包與算法(１７)
１.７字母表與語言(２５)
１.８語言的有窮表示(２９)
參考文獻(33)
第２章有窮自動機(３４)
２.１確定型有窮自動機(３４)
２.２非確定型有窮自動機(３９)
２.３有窮自動機與正則表達式(４７)
２.４正則語言與非正則語言(５４)
２.５狀態(tài)最小化(５８)
２.６關于有窮自動機的算法(６５)
參考文獻(７０)
第３章上下文無關語言(７２)
３.１上下文無關文法(７２)
３.２語法分析樹(７９)
３.３下推自動機(８３)
３.４下推自動機與上下文無關文法(８７)
３.５上下文無關語言與非上下文無關語言(９２)
３.６關于上下文無關文法的算法(９７)
３.７確定性與語法分析(１０２)
參考文獻(１１５)
第４章Ｔuring機(１１７)
４.１Ｔuring機的定義(１１７)
４.２用Ｔuring機計算(１２５)
４.3Ｔuring機的擴充(１３０)
４.４隨機存?。評ring機(１３６)
４.５非確定型Ｔuring機(１４４)
４.６文法(１４８)
４.７數(shù)值函數(shù)(１５１)
參考文獻(１５８)
第５章不可判定性(160)
５.１ChurchＴuring論題(160)
５.２通用Ｔuring機(161)
５.３停機問題(163)
５.４與Ｔuring機有關的不可判定問題(166)
５.５與文法有關的不可解問題(168)
５.６不可解的鋪磚問題(172)
５.７遞歸語言的性質(174)
參考文獻(178)
第６章計算復雜性(179)
６.１P類(179)
６.２若干問題(181)
６.３布爾可滿足性(187)
６.４NP類(190)
參考文獻(194)
第７章NP完全性(196)
７.１多項式時間歸約(196)
７.２Cook定理(202)
７.３其他的NP完全問題(207)
７.４對付NP完全性(218)
參考文獻(229)
中英對照名詞索引(231)