Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 04 octobre 2011 à 10h30 en B311, Brigitte Vallée nous parlera de : De l'importance de la discipline des sources

Résumé : En algorithmique, on manipule très souvent des mots, notamment dans l'algorithmique du texte ; plus souvent encore, on manipule ce qu'on appelle communément des clés, notamment dans les algorithmes de tri ou de recherche, ou dans les bases de données. Dans une perspective plus réaliste, il faut vraiment considérer une clé comme une suite finie de symboles, c'est-à-dire comme un mot. On remplace alors le coût unitaire d'une comparaison entre deux clés par le coût de la comparaison entre deux mots, égal au nombre de symboles comparés. L'algorithmique générale devient alors de l'algorithmique du texte, et le processus qui produit les mots, appelé source, acquiert alors une grande importance.
Notre programme, décrit dans l'exposé, est donc le suivant :
1. Donner un sens à ce qu'on appelle une "source générale", opérer une classification des sources, en exhibant des sous-classes intéressantes, reliées notamment à des systèmes dynamiques.
2. Définir une série génératrice (de type Dirichlet) reliée canoniquement à la source et relier la classification des sources à la classification (analytique) de leurs séries de Dirichlet.
3. Exhiber une propriété importante de la source, appelée la "discipline", et, dans le cas des sources dynamiques, donner des conditions suffisantes qui entraînent la discipline.

 [Slides.pdf]


Dernière modification : mardi 27 septembre 2011 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at lipn.univ-paris13.fr