1.

Michael Sipser

 Preface to the First Edition To the student To the educator The first edition Feedback to the author Acknowledgments Preface to the Second Edition Introduction / 0： Automata, Computability, and Complexity / 0.1： Complexity theory Computability theory Automata theory Mathematical Notions and Terminology / 0.2： Sets Sequences and tuples Functions and relations Graphs Strings and languages Boolean logic Summary of mathematical terms Definitions, Theorems, and Proofs / 0.3： Finding proofs Types of Proof / 0.4： Proof by construction Proof by contradiction Proof by induction Exercises, Problems, and Solutions Automata and Languages / Part 1： Regular Languages / 1： Finite Automata / 1.1： Formal definition of a finite automaton Examples of finite automata Formal definition of computation Designing finite automata The regular operations Nondeterminism / 1.2： Formal definition of a nondeterministic finite automaton Equivalence of NFAs and DFAs Closure under the regular operations Regular Expressions / 1.3： Formal definition of a regular expression Equivalence with finite automata Nonregular Languages / 1.4： The pumping lemma for regular languages Context-Free Languages / 2： Context-free Grammars / 2.1： Formal definition of a context-free grammar Examples of context-free grammars Designing context-free grammars Ambiguity Chomsky normal form Pushdown Automata / 2.2： Formal definition of a pushdown automaton Examples of pushdown automata Equivalence with context-free grammars Non-context-free Languages / 2.3： The pumping lemma for context-free languages Computability Theory / Part 2： The Church-Turing Thesis / 3： Turing Machines / 3.1： Formal definition of a Turing machine Examples of Turing machines Variants of Turing Machines / 3.2： Multitape Turing machines Nondeterministic Turing machines Enumerators Equivalence with other models The Definition of Algorithm / 3.3： Hilbert's problems Terminology for describing Turing machines Decidability / 4： Decidable Languages / 4.1： Decidable problems concerning regular languages Decidable problems concerning context-free languages The Halting Problem / 4.2： The diagonalization method The halting problem is undecidable A Turing-unrecognizable language Reducibility / 5： Undecidable Problems from Language Theory / 5.1： Reductions via computation histories A Simple Undecidable Problem / 5.2： Mapping Reducibility / 5.3： Computable functions Formal definition of mapping reducibility Advanced Topics in Computability Theory / 6： The Recursion Theorem / 6.1： Self-reference Terminology for the recursion theorem Applications Decidability of logical theories / 6.2： A decidable theory An undecidable theory Turing Reducibility / 6.3： A Definition of Information / 6.4： Minimal length descriptions Optimality of the definition Incompressible strings and randomness Complexity Theory / Part 3： Time Complexity / 7： Measuring Complexity / 7.1： Big-O and small-o notation Analyzing algorithms Complexity relationships among models The Class P / 7.2： Polynomial time Examples of problems in P The Class NP / 7.3： Examples of problems in NP The P versus NP question NP-completeness / 7.4： Polynomial time reducibility Definition of NP-completeness The Cook-Levin Theorem Additional NP-complete Problems / 7.5： The vertex cover problem The Hamiltonian path problem The subset sum problem Space Complexity / 8： Savitch's Theorem / 8.1： The Class PSPACE / 8.2： PSPACE-completeness / 8.3： The TQBF problem Winning strategies for games Generalized geography The Classes L and NL / 8.4： NL-completeness / 8.5： Searching in graphs NL equals coNL / 8.6： Intractability / 9： Hierarchy Theorems / 9.1： Exponential space completeness Relativization / 9.2： Limits of the diagonalization method Circuit Complexity / 9.3： Advanced topics in complexity theory / 10： Approximation Algorithms / 10.1： Probabilistic Algorithms / 10.2： The class BPP Primality Read-once branching programs Alternation / 10.3： Alternating time and space The Polynomial time hierarchy Interactive Proof Systems / 10.4： Graph nonisomorphism Definition of the model IP = PSPACE Parallel Computation / 10.5： Uniform Boolean circuits The class NC P-completeness Cryptography / 10.6： Secret keys Public-key cryptosystems One-way functions Trapdoor functions Selected Bibliography
 Preface to the First Edition To the student To the educator
2.

James L. Hein
 出版情報: Sudbury, Mass. : Jones and Bartlett Publishers, c1996  xvii, 572 p. ; 25 cm シリーズ名: Jones and Bartlett books in computer science 所蔵情報: loading…
3.

by Jiří Adámek and Věra Trnková
 出版情報: Dordrecht ; Boston : Kluwer Academic Publishers, c1990  xiv, 470 p. ; 25 cm シリーズ名: Mathematics and its applications ; . East European series ; [v. 37] 所蔵情報: loading…
4.

Gérard Weisbuch ; translated by Sylvie Ryckebusch
 出版情報: Redwood City, Calif. : Addison-Wesley, c1991  xvii, 189 p. ; 24 cm シリーズ名: Santa Fe Institute studies in the sciences of complexity ; Lecture notes ; v. 2 所蔵情報: loading…
5.

B.I. Plotkin, L.Ja. Greenglaz, A.A. Gvaramija
 出版情報: Singapore ; River Edge, N.J. : World Scientific, 1992  xiv, 280 p. ; 23 cm 所蔵情報: loading…
6.

Robert W. Floyd, Richard Beigel
 出版情報: New York : Computer Science Press, c1994  xvii, 706 p. ; 25 cm 所蔵情報: loading…

文献複写・貸借依頼