計(jì)算理論基礎(chǔ)（第2版）

定　價(jià)：￥29.00

作　者：	（美）劉易斯、（希）帕帕蒂米特里奧
出版社：	清華大學(xué)出版社
叢編項(xiàng)：	世界著名計(jì)算機(jī)教材精選
標(biāo)　簽：	暫缺

購(gòu)買這本書可以去

ISBN：	9787302132882	出版時(shí)間：	2006-07-01	包裝：	平裝
開本：	16開	頁(yè)數(shù)：	244	字?jǐn)?shù)：

內(nèi)容簡(jiǎn)介

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

作者簡(jiǎn)介

暫缺《計(jì)算理論基礎(chǔ)（第2版）》作者簡(jiǎn)介

圖書目錄

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