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