自動(dòng)機(jī)理論、語(yǔ)言和計(jì)算導(dǎo)論(英文版.第3版)

用戶評(píng)論 (總計(jì)35條)

•   T大貴系形式語(yǔ)言與自動(dòng)機(jī)教材~
•   學(xué)習(xí)自動(dòng)機(jī)理論的很好的書籍，強(qiáng)烈推薦中英合買
•   聽說是清華大學(xué)計(jì)算機(jī)系教材~就買來看了看，結(jié)果被其里面通俗易懂的語(yǔ)言和其原理深深的吸引，欲罷不能，不似以前的某些教科書，講的知識(shí)過于沉悶和拘于形式。這本書常常會(huì)聯(lián)系一些生活中的例子來說明某些異常難懂的理論。或許，這是美國(guó)大學(xué)教材和中國(guó)的不同吧~
•   學(xué)計(jì)算機(jī)專業(yè)的可以看看這本書，很多人本科四年念完計(jì)算機(jī)，甚至加上三年研究生，對(duì)計(jì)算機(jī)還沒有一個(gè)系統(tǒng)的理解，很多課程也沒能有效的結(jié)合到一起，最后也只是一個(gè)個(gè)散落的點(diǎn)。
•   經(jīng)典著作，書的質(zhì)量很好，支持正版
•   書發(fā)的挺快，完好
•   看著作者來歷不錯(cuò)的……具體書怎么樣還沒看，等看到了再說……
•   可以收藏，長(zhǎng)期保存
•   英文版的，非常值得去讀。Hopcroft是這方面的大師。
•   紙張一般，發(fā)貨速度挺快，，英文的，還沒看。。。
•   這印刷質(zhì)量太差了，整本書都印歪了，印的也不清楚，很模糊，紙的質(zhì)量也是不好。
•   書的紙張很薄，字跡不是特別清晰
•   適合入門且評(píng)價(jià)不錯(cuò)，價(jià)格公道送貨迅速
•   不錯(cuò)，內(nèi)容很好，印刷也很好
•   無論是綠龍, 紅龍還是最近的紫龍…打龍必備!
•   很不錯(cuò)的書，正在看。里面的題目難度也比較合適。
•   不得不看，但作為教材還是不錯(cuò)的
•   這本我看了好幾遍，是一本非常的書，我推薦給大家
•   書是經(jīng)典，但印刷質(zhì)量不好，紙質(zhì)較差。
•   這本書的質(zhì)量不錯(cuò)，而且是最新版本的，希望以后多引進(jìn)這方面的書。
•   　　 讀《Introduction to Automata Theory、Languages and Computation》（自動(dòng)機(jī)理論、語(yǔ)言和計(jì)算導(dǎo)論）時(shí)候。遇到了一個(gè)問題。這個(gè)問題是這樣的。
  　　
  　　 書在講到P與NP時(shí)，首先要給“時(shí)間復(fù)雜性”下一個(gè)定義。那就是，對(duì)于一臺(tái)圖靈機(jī)，首先要求它不論接受與否總會(huì)停機(jī)（也就是說它是一個(gè)“算法”），并且，對(duì)于全體長(zhǎng)度為n的輸入，它運(yùn)行的步數(shù)不超過T(n)。T(n)是n的多項(xiàng)式函數(shù)。這樣的話就說這臺(tái)圖靈機(jī)的時(shí)間復(fù)雜度是T(n)。它接受的那個(gè)語(yǔ)言屬于P。
  　　
  　　 但在432頁(yè)的框中，作者又說道，這個(gè)定義可以改一下：不必要求圖靈機(jī)對(duì)于任何輸入總停機(jī)，只要求它在”接受“的情況下停機(jī)，并且是在T(n)步之內(nèi)，就可以了。因?yàn)?，既然存在這個(gè)”接受“情況下的步數(shù)上限T(n)，那么我們可以構(gòu)造一臺(tái)新圖靈機(jī)：一開始這臺(tái)新圖靈機(jī)先數(shù)一下輸入有多長(zhǎng)，也就是n，然后計(jì)算T(n)，把這個(gè)上限記下來。之后新圖靈機(jī)模擬原來那臺(tái)圖靈機(jī)，每模擬一步計(jì)數(shù)加一。如果新圖靈機(jī)沒有進(jìn)入接受狀態(tài)，但是步數(shù)超了上限T(n)。由于原來那臺(tái)機(jī)器只要”接受“，就一定會(huì)在T(n)步之內(nèi)就進(jìn)入接受狀態(tài)并停機(jī)了。如此看來，現(xiàn)在已經(jīng)超了上限，原來那臺(tái)機(jī)器不可能”接受“了，那么這臺(tái)新機(jī)器就可以停機(jī)了（但不進(jìn)入接受狀態(tài)，也就是說，停機(jī)并拒絕輸入字符串）。這樣就構(gòu)造了一臺(tái)無論如何總會(huì)停機(jī)的圖靈機(jī)。這臺(tái)新機(jī)器用了附加的帶進(jìn)行計(jì)數(shù)和草稿。隨后把多帶圖靈機(jī)轉(zhuǎn)成單帶圖靈機(jī)時(shí)，運(yùn)行時(shí)間會(huì)增長(zhǎng)，但是增長(zhǎng)是多項(xiàng)式的。于是新機(jī)器是一臺(tái)多項(xiàng)式時(shí)間內(nèi)總會(huì)停機(jī)的機(jī)器。這就說明了上面說的兩種定義其實(shí)是等價(jià)的。
  　　
  　　 這時(shí)候我忽然想到一個(gè)問題。上面說對(duì)于長(zhǎng)為n的輸入在T(n)內(nèi)”接受“的圖靈機(jī)，都可以修改構(gòu)造出一臺(tái)永遠(yuǎn)停機(jī)的圖靈機(jī)。那么對(duì)于一般的圖靈機(jī)呢？對(duì)于任何圖靈機(jī)，長(zhǎng)度為n的輸入只有有有限個(gè)，其中它”接受“的輸入自然也只有有限個(gè)，”接受“的情況下圖靈機(jī)總會(huì)停機(jī)。也就是說，對(duì)于所有長(zhǎng)度為n的輸入，圖靈機(jī)”接受“的話，總存在一個(gè)的最大步數(shù)T(n)。T(n)是一個(gè)自然數(shù)到自然數(shù)的映射：任何一個(gè)n（輸入串的長(zhǎng)度），都對(duì)應(yīng)著一個(gè)T(n)（就是某臺(tái)圖靈機(jī)對(duì)于所有長(zhǎng)度n的輸入，"接受”的情況下運(yùn)行的最大步數(shù)）。這個(gè)映射也許不能寫成一個(gè)方程（一個(gè)等式），但它確實(shí)是一個(gè)映射。那么就存在一個(gè)方程 f(n)，使得對(duì)于所有n，f(n) >= T(n)。這樣用上面那段里，也就是書中432頁(yè)框里的方法，不是就可以構(gòu)造一臺(tái)永遠(yuǎn)停機(jī)的圖靈機(jī)了么？
  　　
  　　 如果上面說的成立的話，那么任何圖靈機(jī)都可以構(gòu)造一臺(tái)接受相同語(yǔ)言的總停機(jī)的圖靈機(jī)。也就是任何可被圖靈機(jī)接受的語(yǔ)言，都可以構(gòu)造一臺(tái)永遠(yuǎn)停機(jī)的圖靈機(jī)接受它。也就是任何遞歸可枚舉語(yǔ)言都是遞歸語(yǔ)言。通用語(yǔ)言Lu是可判定的。對(duì)角線語(yǔ)言Ld是圖靈機(jī)可接受的?？墒沁@些都是不可能的。
  　　
  　　 上面說的構(gòu)造法必有錯(cuò)誤。后來我想出來錯(cuò)在哪兒了。就錯(cuò)在：“那么就存在一個(gè)方程 f(n)，使得對(duì)于所有n，f(n) >= T(n)” 上。這個(gè)問題就變成了：對(duì)于任意一個(gè)n -> n的映射T(n)，是否存在一個(gè) f(n)，使得對(duì)于所有n，f(n) >= T(n)。注意 f(n)是可以寫成一個(gè)等式的，而T(n)有可能寫不成，而只能寫成一對(duì)一對(duì)的映射，比如，T(1)=5,T(2)=888,T(3)=1000,T(4)=1,......無窮無盡寫下去。如果存在，上面那些矛盾就都存在。下面可以證明，這樣的f(n)，并不一定存在。
  　　
  　　 因?yàn)?，用那種構(gòu)造法，需要從n計(jì)算出上限T(n)，這個(gè)計(jì)算也是由這個(gè)新圖靈機(jī)的一部分完成的。這個(gè)“部分”可以看做是一個(gè)子程序、子圖靈機(jī)。它單拎出來也是一臺(tái)圖靈機(jī)。也就是我們說的那個(gè)在所有n上大于等于T(n)、好被我們用來計(jì)算圖靈機(jī)運(yùn)行步數(shù)上限的f(n)，必得是一個(gè)圖靈機(jī)能計(jì)算的函數(shù)。這樣我這臺(tái)新圖靈機(jī)才有能力根據(jù)輸入長(zhǎng)度計(jì)算這個(gè)上限f(n)。后面說的計(jì)數(shù)、超上限就停機(jī)等等才能做到。但是是否對(duì)于任何映射T(n)，都能找到一個(gè)“蓋過”它的、可以被圖靈機(jī)計(jì)算的f(n)呢？
  　　
  　　 不能！理由如下：全體圖靈機(jī)是可列的，其中可以用來算f(n)的圖靈機(jī)也是可列的（可列集的子集還可列），那么我們畫一個(gè)矩陣:
  　　
  　　
  　　—————— 1——2—— 3—— 4—— 5—— 6——7——8 ......
  　　 圖靈機(jī)1—— 23
  　　 圖靈機(jī)2—— —— 43
  　　 圖靈機(jī)3—— —— —— —45—— —— —— 178
  　　 圖靈機(jī)4—— —— —— —— —65
  　　 圖靈機(jī)5—— —— —— —— —— ——76
  　　 圖靈機(jī)6—— —— —— —— —— —— —— 78
  　　 ......
  　　
  　?。ㄕ?qǐng)無視那些 —— 它們只是為了把格式撐開）
  　　
  　　 這個(gè)矩陣，橫向上涵蓋所有自然數(shù)，縱向上涵蓋所有算各種f(n)的圖靈機(jī)（這些圖靈機(jī)可列）。每一個(gè)元素，就是該行的圖靈機(jī)把該列的那個(gè)自然數(shù)算成什么。比如圖中看到：圖靈機(jī)3，它計(jì)算的函數(shù)就叫f3(n)吧，把6算成178，f3(6)=178。這個(gè)矩陣對(duì)角線上的元素，就是n號(hào)圖靈機(jī)把n算成什么值。
  　　
  　　 利用對(duì)角線法，構(gòu)造一個(gè)映射T(n)，T(n)把每個(gè)n，映射為比n行n列對(duì)角線交點(diǎn)上那個(gè)值大1的值。比如T(3)=46（比 3 行 3 列上的 45 大 1）。這個(gè)映射T(n)是存在的（因?yàn)槲覀儤?gòu)造出它來了）。但是這個(gè)映射，找不到任何圖靈機(jī)可計(jì)算的f(n)，使得在所有n上，f(n)>=T(n)。因?yàn)閷?duì)于每一個(gè)f(n)，我的T(n)總在一個(gè)n上比f(wàn)(n)大（對(duì)角線上那些值）就是說是：“那么就存在一個(gè)方程 f(n)，使得對(duì)于所有n，f(n) >= T(n)”是不對(duì)的。準(zhǔn)確點(diǎn)說是對(duì)于我們?nèi)绱藰?gòu)造的T(n)，不存在一個(gè)圖靈機(jī)可計(jì)算的 f(n)，使得對(duì)于所有n，f(n)都大于等于T(n)。
  　　
  　　 不是所有的圖靈機(jī)都可以構(gòu)造一臺(tái)與它接受同樣語(yǔ)言的、且永遠(yuǎn)停機(jī)的圖靈機(jī)。那些矛盾的結(jié)論就都出不來了。
