Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 12 Juin 2001

La notion d'aleatoire est-elle d'essence informatique ?

par Serge Grigorieff (LIAFA, Université Paris 7)

La complexite syntaxique des programmes basee sur leur seule longueur donne lieu a une theorie, developpee par Kolmogorov en 1964, qui permet d'etablir une mesure du caractere aleatoire d'un objet fini. Dans le cas des objets infinis, Martin-Lof a introduit une effectivisation des notions de theorie de la mesure conduisant a une famille d'objets ayant toutes les proprietes permettant de les declarer aleatoires. Cette famille peut aussi se caracteriser par une variante de la complexite de Kolmogorov.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr