La soutenance aura lieu
le lundi 12 décembre 2011 à 14h45,
dans l'amphi S3 043 du bâtiment Sciences 3
campus 2, Université de Caen.
Pour ceux qui ne sont jamais venus, voir la page des plans d'accès.
Le jury sera constitué de :
Rapporteurs
- Mireille Bousquet-Mélou, Directrice de recherche, CNRS, Labri (Bordeaux)
- Luc Devroye, Professeur, McGill University (Montréal)
- Philippe Jacquet, Directeur de recherche (INRIA Rocquencourt)
et aussi les examinateurs
- Marie-Pierre Béal, Professeur, LIGM (Paris-Est)
- Conrado Martinez, Professeur, UPC (Barcelone)
- Brigitte Vallée, Directrice de recherche, CNRS, Greyc (Caen)
Résumé
Dans ce mémoire, j'examine différents aspects d'un objet simple mais omniprésent en informatique: la séquence de symboles (appelée selon le contexte mot ou chaîne de caractères). La notion de mot est au carrefour de domaines comme la théorie de l'information et la théorie des langages. S'il est simple, il reste fondamental: nous n'avons, au plus bas niveau, que cela à disposition puisqu'il arrive toujours un moment où une donnée doit être encodée en symboles stockables en mémoire.
La quantité d'information croissante de données mise à disposition et qu'on peut stocker, par exemple des génomes d'individus ou des documents numérisés, justifie que les algorithmes et les structures de données qui les manipulent soient optimisés. En conséquence, les besoins d'analyse se font sentir pour guider le choix et la conception des programmes qui manipulent ces données. L'analyse en moyenne est ici particulièrement adaptée puisque les données atteignent une variété et des volumes tellement importants que c'est le cas typique qui traduit le mieux la complexité et non pas le cas le pire. Cela évidemment pose le problème de la modélisation de données qui reste encore très épineux. En effet on souhaite deux choses contradictoires: un modèle au plus près des données, qui traduise vraiment leurs spécificités, mais aussi un modèle permettant de donner des résultats, c'est-à-dire de prédire les performances (et on comprend vite que le modèle doit donc rester relativement simple pour qu'il subsiste un espoir de le traiter!).
Les méthodes sont le plus souvent celles de la combinatoire analytique et font appel à un objet mathématique, les séries génératrices, pour mener les analyses à bien.
Une version provisoire du manuscrit est téléchargeable.