Accueil » Publications » Le Bulletin Vert » Les dossiers » Coût de l’algorithme d’Euclide et (...)
  APMEP   Coût de l’algorithme d’Euclide et Capes interne

Article du bulletin 445

Adhérer ou faire un don

D. J. Mercier

Résumé de l’article

L’article présente quelques réflexions menées à partir d’un énoncé de CAPES interne qui proposait de majorer le nombre de divisions euclidiennes nécessaires à l’algorithme d’Euclide. Le coût d’un algorithme est défini dans deux modèles différents (coûts fixes ou bilinéaires) pour mieux s’adapter aux méthodes de calcul de l’ordinateur, puis l’on exprime une majoration du coût de l’algorithme d’Euclide et de son cousin l’algorithme d’Euclide étendu. Une dernière partie étudie l’algorithme d’écriture d’un nombre en base b. Ce travail intéressera les candidats au Capes, et sans doute aussi les agrégatifs pour la nouvelle épreuve de modélisation de l’agrégation externe.

Plan de l’article

  • 1. Introduction
  • 2. Un extrait du CAPES interne 2000
  • 3. Le modèle des coûts bilinéaires
  • 4. Algorithme d’Euclide
  • 5. Algorithme d’Euclide étendu
  • 6. Compléments
  • Références

- Télécharger l’article en pdf dans son intégralité

(Article mis en ligne par Armelle BOURGAIN)
 Accueil   Plan du site   Haut de la page   Page précédente