Algorithme

En mathématiques et en informatique , un algorithme ( / ˈ æ l ɡ ə r ɪ ð əm / ^ⓘ ) est une séquence finie d'instructionsmathématiquement rigoureusesproblèmesou pour effectuer uncalcul.Les algorithmes sont utilisés comme spécifications pour effectuerdes calculsetle traitement des données. Des algorithmes plus avancés peuvent utiliserdes conditionspour détourner l'exécution du code par diverses voies (appeléesprise de décision automatisée) et déduiredes inférences(appeléesraisonnement automatisé).

En revanche, une heuristique est une approche souvent incomplètement définie pour résoudre des problèmes qui ne donne pas nécessairement des résultats corrects ou optimaux, souvent appliquée à des problèmes pour lesquels il n'existe pas de résultat correct ou optimal bien défini. les systèmes de recommandation de médias sociaux soient communément appelés « algorithmes », ils reposent en réalité sur des heuristiques car il n'existe pas de recommandation véritablement « correcte ».

En tant que méthode efficace , un algorithme peut être exprimé dans un espace et un temps finis et dans un langage formel bien défini pour calculer une fonction . À partir d'un état initial et d'une entrée initiale (peut-être vide ), les instructions décrivent un calcul qui, une fois exécuté , passe par un nombre fini d'états successifs bien définis, produisant finalement une « sortie » et se terminant à un état final. La transition d'un état à l'autre n'est pas nécessairement déterministe ; certains algorithmes, appelés algorithmes randomisés , intègrent une entrée aléatoire.

Vers 825 après J.-C., le scientifique et polymathe persan Muḥammad ibn Mūsā al-Khwārizmī a écrit le kitāb al-ḥisāb al-hindī (« Livre du calcul indien ») et le kitab al-jam' wa'l-tafriq al-ḥisāb al-hindī (« Addition et soustraction dans l'arithmétique indienne »). Au début du XIIe siècle, des traductions latines desdits textes al-Khwarizmi impliquant le système numérique et l'arithmétique hindou-arabe sont apparues, par exemple le Liber Alghoarismi de practica arismetrice , attribué à Jean de Séville , et le Liber Algorismi de numero Indorum , attribué à Adélard de Bath . Par la présente, alghoarismi ou algorismi est la latinisation du nom d'Al-Khwarizmi ; le texte commence par la phrase Dixit Algorismi , ou « Ainsi parlait Al-Khwarizmi ». Vers 1230, le mot anglais algorism est attesté puis par Chaucer en 1391, l'anglais adopte le terme français. Au XVe siècle, sous l'influence du mot grec ἀριθμός ( arithmos , « nombre » ; cf. « arithmétique »), le mot latin a été modifié en algorithmus .

Une définition informelle est « un ensemble de règles qui définit précisément une séquence d'opérations », qui inclurait tous les programmes informatiques (y compris les programmes qui n'effectuent pas de calculs numériques), et toute procédure bureaucratique prescrite ou recette de livre de cuisine . En général, un programme n'est un algorithme que s'il s'arrête éventuellement — même si des boucles infinies peuvent parfois s'avérer souhaitables. Boolos, Jeffrey & 1974, 1999 définissent un algorithme comme un ensemble explicite d'instructions pour déterminer une sortie, qui peut être suivi par une machine informatique ou un humain qui ne pourrait effectuer que des opérations élémentaires spécifiques sur des symboles .

La plupart des algorithmes sont destinés à être mis en œuvre sous forme de programmes informatiques . Cependant, les algorithmes sont également mis en œuvre par d'autres moyens, comme dans un réseau neuronal biologique (par exemple, le cerveau humain effectuant des opérations arithmétiques ou un insecte à la recherche de nourriture), dans un circuit électrique ou dans un dispositif mécanique.

Des procédures étape par étape pour résoudre des problèmes mathématiques ont été enregistrées depuis l'Antiquité. Cela inclut les mathématiques babyloniennes (vers 2500 av. J.-C.), les mathématiques égyptiennes (vers 1550 av. J.-C.), les mathématiques indiennes (vers 800 av. J.-C. et plus tard), l'oracle d'Ifa (vers 500 av. J.-C.), les mathématiques grecques (vers 240 av. J.-C.), et les mathématiques arabes (vers 800 apr. J.-C.).

