Computability and complexity theory
著者
書誌事項
Computability and complexity theory
（Undergraduate texts in computer science）
Springer, c2001
大学図書館所蔵 件 / 全16件
-
該当する所蔵館はありません
- すべての絞り込み条件を解除する
注記
Includes bibliographical references and index
内容説明・目次
内容説明
Intended for use in an introductory graduate course in theoretical computer science, this text contains material that should be core knowledge in the theory of computation for all graduates in computer science. It is self-contained and is best suited for a one semester course. The text starts with classical computability theory which forms the basis for complexity theory. This has the pedagogical advantage that students learn a qualitative subject before advancing to a quantitative one. Since this is a graduate course, students should have some knowledge of such topics as automata theory, formal languages, computability theory, or complexity theory.
目次
- 1. Preliminaries
- 2. Introduction to Computability
- 3. Undecidability
- 4. Introduction to Complexity Theory
- 5. Basic Results
- 6. Nondeterminism and NP-Completeness
- 7. Relative Computability
「Nielsen BookData」 より