☆☆☆☆☆




點擊這裡下載

類似圖書 點擊查看全場最低價

---

內容簡介

　　《計算理論導引（原書第3版）》由計算理論領域的知名MichaelSipser所撰寫。他以獨特的視角，係統地介紹瞭計算理論的三個主要內容：自動機與語言、可計算性理論和計算復雜性理論。作者以清新的筆觸、生動的語言給齣瞭寬泛的數學原理，而沒有拘泥於某些低層次的細節。在證明之前，均有“證明思路”，幫助讀者理解數學形式下蘊涵的概念。本書可作為計算機專業高年級本科生和研究生的教材，也可作為教師和研究人員的參考書。

目錄

目錄
Introduction to the Theory of Computation,3e
齣版者的話
譯者序
第3版前言
第2版前言
第1版前言
第0章緒論
0.1自動機、可計算性與復雜性
0.1.1計算復雜性理論
0.1.2可計算性理論
0.1.3自動機理論
0.2數學概念和術語
0.2.1集閤
0.2.2序列和多元組
0.2.3函數和關係
0.2.4圖
0.2.5字符串和語言
0.2.6布爾邏輯
0.2.7數學名詞匯總
0.3定義、定理和證明
0.4證明的類型
0.4.1構造性證明
0.4.2反證法
0.4.3歸納法
練習
問題
習題選解
第一部分自動機與語言
第1章正則語言
1.1有窮自動機
1.1.1有窮自動機的形式化定義
1.1.2有窮自動機舉例
1.1.3計算的形式化定義
1.1.4設計有窮自動機
1.1.5正則運算
1.2非確定性
1.2.1非確定型有窮自動機的形式化定義
1.2.2NFA與DFA的等價性
1.2.3在正則運算下的封閉性
1.3正則錶達式
1.3.1正則錶達式的形式化定義
1.3.2與有窮自動機的等價性
1.4非正則語言
練習
問題
習題選解
第2章上下文無關文法
.......

前言/序言

