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 varie considé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 contruites à partir de sources possiblement corrélées.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00092862 |
| Date | 06 September 2006 |
| Creators | Lhote, Loïck |
| Publisher | Université de Caen |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | fra |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.002 seconds