Exemples d'algorithmes
Exemple : Calculs sur une suite.
Commençons par quelque chose de simple...
Considérons la suite définie par :
avec
.
On aimerait calculer par exemple
et la somme
.
On a besoin de trois variables : une variable réelle pour les valeurs de la suite (u), une variable réelle pour la somme (s) et une variable entière qui servira de compteur (n).
L'algorithme peut s'écrire ainsi :
<!---Initialisation des variables--->
variable(réelle) u=1;
variable(réelle) s=1;
variable(entière) n=0;
<!---Traitement--->
tant que (n<20) {
u=(2*u+1)/u;
s=s+u;
n=n+1;
}
afficher u;
afficher s ;
Ceci est un algorithme exprimé de façon " conventionnelle " pour que tout lecteur puisse l'interpréter.
On peut aussi utiliser une autre " boucle " pour cet algorithme :
<!---Initialisation des variables--->
variable(réelle) u=1;
variable(réelle) s=1;
variable(entière) i;
<!---Traitement--->
for(i=0 ;i<20 ;i++){
u=(2*u+1)/u;
s=s+u;
}
afficher u ;
afficher s;
Maintenant il reste à l'écrire en tant que programme pour qu'un ordinateur puisse l'exécuter......
Pour cela il va falloir utiliser un langage de programmation. Il en existe plusieurs ( c++, java-script, Java, Python,php etc......)
Nous utiliserons Java.
Pourquoi Java ?
Parce qu'il faut bien en aborder un.
Pour le reste je vous engage à lire la page de wikipédia consacrée au langage JAVA.
Notre algorithme traduit en Java
Programme réalisé dans Eclipse. Un environnement pour programmer en Java. |  java1 |
Il y a environs 10 TP. prévus pour apprendre les bases de la programmation en Java
Fondamental : Les Algorithmes "classiques"
Beaucoup de programme que l'on cherche à réaliser peuvent souvent se ramener à un algorithme "classique". Comme le tri d'objets, la recherche d'objets dans une liste etc....
Il faut alors passer un peu de temps pour les comprendre pour pouvoir ensuite les réinvestir.
Un algorithme de recherche d'un élément dans une liste classées.
La recherche d'un objet dans une liste ( dictionnaires, annuaires, moteur de recherche.....)
Le principe utilisé est la dichotomie .
Soit une liste de n objets classés. On recherche un objet en particulier.
--> On choisit dans la liste l'objet médian.
--> On compare les deux objets.
--> Si on a trouvé alors c'est fini.
--> Si l'objet recherché est placé avant l'objet choisi alors on recommence avec cette partie de la liste.
--> Si l'objet recherché est placé après l'objet choisi alors on recommence avec cette partie de la liste.
--> Au bout d'un certain nombre d'essais (cela se calcule) soit on a trouvé l'objet soit il n'est pas dans la liste.
Ce principe est utilisé aussi bien en mathématiques (pour rechercher une approximation de solution d'une équation) que pour trouver un mot dans un dictionnaire.
 Algorithme de dichotomie | Voici cet algorithme sous forme d'une fonction. On suppose que tab est un tableau de mots classés. et que l'on recherche le mot contenu dans x. Cette fonction renvoie un booléen. Vrai si le mot est dans la liste Faux s'il n'y est pas |
Il y a beaucoup d'autres algorithmes de recherche et la plupart d'entre eux sont des améliorations de celui-ci.
Ce qui compte c'est le temps d'exécution.
Imaginons un annuaire qui contienne les noms, prénoms, adresses.....des 7 milliards d'êtres humains vivant sur la terre.
Quel est le nombre maximum d'itérations pour trouver un individu ?
Comme à chaque itération on divise le nombre de personne par 2, et, en supposant que la personne cherchée est la 1ère ou la dernière. La question revient à :
Combien de fois faut-il que je divise 7 milliards par 2 pour qu'il n'en reste qu'un ?
Soit à résoudre l'équation :
dont la solution est :
. Soit au maximum 33 itérations !
Un algorithme qui balaye la liste du début à la fin aurait fait 1 itération pour la première personne et 7 milliards d'itérations pour la dernière ! !
Un algorithme de tri
Il existe plusieurs algorithmes de tri dont la différence tient dans leur rapidité à effectuer un tri.
Nous allons regarder l'algorithme de tri par sélection, qui n'est pas le plus rapide, mais qui est intéressant dans son principe.
 Algorithme de tri par sélection | Le tri par sélection d'une liste consiste à : ---> Chercher le maximum de la liste. ---> De le mettre en dernière position. ---> De recommencer avec la liste amputée de son dernier terme. Voici ci-contre cet algorithme |
