内容简介
This book—by a noted authority and educator in the field—presents computer science theory from a uniquely intuitive,"big picture"perspective.The author gounds his clear and interesting study on broad mathematical principles,not low-level technical details:proofs are presented with a "proof idea"component that reveals the comcept underlying the mathematical formalism.Similarly,algorithms are presented using prose rather than pseudocode to focus attention om the algorithms themselves,rather than om specific models. Formerly published in a Preliminary Edition,this First Edition features additional chapters on space complexity(Chapter 8),provable intractability(Chapter 9)and advanced topics in computability theory (Chapter 10).For further information,see the World Wide Web sete for the book at :http://www-math.mit.edu/~sipser/bood.html
目录
Preface To?the?student To?the?educator The?current?edition Feedback?to?the?author Acknowledgments 0?Introduction 0.?l?Automata,?Computability,?and?Complexity Complexity?theory Computability?theory Automata?theory 0.2?Mathematical?Notions?and?Terminology Sets Sequences?and?tuples Functions?and?relations Graphs Strings?and?languages Boolean?logic Summary?of?mathematical?terms O.3?Definitions,?Theorems,?and?Proofs Finding?proofs 0.4?Types?of?Proof Proof?by?construction Proof?by?contradiction Proof?by?induction Exercises?and?Problems Part?One:?Automata?and l?Regular l?.?l?Finite?Automata Formal?definition?of?a?finite?automaton Examples?of?finite?automata Formal?definition?of?computation Designing?finite?automata The?regular?operations l?.2?Nondeterminism Formal?definition?of?a?nondeterministic?finite?automaton Equivalence?of?NFAs?and?DFAs Closure?under?the?regular?operations l?.?3?Regular?expressions Formal?definition?of?a?regular?expression Equivalence?with?finite?automata l?.4?Nonregular?Languages The?pumping?lemma?for?regular?languages Exercises?and?Problems 2?Context-Free?Languages 2?.?l?Context-free?Grammars Formal?definition?of?a?context-free?grammar Examples?of?context-free?grammars Designing?context-free?grammars Ambiguity Chomsky?normal?form 2?.2?Pushdown?Automata Formal?definition?of?a?pushdown?automaton Examples?of?pushdown?automata Equivalence?with?context-free?grammars 2?.?3?Non-context-free?Languages The?pumping?lemma?for?context-free?languages Exercises?and?Problems Part?Two:?Computability?Theory 3?The?Church-Turing?Thesis 3?.?l?Turing?Machines Formal?definition?of?a?Turing?machine Examples?of?Turingmachines 3?.2?Variants?of?Turing?Machines Multitape?Turing?machines Nondeterministic?Turing?machines Enumerators Equivalence?with?other?models 3?.3?The?Definition?of?Algorithm Hilbert''s?problems Terminology?for?describing?Turing?machines Exercises?and?Problems 4?Decidability 4.?l?Decidable?Languages Decidable?problems?concerning?regular?languages Decidable?problems?concerning?context-free?languages 4.2?The?Halting?Problem The?diagonalization?method The?halting?problem?is?undecidable A?Turing-unrecognizable?language Exercises?and?Problems 5?Reducibility 5?.?l?Undecidable?Problems?from?Language?Theory Reductions?via?computation?histories 5.2?A?Simple?Undecidable?Problem 5?.?3?Mapping?Reducibility Computable?functions Formal?definition?of?mapping?reducibility Exercises?and?Problems 6?Advanced?Topics?in?Computability?Theory 6.?1?The?Recursion?Theorem Self-reference Terminology?for?the?recursion?theorem Applications 6.2?Decidability?of?logical?theories A?decidable?theory An?undecidable?theory 6.?3?Turing?Reducibility 6.4?A?Definition?of?Information Minimal?length?descriptions Optimality?of?the?definition Incompressible?Strings?and?randomness Exercises?and?Problems Part?Three:?Complexity?Theory
