Julien Clément (GREYC, Caen)

C’est le premier des trois exposés de présentation de l’équipe AMACC, qui organise ce séminaire ALGO; les deux autres auront lieu le 20 octobre et le 10 novembre.

Ces exposés sont particulièrement dirigés vers les étudiants de Master, et cherchent à leur expliquer les principaux domaines de recherche de l’équipe.

La thématique ‘’Structures aléatoires et analyse d’algorithmes’’ présentée dans cette première séance est centrée sur le rôle de l’Aléa en algorithmique, et notamment sur l’analyse probabiliste des algorithmes. On évoquera d’abord les grandes questions générales du domaine: Pourquoi introduire l’Aléa? Quel Aléa choisir? Quelles sont les principales méthodes d’analyse probabiliste? Quels sont les principaux domaines algorithmiques étudiés? Puis, on précisera tout cela dans deux focus: le premier expliquera comment on peut mieux comprendre les algorithmes de tri de base (enseignés en maîtrise) quand les données sont des mots et le paramètre central est le nombre de comparaisons de symboles. Le second expliquera le lien entre les algorithmes de fouille de données et les graphes et hypergraphes aléatoires.