Telecom Paris
Dep. Informatique & Réseaux J-L. Dessalles ← Home page November 2021 |

and | Pierre-Alexandre Murena |

Etienne Houzé |

- This course does not address the notion of "computational complexity" which measures the speed of algorithms.

Chapter 1. | Description complexity |
Complexity measured by code length.
Complexity of integers. Conditional Complexity. |

Chapter 2. | Measuring Information through compression |
Compressibility.
Language recognition through compression. Huffman codes - Complexity and frequency. Zipf’s law. "Google" distance - Meaning distance. |

Chapter 3. | Algorithmic information applied to mathematics |
Incomputability of C.
Algorithmic probability - Algorithmic Information. Randomness. Gödel’s theorem revisited. |

Chapter 4. | Machine Learning and Algorithmic Information |
Induction - Minimum Description Length (MDL).
Analogy as complexity minimization. Machine Learning and compression. |

Chapter 5. | Subjective information and simplicity (Soon available) |
Cognitive complexity.
Simplicity and coincidences. Subjective probability & subjective information. Relevance. |

Chapitre4 (complexity & ML) |

- Answers to questions during the lab sessions are recorded and evaluated.
- You will have to answer a short quiz on the last day.
- You will make a small original contribution (typically, as a continuation of a lab work question). This micro-study should emphasize the link with Kolmogorov complexity and Algorithmic Information. You are expected to choose a topic of study, and to
*do*something for this project (typically write a small program).__The topic of the project must be related to K-complexity__. - You will prepare a
**3**minute video to present your work.

- Write you report →
**Please use this template**: MSWord or LibreOffice or LaTeX - Upload it → Uploading page
- Upload your program or any relevant material → Uploading page

Your small report will describe your project and what you found (typically: 2 or 3 pages, more if there are images). Don’t forget to include:

- Your name, date and context
- The
__problem__you addressed - What you did + what you found
- A bit of theoretical reflection/extension about what you did.
- A bibliography (with weblinks)

- Chaitin, G. J. (2004). On the intelligibility of the universe and the notions of simplicity, complexity and irreducibility. In W. Hogrebe & J. Bromand (Eds.),
*Grenzen und Grenzüberschreitungen, XIX*, 517-534. Berlin: Akademie Verlag.Devine, S. D. (2014).*Algorithmic information theory: Review for physicists and natural scientists.*. - Chaitin, G. J. (2005). Meta Math! The quest for Omega. Vintage Books, ed. 2006.
- Chater, N. (1999). The search for simplicity: A fundamental cognitive principle?.
*The Quarterly Journal of Experimental Psychology*,*52*(A), 273-302. - Downey, R. G. & Hirschfeldt, D. R. (2010).
*Algorithmic randomness and complexity.*New York: Springer. - Grünwald, P. D. (2007).
*The minimum description length principle.*MIT press. - Hutter, M. (2005).
*Universal artificial intelligence: Sequential decisions based on algorithmic probability.*Berlin: Springer.Li, M. & Vitányi, P. (1993).*An introduction to Kolmogorov complexity and its applications (3rd ed.).*New York: Springer Verlag, ed. 1997. - Li, M. & Vitányi, P. (1993).
*An introduction to Kolmogorov complexity and its applications (3rd ed.).*New York: Springer Verlag, ed. 1997. - Solomonoff, R. J. (1997). The discovery of algorithmic probability.
*Journal of Computer and System Sciences*,*55*(1), 73-88. - Solomonoff, R. J. (1978). Complexity-based induction systems: Comparisons and convergence theorems.
*IEEE transactions on Information Theory*,*24*(4), 422-432. - Vitányi, P. & Li, M. (2001). Simplicity, information, Kolmogorov complexity and prediction. In A. Zellner, H. A. Keuzenkampf & M. McAleer (Eds.),
*Simplicity, inference and modelling: Keeping it sophisticatedly simple*, 135-155. Cambridge, UK: Cambridge University Press. - Zenil, H. (2013).
*A computable universe: understanding and exploring nature as computation.*World Scientific.

- Delahaye, J.-P. (1994).
*Information, complexité et hasard.*Paris: Hermès, ed. 1999. - Delahaye, J-P. (2013). Définir et mesurer la complexité : La théorie algorithmique de l’information. 1024 - Bulletin de la Société Informatique de France, 1, 35-53.
- Dessalles, J.-L. (2008).
*La pertinence et ses origines cognitives - Nouvelles théories.*Paris: Hermes Science.