Gbachelier: /* Table of contents */

2014-11-17T14:02:26Z

‎Table of contents

Gbachelier: /* Table of contents */

2014-11-17T14:02:01Z

‎Table of contents

Änderungen zeigen

Gbachelier: /* Abstract */

2014-11-17T13:57:50Z

‎Abstract

Gbachelier: Die Seite wurde neu angelegt: „ == Reference == Li, M., Vitányi, P.: An Introduction To Kolmogorov Complexity and its Applications. 3nd edn. Springer, New York (2008). == DOI == http://ww…“

2014-11-17T13:57:21Z

Die Seite wurde neu angelegt: „ == Reference == Li, M., Vitányi, P.: An Introduction To Kolmogorov Complexity and its Applications. 3nd edn. Springer, New York (2008). == DOI == http://ww…“

Neue Seite

== Reference ==
Li, M., Vitányi, P.: An Introduction To Kolmogorov Complexity and its Applications. 3nd edn. Springer, New York (2008).

== DOI ==
http://www.springer.com/mathematics/applications/book/978-0-387-33998-6

== Abstract ==

Develops Kolmogorov theory in detail and outlines the wide range of illustrative applications
Presents recent, major results in the field: topics include Omega numbers, Kolmogorov-Loveland randomness, universal learning, communication complexity, Kolmogorov's random graphs, time-limited universal distribution, and Shannon information
Introduces results from prominent researchers in the field, such as those found by Slaman-Kucera, Downey, Hirschfeldt, Nies, Solovay, Miller and many more
Includes applications to hierarchical clustering, phylogeny in genomics, classification of music, Google, and the World Wide Web
Additional exercises on new results
Improved sections on high-probability properties and Kolmogorov’s structure function, information distance

This ongoing bestseller, now in its third edition, is considered the standard reference on Kolmogorov complexity, a modern theory of information that is concerned with information in individual objects.

New key features and topics in the 3rd edition:

* New results on randomness

* Kolmogorov's structure function, model selection, and MDL

* Incompressibility method: counting unlabeled graphs, Shellsort, communication complexity

* Derandomization

* Kolmogorov complexity versus Shannon information, rate distortion, lossy compression, denoising

* Theoretical results on information distance

* The similarity metric with applications to genomics, phylogeny, clustering, classification, semantic meaning, question-answer systems

*Quantum Kolmogorov complexity

Written by two experts in the field, this book is ideal for advanced undergraduate students, graduate students, and researchers in all fields of science. It is self-contained: it contains the basic requirements from mathematics, probability theory, statistics, information theory, and computer science. Included are history, theory, new developments, a wide range of applications, numerous (new) problem sets, comments, source references, and hints to solutions of problems. This is the only comprehensive treatment of the central ideas of Kolmogorov complexity and their applications.

== Extended Abstract ==

== Reviews==

== Bibtex ==

