計算理論導引

出版時間:2006-1  出版社:機械工業(yè)出版社  作者:塞普瑟  頁數(shù):437  
Tag標簽:無  

內(nèi)容概要

  《計算理論導引(英文版)(第2版)(新版)》由計算機理論領(lǐng)域的知名權(quán)威Michaael Sipser所撰寫。他以獨特的視角,系統(tǒng)地介紹了計算機理論的三個主要內(nèi)容:自動機與語言、可計算性理論和計算復雜性理論。約大部分內(nèi)容是基本的,同時對可計算性和計算復雜性理論中的某些高級內(nèi)容進行了重點介紹。作者以清新的筆觸、生動的語言給出了寬泛的數(shù)學原理,而沒有拘泥于某些低層次的細節(jié)。在證明之前,均有“證明思路”,幫助讀者理解數(shù)學形式下涵的概念。同樣,對于算法描述,均以直觀的文字而非偽代碼給出,從而將注意力集中于算法本身,而不是某些模型。新版根據(jù)多年來使用本書的教師和學生的建議進行了改進,并對課堂測試題進行了全面的更新,每章末均有樣例解答?!  队嬎憷碚搶бㄓ⑽陌妫ǖ?版)(新版)》可作為計算機專業(yè)高年級本科生和研究生的教材,也可作為教師和研究人員的參考書。

作者簡介

作者:(美)塞普瑟Michaael Sipser:麻省理工學院應用數(shù)學系教授,計算機科學和人工智能實驗室(CSAIL)成員。他從事理論計算機科學與其他數(shù)學課程的教學工作25年,目前為數(shù)學系主任。他癡迷于復雜性理論,喜歡復雜性理論的教學工作。

書籍目錄

Preface to the First Edition      To the student      To the educator      The first edition      Feedback to the author      AcknowledgmentsPreface to the Sceond Edition(International)  0  Introduction    0.1  Automata,CompUTABILITY,and Complexity      Complexity theory      Computability theory    0.2  Mathematical Notions and Terminology      Sets      Sequemces and tuples      Functions and relations      Graphs      Strings and languges      Boolean logic      Summary of mathematical terms    0.3  Definitions,Theorems,and Proofs      Finding proofs    0.4  Types of Proof      Proof by construction      Proof by construction      Proof by induction    Exercises,Problims,and SolutionsPart One:Automata and Languages  1  Regular Languages    1.1  Finite Automata      Formal definition of afinite automaton      Examples of finite automata      Formal definition of computation      Designign finite automata      The regular operations    1.2  Nondeteriminism      Formal definition of a nondeterministic finite automaton      Equivalence of NFAs and DFAs      Closure under the regular operations    1.3  Regular Expressions      Formal definition of a regular expression      Equivalence with finite automata    1.4  Nonregular Languages      The pumping lemma for regulan languages      Exercises,Problems,and Solutions  2  Context-Free Languages    2.1  Conetxt-free Grammars      Formal definition of a context-free grammar      Examples of context-free grammars      Designing context-free grammars      Ambiguity      Chomaky mormal form    2.2  Pushdown Automata      Formal definition of a pushdown automaton      Examples of pushdown autonata      Equivalence wish context-free grammars    2.3  Non-context-free Languages      The pumping lemma for context-free languages    Exercises,Problems,and SolutionsPart Two:Computability TheoryPart Three:Computability TheorySelected BibliographyIndex

圖書封面

圖書標簽Tags

評論、評分、閱讀與下載


    計算理論導引 PDF格式下載