Les premières traces d'algorithmes se trouvent dans les mathématiques de la Mésopotamie antique . Une tablette d'argile sumérienne découverte à Shuruppak près de Bagdad et datée d'environ 2500 av  . J.-C. décrit le premier algorithme de division . Sous la dynastie Hammurabi , vers  1800 -  1600 av. J.-C. , des tablettes d'argile babyloniennes décrivaient des algorithmes pour le calcul de formules. Les algorithmes étaient également utilisés en astronomie babylonienne . Les tablettes d'argile babyloniennes décrivent et utilisent des procédures algorithmiques pour calculer l'heure et le lieu d'événements astronomiques importants.

Les algorithmes d'arithmétique se retrouvent également dans les mathématiques égyptiennes anciennes , remontant au papyrus mathématique Rhind vers  1550 av . J.-C. Les algorithmes ont ensuite été utilisés dans les mathématiques hellénistiques anciennes . Deux exemples sont le crible d'Ératosthène , qui a été décrit dans l' Introduction à l'arithmétique de Nicomaque , et l' algorithme euclidien , qui a été décrit pour la première fois dans les Éléments d'Euclide ( vers  300 av. J.-C. ). Les exemples de mathématiques indiennes anciennes incluent les Shulba Sutras , l' école du Kerala et le Brāhmasphuṭasiddhānta .

Le premier algorithme cryptographique permettant de déchiffrer un code crypté a été développé par Al-Kindi , un mathématicien arabe du IXe siècle, dans A Manuscript On Deciphering Cryptographic Messages . Il a donné la première description de la cryptanalyse par analyse de fréquence , le premier algorithme de décryptage de code.

Bolter considère l'invention de l'horloge à poids comme « l'invention clé [de l'Europe au Moyen Âge] », en particulier le mécanisme d'échappement à verge produisant le tic-tac d'une horloge mécanique. « La machine automatique précise » a immédiatement conduit aux « automates mécaniques » au XIIIe siècle et aux « machines informatiques » — les machines différentielles et analytiques de Charles Babbage et Ada Lovelace au milieu du XIXe siècle. Lovelace a conçu le premier algorithme destiné au traitement sur ordinateur, le moteur analytique de Babbage, qui est le premier appareil considéré comme un véritable ordinateur Turing-complet au lieu d'une simple calculatrice . Bien qu'une implémentation complète du deuxième appareil de Babbage n'ait pas été réalisée pendant des décennies après sa mort, Lovelace a été appelé « le premier programmeur de l'histoire ».

Bell et Newell (1971) écrivent que le métier Jacquard , précurseur des cartes Hollerith (cartes perforées), et les « technologies de commutation téléphonique » ont conduit au développement des premiers ordinateurs. Au milieu du XIXe siècle, le télégraphe , précurseur du téléphone, était utilisé dans le monde entier. À la fin du XIXe siècle, le téléscripteur ( vers les  années 1870 ) était utilisé, tout comme les cartes Hollerith (vers 1890). Puis vint le téléimprimeur ( vers  1910 ) avec son utilisation du code Baudot sur bande perforée .

Les réseaux de commutation téléphonique à relais électromécaniques furent inventés en 1835. Ils conduisirent à l'invention du dispositif d'addition numérique par George Stibitz en 1937. Alors qu'il travaillait aux laboratoires Bell, il observa l'utilisation « fastidieuse » des calculatrices mécaniques à engrenages. « Il rentra chez lui un soir de 1937 avec l'intention de tester son idée... Une fois le bricolage terminé, Stibitz avait construit un dispositif d'addition binaire ».