== Table of contents ==
Preface to the First Edition . . . . . . . . . . . . . . . . . . . . vii
Preface to the Second Edition . . . . . . . . . . . . . . . . . . xi
Preface to the Third Edition . . . . . . . . . . . . . . . . . . . xii
How to Use This Book . . . . . . . . . . . . . . . . . . . . . . xii
Outlines of One-Semester Courses . . . . . . . . . . . . . . . . xv
Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . xxi
1 Preliminaries
1
1.1 A Brief Introduction . . . . . . . . . . . . . . . . . . . . . 1
1.2 Prerequisites and Notation . . . . . . . . . . . . . . . . . 7
1.3 Numbers and Combinatorics . . . . . . . . . . . . . . . . 8
1.4 Binary Strings . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5 Asymptotic Notation . . . . . . . . . . . . . . . . . . . . 15
1.6 Basics of Probability Theory . . . . . . . . . . . . . . . . 18
1.7 Basics of Computability Theory . . . . . . . . . . . . . . 24
1.8 The Roots of Kolmogorov Complexity . . . . . . . . . . . 47
1.9 Randomness . . . . . . . . . . . . . . . . . . . . . . . . . 49
1.10 Prediction and Probability . . . . . . . . . . . . . . . . . 59
xviii
Contents
1.11 Information Theory and Coding . . . . . . . . . . . . . . 65
1.12 State × Symbol Complexity . . . . . . . . . . . . . . . . 90
1.13 History and References . . . . . . . . . . . . . . . . . . .
2 Algorithmic Complexity
92
101
2.1 The Invariance Theorem . . . . . . . . . . . . . . . . . . 104
2.2 Incompressibility . . . . . . . . . . . . . . . . . . . . . . . 116
2.3 C as an Integer Function . . . . . . . . . . . . . . . . . . 126
2.4 Random Finite Sequences . . . . . . . . . . . . . . . . . . 133
2.5 *Random Infinite Sequences . . . . . . . . . . . . . . . . 143
2.6 Statistical Properties of Finite Sequences . . . . . . . . . 165
2.7 Algorithmic Properties of C
2.8 Algorithmic Information Theory . . . . . . . . . . . . . . 186
2.9 History and References . . . . . . . . . . . . . . . . . . . 192
. . . . . . . . . . . . . . . . 174
3 Algorithmic Prefix Complexity
197
3.1 The Invariance Theorem . . . . . . . . . . . . . . . . . . 200
3.2 *Sizes of the Constants . . . . . . . . . . . . . . . . . . . 206
3.3 Incompressibility . . . . . . . . . . . . . . . . . . . . . . . 211
3.4 K as an Integer Function . . . . . . . . . . . . . . . . . . 216
3.5 Random Finite Sequences . . . . . . . . . . . . . . . . . . 218
3.6 *Random Infinite Sequences . . . . . . . . . . . . . . . . 220
3.7 Algorithmic Properties of K . . . . . . . . . . . . . . . . 239
3.8 *Complexity of Complexity . . . . . . . . . . . . . . . . . 241
3.9 *Symmetry of Algorithmic Information . . . . . . . . . . 244
3.10 History and References . . . . . . . . . . . . . . . . . . . 255
4 Algorithmic Probability
259
4.1 Semicomputable Functions Revisited . . . . . . . . . . . . 260
4.2 Measure Theory . . . . . . . . . . . . . . . . . . . . . . . 262
4.3 Discrete Sample Space . . . . . . . . . . . . . . . . . . . . 265
4.4 Universal Average-Case Complexity . . . . . . . . . . . . 290
4.5 Continuous Sample Space . . . . . . . . . . . . . . . . . . 294
4.6 Universal Average-Case Complexity, Continued . . . . . . 330
4.7 History and References . . . . . . . . . . . . . . . . . . . 331
Contents
5 Inductive Reasoning
xix
339
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 339
5.2 Solomonoff’s Theory of Prediction . . . . . . . . . . . . . 348
5.3 Simple Pac-Learning . . . . . . . . . . . . . . . . . . . . . 370
5.4 Hypothesis Identification by MDL . . . . . . . . . . . . . 382
5.5 Nonprobabilistic Statistics . . . . . . . . . . . . . . . . . 401
5.6 History and References . . . . . . . . . . . . . . . . . . . 431
6 The Incompressibility Method
441
6.1 Three Examples . . . . . . . . . . . . . . . . . . . . . . . 442
6.2 High-Probability Properties . . . . . . . . . . . . . . . . . 448
6.3 Combinatorics . . . . . . . . . . . . . . . . . . . . . . . . 451
6.4 Kolmogorov Random Graphs . . . . . . . . . . . . . . . . 461
6.5 Compact Routing . . . . . . . . . . . . . . . . . . . . . . 469
6.6 Average-Case Analysis of Sorting . . . . . . . . . . . . . . 476
6.7 Longest Common Subsequence . . . . . . . . . . . . . . . 486
6.8 Formal Language Theory . . . . . . . . . . . . . . . . . . 490
6.9 Online CFL Recognition . . . . . . . . . . . . . . . . . . 497
6.10 Turing Machine Time Complexity . . . . . . . . . . . . . 502
6.11 Communication Complexity
. . . . . . . . . . . . . . . . 516
6.12 Circuit Complexity . . . . . . . . . . . . . . . . . . . . . 521
6.13 History and References . . . . . . . . . . . . . . . . . . . 524
7 Resource-Bounded Complexity
531
7.1 Mathematical Theory . . . . . . . . . . . . . . . . . . . . 532
7.2 Language Compression . . . . . . . . . . . . . . . . . . . 550
7.3 Computational Complexity . . . . . . . . . . . . . . . . . 562
7.4 Instance Complexity . . . . . . . . . . . . . . . . . . . . . 571
7.5 Kt and Universal Search . . . . . . . . . . . . . . . . . . . 577
7.6 Time-Limited Universal Distributions . . . . . . . . . . . 582
7.7 Logical Depth . . . . . . . . . . . . . . . . . . . . . . . . 589
7.8 History and References . . . . . . . . . . . . . . . . . . . 596
xx
Contents
8 Physics, Information, and Computation
601
8.1 Information Theory . . . . . . . . . . . . . . . . . . . . . 602
8.2 Reversible Computation . . . . . . . . . . . . . . . . . . . 629
8.3 Information Distance . . . . . . . . . . . . . . . . . . . . 641
8.4 Normalized Information Distance . . . . . . . . . . . . . . 660
8.5 Thermodynamics . . . . . . . . . . . . . . . . . . . . . . . 674
8.6 Entropy Revisited . . . . . . . . . . . . . . . . . . . . . . 686
8.7 Quantum Kolmogorov Complexity . . . . . . . . . . . . . 696
8.8 Compression in Nature . . . . . . . . . . . . . . . . . . . 711
8.9 History and References . . . . . . . . . . . . . . . . . . . 714
References 723
Index 765

