Quelques propositions d'algorithmes

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

*">

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

*">

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

* * *">

Propose un tirage pseudo-aléatoire de six nombres, plus un, parmi 49 sans remise.

4. Permutation de n éléments 

* * *">

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

* *">

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)

*">

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

* * *">

On se propose de déterminer les zéros du polynôme définie sur 

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 . ( 2¹⁰ =1024 est voisin de 10³, 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

* *">

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

* * *">

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

* *">

Que constate-t-on ?
Quel que soit l'entier naturel duquel on part on aboutit soit au cycle
4

On peut étudier ce qu'il advient pour p > 2 en posant

11. Recherche des extrema d'une fonction sur un intervalle

* *">

Recherche du maximum et de minimum d'une fonction par balayage.
Par exemple, étude des extrema de la fonction f définie sur 

12. Méthode de Monte-Carlo

*">

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 

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

14. Tri par sélection

* *">

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

* *">

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

* *">

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)

* *">

On cherche une valeur approchée de 

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 n^ième.

18. Algorithme de Kaprekar (mathématicien indien 1905-1988)

* * *">

On part d'un nombre

Exemple : 

On observe que la suite aboutit rapidement à un point fixe (appelé "puits") :
323 980

ou la suite aboutit à un "cycle" :
925168

19. Fractions

* *">

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

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"

* *">

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

* *">

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 

22. Conjecture de Syracuse

* *">

Il semblerait que, quel que soit l'entier naturel

23. Intersection de deux droites 

*">

Les deux droites sont données par leurs équations cartésiennes réduites (

24. Image d'un réel par une fonction, tableau de valeurs, tracé

*">

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.