Les exemples suivants montrent que beaucoup d'algorithmes décrivent des tâches quotidiennes. Pour la présentation de ces algorithmes nous utiliserons tout simplement des instructions rédigées en langue française. Ces instructions seront suffisamment claires pour que le lecteur comprenne leur intention.
Exemple 1: Prise d'un médicament contre la toux
Algorithme:
"En cas de toux, prendre, sauf avis contraire du médecin, un comprimé toutes les 4 heures, jusqu'à disparition des symptômes. Pour les enfants, un comprimé toutes les 8 heures suffit."
Exemple 2: Tri d'un jeu de cartes suivant la couleur
Algorithme:
(1) Prendre la première carte;
(2) La carte est-elle rouge?
Si oui, poser la carte sur le premier tas;
Sinon, poser la carte sur le second tas;
(3) Reste-t-il des cartes?
Si oui, prendre la carte suivante et continuer sous 2;
Sinon, fin du tri.
Exemple 3: Crible d'Eratosthène pour la construction de nombres premiers
Historique:
Depuis l'Antiquité les mathématiciens se sont intéressés aux problèmes relatifs aux nombres entiers, et plus particulièrement aux nombres premiers. Ainsi se posait-il toujours la question: est-ce qu'un nombre entier positif donné est premier ou non? Ce fut le mathématicien, astronome et philosophe grec ERATOSTHENE (284 - 192 avant J.-C.) de l'école d'Alexandrie, qui inventait une méthode pour la construction de nombres premiers qui a gardé son importance jusqu'à nos jours. L'algorithme, connu sous le nom de crible d'Eratosthène, se présente comme suit :
Algorithme:
(1) en P ranger 2;
(2) Biffer tous les multiples de P qui suivent P;
(3) En P ranger le premier nombre non biffé qui suit P;
(4) Continuer sous 2.
Ainsi on obtient schématiquement:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 . . .
1 3 5 7 9 11 13 15 . . .
1 3 5 7 11 13 . . .
etc.
Exemple 4: L'algorithme d'EUCLIDE
Historique:
L'algorithme le plus ancien qui n'a cessé de garder son importance jusqu'aujourd'hui, est la célèbre méthode de calcul, imaginée par EUCLIDE, un mathématicien grec qui enseignait à Alexandrie sous le règne de Ptolémée Ier au IIIe siècle avant J.-C., pour la recherche du plus grand commun diviseur (PGCD) de deux nombres entiers naturels non nuls. Grâce à sa richesse et à sa brièveté, l'algorithme d'EUCLIDE nous fournit un exemple classique d'un algorithme.
En écriture moderne, l'algorithme d'Euclide est formulé comme suit:
Considérer deux nombres entiers naturels non nuls M et N.
Déterminer le plus grand commun diviseur de M et de N.
Algorithme:
(1) {Déterminer le reste}
Diviser M par N et obtenir R comme reste, tel que 0 £ R < N.
(2) {Est-ce que le reste est égal à zéro ?}
Si R = 0, alors l'algorithme se termine.
On a : PGCD (M,N) = N.
(3) {Permuter}
Si R ¹ 0, alors remplacer M par N, N par R et continuer sous (1).
La séquence ordonnée des opérations de l'algorithme d'Euclide peut être schématisée comme suit :
Figure 2.1 L'algorithme d'EUCLIDE
Remarques:
1) L'algorithme d'Euclide termine après un nombre fini de pas puisque les restes obtenus forment une suite strictement décroissante d'entiers naturels qui tend vers 0.
2) Aussi longtemps que sous (2) le reste R est non nul, le problème de la détermination du plus grand diviseur commun de M et de N est ramené au problème plus simple de la recherche du plus grand diviseur commun de N et de R. On continue de cette manière jusqu'à ce qu'avec R égal à zéro le problème soit résolu. Ce principe qui consiste à réduire considérablement la complexité d'un algorithme est souvent utilisé en programmation.
© Aflo Informatique , 2003-2004