計算理論導引

內(nèi)容概要

本書是計算理論領域的經(jīng)典著作，被國外多所大學選用用為教材。本書以注重思路、深入引導為特色，系統(tǒng)地介紹計算機理論的三大主要內(nèi)容：自動機與語言、可計算性理論和計算復雜性理論。同時，對可計算性和計算復雜理論中的某些高級內(nèi)容作了重點講解。全書通過啟發(fā)性的問題、精彩的結(jié)果和待解決問題來引導讀者挑戰(zhàn)此領域中的高層次問題。新版的一大亮點是增加了更多習題、教輔資料和部分習題解答，更加有利于教學。    全書敘述由淺入深、詳略得當，重點突出，不拘泥于技術細節(jié)?？勺鳛橛嬎銠C專業(yè)高年級本科生和研究生的教材，也可作為相關專業(yè)教師和研究人員的參考書。

作者簡介

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

書籍目錄

出版者的話專家指導委員會譯者序譯者簡介第1版前言第2版前言第0章  緒論  0.1 自動機、可計算性與復雜性  0.2 數(shù)學概念和術語  0.3 定義、定理和證明  0.4 證明的類型  練習  問題  習題選解第一部分  自動機與語言  第1章 正則語言    1.1 有窮自動機    1.2 非確定性    1.3 正則表達式    1.4 非正則語言    練習    問題    習題選解  第2章 上下文無關文法    2.1 上下文無關文法概述    2.2 下推自動機    2.3 非上下文無關語言    練習    問題    習題選解第二部分  可計算性理論  第3章 丘奇-圖靈論題    3.1 圖靈機    3.2 圖靈機的變形    3.3 算法的定義    練習    問題    習題選解  第4章 可判定性    4.1 可判定性    4.2 停機問題    練習    問題    習題選解  第5章 可歸約性    5.1 語言理論中的不可判定問題    5.2 一個簡單的不可判定問題    5.3 映射可歸約性    練習    問題    習題選解  第6章 可計算性理論的高級專題    6.1 遞歸定理    6.2 邏輯理論的可判定性    6.3 圖靈可歸約性    ……第三部分  復雜性理論  第7章 時間復雜性  第8章 空間復雜性  第9章 難解性  第10章 復雜性理論高級專題參考文獻索引

媒體關注與評論

　　元昌安（教授，碩士生導師）　?。◤V西師范學院信息技術系，南寧，530001）　　我在攻讀博士學位期間曾經(jīng)認真攻讀學習《計算理論導引》，如今我又引導我的學生學習這門功課，作為雙重身份的“過來人”, 我有獨特的體會。作者Michael Sipser以其獨特的視角，綜合地描述了計算機科學理論，并以清新的筆觸、生動的語言給出了寬泛的數(shù)學原理，對一些低層次的技術細節(jié)，或通俗解釋描述，或高屋建瓴、給出思想而不陷入細節(jié)，或讓讀者自己思考取舍。閱讀完教材并修完這門課程時，感觸頗深：　　1．喚醒了久違的數(shù)學解題思路，學習能力進一步提高。我們這一代人（20世紀60年代出生），曾幾何時，捧著代數(shù)、幾何題，展開想象的翅膀、推導著一道又一道難題。但是，多年來從事計算機科學研究的經(jīng)歷，已經(jīng)讓我們當年活躍的解題思維出現(xiàn)遲鈍。正是這本教材的證明和練習，喚醒了久違的活躍的邏輯推導思維，激發(fā)起當年高考解題的斗志，又一次讓我嘗到了遇到難題愁眉不展和解決了一個難題后歡呼雀躍的滋味。一門課修完，自感不惑之年，又一次提高了學習能力?！　?．同類教材中，難度廣度均顯現(xiàn)出來。教材從自動機語言到可計算機性理論和復雜性理論，計算機軟硬件理論均給出了較有深度且嚴謹?shù)拿枋觯渲卸ɡ砝斫饧捌渥C明的難度絕不亞于任何一門代數(shù)學的課程。行內(nèi)人都知道，從事計算機科學研究的人，往往被數(shù)學界所看貶，其重要原因是，計算機科學研究的內(nèi)容所涉及的數(shù)學內(nèi)容往往較之數(shù)學界的前沿研究淺顯。但這本教材所描述的計算機理論卻向人們顯示出計算機科學研究的難度和深度，也即計算機科學技術的研究并不單純只是炒其他學科的剩飯！這讓廣大從事計算機科學理論研究的人在基礎研究領域也能挺直腰桿！　　3． 作為一門理論修養(yǎng)課，自感受益匪淺！在計算機學習的各個階段，我們都接觸了一些計算機理論知識。學完這本書，卻感覺在計算機理論的理解上產(chǎn)生了一個質(zhì)的飛躍，對許多問題知其然且知其所以然。由于作者對理論證明的獨特設計，再加上導師課堂上對作者意圖的深刻理解和堅決貫徹，使得在學習過程中，能把許多復雜問題簡單化，從而達到真正理解的目的。計算機理論修養(yǎng)的提高，直接影響著博士論文和研究論文的質(zhì)量。我周圍的同學都受到《計算機理論》的影響，論文中不斷迸發(fā)出計算機理論指導的火花，亮點不斷閃現(xiàn)?！　　　∥业捏w會或許有一點個人的情感雜于其中，但《計算理論導引》已然是一本經(jīng)典著作而為舉世所公認。如果你想讓自己的計算機理論素養(yǎng)升華，建議閱讀一下這本教材！

編輯推薦

　　《計算理論導引》（第2版）敘述由淺入深、詳略得當，重點突出，不拘泥于技術細節(jié)?？勺鳛橛嬎銠C專業(yè)高年級本科生和研究生的教材，也可作為相關專業(yè)教師和研究人員的參考書。

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    計算理論導引 PDF格式下載

---