•   　　書中通過將 3SAT 問題多項(xiàng)式時(shí)間規(guī)約到獨(dú)立集問題。證明了獨(dú)立集問題是NP完全的。
  　　
  　　
  　　但他的獨(dú)立集問題IS，是這么表述的：
  　　
  　　給定一個(gè)無向圖(n個(gè)頂點(diǎn))和一個(gè)數(shù)k，問這個(gè)圖存不存在k個(gè)頂點(diǎn)的獨(dú)立集。
  　　
  　　這個(gè)問題是P的。因?yàn)?，?duì)于題面中給定的k，從全部n個(gè)定點(diǎn)中選出k個(gè)頂點(diǎn)的子集的個(gè)數(shù)是 c = C(n,k) = n! / (k!*(n-k)!)。這個(gè)數(shù)是n的多項(xiàng)式。挨個(gè)考察這 c 個(gè)頂點(diǎn)子集是否獨(dú)立，每次考察需要多項(xiàng)式時(shí)間。一共有多項(xiàng)式次考察，每次考察又是多項(xiàng)式時(shí)間，于是這個(gè)算法總時(shí)間是多項(xiàng)式的。
  　　
  　　也就是說，IS問題，像書中那么表述的話，是P不是NP，自然也不是NP-Complete。
  　　
  　　其實(shí)書中沒有將3SAT問題歸約成像上面陳述的那種IS問題。問題就在于上面陳述中的k，是一個(gè)與n無關(guān)的量。
  　　
  　　書中用3SAT問題中的那個(gè) 3CNF構(gòu)造出來那個(gè)圖，然后找它的獨(dú)立集，要求要找的獨(dú)立集的定點(diǎn)數(shù)不是一個(gè)與n無關(guān)的k，而是k=n/3。3CNF的每個(gè)文字一個(gè)頂點(diǎn)，每個(gè)字句三個(gè)頂點(diǎn)，出來的那個(gè)圖，要想判斷原來那個(gè)3CNF是否可滿足，就要看存不存在k=n/3個(gè)頂點(diǎn)的獨(dú)立集。
  　　
  　　如果k是n/3，那么按上面說的那個(gè)算法，需要遍歷考察的子集數(shù)就是 C(n,n/3)了，這就不是多項(xiàng)式，而是指數(shù)了。
  　　
  　　給作者（Ullman）寫了信。他說這問題早就發(fā)現(xiàn)了。