== Links ==
=== Full Text ===
[extern file]

[[intern file]]

=== Sonstige Links ===

← Nächstältere Version		Version vom 17. November 2014, 14:02 Uhr
Zeile 64:		Zeile 64:

	1 Preliminaries		1 Preliminaries
−
−	1

	1.1 A Brief Introduction . . . . . . . . . . . . . . . . . . . . . 1		1.1 A Brief Introduction . . . . . . . . . . . . . . . . . . . . . 1

@@ Zeile 8: / Zeile 8: @@
 == Abstract ==
-    Develops Kolmogorov theory in detail and outlines the wide range of illustrative applications
+Presents recent, major results in the field: topics include Omega numbers, Kolmogorov-Loveland randomness, universal learning, communication complexity, Kolmogorov's random graphs, time-limited universal distribution, and Shannon information
-    Presents recent, major results in the field: topics include Omega numbers, Kolmogorov-Loveland randomness, universal learning, communication complexity, Kolmogorov's random graphs, time-limited universal distribution, and Shannon information
-    Introduces results from prominent researchers in the field, such as those found by Slaman-Kucera, Downey, Hirschfeldt, Nies, Solovay, Miller and many more
+Introduces results from prominent researchers in the field, such as those found by Slaman-Kucera, Downey, Hirschfeldt, Nies, Solovay, Miller and many more
-    Includes applications to hierarchical clustering, phylogeny in genomics, classification of music, Google, and the World Wide Web
-    Additional exercises on new results
+Includes applications to hierarchical clustering, phylogeny in genomics, classification of music, Google, and the World Wide Web
-    Improved sections on high-probability properties and Kolmogorov’s structure function, information distance
 This ongoing bestseller, now in its third edition, is considered the standard reference on Kolmogorov complexity, a modern theory of information that is concerned with information in individual objects.
@@ Zeile 37: / Zeile 41: @@
 Written by two experts in the field, this book is ideal for advanced undergraduate students, graduate students, and researchers in all fields of science. It is self-contained: it contains the basic requirements from mathematics, probability theory, statistics, information theory, and computer science. Included are history, theory, new developments, a wide range of applications, numerous (new) problem sets, comments, source references, and hints to solutions of problems. This is the only comprehensive treatment of the central ideas of Kolmogorov complexity and their applications.
 == Extended Abstract ==

An Introduction To Kolmogorov Complexity and its Applications - Versionsgeschichte

Gbachelier: /* Table of contents */

Gbachelier: /* Table of contents */

Gbachelier: /* Abstract */

Gbachelier: Die Seite wurde neu angelegt: „ == Reference == Li, M., Vitányi, P.: An Introduction To Kolmogorov Complexity and its Applications. 3nd edn. Springer, New York (2008). == DOI == http://ww…“