"Théorie algorithmique de l'information" par le Professeur Jean-Paul Delahaye

Professeur Jean-Paul Delahaye, Laboratoire d’Informatique Fonda- mentale de Lille, Université des Sciences et Technologies de Lille.

La théorie de la calculabilité propose une définition de la complexité des objets numériques : la complexité de Kolmogorov (introduite en 1965). Celle-ci est une mesure du « contenu incompressible d’information », mais ne doit être conçue comme une mesure de la « richesse en structures ou en organisation » (complexité structurelle), qui serait mathématiquement définie par la profondeur logique de Bennett (introduite en 1977). Les applications de la complexité de Kolmogorov (par le biais des algorithmes de compression de don- nées) sont maintenant nombreuses : classification de textes et de mu- siques, évaluation de la ressemblance entre séquences génétiques, comparaison d’images, repérage du plagiat, identification des spam, détection des tentatives d’intrusion dans les systèmes informatiques, etc. L’évaluation de la complexité structurelle est plus difficile en pratique, mais des progrès ont été faits récemment qui permettent d’envisager des applications comme pour la complexité de Kolmogorov.
Conférence organisée par les laboratoires LMIA - LPMT - MIPS de l’UHA.