Algorithme
   |
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Consultez la liste des tâches à accomplir en page de discussion. |
Un algorithme est une suite finie et non-ambiguë d’opérations ou d'instructions permettant de résoudre un problème.
Le mot algorithme vient du nom latinisé du mathématicien perse Al-Khawarizmi, surnommé « le père de l'algèbre ». Le domaine qui étudie les algorithmes est appelé l'algorithmique. On retrouve aujourd'hui des algorithmes dans de nombreuses applications telles que la cryptographie, le routage d'informations, la planification et l'optimisation de ressources, la bio-informatique, etc.
Sommaire |
Algorithme mathématique [modifier]
Un algorithme est correct lorsque, pour chaque instance, il se termine en produisant la bonne sortie, c'est-à-dire qu'il résout le problème posé. On mesure l'efficacité d'un algorithme notamment par sa durée de calcul, par sa consommation de mémoire RAM (en partant du principe que chaque instruction a un temps d'exécution constant), par la précision des résultats obtenus (par exemple avec l'utilisation de méthodes probabilistes, comme la méthode de Monte-Carlo), sa scalabilité (son aptitude à être efficacement parallélisé) etc. Les ordinateurs sur lesquels tournent ces algorithmes ne sont pas infiniment rapides : le temps de machine reste une ressource limitée, malgré une augmentation constante des performances des ordinateurs. Un algorithme sera donc dit performant s'il utilise avec parcimonie les ressources dont il dispose, c'est-à-dire le temps CPU et la mémoire RAM. L’analyse de la complexité algorithmique permet de prédire l'évolution en temps calcul nécessaire pour amener un algorithme à son terme, en fonction de la quantité de données à traiter.
Quelques définitions [modifier]
- Donald_Knuth (1938/--), également professeur à l'université de Stanford University au même moment que Marshall Harvey STONE, lista les cinq propriétés suivantes comme étant les pré-requis d'un algorithme :
- La finitude : "Un algorithme doit toujours se terminer après un nombre fini d'étapes."
- Définition précise : "Chaque étape d'un algorithme doit être définie précisément, les actions à transposer doivent être spécifiées rigoureusement et sans ambiguïté pour chaque cas."
- Entrées : "...des quantités qui lui sont données avant qu'un algorithme ne commence. Ces entrées sont prises dans un ensemble d'objets spécifié."
- Sorties : "...des quantités ayant une relation spécifiées avec les entrées."
- Rendement: "...toutes les opérations que l'algorithme doit accomplir, doivent être suffisamment basiques pour pouvoir être en principe réalisées dans une durée finie par un homme utilisant un papier et un crayon."
- George Boolos (en) (1940/1996), philosophe et mathématicien, proposa la définition suivante :
"Des instructions explicites pour déterminer le nième membre d'un ensemble, pour _b{n} arbitrairement fini. De telles instructions sont données de façon bien explicite, sous une forme qui puisse être utilisée par une machine à calculer ou par un humain qui est capable de transposer des opérations très élémentaires en symboles ."
Algorithme non mathématique [modifier]
- Une recette de cuisine est également un algorithme. Elle en contient les éléments constitutifs :
- des entrées (les ingrédients, le matériel utilisé)
- des instructions élémentaires simples, dont l'exécution amène au résultat voulu
- un résultat : le plat préparé.
- Cependant, les recettes de cuisine ne sont en général pas présentées rigoureusement sous forme non-ambigüe : il est d'usage d'y employer des termes vagues laissant une liberté d'appréciation à l'exécutant alors qu'un algorithme stricto-sensu doit être précis et sans ambigüité.
- Un casse-tête peut être résolu de façon systématique par un algorithme d'exécution, tel que celui du Rubik's Cube.
- En sport, l'exécution de séquences répondant à des finalités d'attaque, de défense, de progression, correspond à des algorithmes.
Algorithme et traitement de l'information [modifier]
Tout d’abord utilisés en mathématiques, les algorithmes jouent aujourd’hui un rôle de plus en plus important sinon primordial en sciences de l’information comme en informatique. L’enjeu est de taille, puisqu'il s'agit de classer l'information correctement afin de la traiter automatiquement pour répondre aux besoins d'une société de plus en plus numérique. Publicités ciblées, moteurs de recherches, programmes informatiques... Tant de nouvelles pratiques issues du web 2.0 qui ont pu émerger dans un contexte qui leur est propre. Plus de détails dans la page dédiée à cette rubrique.
Notes et références [modifier]
Néant
Voir aussi [modifier]
Article connexe [modifier]
Liens externes [modifier]
- Qu’est-ce qu'un algorithme ? par Philippe Flajolet et Étienne Parizot sur la revue en ligne Interstices
- Définition du terme algorithme par les auteurs
