Etude algorithmique et structurelle des ordre et des treillis.

______________________________________________________________

Porteurs du sujet : Laurent Beaudou et Olivier Raynaud

Une bourse de thèse MENRT est offerte dans le domaine de l’algorithmique de graphes, des structures ordonnées et des treillis au Laboratoire LIMOS, à l’Université Blaise Pascal – Clermont-Ferrand II.

Le concept de treillis apparaît sous différents noms dans la littérature en fonction du champs scientifique retenu. Ainsi on parlera aussi de familles d'ensembles fermée par intersection, de familles de Moore ou encore de systèmes de fermeture. Ce concept est utile dans de nombreux domaines des mathématiques pures et appliquées ainsi qu'en science de l'informatique. A titre d’exemple, les systèmes de fermeture apparaissent plus récemment comme un concept essentiel pour des recherche consacrées aux bases de données relationnelles, à l’analyse de données et à l’analyse formelle de concepts.

Dans le cadre de cette thèse vous étudierez des propriétés structurelles des treillis, et vous concevrez un ensemble d’outils algorithmiques pour la reconnaissances de sous-structures ou motifs particuliers et pour leur énumération/génération.

Les perspectives de ce travail sont nombreuses. A titre d’exemple citons les applications métier pour l’extraction d’information et pour la génération aléatoires de structures de treillis (via des chaines de Markov) dans le but d’alimenter les applications de tests. Citons aussi des problématiques de recherche fondamentale telle que le problème de la génération efficace d’un système de fermeture ou l’étude de la conjecture de Frankl.

Vous serez encadré par Laurent Beaudou et Olivier Raynaud au sein du Laboratoire Limos.

Le candidat devra faire état de connaissances solides en théorie des graphes, algorithmique et complexité. Le candidat devra aussi avoir des dispositions en développement pour implémenter les algorithmes conçus dans le cadre de cette thèse. Enfin, le candidat devra avoir un goût prononcé pour la recherche fondamentale.

Si vous êtes intéressé par ce sujet de recherche, merci de constituer un dossier de candidature avec :

- un C.V. ;

- les note du M2 Informatique et votre classement (rg/effectif) ;

- les note du M1 Informatique et votre classement (rg/effectif) ;

- une ou plusieurs lettres de recommandation.

et de contacter : Olivier Raynaud, Courriel : Cette adresse email est protégée contre les robots des spammeurs, vous devez activer Javascript pour la voir. , Tèl : 04 73 40 74 36.