Gems of Theoretical Computer Science

Um unseren Shop nutzen zu können, müssen Sie Javascript in Ihrem Browser aktivieren.

Dekorationsartikel gehören nicht zum Leistungsumfang.

Sprache: Englisch

111,95 €*

inkl. MwSt.

Versandkostenfrei per Post / DHL

Lieferzeit 4-7 Werktage

Sie können kein Produkt in den Warenkorb legen, da Javascript und technisch notwendige Cookies aktiviert sein müssen.

Kategorien:

Der Artikel ist nicht in deutscher Sprache verfasst.
Die Sprache der Produktbeschreibung und Details kann in Englisch angegeben sein. Sollten Sie Verständnisprobleme haben, wenden Sie sich gerne an uns.

Beschreibung

While I was visiting Boston University during the 1996-97 academic year, I noticed a small book, written in German, on a shelf in Steve Homer's office. Curious, I borrowed it for my train ride home and began reading one of the chapters. I liked the style and format of the book so much that over the course of the next few months I frequently found myself reaching for it and working through one chapter or another. This was my introduction to Peden der Theoretischen Informatik. A few of my colleagues had also seen the book. They also found it inter esting, but most of them did not read German well enough to read more than small portions of it enjoyably. I hope that the English version will rectify this situation, and that many will enjoy (and learn from) the English version as much as I enjoyed the German version. The front matter of this book says that it has been "translated, revised, and expanded." I should perhaps say a few words about each of these tasks. In translating the book, Ihave tried as much as possible to retain the feel of the original, which is somewhat less formal and impersonal than a typical text book yet relatively concise. I certainly hope that the "pleasure of the pursuit of understanding" has not gotten lost in the translation.

Zusammenfassung

Compilation of the most glorious episodes from the annals of theoretical computer science * Over 240 fascinating exercises with elegant solutions on the centrals themes of theoretical computer science

Inhaltsverzeichnis

Fundamental Definitions and Results.- 1. The Priority Method.- 2. Hilbert's Tenth Problem.- 3. The Equivalence Problem for LOOP(l)- and LOOP(2)-Programs.- 4. The Second LBA Problem.- 5. LOGSPACE, Random Walks onGraphs, and Universal Traversal Sequences.- 6. Exponential Lower Bounds for the Length of Resolution Proofs.- 7. Spectral Problems and Descriptive Complexity Theory.- 8. Kolmogorov Complexity, the Universal Distribution, and Worst-Case vs. Average-Case.- 9. Lower Bounds via Kolmogorov Complexity.- 10. PAC-Learning and Occam's Razor.- 11. Lower Bounds for the Parity Function.- 12. The Parity Function Again.- 13. The Complexity of Craig Interpolants Ill.- 14. Equivalence Problems and Lower Bounds for Branching Programs.- 15. The Berman-Hartmanis Conjecture and Sparse Sets.- 16. Collapsing Hierarchies.- 17. Probabilistic Algorithms, Probability Amplification, and the Recycling of Random Numbers.- 18. The BP Operator and Graph Isomorphism.- 19. The BP-Operator and the Power of Counting Classes.- 20. Interactive Proofs and Zero Knowledge.- 21. IP = PSPACE.- 22. P ? NP with probability 1.- 23. Superconcentrators and the Marriage Theorem.- 24. The Pebble Game.- 25. Average-Case Complexity.- 26. Quantum Search Algorithms.- Solutions.

Erscheinungsjahr:	2011
Genre:	Informatik
Rubrik:	Naturwissenschaften & Technik
Medium:	Taschenbuch
Seiten:	336
Inhalt:	x 320 S.
ISBN-13:	9783642643521
ISBN-10:	3642643523
Sprache:	Englisch
Ausstattung / Beilage:	Paperback
Einband:	Kartoniert / Broschiert
Autor:	Schöning, Uwe Pruim, Randall J.
Übersetzung:	Pruim, R.
Auflage:	Softcover reprint of the original 1st ed. 1998
Hersteller:	Springer-Verlag GmbH Springer Berlin Heidelberg
Maße:	235 x 155 x 19 mm
Von/Mit:	Uwe Schöning (u. a.)
Erscheinungsdatum:	19.09.2011
Gewicht:	0,511 kg

Ähnliche Produkte