**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

**A Short Course in Information Theory**

by

**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.

(

**9282**views)

**Information and Coding**

by

**Karl Petersen**-

**AMS**

The aim is to review the many facets of information, coding, and cryptography, including their uses throughout history and their mathematical underpinnings. Prerequisites included high-school mathematics and willingness to deal with unfamiliar ideas.

(

**1895**views)

**Entropy and Information Theory**

by

**Robert M. Gray**-

**Springer**

The book covers the theory of probabilistic information measures and application to coding theorems for information sources and noisy channels. This is an up-to-date treatment of traditional information theory emphasizing ergodic theory.

(

**12757**views)

**Data Compression Explained**

by

**Matt Mahoney**-

**mattmahoney.net**

This book is for the reader who wants to understand how data compression works, or who wants to write data compression software. Prior programming ability and some math skills will be needed. This book is intended to be self contained.

(

**6744**views)