Algorithmic Information Theory
People
Course director
Description
Algorithmic information theory uses optimal data compression to root the con-cept of information in computation rather than probability. Arising as the mer-gence of Turing’s theory of computation and Shannon’s theory of information,algorithmic information involves many theoretical concepts like the Church-Turing thesis, prefix codes, Kolmogorov complexity, algorithmic randomness,Solomonoff’s induction and logical depth. It is also rich in applications, noto-riously by clearly expressing the incompleteness of mathematics and detachingstatistics and model selection from probabilities. Even more concrete are appli-cations to machine learning, like classification, risk analysis in generalized dataand anomaly detection. All the abovementioned concepts shall be investigatedto varying degrees of precision throughout the course.
Objectives
The key aims of the course are:
- to develop creative thought and technical abilities to solve problems;
- to convey an algorithmic-based view of statistics and data analysis in whichrandomness is defined in terms of computation and
- to appreciate the philosophical consequences of such a strong theory of in-formation, notably by modern expressions of mathematical incompleteness.
Teaching mode
In presence
Learning methods
This course explores the theory and applications of algorithmic informationvia both magistral presentations (∼10 classes) and participatory seminars (∼4classes).
Examination information
Problem sheets to hand in (50%) & presentation of a research article (50%).
Bibliography
- Cover, Thomas M., Thomas, Joy A.. Elements of information theory. 2nd ed.. Hoboken, N.J.: Wiley-Interscience, 2006.
- Hutter, Marcus.. Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability. 1st ed. 2005.. Berlin, Heidelberg :: Springer Berlin Heidelberg, 2005.
- Li, Ming, Vitányi, Paul. An introduction to Kolmogorov complexity and its applications. Fourth edition. Cham, Switzerland: Springer, 2019.
Education
- Master of Science in Informatics, Lecture, Elective, 1st year
- Master of Science in Informatics, Lecture, Elective, 2nd year
- PhD programme of the Faculty of Informatics, Lecture, Elective, 1st year