Kolmogorov complexity and algorithmic randomness /
xviii, 511 pages : illustrations ; 27 cm. - (Mathematical surveys and monographs ; v 220.) Content notes : Preface --
Basic notions and notation --
Introduction : What is this book about? --
1. Plain Kolmogorov complexity -
2. Complexity of pairs and conditional complexity --
3. Martin-Löf randomness --
4. A priori probability and prefix complexity --
5. Monotone complexity --
6. General scheme for complexities --
7. Shannon entropy and Kolmogorov complexity --
8. Some applications --
9. Frequency and game approaches to randomness --
10. Inequalities for entropy, complexity, and size --
11. Common information --
12. Multisource algorithmic information theory --
13. Information and logic --
14. Algorithmic statistics --
Appendix 1. Complexity and foundations of probability --
Appendix 2. Four algorithmic faces of randomness. Computational complexity. Information theory. Vereshchagin, N.,