Accueil » Publications » Le Bulletin Vert » Les dossiers » Algorithmique au Lycée, deuxième (...)
  APMEP   Algorithmique au Lycée, deuxième partie.

Article du bulletin 446

Adhérer ou faire un don

par la CREM

Commission de Réflexion sur l’Enseignement des Mathématiques

(suite du numéro 445 : lire la première partie)

Plan de l’article :

8. Quelques algorithmes abordables au Lycée

On a dressé ici une première liste de quelques algorithmes qui peuvent être envisagés à partir du programme actuel du Lycée [1].

8.1. Arithmétique
- 1. Génération de la liste des nombres premiers inférieurs à un entier par le crible d’Ératosthène
- 2. Recherche du PGCD de deux entiers par l’algorithme d’Euclide
- 3. Recherche du PPCM de deux entiers
- 4. Résolution de l’identité de Bézout par l’algorithme d’Euclide
- 5. Test de primalité
- 6. Conversion du système décimal au système binaire

  • avec un test systématique des entiers inférieurs à $\sqrt{N}$
  • amélioration : test avec 2, puis les entiers impairs inférieurs à $\sqrt{N}$
  • amélioration : test avec 2, puis 3, puis les entiers de la forme 6p − 1 ou 6p + 1 inférieurs à $\sqrt{N}$

- 7. Factorisation d’un entier en produit de facteurs premiers

  • avec un test systématique des entiers inférieurs à $\sqrt{N}$
  • amélioration : test avec 2, puis les entiers impairs inférieurs à$\sqrt{N}$
  • par recherche de a et b entiers tels que $N = a^{2} - b^{2}$, ou encore par recherche de a pour que $a^{2}- N $soit un carré parfait
  • amélioration : algorithme de Fermat
    - 8. Recherche de nombres amicaux
    - 9. Recherches de nombres parfaits, abondants, déficients
    - 10. Recherche de triplets pythagoriciens
    • entiers quelconques
    • avec la contrainte : un des 3 entiers est fixé ou le plus petit des 3 entiers est fixé

8.2. Analyse

8.2.1. Suites numériques

  • 1. Calcul des termes d’une suite récurrente
  • 2. Vitesse de convergence d’une suite récurrente monotone convergente

- 8.2.2. Approximation de réels

- 1. Calcul d’une approximation d’une fonction par une fonction affine
- 2. Recherche approchée d’une solution d’une équation différentielle du type y′ = ay + b par la méthode d’Euler
- 3. Recherche d’une aire sous une courbe par la méthode des rectangles ou des trapèzes
- 4. Régression affine

8.3. Statistique
- 1. Calculs de paramètres statistiques (moyenne, écart-type, médiane, quartiles, déciles)
- 2. Algorithmes de simulation :

  • Lancements répétés d’une pièce ou d’un dé, comptage des occurrences
  • Lancements répétés d’une pièce ou d’un dé truqués, comptage des occurrences
  • Lancements répétés de 2 ou 3 dés, calcul de la somme des faces, comptage des occurrences
  • Lancements répétés d’un dé, comptage du nombre de lancers jusqu’à l’apparition du 6
  • Réalisation d’un sondage sur un échantillon aléatoire
  • Marche aléatoire dans le plan ou dans l’espace

8.4. Mathématiques discrètes, graphes

- 1. Coloration d’un graphe
- 2. Recherche de la plus courte chaîne entre deux sommets

8.5. Divers
- 1. Génération du triangle de Pascal
- 2. Rangement d’une liste par ordre croissant
- 3. Mélange d’une liste de façon aléatoire
- 4. Résolution d’un système linéaire par la méthode de Gauss

Lire cette deuxième partie dans son intégralité


[1] On pourra consulter : J. Chabert et al., Histoire d’algorithmes – Du caillou à la puce, (Belin, 1994), ainsi que : Algorithmique et traduction pour calculatrice, (IREM de Grenoble, 2000).


 Accueil   Plan du site   Haut de la page   Page précédente