En 1928, une formalisation partielle du concept moderne d'algorithmes a commencé avec des tentatives de résolution du problème de décision ( Entscheidungsproblem ) posé par David Hilbert . Les formalisations ultérieures ont été formulées comme des tentatives de définition de la « calculabilité effective » ou de la « méthode effective ». Ces formalisations comprenaient les fonctions récursives de Gödel - Herbrand - Kleene de 1930, 1934 et 1935, le calcul lambda d' Alonzo Church de 1936, la Formulation 1 d' Emil Post de 1936 et les machines de Turing d' Alan Turing de 1936-37 et 1939.

Les algorithmes peuvent être exprimés dans de nombreux types de notation, notamment les langages naturels , les pseudo-codes , les organigrammes , les diagrammes Drakon , les langages de programmation ou les tables de contrôle (traitées par des interprètes ). Les expressions en langage naturel des algorithmes ont tendance à être verbeuses et ambiguës et sont rarement utilisées pour les algorithmes complexes ou techniques. Le pseudo-code, les organigrammes, les diagrammes Drakon et les tables de contrôle sont des expressions structurées d'algorithmes qui évitent les ambiguïtés courantes du langage naturel. Les langages de programmation servent principalement à exprimer des algorithmes sous une forme exécutable par ordinateur, mais sont également utilisés pour définir ou documenter des algorithmes.

Il existe de nombreuses représentations possibles et les programmes de la machine de Turing peuvent être exprimés comme une séquence de tables de machines (voir machine à états finis , table d'états-transitions et table de contrôle pour plus d'informations), comme des organigrammes et des diagrammes de drakon (voir diagramme d'état pour plus d'informations), comme une forme de code machine rudimentaire ou de code d'assemblage appelé « ensembles de quadruples », et plus encore. Les représentations d'algorithmes peuvent également être classées en trois niveaux acceptés de description de la machine de Turing : description de haut niveau, description d'implémentation et description formelle. Une description de haut niveau décrit les qualités de l'algorithme lui-même, en ignorant la manière dont il est implémenté sur la machine de Turing. Une description d'implémentation décrit la manière générale dont la machine déplace sa tête et stocke les données afin d'exécuter l'algorithme, mais ne donne pas d'états exacts. Dans le plus détaillé, une description formelle donne la table d'état exacte et la liste des transitions de la machine de Turing.

L'outil graphique appelé organigramme permet de décrire et de documenter un algorithme (et un programme informatique correspondant). Il comporte quatre symboles principaux : des flèches indiquant le déroulement du programme, des rectangles (SÉQUENCE, GOTO), des losanges (IF-THEN-ELSE) et des points (OR-tie). Les sous-structures peuvent « s'imbriquer » dans des rectangles, mais seulement si une seule sortie se produit depuis la superstructure.

Il est souvent important de savoir combien de temps, de stockage ou d'autres coûts un algorithme peut nécessiter. Des méthodes ont été développées pour l'analyse des algorithmes afin d'obtenir de telles réponses quantitatives (estimations) ; par exemple, un algorithme qui additionne les éléments d'une liste de n nombres aurait un besoin en temps de ⁠ ⁠ , en utilisant la notation O grand . L'algorithme n'a besoin de mémoriser que deux valeurs : la somme de tous les éléments jusqu'à présent et sa position actuelle dans la liste d'entrée. Si l'espace requis pour stocker les nombres d'entrée n'est pas compté, il a un besoin en espace de ⁠ ⁠ , sinon ⁠ ⁠ est requis.

Différents algorithmes peuvent effectuer la même tâche avec un ensemble d'instructions différent en moins ou plus de temps, d'espace ou d' effort que d'autres. Par exemple, un algorithme de recherche binaire (avec un coût ⁠ ⁠ ) surpasse une recherche séquentielle (coût ⁠ ⁠ ) lorsqu'il est utilisé pour des recherches dans des tableaux sur des listes ou des tableaux triés.

