algorithmenom masculin(latin médiéval algorithmus, latinisation

Origines et principeLe principe des algorithmes, mot dérivant du nom du mathématicien arabe al-Khwarizmi, est connu quasiment depuis l'origine des mathématiques. Dès l'Antiquité sont proposés des procédés ou méthodes de calcul qualifiables aujourd'hui d'algorithmes (par exemple, calcul du PGCD ou résolution de certaines équations algébriques). Mais le concept ne sera développé et étudié qu'avec l'émergence, au XXe s., des sciences et techniques de l'informatique, puisque les algorithmes sont l'un des outils de base de la programmation. Ainsi, on appelle algorithme tout processus qui décompose une tâche globale en un nombre fini d'actions élémentaires (les primitives), susceptibles d'être effectuées par l'entité à laquelle en sera confiée l'exécution (le processeur), et qui en décrit explicitement l'ordonnancement temporel.Algorithmes et logique formelleLa réflexion sur les algorithmes n'est pas seulement d'ordre pratique : elle rejaillit sur les études de logique formelle, en particulier chez David Hilbert et Kurt Gödel. Avant d'écrire l'algorithme de résolution d'un problème (de calcul ou de décision), il faut se demander si un tel algorithme existe (problème de la calculabilité ou de la décidabilité), puis dans quels délais le processeur (homme ou machine) sera à même de produire le résultat. Cela conduit, dans un deuxième temps, à déterminer la complexité algorithmique du problème. Pour ce faire, on range les problèmes par classes, sachant qu'un algorithme qui permet de résoudre un problème fournit la solution de tous ceux de la même classe.Calculabilité et décidabilitéAvant de se lancer dans la recherche d'un algorithme de résolution d'un problème, on doit savoir si ce dernier peut être résolu en un nombre fini d'étapes. C'est ce que sous-entendent les termes de calculabilité et de décidabilité.En 1928, David Hilbert formula le problème de la décidabilité : dans un système formel, on doit pouvoir, sans en faire la démonstration, décider si une proposition est vraie. « Tout problème mathématique défini doit nécessairement appeler une conclusion : soit une réponse effective à la question posée, soit une preuve de l'impossibilité de la solution et donc de l'échec inévitable de toute tentative. »Or des travaux publiés dans les années 1930 vont établir l'indécidabilité de certaines propositions de la théorie élémentaire des nombres et montrer qu'il existe des problèmes qui ne comportent pas de solution. Le problème de la décidabilité n'est donc pas calculable, en ce sens qu'il n'existe pas d'algorithme qui permette de déterminer pour une proposition donnée, dans un système formel, si cette proposition est vraie ou fausse. Ainsi, en 1931, Kurt Gödel publie la preuve du théorème d'incomplétude de l'arithmétique : il existe des propositions qui, bien que vraies, ne peuvent être ni démontrées ni infirmées.Puis, en 1936, Alonzo Church établit l'insolubilité de certains problèmes de théorie des nombres. Ces résultats marquent, d'une certaine façon, les limites de la pensée formaliste. En mettant en évidence des énoncés pour lesquels il n'existe pas d'algorithme permettant de décider s'ils sont vrais ou faux, ces travaux vont en susciter d'autres en vue de préciser ce que l'on entend par algorithme, par méthode effective et par calculabilité.Complexité des algorithmesSelon le type d'algorithme utilisé, tous les problèmes ne sont pas équivalents : certains sont plus faciles (ou rapides) à résoudre que d'autres. Les problèmes sont ainsi rangés par classes. Il est démontré qu'un algorithme qui permet de résoudre un problème fournit la solution de tous les problèmes de la même classe. Par ailleurs, des algorithmes distincts peuvent résoudre le même problème. Quels critères peuvent alors guider un utilisateur dans le choix d'un algorithme ? Les exigences sont fréquemment contradictoires : d'une part, simplicité et transparence du schéma de calcul qui fournit la solution du problème donné ; d'autre part, utilisation optimale des ressources disponibles, c'est-à-dire, le plus souvent, rapidité d'exécution du code de l'algorithme par les moyens informatiques.La classification des solutions algorithmiques d'un problème peut s'effectuer sur la base du nombre d'opérations élémentaires nécessaires à leur exécution ; cette mesure s'appelle complexité algorithmique ou complexité théorique. Cette notion devrait être indépendante du processeur sur lequel l'algorithme est mis en œuvre, alors que son temps d'exécution fait intervenir, outre sa propre complexité, d'autres facteurs : nature des données utilisées et du processeur, vitesse d'exécution des instructions par celui-ci, etc. Pour évaluer cette complexité, on en simplifie le calcul en ne retenant que les ordres de grandeur du nombre d'opérations élémentaires les plus significatives.Dans la pratique, les informaticiens estiment que les algorithmes dont le temps d'exécution croît de façon exponentielle avec le nombre de données ne sont pas utilisables. En revanche, ceux de type « polynomial » – dont le temps d'exécution croît en suivant une fonction polynôme (de la taille n des données) – sont considérés comme exploitables.

Aucun site ajouté récemment