Print

Résumés des exposés scientifiques

10h-10h50 : Frédérique Bassino, Laboratoire d'Informatique de l’université Paris-Nord (LIPN)

Titre : Énumération asymptotique d'automates finis

Résumé : Cet exposé portera sur l'énumération d'automates finis. Les automates peuvent être vus comme des graphes orientés dont les arêtes sont étiquetées sur un alphabet fini et dont deux sous-ensembles de sommets sont distingués (l'ensemble respectivement des états initiaux et des états terminaux). Les automates (resp. minimaux) constituent une représentation (resp. canonique) des langages rationnels et de ce fait jouent un rôle important en informatique.
Nous présenterons des résultats concernant l'énumération des automates déterministes et accessibles, i. e. dans lesquels tout état peut-être atteint par un chemin partant de l'unique état initial. Nous déterminerons ensuite précisément la proportion asymptotique d'automates minimaux parmi les automates déterministes accessibles et complets. Ces résultats ont des conséquences en terme de complexité en moyenne d'algorithmes.
Toutes ces estimations peuvent être obtenues grâce à une interprétation combinatoire des propriétés structurelles des automates et à des bijections qui permettent de se ramener à l'étude combinatoire de tableaux particuliers.
Nous conclurons en présentant quelques problèmes ouverts.
Cet exposé s'appuie sur une série de travaux communs avec Julien David, Cyril Nicaud et Andrea Sportiello.

Transparents

11h-11h50 : Bruno Salvy, Laboratoire de l'Informatique du Parallélisme (LIP, INRIA) – ENS Lyon

Titre : Variations algorithmiques sur les équations différentielles linéaires

Résumé : Depuis une vingtaine d'années, le calcul formel a beaucoup progressé dans l'algorithmisation des mathématiques. De nombreuses suites et fonctions spéciales utiles en mathématiques appliquées et en combinatoire sont ainsi devenues manipulables efficacement et de manière fiable. Nous montrerons quelques idées simples et fécondes qui ont mené à un ensemble de progrès récents dans ce domaine.

Transparents

14h-14h50 : Gilles Schaeffer, Laboratoire d'Informatique de l'École polytechnique (LIX, CNRS)

Titre : Arbres et cartes combinatoires : de l'énumération au codage compact

Résumé : Depuis des années les belles propriétés énumératives des cartes planaires passionnent des combinatoristes de Bordeaux et d'ailleurs. Je raconterai une (petite) partie de cette histoire et en particulier comment le fait de comprendre bijectivement une jolie formule peut conduire à des algorithmes de codage compact.

Transparents