L' analyse et l'étude des algorithmes sont une discipline de l'informatique . Les algorithmes sont souvent étudiés de manière abstraite, sans référence à un langage de programmation ou à une implémentation spécifique. L'analyse des algorithmes ressemble à d'autres disciplines mathématiques car elle se concentre sur les propriétés de l'algorithme et non sur son implémentation. Le pseudo-code est typique de l'analyse car il s'agit d'une représentation simple et générale. La plupart des algorithmes sont implémentés sur des plates-formes matérielles/logicielles particulières et leur efficacité algorithmique est testée à l'aide de code réel. L'efficacité d'un algorithme particulier peut être insignifiante pour de nombreux problèmes « ponctuels », mais elle peut être critique pour les algorithmes conçus pour une utilisation interactive rapide, commerciale ou scientifique à long terme. Le passage d'un petit n à un grand n expose fréquemment des algorithmes inefficaces qui sont par ailleurs bénins.

Les tests empiriques sont utiles pour découvrir des interactions inattendues qui affectent les performances. Les tests de référence peuvent être utilisés pour comparer les améliorations potentielles avant/après d'un algorithme après l'optimisation du programme. Les tests empiriques ne peuvent cependant pas remplacer l'analyse formelle et ne sont pas faciles à réaliser.

Pour illustrer les améliorations potentielles possibles même dans des algorithmes bien établis, une innovation récente importante, liée aux algorithmes FFT (largement utilisés dans le domaine du traitement d'images), peut réduire le temps de traitement jusqu'à 1 000 fois pour des applications comme l'imagerie médicale. En général, les améliorations de vitesse dépendent de propriétés spéciales du problème, qui sont très courantes dans les applications pratiques. Des accélérations de cette ampleur permettent aux appareils informatiques qui font un usage intensif du traitement d'images (comme les appareils photo numériques et les équipements médicaux) de consommer moins d'énergie.

La conception d'algorithmes est une méthode ou un processus mathématique de résolution de problèmes et d'ingénierie d'algorithmes. La conception d'algorithmes fait partie de nombreuses théories de résolution, telles que la division pour régner ou la programmation dynamique dans le cadre de la recherche opérationnelle . Les techniques de conception et de mise en œuvre de conceptions d'algorithmes sont également appelées modèles de conception d'algorithmes, avec des exemples incluant le modèle de méthode de modèle et le modèle de décorateur. L'un des aspects les plus importants de la conception d'algorithmes est l'efficacité des ressources (temps d'exécution, utilisation de la mémoire) ; la notation O est utilisée pour décrire par exemple la croissance du temps d'exécution d'un algorithme à mesure que la taille de son entrée augmente.

Selon la thèse de Church-Turing , tout algorithme peut être calculé par tout modèle complet de Turing . La complétude de Turing ne nécessite que quatre types d'instructions : GOTO conditionnel, GOTO inconditionnel, affectation, HALT. Cependant, Kemeny et Kurtz observent que, bien que l'utilisation « indisciplinée » de GOTO inconditionnels et de GOTO conditionnels IF-THEN puisse donner lieu à du « code spaghetti », un programmeur peut écrire des programmes structurés en utilisant uniquement ces instructions ; d'un autre côté, « il est également possible, et pas trop difficile, d'écrire des programmes mal structurés dans un langage structuré ». Tausworthe augmente les trois structures canoniques de Böhm-Jacopini : SEQUENCE, IF-THEN-ELSE et WHILE-DO, avec deux autres : DO-WHILE et CASE. Un avantage supplémentaire d'un programme structuré est qu'il se prête aux preuves d'exactitude en utilisant l'induction mathématique .

