Gems of theoretical computer science
著者
書誌事項
Gems of theoretical computer science
Springer, c1998
- : pbk.
- タイトル別名
-
Perlen der theoretischen Informatik
- 統一タイトル
-
Perlen der theoretischen Informatik
大学図書館所蔵 件 / 全26件
-
該当する所蔵館はありません
- すべての絞り込み条件を解除する
注記
Includes bibliographical references and index
内容説明・目次
- 巻冊次
-
ISBN 9783540644255
内容説明
An introduction to important results in theoretical computer science. The "gems" are central problems and their solutions from the areas of computability, logic, circuit theory, and complexity. The text presents complete proofs in understandable form, as well as previously open problems that have found a (perhaps unexpected) solution, complex proofs from bottom drawers, probabilistic constructions, and more. There are over 240 exercises.
目次
- The priority method
- Hilbert's tenth problem
- LOOP programs
- bottom drawers for resolution proofs
- the spectral problem
- Kolmogorov complexity
- circuits for the parity function
- PAC learning
- the Berman Hartmanis conjecture
- collaborating hierarchies
- equivalence of branching programs
- Craig interpolants
- probability amplification
- interactive proof systems
- zero knowledge
- graph isomorphism
- superconcentrations
- pebble game.
- 巻冊次
-
: pbk. ISBN 9783642643521
内容説明
This book assembles some of the most important problems and solutions in theoretical computer science-from computability, logic, circuit theory, and complexity. The book presents these important results with complete proofs in an understandable form. It also presents previously open problems that have found (perhaps unexpected) solutions, and challenges the reader to pursue further active research in computer science.
目次
The Priority Method.- Hilbert's Tenth Problem.- LOOP Programs.- Bottom Drawers for Resolution Proofs.- The Spectral Problem.- Kolmogorov Complexity.- Circuits for the Parity Function.- PAC Learning.- The Berman-Hartmanis Conjecture.- Collaborating Hierarchies.- Equivalence of Branching Programs.- Craig Interpolants.- Probability Amplification.- Interactive Proof Systems.- Zero Knowledge.- Graph Isomorphism.- Superconcentrations.- Pebble Game.
「Nielsen BookData」 より
