1.

by Václav Pinkava
 出版情報: Cambridge, Mass. : Abacus Press, 1988  132 p. ; 25 cm 所蔵情報: loading…
2.

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
3.

[by] R.J. Nelson
 出版情報: New York : Wiley, [1967, c1968]  xii, 400 p. ; 24 cm 所蔵情報: loading…
4.

edited by Madan M. Gupta, with associate editors George N. Saridis, Brian R. Gaines
 出版情報: New York : North-Holland, c1977  xiv, 496 p. ; 24 cm 所蔵情報: loading…
5.

John E. Savage
 出版情報: New York : Wiley, c1976  xiii, 391 p. ; 24 cm 所蔵情報: loading…
6.

John von Neumann ; edited and completed by Arthur W. Burks
 出版情報: Urbana : University of Illinois Press, 1966  xix, 388 p. ; 24 cm 所蔵情報: loading…
7.

R.E. Kalman, P.L. Falb, M.A. Arbib
 出版情報: New York : McGraw-Hill, c1969  xiv, 358 p. ; 23 cm シリーズ名: International series in pure and applied mathematics 所蔵情報: loading…
8.

Azriel Rosenfeld
 出版情報: New York : Academic Press, 1979  xiii, 225 p. ; 24 cm シリーズ名: Computer science and applied mathematics 所蔵情報: loading…

文献複写・貸借依頼