Introduction à l'algorithmique
Introduction
Que signifie le mot « algorithme » ? Dans un premier temps, on peut dire qu'un algorithme, tout simplement, c'est une méthode, une manière systématique de procéder pour faire quelque chose : trouver un chemin, préparer une tarte, trier un jeu de cartes, rechercher un mot dans le dictionnaire, etc. Les définitions plus formelles sont certes plus compliquées, mais c'est cette idée qui se cache derrière ce mot mystérieux.
Vers l'an 820, le mathématicien arabe Mohammed Ibn Musa Abu Djefar Al-Khwarizmi tenta une première définition : « Un algorithme est séquence d'opérations visant à la résolution d'un problème en un temps fini. » Un terme important de cette définition est « séquence d'opérations » : un algorithme est une suite d'instructions permettant d'obtenir un résultat.
On retrouve cette idée dans la définition de l'encyclopédie libre : « Un algorithme est un moyen pour un humain de présenter la résolution par calcul d'un problème à une autre personne physique (un autre humain) ou virtuelle (un calculateur). En effet, un algorithme est un énoncé dans un langage bien défini d'une suite d'opérations permettant de résoudre par calcul un problème. » Ainsi, une fois que quelqu'un a une idée du procédé permettant d'obtenir le bon résultat à partir des informations initiales, il peut formaliser le processus sous forme de pseudo-code, pour un être humain, ou de code source, pour une machine.
En résumé, un algorithme, c'est un processus systématique, à appliquer sans réfléchir, qui permet de passer d'un ensemble d'"ingrédients" (les données d'entrée) à un résultat.
Exemples
Revenons sur quelques exemples d'algorithmes courants. Une recette de cuisine, par exemple, est un algorithme : à partir des ingrédients, elle explique comment parvenir au plat. De même, un itinéraire routier explique comment, à partir d'une position initiale, rejoindre une position finale en un certain nombre d'étapes : c'est aussi un algorithme.
La recherche d'un mot dans le dictionnaire est encore algorithme : à chaque page, on compare les lettres du mot cherché et des mots de la page. Suivant le résultat, on passe aux pages suivantes ou précédentes, puis on réitère le processus jusqu'à ce trouver le mot cherché. Enfin, plus évident : les méthodes de calcul vues dans les petites classes (addition, multiplication, calcul du PGCD, etc.) sont des algorithmes.
On voit donc que les algorithmes font partie de notre quotidien, et qu'ils peuvent manipuler des objets de natures très différentes : ingrédients de cuisine, positions, mots, nombres, etc.
Applications informatiques
L'algorithmique a des implications directes en informatique : on utilise ses notions pour étudier les programmes, leur temps d'exécution et leur occupation mémoire à travers ce qu'on appelle la complexité des algorithmes. On apprend à identifier les solutions les plus efficaces, les meilleures représentations en mémoire, pour pouvoir calculer plus vite et de façon moins coûteuse (pe. en mémoire) sur nos machines qui sont, par nature, limitées (en puissance de calcul comme en mémoire).
Avant d'aborder des articles d'algorithmique, il est recommandé d'avoir des notions mathématiques élémentaires (niveau second cycle), pour ne pas être gêné par les calculs, et de maîtriser au moins un langage de programmation : le C++ est un choix de référence, mais Caml ou Java sont tout aussi adéquats. Une fois l'algorithme en tête, le passage au code source ne doit poser aucun problème.
Conclusion
Au cours de cette brève introduction, nous avons tenté de définir et de comprendre la portée des algorithmes avant de préciser les pré-requis indispensables à l'étude de l'algorithmique en informatique. Si vous souhaitez découvrir d'autres approches de ce même sujet, vous pouvez aussi consulter les articles suivants :
- Qu'est-ce qu'un algorithme ? par P. Flajolet et É. Parizot ;
- Algorithmique sur Wikipédia.