计算理论导引

图书标准信息

• 作者 [美]塞普瑟（Sipser M.） 著
• 出版社 机械工业出版社
• 出版时间 2006-01
• 版次 1
• ISBN 9787111173274
• 定价 49.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 437页
• 丛书 经典原版书库

【内容简介】

《计算理论导引（英文版）（第2版）（新版）》由计算机理论领域的知名权威MichaaelSipser所撰写。他以独特的视角，系统地介绍了计算机理论的三个主要内容：自动机与语言、可计算性理论和计算复杂性理论。约大部分内容是基本的，同时对可计算性和计算复杂性理论中的某些高级内容进行了重点介绍。作者以清新的笔触、生动的语言给出了宽泛的数学原理，而没有拘泥于某些低层次的细节。在证明之前，均有“证明思路”，帮助读者理解数学形式下涵的概念。同样，对于算法描述，均以直观的文字而非伪代码给出，从而将注意力集中于算法本身，而不是某些模型。新版根据多年来使用本书的教师和学生的建议进行了改进，并对课堂测试题进行了全面的更新，每章末均有样例解答。
《计算理论导引（英文版）（第2版）（新版）》可作为计算机专业高年级本科生和研究生的教材，也可作为教师和研究人员的参考书。

【作者简介】

Michaael Sipser：麻省理工学院应用数学系教授，计算机科学和人工智能实验室（CSAIL）成员。他从事理论计算机科学与其他数学课程的教学工作25年，目前为数学系主任。他痴迷于复杂性理论，喜欢复杂性理论的教学工作。

【目录】

PrefacetotheFirstEdition
Tothestudent
Totheeducator
Thefirstedition
Feedbacktotheauthor
Acknowledgments
PrefacetotheSceondEdition（International）
0Introduction
0.1Automata,CompUTABILITY,andComplexity
Complexitytheory
Computabilitytheory
0.2MathematicalNotionsandTerminology
Sets
Sequemcesandtuples
Functionsandrelations
Graphs
Stringsandlanguges
Booleanlogic
Summaryofmathematicalterms
0.3Definitions,Theorems,andProofs
Findingproofs
0.4TypesofProof
Proofbyconstruction
Proofbyconstruction
Proofbyinduction
Exercises,Problims,andSolutions

PartOne:AutomataandLanguages
1RegularLanguages
1.1FiniteAutomata
Formaldefinitionofafiniteautomaton
Examplesoffiniteautomata
Formaldefinitionofcomputation
Designignfiniteautomata
Theregularoperations
1.2Nondeteriminism
Formaldefinitionofanondeterministicfiniteautomaton
EquivalenceofNFAsandDFAs
Closureundertheregularoperations
1.3RegularExpressions
Formaldefinitionofaregularexpression
Equivalencewithfiniteautomata
1.4NonregularLanguages
Thepumpinglemmaforregulanlanguages
Exercises,Problems,andSolutions
2Context-FreeLanguages
2.1Conetxt-freeGrammars
Formaldefinitionofacontext-freegrammar
Examplesofcontext-freegrammars
Designingcontext-freegrammars
Ambiguity
Chomakymormalform
2.2PushdownAutomata
Formaldefinitionofapushdownautomaton
Examplesofpushdownautonata
Equivalencewishcontext-freegrammars
2.3Non-context-freeLanguages
Thepumpinglemmaforcontext-freelanguages
Exercises,Problems,andSolutions

PartTwo:ComputabilityTheory
PartThree:ComputabilityTheory
SelectedBibliography
Index