•   　　建議大家還是直接讀原著吧，不要看翻譯的了。
  　　
  　　今天看的時(shí)候，發(fā)現(xiàn)一句話很費(fèi)解，特意對(duì)比了一下：
  　　翻譯版本的41頁(yè)第二段：“重要的是注意，子集構(gòu)造是這樣一個(gè)例子：說明如何……”
  　　
  　　看了一下原文是這樣寫的（原書第二版61頁(yè)第一段）：“It is important fot us to observe the subset construction as an example of how one formally……”
  　　
  　　這種翻譯方法真是驚天地，泣鬼神啊。
  　　正確的應(yīng)該翻譯為：“重要的是（我們）應(yīng)該將子集構(gòu)造看成是如何形式化地……的一個(gè)實(shí)例。”
  　　observe something as something，這樣的句式都看不出來嗎？
•   lz你的名字難道出自“覺今是而作非”么
•   作-->昨
•   是啊 ： ）
•   哥果然有文化
•   他是說已經(jīng)出過勘誤表了, 還是在后續(xù)印次里糾正了?
•   沒有說。這影印版是第三版，好像沒有更新的版本。網(wǎng)上勘誤表里也沒有，我寫信前查過。
•   版次往往有N次印刷, 會(huì)在后續(xù)刷次勘誤, 我在另一本Sedgewick的Algorithms, 4E有過經(jīng)驗(yàn)
  不過既然勘誤表沒有, 那后續(xù)印次糾正的可能不大
