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 10 Novembre 2009

Une introduction à la complexité de Kolmogorov et une application à l'algorithmique

par Laurent Bienvenu (LIAFA, Paris)

Cet exposé se fera en deux parties. Dans un premier temps on présentera la notion de complexité de Kolmogorov. Cette dernière, introduite par Chaitin et Kolmogorov dans les années 1960, permet de mesure la quantité d'information contenue dans un objet fini discret (graphe, chaîne de caractères, etc), et peut être vue comme une version algorithmique de l'entropie à la Shannon. On discutera de ses principales propriétés. La seconde partie de l'exposé sera consacrée à un exemple d'application de la complexité de Kolmogorov à travers un récent résultat fondamental de Möser, qui a donné une preuve constructive du lemme local de Lovasz (un théorème central en combinatoire), présenté sous forme de problème de satisfaction de contraintes. Cette preuve est "constructive" dans la mesure où elle fait intervenir un algorithme probabiliste pour résoudre le problème de satisfaction de contraintes associé. L'algorithme en question est extrêmement concis, voire presque trivial, mais la preuve de sa correction est a priori difficile. Cependant, comme l'a montré Möser, cette preuve se trouve elle-même grandement simplifiée par l'utilisation de la complexité 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