Portal de Periódicos da CAPES

Digits and continuants in euclidean algorithms. Ergodic versus tauberian theorems

2000; Institut de Mathématiques de Bordeaux; Volume: 12; Issue: 2 Linguagem: Francês

10.5802/jtnb.296

2118-8572

Brigitte Vallée,

Topological and Geometric Data Analysis

Nous faisons ici l'analyse en moyenne des principales quantités qui interviennent dans des algorithmes de type Euclide -quotients partiels (chiffres) et continuants-. L'étude de ces paramètres est en particulier essentielle quand on s'intéresse à une mesure très précise (et très réaliste) de la complexité de ces algorithmes, i.e., la complexité en bits, où l'on compte toutes les opérations sur les bits. Nous développons un cadre général pour une telle analyse, où la complexité moyenne est reliée au comportement analytique dans le plan complexe des homographies utilisées par l'algorithme. Nos méthodes sont fondées sur l'utilisation des opérateurs de transfert, objets de base de la théorie des systèmes dynamiques, que nous adaptons à nos besoins. Nous opérons dans un cadre discret, où les théorèmes Taubériens prennent le relais des théorèmes ergodiques. Ainsi, nous obtenons des résultats nouveaux sur la complexité moyenne -mesurée en bits- de toute une classe d'algorithmes de type Euclide, et ce, dans un cadre unificateur.