Complexité de Kolmogorov
Cours de recherche (30h de cours, travail
sur des articles scientifiques)
Cours : Andrei Romashchenko (Andrei.Romashchenko)
Dans ce cours nous étudierons les idées centrales de complexité de
Kolmogorov : les approches différentes à la définition de quantité
d'information dans les objets individuels ; la théorie de l'information
algorithmique ; les sequences aléatoires par Martin-Löf. Puis nous
considérerons l'application de complexité de Kolmogorov dans quelques
domaines, y compris la théorie de codage, la complexité de communication,
la complexité de calculs, la combinatoire.
Bibliographie
- M.Li, P.Vitnayi, Kolmogorov Complexity and its Applications,
2nd Ed., Springer-Verlag, New York, 1997.
- A.Shen, N.Vereshchagin, Notes on Kolmogorov complexity,
ftp://ftp.mccme.ru/usrs/shen/kolmbook-e.ps.gz