　　第3版前言Introduction to the Theory of Computation,3e本版新增瞭關於確定型上下文無關語言的一節。我選擇這個主題有以下幾個原因。首先，它填補瞭我之前對自動機理論和語言處理之間的明顯空白。以前的版本介紹瞭有窮自動機以及圖靈機在確定型和非確定型上的變形，但卻隻包含瞭下推自動機的非確定型變形。因此，增加關於確定型下推自動機的討論正如同找到完成拼圖遊戲所缺的那塊。
　　其次，確定型上下文無關文法理論是LR(k)文法的基礎，同時也是自動機理論在編程語言和編譯器設計上重要且非平凡應用的基礎。這個應用將一些關鍵概念，包括確定型和非確定型有窮自動機的等價性、上下文無關文法和下推自動機之間的相互轉換，匯聚一起得到一個高效且漂亮的語法分析方法。這裏我們實現瞭理論和實踐的相互聯係。
　　最後，雖然該主題作為自動機理論一個真實的應用非常重要，但它在現有理論教科書中卻沒有得到足夠重視。我研究LR(k)文法多年但一直沒有完整理解它們如何工作，也沒有看到它們與確定型上下文無關語言理論的完美契閤。我寫作這一節旨在為理論學者和實踐者提供關於這個領域直觀而不失嚴謹的介紹，並由此對該領域做齣貢獻。需要注意的是：這一節的部分內容非常具有挑戰性，因此基礎理論課程的教師可考慮將其作為補充讀物。之後的章節不依賴於這部分內容。
　　在撰寫本版的過程中，很多人給瞭我直接或間接的幫助。我很感激兩位審閱者Christos Kapoutsis和Cem Say。他們閱讀瞭這一版新內容的初稿，並提供瞭很有價值的反饋意見。在Cengage Learning的一些人協助瞭本書的齣版工作，特彆是Alyssa Pratt和Jennifer Feltri�睪eorge。Suzanne Huizenga編輯瞭文字，ByteGraphics的Laura Segel繪製瞭新的圖片並修改瞭以前版本中的圖片。
　　感謝我在MIT的助教：Victor Chen, Andy Drucker, Michael Forbes, Elena Grigorescu, Brendan Juba, Christos Kapoutsis, Jon Kelner, Swastik Kopparty, Kevin Matulef, Amanda Redlich, Zack Remscrim, Ben Rossman, Shubhangi Saraf, Oren Weimann。他們都給予瞭我幫助，包括：討論新的問題並給齣解決方法，提齣如何讓學生理解課程內容的見解。我非常享受與這群有天賦、有熱情的年輕人一起工作。
　　我很高興收到瞭來自世界各地的郵件，非常感謝你們的建議、問題和思路。這裏有一個相關人員列錶，他們的意見對這個版本産生瞭影響：
　　Djihed Afifi, Steve Aldrich, Eirik Bakke, Suzanne Balik, Victor Bandur, Paul Beame, Elazar Birnbaum, Goutam Biswas, Rob Bittner, Marina Blanton, Rodney Bliss, Promita Chakraborty, Lewis Collier, Jonathan Deber, Simon Dexter, Matt Diephouse, Peter Dillinger, Peter Drake, Zhidian Du, Peter Fejer, Margaret Fleck, Atsushi Fujioka, Valerio Genovese, Evangelos Georgiadis, Joshua Grochow, Jerry Grossman, Andreas Guelzow, Hjalmtyr Hafsteinsson, Arthur Hall III, Cihat Imamoglu, Chinawat Isradisaikul, Kayla Jacobs, Flemming Jensen, Barbara Kaiser, Matthew Kane, Christos Kapoutsis, Ali Durlov Khan, Edwin Sze Lun Khoo, Yongwook Kim, Akash Kumar, Eleazar Leal, Zsolt Lengvarszky, Cheng�睠hung Li, Xiangdong Liang, Vladimir Lifschitz, Ryan Lortie, Jonathan Low, Nancy Lynch, Alexis Maciel, Kevin Matulef, Nelson Max, Hans�睷udolf Metz, Mladen Mik�峚, Sara Miner More, Rajagopal Nagarajan, Marvin Nakayama, Jonas Nyrup, Gregory Roberts, Ryan Romero, Santhosh Samarthyam, Cem Say, Joel Seiferas, John Sieg, Marc Smith, John Steinberger, Nuri Ta?瘙塂demir, Tamir Tassa, Mark Testa, Jesse Tjang, John Trammell, Hiroki Ueda, Jeroen Vaelen, Kurt L. Van Etten, Guillermo Vázquez, Phanisekhar Botlaguduru Venkata, Benjamin Bing�瞃i Wang, Lutz Warnke, David Warren, Thomas Watson, Joseph Wilson, David Wittenberg, Brian Wongchaowart, Kishan Yerubandi, Dai Yi。
　　最重要的是，我要感謝我的傢人——我的妻子Ina以及我們的孩子Rachel和Aaron。時光荏苒，歲月如梭，你們的愛就是一切。
　　Michael Sipser馬薩諸塞州，劍橋2012年4月第2版前言Introduction to the Theory of Computation,3e大量讀者來的電子郵件反映，第1版沒有習題解答是一個缺陷。這一版彌補瞭這一缺陷。每一章現在都增加瞭“習題選解”小節，給齣瞭該章的練習和問題中有代錶性題目的答案。給齣瞭答案的問題就不能再作為有趣的有挑戰性的傢庭作業，為彌補這一損失，又添加瞭若乾新問題。教師可以和www�眂ourse�眂om上所指定的相應地區的銷售代錶聯係，索取一份教師手冊，其中包含瞭附加的答案。
　　第2版的國際版是針對國外讀者的。盡管涵蓋瞭同樣的主題，它和標準第2版還是有所不同，並且不是用來替代標準第2版的。
　　許多讀者更喜歡學習更多的“標準”主題，比如Myhill�睳erode定理和Rice定理。通過將這些主題展示在給齣答案的問題中，我部分地采納瞭這些讀者的意見。沒有將Myhill�睳erode定理放到書本主體中是因為我認為，這門課程的目標是初步介紹而非深入研究有窮自動機。有窮自動機在這裏的角色是使學生通過研究計算的簡單形式模型，為瞭解復雜模型奠定基礎，同時為後續的主題提供方便的例子。當然，一些人希望有更全麵的內容，同時另一些人覺得應該略去所有對有窮自動機的引用（或者至少是依賴）。盡管Rice定理對於不可判定性的證明是一個有用的“工具”，第2版還是沒有將它放到書本主體中，因為一些學生可能隻是機械地使用它而沒有真正理解其作用。換用歸約來證明不可判定性，可以為學習復雜性理論中齣現的歸約做更好的準備。
　　我很感謝我的助教Ilya Baran、Sergi Elizalde、Rui Fan、Jonathan Feldman、Venkatesan Guruswami、Prahladh Harsha、Christos Kapoutsis、Julia Khodor、Adam Klivans、Kevin Matulef、Ioana Popescu、April Rasala、Sofya Raskhodnikova和Iuliu Vasilescu，他們幫助我草擬瞭若乾新問題及其答案。Ching Law、Edmond Kayi Lee和Zulfikar Ramzan也為給齣答案付齣瞭努力。感謝Victor Shoup提齣瞭一個簡潔的方法，用於修整在第1版中齣現在概率原始算法分析中的缺陷。
　　感謝Course Technology齣版社的編輯們的努力，尤其是Alyssa Pratt和Aimee Poirier。多謝Gerald Eisman、Weizhen Mao、Rupak Majumdar、Chris Umans和Christopher Wilson所做的審校。感謝Jerry Moore在編輯上的齣色工作，還有ByteGraphics的Laura Segel (lauras@bytegraphics�眂om) 精彩而又精確的圖錶再現。
　　我所收到的電子郵件數量超乎預料。收到來自這麼多地方的這麼多人的來信絕對是一種快樂。我會盡量迴復並嚮我未曾迴復者錶示歉意。我在此列齣對本書第2版提供瞭有益的建議的人，同時對所有給我來信的人錶示感謝。
　　Luca Aceto，Arash Afkanpour，Rostom Aghanian，Eric Allender，Karun Bakshi，Brad Ballinger，Ray Bartkus，Louis Barton，Arnold Beckmann，Mihir Bellare，Kevin Trent Bergeson，Matthew Berman，Rajesh Bhatt，Somenath Biswas，Lenore Blum，Mauro A�盉onatti，Paul Bondin，Nicholas Bone，Ian Bratt，Gene Browder，Doug Burke，Sam Buss，Vladimir Bychkovsky，Bruce Carneal，Soma Chaudhuri，Rong�睯aye Chen，Samir Chopra，Benny Chor，John Clausen，Allison Coates，Anne Condon，Jeffrey Considine，John J�盋rashell，Claude Crepeau，Shaun Cutts，Susheel M�盌aswani，Geoff Davis，Scott Dexter，Peter Drake，Jeff Edmonds，Yaakov Eisenberg，Kurtcebe Eroglu，Georg Essl，Alexander T�盕ader，Farzan Fallah，Faith Fich，Joseph E�盕itzgerald，Perry Fizzano，David Ford，Jeannie Fromer，Kevin Fu，Atsushi Fujioka，Michel Galley，K�盙anesan，Simson Garfinkel，Travis Gebhardt，Peymann Gohari，Ganesh Gopalakrishnan，Steven Greenberg，Larry Griffith，Jerry Grossman，Rudolf de Haan，Michael Halper，Nick Harvey，Mack Hendricks，Laurie Hiyakumoto，Steve Hockema，Michael Hoehle，Shahadat Hossain，Dave Isecke，Ghaith Issa，Raj D�盜yer，Christian Jacobi，Thomas Janzen，Mike D�盝ones，Max Kanovitch，Aaron Kaufman，Roger Khazan，Sarfraz Khurshid，Kevin Killourhy，Seungjoo Kim，Victor Kuncak，Kanata Kuroda，Suk Y�盠ee，Edward D�盠egenski，Li�瞁ei Lehman，Kong Lei，Zsolt Lengvarszky，Jeffrey Levetin，Baekjun Lim，Karen Livescu，Thomas Lasko，Stephen Louie，TzerHung Low，Wolfgang Maass，Arash Madani，Michael Manapat，Wojciech Marchewka，David M�盡artin Jr�保珹nders Martinson，Lyle McGeoch，Alberto Medina，Kurt Mehlhorn，Nihar Mehta，Albert R�盡eyer，Thomas Minka，Mariya Minkova，Daichi Mizuguchi，G�盇llen Morris Ⅲ，Damon Mosk�睞oyama，Xiaolong Mou，Paul Muir，German Muller，Donald Nelson，Gabriel Nivasch，Mary Obelnicki，Kazuo Ohta，Thomas M�監leson，Jr�保珻urtis Oliver，Owen Ozier，Rene Peralta，Alexander Perlis，Holger Petersen，Detlef Plump，Robert Prince，David Pritchard，Bina Reed，Nicholas Riley，Ronald Rivest，Robert Robinson，Christi Rockwell，Phil Rogaway，Max Rozenoer，John Rupf，Teodor Rus，Larry Ruzzo，Brian Sanders，Cem Say，Kim Schioett，Joel Seiferas，Joao Carlos Setubal，Geoff Lee Seyon，Mark Skandera，Bob Sloan，Geoff Smith，Marc L�盨mith，Stephen Smith，Alex C�盨noeren，Guy St�睤enis，Larry Stockmeyer，Radu Stoleru，David Stucki，Hisham M�盨ueyllam，Kenneth Tam，Elizabeth Thompson，Michel Toulouse，Eric Tria，Chittaranjan Tripathy，Dan Trubow，Hiroki Ueda，Giora Unger，Kurt L�盫an Etten，Jesir Vargas，Bienvenido Velez�睷ivera，Kobus Vos，Alex Vrenios，Sven Waibel，Marc Waldman，Tom Whaley，Anthony Widjaja，Sean Williams，Joseph N�盬ilson，Chris Van Wyk，Guangming Xing，Vee Voon Yee，Cheng Yongxi，Neal Young，Timothy Yuen，Kyle Yung，Jinghua Zhang，Lilla Zollei。
　　當我夜以繼日地坐在我的電腦屏幕前時，尤其要感謝我的傢人Ina、Rachel和Aaron的耐心、理解和愛。
　　Michael Sipser馬薩諸塞州，劍橋2004年12月第1版前言Introduction to the Theory of Computation,3e寫給學生歡迎使用本書！
　　將要開始學習的是重要而又引人入勝的課題：計算理論。它包括計算機硬件、軟件以及某些應用的基本數學特性。這一課程試圖迴答什麼是不能計算的，什麼是能計算的，可以算多快，要用多少存儲，以及采用什麼計算模型等。這些問題與工程實踐有著緊密的聯係，也具有純理論的一麵。
　　許多同學主動盼望學習這門課程，有些同學可能隻是為瞭完成計算機科學或者計算機工程的學位必需的理論課程學分——他們也許認為理論比較神秘、難學且用處不大。
　　通過學習，讀者會發現理論既不神秘、也不討厭，是好理解、甚至是有趣的。理論計算機科學有許多迷人而重要的思想，同時它也有許多細小的、有時甚至是乏味的細節，這些細節可能令人感到厭倦。學習任何一門新的課程都是一件艱苦的工作。但是，如果能把它適當地錶述齣來，學習就會變得容易和更愉快些。本書的一個基本目標是讓讀者接觸到計算理論中真正令人激動的方麵，而不陷入單調乏味之中。當然，對理論感興趣的唯一途徑是努力去學習並掌握它。
　　理論與實踐是密切聯係的，計算理論為實際工作者提供瞭在計算機工程中使用的理性工具。要為具體的應用設計一個新的程序設計語言嗎？本課程中關於語法的內容遲早是會有用的。要進行字符串搜索和模式匹配嗎？不要忘瞭有窮自動機和正則錶達式。遇到瞭一個看來需要比你能夠提供的計算機時間還要多的問題嗎？想一想你學過的有關NP完全性的內容。各種應用領域，如現代密碼協議，都依賴於在這裏將要學習的理論原則。
　　理論是有意義的，它嚮讀者展示瞭計算機新的、簡單的、更加優美的一麵，而通常我們把計算機看作一颱復雜的機器。最好的計算機設計和應用齣自完美的構思。一門理論課程可以提高審美意識，幫助讀者建立更加優秀的係統。
　　理論是實踐的指南，學習理論能夠擴展你的思維。計算機技術更新很快，專門的技術知識雖然今天有用，但是僅僅在幾年內就會變成過時的東西。而能力具有持久的價值，課程應該注重培養思考能力、清楚準確的錶達能力、解決問題的能力以及知道問題什麼時候還沒有解決的能力，理論能夠訓練這些能力。
　　除瞭實際的考慮，幾乎每一位使用計算機的人都想瞭解這個神奇的創造，它的能力，以及它的局限性。為瞭解答某些基本問題，在過去的30年裏，一個全新的數學分支已經確立。這裏還有一個重大問題沒有解決：如果給定大的自然數，例如有500位，能夠在閤理的時間內把它分解成素數的乘積嗎？即使使用一颱超級計算機，現今還沒人知道怎樣纔能在宇宙毀滅之前做完這件事！因子分解問題與現代密碼係統中的某些密碼有關。去尋找一個快速的因子分解方法吧，也許，讀者會因此而一舉成名！
　　寫給教師本書是計算機學科高年級本科生或研究生的計算理論入門教材。它涉及計算理論的數學論述，包括敘述和證明定理的基本技能。作者努力使本書適用於那些缺乏定理證明的基本訓練的學生，當然，有較多這種經驗的學生會學習得更輕鬆。
　　強調清楚和生動是本書敘述的一個特色，本課程對某些低層次的細節強調瞭直覺和“大的輪廓”。例如，雖然在第0章介紹瞭證明的歸納法以及其他的數學預備知識，但在後麵部分它並不是重點。關於自動機的各種構造方法的正確性，一般不 計算理論導引（原書第3版） 下載 mobi epub pdf txt 電子書

評分☆☆☆☆☆

京東摺扣太給力瞭，屯一波書，給兒子也買瞭不少，兒子很喜歡。

評分☆☆☆☆☆

還行，挺新的，經典書籍，還不錯

評分☆☆☆☆☆

很好看的書，我非常喜歡。

評分☆☆☆☆☆

書質量很好，很厚實很耐看。

評分☆☆☆☆☆

發貨快 包裝的很好 有需要還會再來

評分☆☆☆☆☆

正版！

評分☆☆☆☆☆

上課用的，比較難懂，需要有本科編譯原理的基礎，書也比較簡潔，沒有過多解釋，哎，沒基礎看起來真的很吃力。

評分☆☆☆☆☆

商品不錯，值得推薦購買

評分☆☆☆☆☆

跟評價一樣，非常好的書

類似圖書 點擊查看全場最低價

查看全網最低價