用戶評論 (總計45條)

 
 

  •   這本書挺好的,對英語也有幫助
  •   Hardcover: 480 pagesPublisher: Course Technology; 3 edition (June 27, 2012)Language: EnglishISBN-10: 113318779XISBN-13: 978-1133187790
  •   純英文版的,對于形式化語言的學習有幫助
  •   內(nèi)容就不用講了 紙張也不錯
  •   英文原版,喜歡的人可以試試
  •   內(nèi)容還是不錯的,英文原版經(jīng)典,紙張一般。
  •   剛開始讀的時候還有些疑惑,怎么mit的教材如此簡單,后來才在封面上發(fā)現(xiàn)這是國際版,而且前言里說國際版不能代替標準版,看來還得看別的書才能在這方面入門。ps:真想看看美國版的是啥樣。
  •   書是正品,幫助很大,很喜歡~
  •   書是沒有一點問題,很喜歡。但是金書網(wǎng)發(fā)貨實在是太慢了,說是拍后的1-2天內(nèi)發(fā)貨,他們非要等到第2天的晚上才發(fā)貨,這也太坑爹了吧?并且,剛好我拍下的時候是凌晨1點左右,我等了足足有3天,金書網(wǎng)才發(fā)貨,發(fā)貨后物流速度也真是不敢恭維,整整4天才到,淘寶上發(fā)貨加上物流速度3天之內(nèi)就到了,這也太慢了吧?這是我買書以來等時間最長的一次,再晚幾天,課都上完了估計。。。
  •   university of colorado at colorado springs的教材,幫國外的哥們買的,剛好有人捎過去,買國內(nèi)這個授權(quán)影印版要比在國外買便宜多了。指定教材,質(zhì)量水平有保證。亞馬遜送貨及時,書本本身外面還有透明塑封保護。
  •   書有點破損,印刷質(zhì)量有點偏差
  •   不錯的書,比《計算理論基礎(chǔ)》要系統(tǒng)和全面,更生動
  •     看了好幾家都是沒貨,機械工業(yè)2006出版的這本絕版了??啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
  •     RT,英語真心一般啊,想看看有木有翻譯版本的,Introduction to the Theory of Computation,第二版,請各位大神指導一下,請告知翻譯版本的書名,出版社等信息
      RT,英語真心一般啊,想看看有木有翻譯版本的,Introduction to the Theory of Computation,第二版,請各位大神指導一下,請告知翻譯版本的書名,出版社等信息
      RT,英語真心一般啊,想看看有木有翻譯版本的,Introduction to the Theory of Computation,第二版,請各位大神指導一下,請告知翻譯版本的書名,出版社等信息
      
      導師推薦的書,肯定是經(jīng)典的書
  •     如果你周圍的人在說P, NP之類,而你還不知道這些概念,請捧起這本書!
      
      之后,如果你還想去解決它們,尋求解決思路可以參考這本Metaheuristics For Hard Optimization
      
      
  •     我覺得作者很可愛,他同很多人一樣很喜歡把一個復雜的問題說的很簡單很通俗?! τ谶@本書來說,看了第一章,就應當一成的收獲。計算機中重要的數(shù)學概念被解構(gòu)的如此清楚,非常的難得?! ×硗?,要說一下,翻譯的問題。翻譯的很不錯(話說本來英文版就很上口),但是卻是看原版會體會更深刻的意義。例如 “有限狀態(tài)自動機及其對照物馬爾可夫鏈...” 一句,顯然就不如 “finite automata and their probabilistic counterpart markov chains...”
  •     讓人了解計算機的本質(zhì),它的能力與它的局限性。
      
      計算理論課的教材,上課上的很累,但很有收獲。我覺得沒讀過這本書的不好意思說自己是Computer Science專業(yè)畢業(yè)的。
  •     事知其然而后知其所以然。
      
      現(xiàn)代計算機體系的構(gòu)建,圖靈機的數(shù)學模型的實現(xiàn),正是指出了這道創(chuàng)世紀的光。
      
      現(xiàn)在書里面的內(nèi)容已經(jīng)忘記的差不多了,只是記得不斷的證明,一步步的證明,充滿了智慧的光芒。
      
      總之,是一本好的數(shù)學書。
  •     在所有我看過的計算理論、可計算性、計算復雜度的教材中,Sipser的這本Introduction to the Theory of Computation是最適合入門的。把計算理論這么個艱深的學問講解得清晰簡潔,直觀易懂。而且涵蓋了計算理論的各個經(jīng)典內(nèi)容。作為一本introduction,真是再好不過了。
      
      計算理論這門學問,顧名思義,就是把“計算”(computation)這個抽象的現(xiàn)象作為我們的研究對象,用數(shù)學工具來分析和刻畫,并為此而建立的理論體系。
      
      全書分為三部分:自動機;可計算性;復雜度。這剛好是計算的三個不同的方面:計算的模型;計算的界限;計算的代價。自動機理論抽象的描述了什么叫“問題”,什么叫“解”,計算的機制可以有什么樣的形式??捎嬎阈躁P(guān)注的是計算的“行不行”的一面。而復雜度關(guān)注的是“好不好”的一面、也即問題的“難”和“易”。
      
      什么是計算機?什么可以被計算?什么樣的問題是難的、什么樣的問題是容易的?這些計算機科學最自然最根本的問題,是計算理論這門學問的主題,也是這本書的主題。
      
      這本書最美妙之處,并不在于它描述的那些艱深的問題和結(jié)果,而是它全面展示了計算理論中那些最引人入勝的深刻想法(idea):抽象問題(problems)的形式語言(formal languages)描述,確定性(deterministic)和非確定性(nondeterministic)的引入,對角化(diagonalization)和停機(halting)問題,歸約(reduction)的思想,完全性(completeness),relativization,alternation。
      
      這些都是計算理論中最具創(chuàng)造性的劃時代的思想。這些不僅僅是單純的研究結(jié)果,這些idea的出現(xiàn)更是影響了人類今天對計算這個現(xiàn)象的根本認識。
      
      唯一的小缺憾就是,應該在最后一章advanced topics里面,去掉parallel computation,加上communication complexity和著名的PCP (probabilistically checkable proofs)。
      
      很高興能有這么一本書,收集了這些璀璨珍珠,清楚的呈現(xiàn)給我們。
      
      
      然而,盡管我對這本書和這門學問都很推崇,我對于學習計算理論的必要性卻并不堅定。我自己喜歡這些,可我該如何向別人解釋學習它是必要的?
      
      Sipser在前言中也試圖說明這個問題:"After all, isn't theory arcane, boring, and worst of all, irrelevant?"
      他很認真的試圖從幾個方面說服學生,計算理論是“有用”的,但我總覺得這些說服很徒勞:書中的三個部分,對于搞研究的人來說,前兩個領(lǐng)域已經(jīng)或走到頭了或不再是主流研究趣味了,只有復雜度尚活躍,但也只是個理論方向之一;而對于那些有志于業(yè)界工作的學生,后兩個部分幾乎永遠不會在工作中用到,而只有第一部分的自動機,可能會用到一點點正則表達式。
      
      看來,從“有用”這個方向去為計算理論辯護,難免會遭遇尷尬和勉強。
      
      我能想到的理由就只剩兩個:
     ?。ㄒ唬┻@些是計算機科學的根本,沒有它們計算機科學不能算作是個正經(jīng)學問,因此,一個自稱計算機科學專業(yè)的人,應當知道這些。
     ?。ǘ┻@些是美好的,值得在短暫的人生中去經(jīng)歷去見識。
      
      我覺得這已是足夠的理由了。
      
  •     本書的作者是著名的計算理論方面專家,麻省理工學院應用數(shù)學系主任 M. Sipser。全書分為11章,并附有部分習題解答。全書思路清晰,由淺入深,內(nèi)容詳細,是一本零起點學習計算理論的理想教材。我是出于研究需要閱讀此書的。其中第零章簡要介紹了所需要的基本數(shù)學知識。第一到三章介紹了三種計算模型,正則語言類-有限自動機,上下文無關(guān)語言類-下推自動機,圖靈可識別語言類-圖靈機。之后,在四到六章,介紹了可計算理論。七到十章介紹了復雜性理論。由于個人需要,我詳細閱讀了本書的0、1、2、3、4、5、7章節(jié),并作了相應的習題。這些章節(jié)應該對非計算理論方向研究人員搞清計算理論的基礎(chǔ)以及時間復雜性方面的初步問題已經(jīng)足夠。我簡要閱讀了6、9、10章中的部分內(nèi)容,其中第六章是可計算理論中的高級專題,本章趣味性和難度都比較強,由于對我個人研究幫助不大,我并沒有詳細閱讀此章。第九章部分需要第八章作為基礎(chǔ)。而第十章前兩節(jié)是極其有用的,分別介紹近似算法以及概率算法,但是此處是一個大概的介紹,具體應參照另外兩本專門介紹此內(nèi)容的書籍。第8章空間復雜度由于在應用當中并沒有多少人關(guān)注,所以我并沒有閱讀??傮w來講本書應該是有志從事計算機科研方面的必備教材,我對此書的閱讀至此告一段落,也許以后對于某些概念的精確定義我還會重新翻開此書。
      12/29 2007
  •   是否需要很好的基礎(chǔ)?
  •   我覺得不需要什么特別的基礎(chǔ),我當時是為了“反問題”那門課看的。之前也只是本科學的那點數(shù)學底子。
  •   謝謝。:)
  •   counterpart這個詞確實不好翻譯
  •   目測,學長被廖士忠虐過。
  •   en 想當初我考的可是很高的
  •   同樣也是計算理論的兩本參考書之一。另一本是Elements of the Theory of Computation
  •   感覺有趣算不算一個理由?當然,也許并非所有人都會覺得有趣,我只是說,也許很多人會覺得TCS有趣。顯然,能感覺出美來,那是更深層次的收獲。
  •   同意樓上的,我以后可能不會搞計算理論,但看一看這方面的問題是一種快樂,這對我來說是最好的理由
  •   宋公說:學習TCS是為了體會美和偉大
  •   計算理論確實很有趣,喜歡數(shù)學的人應該都會喜歡的
  •   (二)這些是美好的,值得在短暫的人生中去經(jīng)歷去見識。
    同意!
    這個世界上有很多美麗的東西,然而很多時候這些美麗需要一定的基礎(chǔ)去理解。難得這生做與計算機科學有關(guān)的事情,過寶山而不入就太遺憾了(這個比喻可能不恰當,原諒我的詞匯貧乏).
  •   悲劇的是只有寥寥幾人評分
  •   只能說lz對計算理論的理解還是比較深刻的
  •   做了大量計算機的應用后,不了解根的人很多很多.想了解,才發(fā)現(xiàn)時這么的難找資料.得找數(shù)學系的人.聊聊才行.
  •   正在學這門課程,感覺挺沒意思的。不知道是自己不重視,還是老師講的不怎麼樣。。。
  •     這個世界上有很多美麗的東西,然而很多時候這些美麗需要一定的基礎(chǔ)去理解。難得這生做與計算機科學有關(guān)的事情,過寶山而不入就太遺憾了(這個比喻可能不恰當,原諒我的詞匯貧乏).
    =======================
    講的太好了
  •   這個課大家都知道很重要 但是上課就是聽不懂 真郁悶
  •   樓主書評寫得不錯
  •   書評很棒,其實只要是理論方面,都是很美的,都值得去見識
  •   除了紙張不好,內(nèi)容非常不錯的。
    然而,機工的影印版是國際版,個人認為可以作為興趣讀物和導論教材。若要深入了解計算理論或應付考試,還是推薦Hopcroft的自動機。
  •   我的想法和LZ一樣,覺得這些知識是“有必要”了解的,至于為什么有必要?它就是有必要……
    看書的時候?qū)φ罩瞥=芙淌诘腜PT看,感覺作者和譯者都是樂之者,另外這本書思路先行的寫法真的是very nice,多么復雜神奇的證明都是娓娓道來
  •   理解是最大的快樂。
  •   “研究走到頭”不說明不要去了解去學習。九九乘法口訣也走到頭了,但小學生照樣要學,因為這是基礎(chǔ)。這個是計算機的基本理論,一定要去“研究”沒有必要,但作為一門專業(yè)課程去“學習”還是很有必要的。
  •   2009-04-14 13:45:45 azalea
    計算理論確實很有趣,喜歡數(shù)學的人應該都會喜歡的
    2010-10-14 13:48:22 hello
    正在學這門課程,感覺挺沒意思的。不知道是自己不重視,還是老師講的不怎麼樣。。。
    ===================
    只能說人和人差異很大。
 

250萬本中文圖書簡介、評論、評分,PDF格式免費下載。 第一圖書網(wǎng) 手機版

京ICP備13047387號-7