close
1.

図書

図書
Chander Dhawan
出版情報: New York : McGraw-Hill, c1997  xxxiii, 579 p. ; 24 cm
シリーズ名: McGraw-Hill series on computer communications
所蔵情報: loading…
2.

図書

図書
吉村善太郎編
出版情報: 東京 : 雄松堂出版, 1997.7  vii, 332p ; 22cm
シリーズ名: 雄松堂ライブラリー・リサーチ・シリーズ ; 3
所蔵情報: loading…
3.

図書

図書
飯田幸郷著
出版情報: 東京 : 発明協会, c1997  277p ; 21cm
所蔵情報: loading…
4.

図書

図書
Jorge Angeles
出版情報: Berlin ; New York : Springer, c1997  xix, 510 p. ; 24 cm
シリーズ名: Mechanical engineering series
所蔵情報: loading…
5.

図書

図書
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
6.

学位論文

学位
Herman
出版情報: 東京 : 東京工業大学, 1997
所蔵情報: loading…
7.

学位論文

学位
Suguru Shimizu
出版情報: 東京 : 東京工業大学, 1997
所蔵情報: loading…
8.

学位論文

学位
Xu Weigang
出版情報: 東京 : 東京工業大学, 1997
所蔵情報: loading…
9.

学位論文

学位
Keun-Hong Park
出版情報: 東京 : 東京工業大学, 1997
所蔵情報: loading…
10.

学位論文

学位
Hua Jiang
出版情報: 東京 : 東京工業大学, 1997
所蔵情報: loading…
文献の複写および貸借の依頼を行う
 文献複写・貸借依頼