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 30 Novembre 1999

Autour de la structure de BDD

par Philippe Flajolet (INRIA Rocquencourt)

Une nouvelle célèbre de Jorge-Luis Borges décrit la bibliothèque de Babylone, si incroyablement grande qu'elle contient les oeuvres de Shakespeare dans l'ordre et a l'envers, son propre catalogue et de multiples versions légèrement fausses de son catalogue, etc. Par ailleurs, des numérologues observent que la suite 314159 apparaît en position 176451 dans le développement décimal du nombre pi.

Une classe d'objets combinatoire sera dite "vérifiant le théorème de Borges" (mots, arbres, graphes, permutations, etc) si toute famille finie de motifs apparaît avec probabilité tendant vers 1 dans un objet de grande taille. Les nombres réels, les mots, les arbres binaires de recherche, les arbres digitaux, par exemple satisfont a diverses versions quantifiables du théorème de Borges. Les méthodes de preuve sont du ressort de la combinatoire analytique.

Dans cet expose correspondant à des travaux inachevés, on tentera de montrer l'intérêt de ces phénomènes dans des contextes informatiques variés:

De nombreux problèmes ouverts subsistent ...

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