Contenu

mathématiques

Recherche simple Vous recherchez ...

espace pédagogique > disciplines du second degré > mathématiques > enseignement > animations pédagogiques

Quelques propositions d'algorithmes

mis à jour le 21/12/2009


Si-Alors.jpg

Des ressources utilisées lors d'animations pédagogiques autour de l'algorithmique.

mots clés : algorithmique, algorithme, algobox, tableur


Sont indiquées entre des crochets une ou plusieurs propositions de logiciels à utiliser pour mettre en oeuvre l'algorithme proposé ainsi que des étoiles indiquant sa difficulté de réalisation. Cette difficulté est bien sûr une appréciation personnelle purement subjective. Les algorithmes réalisables avec AlgoBox le sont également avec Scratch, Python, Xcas, Scilab ou tout autre logiciel de programmation pour peu qu'on en maitrise le langage. La plupart sont aussi réalisables avec un tableur, Excel ou OpenOffice, mais ne présentent pas toujours le même intérêt (par exemple la présence de la fonction ALEA.ENTRE.BORNES rend inintéressant l'item 1). La "philosophie algorithmique" des tableurs est parfois assez différente de celle des logiciels de programmation. Mais ce sont des outils extrêmement puissants et souples qu'il serait, à mon avis, regrettable de négliger. Enfin les algorithmes les plus simples peuvent être réalisés sans difficulté sur une calculatrice programmable courante (TI 82 ou Graph 35).
 

1. Tirage d'un nombre entier compris entre deux valeurs
Logiciel d'algorithmique*
Créer un générateur de nombres entiers pseudo-aléatoires compris entre deux bornes à partir du générateur de nombres décimaux pseudo-aléatoires compris entre 0 et 1.

2. Tirage sans remise de deux valeurs
Logiciel d'algorithmique*
Désigner deux élèves au hasard dans une classe de 35 (tirer deux nombres distincts entre 1 et 35). On utilisera le générateur de nombres pseudo-aléatoires défini à l'item 1. (On peut élargir facilement à deux nombres compris entre 1 et n.)

3. Tirage du Loto
Logiciel d'algorithmique***
Propose un tirage pseudo-aléatoire de six nombres, plus un, parmi 49 sans remise.

4. Permutation de n éléments 
Logiciel d'algorithmique***
C'est à la fois une généralisation (n éléments au lieu de 49) de l'algorithme précédent et un cas particulier (n éléments parmi n).

5. Lancers de dés
Logiciel d'algorithmique **
On utilise un dé à six faces (généralisation possible à k faces).
Première version : On effectue n lancers et on affiche les fréquences obtenues.
Deuxième version : On effectue p séries de n lancers et on affiche le tableau des fréquences obtenues.

6. Ecriture décimale illimitée périodique d'un rationnel. (Division à virgule)
Logiciel d'algorithmique** *
Poursuivre une division aussi loin que nécessaire pout déterminer la période de l'écriture décimale illimitée d'un nombre rationnel.

7. Détermination des racines d'une équation polynomiale par dichotomie
Logiciel d'algorithmique*** ***
On se propose de déterminer les zéros du polynôme définie sur ensemble des réels par :

Ce polynôme s'annule pour six valeurs comprises entre -3 et 3. AlgoBox permet d'en déterminer des valeurs approchées avec une précision de 10-7 . ( 210 =1024 est voisin de 103, on gagne 3 décimales toutes les dix itérations.)

8. Distance de deux points, milieu d'un segment, équation d'une droite passant par deux points, médiatrice d'un segment
Logiciel d'algorithmique**
Connaissant les coordonnées de deux points du plan, on veut déterminer les coordonnées du milieu du segment ayant pour extrémités ces deux points, l'équation de la droite passant par ces deux points ainsi que l'équation de la médiatrice du segment. Cet algorithme peut être réalisé en plusieurs étapes. On peut également en faire une représentation graphique

9. Avec trois points
Logiciel d'algorithmique***
Déterminer les longueurs des côtés, tester une condition d'alignement, déterminer les équations des droites, des médiatrices des côtés, déterminer les coordonnées du centre du cercle circonscrit ainsi que son rayon. Tracer le triangle, les 3 médiatrices et le cercle circonscrit. On peut imaginer encore bien d'autres choses (détermination de la nature du triangle, distance d'un point à la droite passant par les deux autres, détermination des médianes, des hauteurs, des bissectrices, enfin tout sur le triangle et
plus encore).

10. Algorithme de Prabhakar **
. . (écriture pour profs de maths !)
Que constate-t-on ?
Quel que soit l'entier naturel duquel on part on aboutit soit au cycle
41637588914542204 etc. soit à 1, soit à 0 (uniquement pour 0).
On peut étudier ce qu'il advient pour p > 2 en posant .

11. Recherche des extrema d'une fonction sur un intervalle
Logiciel d'algorithmique**
Recherche du maximum et de minimum d'une fonction par balayage.
Par exemple, étude des extrema de la fonction f définie sur ensemble des réels par .

12. Méthode de Monte-Carlo
Logiciel d'algorithmique* *
On tire de façon aléatoire, deux nombres x et y, compris entre 0 et 1 et on place dans le plan (rapporté à un repère orthonormal) le point M de coordonnées (x ; y). Il s'agit de faire apparaître la fréquence des points dont la distance à l'origine est strictement inférieure à 1. Cette fréquence tend vers  mais il faut faire un grand nombre de tirages pour obtenir une approximation significative.

 
13. Les aiguilles de Buffon **
On lance un grand nombre d'aiguilles sur un parquet formé de planches parallèles. On supposera que la largeur des planches est égale à la longueur des aiguilles. On compte le nombre de fois où les aiguilles tombent à cheval sur une rainure du parquet. Le rapport de ce nombre sur le nombre total de lancers tend vers . Comme dans la méthode de Monte-Carlo la convergence est lente.

14. Tri par sélection
Logiciel d'algorithmique**
On cherche dans la liste la plus petite valeur. On la place au début et on recommence.
Performance : 5000 valeurs triées en 1 min 55 s. [Pour un ordinateur de référence.]

15. Tri par insertion Logiciel d'algorithmique**
On prend une nouvelle valeur et on l'insère dans la liste déjà triée.
Performance : 5000 valeurs triées en 1 min 6 s. [Pour un ordinateur de référence.]

16. Tri par dénombrement Logiciel d'algorithmique**
On compte le nombre de tirages pour chacune des valeurs et on restitue ces valeurs dans l'ordre.
Performance : 5000 valeurs triées en 46 s. [Pour un ordinateur de référence.]

17. Algorithme de Babylone (ou algorithme de Héron) Logiciel d'algorithmique**
On cherche une valeur approchée de  pour aensemble des réels. On crée la suite suivante :
et pour tout , .
Cet algorithme converge très rapidement et il est facile à comprendre. On peut l'adapter sans difficulté pour rechercher la racine cubique ou la racine nième.

18. Algorithme de Kaprekar (mathématicien indien 1905-1988) ***
On part d'un nombre écrit en base 10. est le nombre écrit à l'aide des mêmes chiffres pris dans l'ordre décroissant. est le nombre écrit avec les même chiffres pris dans l'ordre croissant. Enfin , et on recommence.
Exemple :  = 351947 , = 975 431,  =134 579 et = 975 431-134 579 = 840 852 .
On observe que la suite aboutit rapidement à un point fixe (appelé "puits") :
323 980959 931863 832631 764631 764...
ou la suite aboutit à un "cycle" :
925168860 832862 632642 654420 876851742750 843840 852860 832...

19. Fractions Logiciel d'algorithmique**
On dispose des chiffres de 1 à 9. On forme un nombre a en choisissant quatre d'entre eux et un nombre b avec les 5 restants. Est-il possible que la fraction soit égale à ? , , , , , , ?
Il existe bien des manières de chercher les solutions à l'aide d'un algorithme mais une manière originale
consiste à essayer des permutations (item 4) de façon aléatoires avec un test d'arrêt.
Ce qui revient à écrire n'importe quoi et compter sur la chance ... et ça marche (le plus souvent) !

20. Coder et décoder en "Jules César" Logiciel d'algorithmique**
Il s'agit du codage le plus simple, celui par décalage des caractères.
Il parait naturel à un professeur de maths d'utiliser les congruences modulo 26 mais on peut aussi, moins savament, utiliser une structure alternative. Pour information les codes Ascii des minuscules vont de 97 à 122 ceux des majuscules de 65 à 90 et l'espacement a le code 32.
 

21. La Bibliothèque de Babel
Logiciel d'algorithmique**
Dans la nouvelle La Bibliothèque de Babel (extraite de Fictions) l'écrivain argentin Jorge Luis Borges imagine une bibliothèque contenant tous les volumes possibles obtenus par combinaisons de vingt-cinq caractères.
« ...chaque livre a quatre cent dix pages ; chaque page, quarante lignes, et chaque ligne, environ quatre-vingts caractères noirs. »
« Le manuscrit original du présent manuscrit ne contient ni chiffres ni majuscules. La ponctuation a été limitée à la virgule et au point. Ces deux signes, l'espace et les vingt-deux lettres de l'alphabet sont vingt-cinq symboles suffisants énumérés par l'inconnu. »
On veut écrire un algorithme qui génère une ou plusieurs pages d'un des volumes de cette bibliothèque.
Un calcul simple montre qu'il y a environ  volumes possibles.

22. Conjecture de Syracuse Logiciel d'algorithmique* **
. Pour tout entier naturel k, si  est impair alors , sinon .
Il semblerait que, quel que soit l'entier naturel , cette suite aboutisse à 1. On obtient ensuite le cycle 4 - 2 - 1 indéfiniment. Cette conjecture est connu sous le nom de conjecture de Syracuse ou conjecture de Collatz ou conjecture d'Ulam ou conjecture tchèque. En dépit de la simplicité de son énoncé, elle n'a pas encore été démontrée. Le mathématicien hongrois Paul Erdös dit à son propos que « les mathématiques ne sont pas encore prêtes pour de tels problèmes » . Il ne s'agit bien sûr pas de la démontrer, mais on peut la découvrir, l'essayer, compter le nombre d'étapes, faire des statistiques, des tableaux.

23. Intersection de deux droites  Logiciel d'algorithmique* *
Les deux droites sont données par leurs équations cartésiennes réduites (). Il s'agit en fonction des coefficients directeurs et des ordonnées à l'origine de déterminer si les droites sont confondues, disjointes ou sécantes. Dans ce dernier cas on pourra déterminer les coordonnées de leur point d'intersection. On peut ajouter éventuellement une représentation graphique.

24. Image d'un réel par une fonction, tableau de valeurs, tracé Logiciel d'algorithmique*
Il s'agit d'un algorithme d'initiation que l'on peut enrichir progressivement.
Déterminer l'image d'un nombre par une fonction numérique d'une variable réelle.
Faire un tableau de valeurs et une représentation graphique sur un intervalle.
 
auteur(s) :

Frederic Martin

information(s) pédagogique(s)

niveau : 2nde

type pédagogique : non précisé

public visé : enseignant, élève

contexte d'usage : non précisé

référence aux programmes :

ressource(s) principale(s)

Si-Alors2.jpg ateliers d'algorithmique en seconde 10/01/2010
Des exemples d'algorithmes proposés lors des animations sur le nouveau programme de seconde en 2009.
algorithmique, algorithme

documents complémentaires

Les fichiers associés
PDF Les propositions ci-dessus PDF Solutions et commentaires Logiciel d'algorithmique Les fichiers ressources regroupés dans un archive.
Le logiciel Algobox
    http://www.xm1math.net/algobox/index.html

haut de page

mathématiques - Rectorat de l'Académie de Nantes