close
1.

図書

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

図書

図書
Michael Sipser
出版情報: Boston : PWS Pub., c1997  xv, 396 p.
所蔵情報: loading…
目次情報: 続きを見る
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…
文献の複写および貸借の依頼を行う
 文献複写・貸借依頼