En soi, les algorithmes ne sont généralement pas brevetables. Aux États-Unis, une revendication consistant uniquement en de simples manipulations de concepts abstraits, de nombres ou de signaux ne constitue pas un « processus » (USPTO 2006), de sorte que les algorithmes ne sont pas brevetables (comme dans l'affaire Gottschalk c. Benson ). Cependant, les applications pratiques des algorithmes sont parfois brevetables. Par exemple, dans l'affaire Diamond c. Diehr , l'application d'un algorithme de rétroaction simple pour aider au durcissement du caoutchouc synthétique a été jugée brevetable. Le brevetage des logiciels est controversé, et il existe des brevets critiqués impliquant des algorithmes, en particulier des algorithmes de compression de données , comme le brevet LZW d' Unisys . De plus, certains algorithmes cryptographiques sont soumis à des restrictions d'exportation (voir l'exportation de la cryptographie ).

Récursivité

Un algorithme récursif s'invoque lui-même de manière répétée jusqu'à ce qu'une condition de terminaison soit remplie. Il s'agit d'une méthode de programmation fonctionnelle courante. Les algorithmes itératifs utilisent des répétitions telles que des boucles ou des structures de données telles que des piles pour résoudre des problèmes. Les problèmes peuvent être adaptés à une implémentation ou à une autre. Les Tours de Hanoi sont un casse-tête généralement résolu à l'aide d'une implémentation récursive. Chaque version récursive a une version itérative équivalente (mais éventuellement plus ou moins complexe), et vice versa.

Série, parallèle ou distribué

Les algorithmes sont généralement abordés en partant du principe que les ordinateurs exécutent une instruction d'un algorithme à la fois sur des ordinateurs série. Les algorithmes série sont conçus pour ces environnements, contrairement aux algorithmes parallèles ou distribués . Les algorithmes parallèles tirent parti des architectures informatiques dans lesquelles plusieurs processeurs peuvent travailler sur un problème en même temps. Les algorithmes distribués utilisent plusieurs machines connectées via un réseau informatique. Les algorithmes parallèles et distribués divisent le problème en sous-problèmes et collectent les résultats ensemble. La consommation de ressources dans ces algorithmes ne correspond pas seulement aux cycles de processeur sur chaque processeur, mais également à la surcharge de communication entre les processeurs. Certains algorithmes de tri peuvent être parallélisés efficacement, mais leur surcharge de communication est coûteuse. Les algorithmes itératifs sont généralement parallélisables, mais certains problèmes n'ont pas d'algorithmes parallèles et sont appelés problèmes intrinsèquement sériels.

Déterministe ou non déterministe

Les algorithmes déterministes résolvent le problème en prenant une décision exacte à chaque étape, tandis que les algorithmes non déterministes résolvent les problèmes en devinant. Les suppositions sont généralement rendues plus précises grâce à l'utilisation d' heuristiques .

Exacte ou approximative

Alors que de nombreux algorithmes parviennent à une solution exacte, les algorithmes d'approximation recherchent une approximation proche de la vraie solution. De tels algorithmes ont une valeur pratique pour de nombreux problèmes difficiles. Par exemple, le problème du sac à dos , où il y a un ensemble d'articles et l'objectif est de remplir le sac à dos pour obtenir la valeur totale maximale. Chaque article a un certain poids et une certaine valeur. Le poids total qui peut être transporté n'est pas supérieur à un nombre fixe X. Ainsi, la solution doit prendre en compte le poids des articles ainsi que leur valeur.

Algorithme quantique

Les algorithmes quantiques s'appuient sur un modèle réaliste de calcul quantique . Le terme est généralement utilisé pour les algorithmes qui semblent intrinsèquement quantiques ou qui utilisent une caractéristique essentielle de l'informatique quantique, comme la superposition quantique ou l'intrication quantique .

Une autre façon de classer les algorithmes est de les classer selon leur méthodologie de conception ou paradigme . Voici quelques paradigmes courants :

Recherche par force brute ou recherche exhaustive

La force brute est une méthode de résolution de problèmes qui consiste à essayer systématiquement toutes les options possibles jusqu'à ce que la solution optimale soit trouvée. Cette approche peut prendre beaucoup de temps, car elle nécessite de tester toutes les combinaisons possibles de variables. Elle est souvent utilisée lorsque d'autres méthodes ne sont pas disponibles ou trop complexes. La force brute peut résoudre une variété de problèmes, notamment la recherche du chemin le plus court entre deux points et le déchiffrage de mots de passe.

Diviser pour mieux régner

Un algorithme de division et de conquête réduit de manière répétée un problème à une ou plusieurs instances plus petites de lui-même (généralement de manière récursive ) jusqu'à ce que les instances soient suffisamment petites pour être résolues facilement. Le tri par fusion est un exemple de division et de conquête, où une liste non ordonnée peut être divisée en segments contenant un élément et le tri de la liste entière peut être obtenu en fusionnant les segments. Une variante plus simple de division et de conquête est appelée algorithme de diminution et de conquête , qui résout un sous-problème identique et utilise la solution pour résoudre le problème plus important. Diviser pour régner divise le problème en plusieurs sous-problèmes et donc l'étape de conquête est plus complexe que les algorithmes de diminution et de conquête. Un exemple d'algorithme de diminution et de conquête est l' algorithme de recherche binaire .

Recherche et dénombrement

De nombreux problèmes (comme jouer aux échecs ) peuvent être modélisés comme des problèmes sur des graphes . Un algorithme d'exploration de graphe spécifie des règles pour se déplacer dans un graphe et est utile pour de tels problèmes. Cette catégorie comprend également les algorithmes de recherche , l'énumération par branchement et par limite et le retour en arrière .

Algorithme randomisé

De tels algorithmes font des choix de manière aléatoire (ou pseudo-aléatoire). Ils peuvent être utilisés pour trouver des solutions approximatives lorsque la recherche de solutions exactes peut s'avérer difficile (voir la méthode heuristique ci-dessous). Pour certains problèmes, les approximations les plus rapides doivent impliquer une part d'aléatoire . La question de savoir si les algorithmes randomisés avec une complexité temporelle polynomiale peuvent être l'algorithme le plus rapide pour certains problèmes est une question ouverte connue sous le nom de problème P versus NP . Il existe deux grandes classes de tels algorithmes :

1. Les algorithmes de Monte Carlo renvoient une réponse correcte avec une probabilité élevée. Par exemple, RP est la sous-classe de ceux-ci qui s'exécutent en temps polynomial .
2. Les algorithmes de Las Vegas renvoient toujours la bonne réponse, mais leur temps d'exécution n'est lié que de manière probabiliste, par exemple ZPP .

Réduction de la complexité

Cette technique transforme des problèmes difficiles en problèmes plus connus, résolubles avec des algorithmes asymptotiquement optimaux (espérons-le) . L'objectif est de trouver un algorithme réducteur dont la complexité n'est pas dominée par les algorithmes réduits résultants. Par exemple, un algorithme de sélection trouve la médiane d'une liste non triée en triant d'abord la liste (la partie coûteuse), puis en retirant l'élément du milieu de la liste triée (la partie bon marché). Cette technique est également connue sous le nom de transformer et conquérir .

Retour en arrière

Dans cette approche, plusieurs solutions sont élaborées de manière incrémentale et abandonnées lorsqu’il est déterminé qu’elles ne peuvent pas conduire à une solution complète valide.

Pour les problèmes d'optimisation, il existe une classification plus spécifique des algorithmes ; un algorithme pour de tels problèmes peut appartenir à une ou plusieurs des catégories générales décrites ci-dessus ainsi qu'à l'une des suivantes :

Programmation linéaire

Lors de la recherche de solutions optimales à une fonction linéaire liée par des contraintes d'égalité et d'inégalité linéaires, les contraintes peuvent être utilisées directement pour produire des solutions optimales. Il existe des algorithmes qui peuvent résoudre n'importe quel problème de cette catégorie, comme l' algorithme du simplexe populaire . Les problèmes qui peuvent être résolus avec la programmation linéaire incluent le problème du flux maximal pour les graphes orientés. Si un problème nécessite également que l'une des inconnues soit un entier , il est alors classé dans la programmation en nombres entiers . Un algorithme de programmation linéaire peut résoudre un tel problème s'il peut être prouvé que toutes les restrictions pour les valeurs entières sont superficielles, c'est-à-dire que les solutions satisfont de toute façon ces restrictions. Dans le cas général, un algorithme spécialisé ou un algorithme qui trouve des solutions approximatives est utilisé, selon la difficulté du problème.

Programmation dynamique

Lorsqu'un problème présente des sous-structures optimales (ce qui signifie que la solution optimale peut être construite à partir de solutions optimales aux sous-problèmes) et des sous-problèmes qui se chevauchent (ce qui signifie que les mêmes sous-problèmes sont utilisés pour résoudre de nombreuses instances de problèmes différentes), une approche plus rapide appelée programmation dynamique évite de recalculer les solutions. Par exemple, avec l'algorithme de Floyd-Warshall , le chemin le plus court entre un sommet de départ et un sommet d'arrivée dans un graphe pondéré peut être trouvé en utilisant le chemin le plus court vers le but à partir de tous les sommets adjacents. La programmation dynamique et la mémorisation vont de pair. Contrairement à la division pour mieux régner, les sous-problèmes de programmation dynamique se chevauchent souvent. La différence entre la programmation dynamique et la récursivité simple réside dans la mise en cache ou la mémorisation des appels récursifs. Lorsque les sous-problèmes sont indépendants et ne se répètent pas, la mémorisation n'est d'aucune aide ; par conséquent, la programmation dynamique n'est pas applicable à tous les problèmes complexes. L'utilisation de la programmation dynamique par mémorisation réduit la complexité de nombreux problèmes d'exponentielle à polynomiale.

La méthode gourmande

Les algorithmes gloutons , de manière similaire à la programmation dynamique, fonctionnent en examinant les sous-structures, dans ce cas non pas du problème mais d'une solution donnée. De tels algorithmes commencent avec une solution et l'améliorent en y apportant de petites modifications. Pour certains problèmes, ils trouvent toujours la solution optimale, mais pour d'autres, ils peuvent s'arrêter aux optima locaux . L'utilisation la plus courante des algorithmes gloutons est la recherche d'arbres couvrants minimaux de graphes sans cycles négatifs. Huffman Tree , Kruskal , Prim , Sollin sont des algorithmes gloutons qui peuvent résoudre ce problème d'optimisation.

La méthode heuristique

Dans les problèmes d'optimisation , les algorithmes heuristiques trouvent des solutions proches de la solution optimale lorsque la recherche de la solution optimale est impossible. Ces algorithmes se rapprochent de plus en plus de la solution optimale au fur et à mesure de leur progression. En principe, s'ils sont exécutés pendant une durée infinie, ils trouveront la solution optimale. En pratique, ils peuvent idéalement trouver une solution très proche de la solution optimale dans un délai relativement court. Ces algorithmes comprennent la recherche locale , la recherche taboue , le recuit simulé et les algorithmes génétiques . Certains, comme le recuit simulé, sont des algorithmes non déterministes tandis que d'autres, comme la recherche taboue, sont déterministes. Lorsqu'une limite sur l'erreur de la solution non optimale est connue, l'algorithme est en outre classé comme un algorithme d'approximation .

L'un des algorithmes les plus simples consiste à trouver le plus grand nombre dans une liste de nombres d'ordre aléatoire. Pour trouver la solution, il faut examiner chaque nombre de la liste. Il en résulte un algorithme simple, qui peut être décrit en termes simples comme suit :

Description de haut niveau :

1. Si un ensemble de nombres est vide, alors il n’y a pas de nombre le plus élevé.
2. Supposons que le premier nombre de l’ensemble soit le plus grand.
3. Pour chaque nombre restant dans l'ensemble : si ce nombre est supérieur au plus grand nombre actuel, il devient le nouveau plus grand.
4. Lorsqu'il ne reste plus de nombres non vérifiés dans l'ensemble, considérez le plus grand nombre actuel comme le plus grand de l'ensemble.

Description (quasi-)formelle : Écrit en prose mais beaucoup plus proche du langage de haut niveau d'un programme informatique, voici le codage plus formel de l'algorithme en pseudo-code ou code pidgin :

Algorithme LargestNumber Entrée : une liste de nombres L . Sortie : Le plus grand nombre de la liste L . 

si 
L.size = 0 renvoie null le plus grand ← L [0] pour chaque 
élément 
de 
L , faire 
si 
élément > le plus grand , alors 
le plus grand ← élément 
renvoie 
le plus grand