close
1.

図書

図書
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
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…
文献の複写および貸借の依頼を行う
 文献複写・貸借依頼