Return to search

Analyse des algorithmes d'Euclide : une approche dynanique

Les objets étudiés dans cette thèse sont des algorithmes de calcul de pgcd. Nous effectuons dans cette thèse des analyses probabilistes de plusieurs de ces algorithmes : les algorithmes alpha-euclidiens, l'algorithme LSB et l'algorithme de Lehmer-Euclide. Nous obtenons des résultats précis sur le comportement moyen de toute une gamme de paramètres, entre autres le nombre d'itérations et la complexité en bits. Les techniques employées sont celles de l'analyse dynamique d'algorithmes, et les analyses effectuées dans cette thèse permettent d'élargir le champ d'application de cette méthodologie. En particulier, nous étudions des systèmes dynamiques à branches non surjectives, des systèmes dynamiques définis sur l'ensemble des nombres p-adiques ou encore des systèmes de fonctions itérées. Ces analyses impliquent une étude très précise des opérateurs de Perron-Frobenius et des opérateurs de transfert associés à ces systèmes. En particulier, le comportement probabiliste des algorithmes est relié aux propriétés spectrales de ces opérateurs. Nous analysons également l'évolution des principaux paramètres des algorithmes au cours de leur execution.

Identiferoai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00258776
Date22 June 2005
CreatorsDaireaux, Benoit
PublisherUniversité de Caen
Source SetsCCSD theses-EN-ligne, France
LanguageFrench
Detected LanguageFrench
TypePhD thesis

Page generated in 0.002 seconds