Rechercher

sur ce site


Accueil du site > Résumés des séminaires > Labo > La théorie algorithmique de l’information et ses applications

La théorie algorithmique de l’information et ses applications

La théorie algorithmique de l’information propose une double définition qui permet de comprendre la notion d’objet numérique complexe. La complexité de Kolmogorov de s (taille du plus court programme qui produit s) mesure son contenu incompressible d’information, et donc une suite aléatoire s est très complexe selon cette mesure. La profondeur logique de Bennett de s (temps de calcul des programmes courts qui produisent s) est une mesure de son contenu en calcul et en conséquence de sa complexité structurelle. Dans un premier temps ces notions ont été considérées comme inutilisables. Depuis quelques années grâce aux algorithmes de compression (sans perte) on a réussi à en faire des mesures de complexité utiles permettant en particulier la classification de textes, de séquences génétiques et d’images.

CMAP UMR 7641 École Polytechnique CNRS, Route de Saclay, 91128 Palaiseau Cedex France, Tél: +33 1 69 33 46 23 Fax: +33 1 69 33 46 46