Introduction to the theory of computation

>> Google Books

所蔵情報QRコード

Introduction to the theory of computation / Michael Sipser

版:: 3rd ed
資料種別:: 図書
出版情報:: Boston, MA : Cengage Learning, c2013
形態:: xxii, 458 p. ; 24 cm
著者名:: Sipser, Michael
ISBN:: 9781133187790 [113318779X] (: hbk)
9788131525296 [8131525295] (: pbk)
書誌ID:: BB0978645X

子書誌情報

フルテキスト

所蔵情報

他の版・巻

書誌詳細

注記:

Includes bibliographical references and index

主題:

Computational complexity; Machine theory

言語:

英語

目次情報:

Preface to the First Edition

To the student

To the educator

The first edition

Feedback to the author

Acknowledgments

Preface to the Second Edition

Preface to the Third 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

Deterministic Context-Free Languages / 2.4：

Properties of DCFLs

Deterministic context-free grammars

Relationship of DPDAs and DCFGs

Parsing and LR(k) Grammars

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

Undecidability / 4.2：

The diagonalization method

An undecidable language

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

Exercises, Problems, arid Solutions

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

Index

Preface to the First Edition

To the student

To the educator

The first edition

Feedback to the author

Acknowledgments

続きを見る

東工大ブックレビュー

類似資料:

1 図書 Introduction to the theory of computation Sipser, Michael PWS Pub.	7 図書 Complex systems dynamics : an introduction to automata networks (: pbk) Weisbuch, G., Ryckebusch, Sylvie Addison-Wesley
2 電子ブック Introduction to the theory of computation (: electronic bk) Sipser, Michael Maruzen eBook Library	8 図書 Information, randomness & incompleteness : papers on algorithmic information theory (: pbk.) Chaitin, Gregory J. World Scientific
3 図書 Introduction to automata theory, languages, and computation (: hbk ; : student access kit ; : Pearson international ed.) Hopcroft, John E., 1939-, Motwani, Rajeev, Ullman, Jeffrey D., 1942- Pearson Addison-Wesley	9 図書 Theory of computation : an introduction Hein, James L. Jones and Bartlett Publishers
4 図書 Introduction to automata theory, languages, and computation Hopcroft, John E., 1939-, Motwani, Rajeev, Ullman, Jeffrey D., 1942- Addison-Wesley	10 図書 Programs, machines, and computation : an introduction to the theory of computing Clark, Keith L., Cowell, Don McGraw-Hill
5 図書 Introduction to automata theory, languages, and computation Hopcroft, John E., 1939-, Ullman, Jeffrey D., 1942- Addison-Wesley	11 図書 Stochastic complexity in statistical inquiry Rissanen, Jorma World Scientific
6 図書 Elements of the theory of computation (: UK) Lewis, Harry R., Papadimitriou, Christos H. Prentice-Hall, Prentice-Hall International	12 図書 Problem solving in automata, languages, and complexity Du, Dingzhu, Ko, Ker-I John Wiley & Sons