Exemples d'analyses d'algorithmes en Arithmétique, Théorie de l'Information et Fouille de Données

Introduit par Knuth dans les années 60, l'analyse d'algorithmes est un domaine de l'Informatique Mathématique qui vise à comprendre le comportement des algorithmes lorsque la taille des entrées augmente.Le plus souvent, les analyses concernent la complexité en temps ou en mémoire mais d'autres paramètres peuvent aussi être étudiés. Les analyses dans le pire et le meilleur des cas se focalisent sur les comportements extrémaux des paramètres qui correspondent généralement à des entrées pathologiques rares dans les applications. Les analyses d'algorithmes tiennent compte de toutes les entrées et attribuent un poids à chacune d'entre elles. Dans l'idéal, une entrée plus fréquente dans les applications a un poids plus important. Ainsi, les analyses décrivent plus fidèlement le comportement "typique" des algorithmes.Depuis les années 60, de nombreuses méthodes ont été proposées. Nous en utilisons deux : la Combinatoire Analytique développée en France depuis les années 80 autour de Philippe Flajolet, et l'Analyse Dynamique, développée autour de Brigitte Vallée depuis le milieu des années 90. Ces méthodes reposent sur des manipulations à la fois formelles et analytiques de séries génératrices. L'Analyse Dynamique s'appuie en plus sur des opérateurs fonctionnels issus de l'étude des systèmes dynamiques.Les algorithmes étudiés dans ce mémoire sont en lien avec trois domaines de l'informatique : les algorithmes du PGCD, la Théorie de l'Information et la Fouille de Données. Après s'être intéressés aux algorithmes calculant le PGCD de deux entiers ou polynômes, nous nous orientons maintenant vers des généralisations à la dimension supérieure. Ce mémoire présente les résultats obtenus pour deux types de généralisations possibles : les algorithmes qui calculent le PGCD de plusieurs entiers ou polynômes et les algorithmes de réduction de réseaux euclidiens. Dans le cadre de la Théorie de l'Information, nous étudions une grandeur caractéristique des sources : les taux d'entropie. Nous nous intéressons aussi à la fréquence d'une famille de motifs dans un texte produit par une source. Finalement, nous étudions la complexité d'extraire les motifs de la bordure négative en Fouille de données, ou de manière équivalente, à la complexité de générer l'hypergraphe transversal d'un hypergraphe aléatoire.Bien que les domaines et les objets abordés soient très différents, l'aléa et l'analyse d'algorithmes structurent tous les travaux présents dans ce mémoire