•   這第2版的中文版的確很差。不過第三版換孫家骕翻譯了，應(yīng)該好很多吧
•   不幸的是，第三版譯版還是很差，感覺都像機(jī)翻的，前后翻譯風(fēng)格還不一致= =||
•   所以推薦大家還是看英文吧。
•   我去！手滑誤點(diǎn)“關(guān)鍵情節(jié)泄露”不能取消么= =？
•   確實(shí)翻譯得很差, 看了一會(huì)兒很后悔買了書. 比如105頁(yè)的"兩個(gè)正則語(yǔ)言的兩個(gè)描述是否其實(shí)定義相同語(yǔ)言的問題涉及到相當(dāng)可觀的智力技巧". 不知道多少人看了這句話會(huì)放棄中文版.

相關(guān)圖書

• 計(jì)算機(jī)導(dǎo)論
• 計(jì)算機(jī)應(yīng)用基礎(chǔ)學(xué)習(xí)指導(dǎo)與上機(jī)操作指南
• 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)
• 會(huì)展場(chǎng)館經(jīng)營(yíng)與管理
• 國(guó)際市場(chǎng)營(yíng)銷
• 國(guó)際宋代文化研討會(huì)論文集
• 100名畫：古希臘羅馬神話
• 病由心生2
• 解剖組織胚胎學(xué)
• 邃谷師友
• 從自愿到自由-近現(xiàn)代社團(tuán)組織的發(fā)展演進(jìn)
• 落花人獨(dú)立
• 追尋魯迅在南京
• 規(guī)劃引介
• 謎語(yǔ)300首
• 新東方高考英語(yǔ)真題分類閱讀200篇
• 電力系統(tǒng)概論
• 電氣控制與PLC
• 分散控制系統(tǒng)的人機(jī)交互技術(shù)
• 建筑工程測(cè)量學(xué)習(xí)指導(dǎo)與虛擬實(shí)驗(yàn)
• 信息安全技術(shù)實(shí)驗(yàn)
• 企業(yè)家戰(zhàn)略
• 東北家常菜
• 會(huì)議運(yùn)營(yíng)管理
• 明清時(shí)期云南藏緬語(yǔ)諸族關(guān)系研究