Around Kolmogorov Complexity: Basic Notions and Results
by Alexander Shen
Publisher: arXiv.org 2015
Number of pages: 51
Description:
Algorithmic information theory studies description complexity and randomness and is now a well known field of theoretical computer science and mathematical logic. This report covers the basic notions of algorithmic information theory: Kolmogorov complexity (plain, conditional, prefix), Solomonoff universal a priori probability, notions of randomness, effective Hausdorff dimension.
Download or read it online for free here:
Download link
(300KB, PDF)
Similar books
Information Theory and Codingby John Daugman - University of Cambridge
The aims of this course are to introduce the principles and applications of information theory. The course will study how information is measured in terms of probability and entropy, and the relationships among conditional and joint entropies; etc.
(26604 views)
Quantum Information Theoryby Robert H. Schumann - arXiv
A short review of ideas in quantum information theory. Quantum mechanics is presented together with some useful tools for quantum mechanics of open systems. The treatment is pedagogical and suitable for beginning graduates in the field.
(18604 views)
Essential Coding Theoryby Venkatesan Guruswami, Atri Rudra, Madhu Sudan - University at Buffalo
Error-correcting codes are clever ways of representing data so that one can recover the original information even if parts of it are corrupted. The basic idea is to introduce redundancy so that the original information can be recovered ...
(11687 views)
A Short Course in Information Theoryby David J. C. MacKay - University of Cambridge
This text discusses the theorems of Claude Shannon, starting from the source coding theorem, and culminating in the noisy channel coding theorem. Along the way we will study simple examples of codes for data compression and error correction.
(15351 views)