計算理論導(dǎo)引

內(nèi)容概要

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

作者簡介

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

書籍目錄

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

媒體關(guān)注與評論

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

編輯推薦

　　《計算理論導(dǎo)引》（第2版）敘述由淺入深、詳略得當(dāng)，重點突出，不拘泥于技術(shù)細節(jié)。可作為計算機專業(yè)高年級本科生和研究生的教材，也可作為相關(guān)專業(yè)教師和研究人員的參考書。

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    計算理論導(dǎo)引 PDF格式下載

---