algorithme - Définition.

algorithme - Définition. n.m. (du nom du mathématicien arabe al-Kh?razmi), résultat de l'analyse d'un problème sous la forme d'un schéma décrivant l'enchaînement des opérations élémentaires qu'il faut effectuer pour le résoudre. L'algorithme en mathématiques. Longtemps avant l'apparition des ordinateurs et de l'informatique, les mathématiciens ont désigné par le mot « algorithme « tout procédé de calcul ou de construction exprimé par une liste finie et bien déterminée de tâches élémentaires. Par exemple, dans le calcul polynomial, on utilise l'algorithme de Hörner. Le plus connu et le plus ancien des algorithmes mathématiques est celui qui est utilisé dans la technique écrite de la division, et qu'on appelle algorithme d'Euclide. Il consiste à poursuivre un certain processus de soustraction aussi longtemps que son résultat n'est pas nul. En voici une variante où il s'agit de calculer le plus grand commun diviseur (PGCD) de deux nombres entiers non nuls a e t b : soustraire le plus grand nombre du plus petit ; remplacer le plus grand nombre par la différence obtenue ; recommencer la soustraction et le remplacement jusqu'à ce que les deux nombres en présence soient égaux ; on a alors le PGCD cherché. Appliquons cet algorithme à partir des nombres 117 et 1365 : 1365 - 117 = 1248, 1248 - 117 = 1131, ... Les soustractions successives de 117 jusqu'à obtenir un nombre inférieur à 117 reviennent à la division de 1365 par 117 : 1365 = (117 × 11) + 78 117 - 78 = 39, 78 - 39 = 39. Le PGCD de 117 et 1365 est donc 39. L'algorithme en informatique. Depuis les origines, alors que les premiers ordinateurs étaient programmés en alignant des suites de 0 et de 1, jusqu'à aujourd'hui, où l'on dispose de langages de très haut niveau, l'un des grands problèmes de l'informatique est de faire de la programmation une technique fiable et performante, sinon une discipline scientifique. Tout un secteur de la recherche en informatique s'est développé à partir de cette problématique : l'algorithmique ou programmation systématique. À un premier niveau, l'algorithmique analyse la façon dont sont résolus concrètement les problèmes. Ce travail permet de ramener les éléments nécessaires à la résolution d'un problème quelconque à un petit nombre de notions et de techniques fondamentales. Ainsi, les structures de données (types scalaires, vectoriels, etc.), l'affectation, la sélection (instructions conditionnelles), l'itération ou la récursion, la modularité, etc., font l'objet de nombreuses recherches théoriques. Les langages les plus récents, comme Ada, les microprocesseurs Risc sont construits sur les analyses qui en découlent. À un deuxième niveau, plus opérationnel, l'algorithmique s'intéresse aux portions de programmes qui correspondent à des tâches élémentaires et qu'on retrouve dans beaucoup de programmes. Contrairement à la situation précédente, où l'on n'en tenait pratiquement pas compte, les caractéristiques des machines elles-mêmes jouent un rôle important. Par exemple, l'étude de l'opération de tri, une des plus fréquentes en informatique de gestion, a abouti à un nombre réduit d'algorithmes efficaces. Le programmeur, qui a un problème de tri à résoudre à l'intérieur d'un programme, peut ainsi choisir l'algorithme le plus efficient, compte tenu des caractéristiques de son ordinateur, de la nature et du volume de ses données, du support de celles-ci. La recherche en algorithmique. Troisième et dernier niveau, celui-ci de très haute abstraction, les algorithmes en tant qu'entités sont l'objet même de la recherche en algorithmique. Dans un système formel donné, il existe des propositions dont la décidabilité n'est pas calculable : c'est le fameux théorème d'incomplétude de Gödel (1931). Il y a donc des problèmes qui n'ont pas de solution algorithmique. Encore faut-il savoir définir ce qu'est un algorithme. Qu'on utilise une suite de règles sous forme de fonctions mathématiques comme Gödel, le lambda calcul comme Church ou une machine hypothétique comme Turing, on admet toujours, depuis les années trente, la « thèse de Church-Turing « : toutes les définitions rationnelles, présentes ou futures, du terme algorithme sont équivalentes. Rien, jusqu'ici, n'est venu démentir cette thèse, émise bien avant l'existence des ordinateurs. L'exécution des algorithmes reposant aujourd'hui sur l'emploi des ordinateurs, il est légitime d'accepter la confusion courante entre algorithme et ce qui peut être exécuté par un ordinateur. Un autre sujet de l'algorithmique est la question suivante : « Mon programme boucle-t-il ? « Un raisonnement typique de l'algorithmique démontre qu'il n'existe malheureusement pas d'algorithme permettant d'en décider. La question de la complexité et des ressources est d'une grande importance pratique : qu'importe l'existence d'un algorithme, s'il nécessite un temps de calcul qui se compte en milliards d'années. Un des défis de l'informatique est de découvrir des algorithmes dont la durée soit de l'ordre du polynomial et non de l'exponentiel. Là encore, on n'a pas de solution satisfaisante, en admettant qu'il en existe.