Théorie des espèces, génération aléatoire et itération de Newton

français

Seminar Modèles et Algorithmes Déterministes: CASYS

23/01/2014 - 09:45 Mr Bruno Salvy (ENS Lyon) Salle 1 - Tour IRMA

La théorie des espèces, fondée par Joyal en 1980 dans le langage des catégories, fournit un cadre commode pour de nombreuses questions de combinatoire. Elle permet de raisonner sur des constructions combinatoires ou de structures de données en informatique. En particulier, les constructions récursives sont gouvernées par un ``théorème des espèces implicites''. Une opération de dérivation correspond en informatique à des ``types à trous'' et permet de développer une algorithmique efficace de l'énumération, via une itération de Newton combinatoire. Les applications naturelles sont le dénombrement et la génération automatique de tests exhaustifs ou aléatoires. L'exposé ne sera pas exhaustif (ni aléatoire !), mais fournira une introduction au sujet suffisante pour entrer dans sa littérature.