Adhérer ou faire un don

Algorithmique au Lycée, deuxième partie.

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).