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.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00258776 |
| Date | 22 June 2005 |
| Creators | Daireaux, Benoit |
| Publisher | Université de Caen |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.002 seconds