Algorithmes du PGCD et Fouille de Données : le point de vue de l’analyse dynamique
Institution:
CaenDisciplines:
Directors:
Abstract EN:
This thesis deals with two main algorithmical domains : Data Mining and Arithmetical computations. In both, we are interested in the average-case analysis of algorithms, and, we adopt more precisely the dynamical analysis point of vue which is a mixed method between Analysis of Algorithms and Dynamical Systems. The Euclid algorithms compute the gcd of two numbers ; these are fundamental blocks in computer algebra, but their fine probabilistic behavior is always unknown. Thanks to Dynamical Analysis methods, recent important results have been obtained. In this thesis, we extend this approach to a precise analysis of parameters, as the binary complexity or the size of remainders. These parameters are essential for the Divide and Conquer gcd algorithm due to Knuth-Schönhage. Dynamical Analysis is also used for proven computations of spectral constants. The dynamical approach is then adapted to on polynomial Euclid algorithms even if, in this case, classical Analytic Combinatorics already applies. We also deal with Data Mining. We restrict ourselves to binary databases where the knowledge is represented by 'frequent patterns'. The number of frequent patterns is essential for analysing algorithms but experiments show that it significantly changes with the parameters of the database. Then, the worst case analysis is not meaningful in practice. In this thesis, we elucidate the average beahvior of the number of frequent patterns under a large model of databases built with eventually correlated sources.
Abstract FR:
Cette thèse aborde deux domaines de l'algorithmique: la fouille de données et l'arithmétique. Le point de vue adopté est celui de l'analyse en moyenne et, plus précisément, celui de l'analyse dynamique, qui combine des méthodes d'analyse d'algorithmes et des systèmes dynamiques. Les algorithmes de type Euclide calculent le pgcd de deux nombres ;ce sont donc des briques de base du calcul formel, mais leur comportement probabiliste fin reste encore mal connu. Tout récemment, les méthodes dynamiques ont permis des avancées significatives dans ce domaine. Nous étendons cette approche à l'analyse fine d'autres paramètres, comme la complexité binaire et la taille des restes. Ces paramètres s'avèrent essentiels pour l'analyse de l'algorithme de type diviser pour régner introduit par Knuth et Schönhage. Nous utilisons également l'analyse dynamique dans le calcul prouvé de grandeurs spectrales. L'approche dynamique s'adapte aussi à l'algorithme d'Euclide sur les polynômes, même si, dans ce cas, les méthodes de la combinatoire analytique classique s'appliquent déjà. Nous abordons également la fouille de données. Nous nous limitons à des bases de données binaires où la connaissance se représente sous forme de 'motifs fréquents'. Le nombre de ces motifs est un paramètre essentiel pour les algorithmes. D'après les expérimentations, il varieconsidérablement selon les paramètres de la base, et l'analyse dans le pire des cas n'est donc pas significative en pratique. Dans cette thèse, nous élucidons le comportement moyen du nombre de motifs fréquents dans un modèle très général, où les bases sont construites à partir de sources possiblement corrélées.