En mathématiques et en informatique, un algorithme AL-gə-ridh-əm) est une spécification non ambiguë de la façon de résoudre une classe de problèmes. Les algorithmes peuvent effectuer des tâches de calcul, de traitement de données et de raisonnement automatisé.

En tant que méthode efficace, un algorithme peut être exprimé dans une quantité limitée d’espace et de temps et dans un langage formel bien défini pour calculer une fonction. Partant d’un état initial et d’une entrée initiale (peut-être vide), les instructions décrivent un calcul qui, lorsqu’il est exécuté, passe par un nombre fini d’états successifs bien définis, produisant finalement une sortie et se terminant à un état final. Le passage d’un état à l’autre n’est pas nécessairement déterministe; certains algorithmes, connus sous le nom d’algorithmes randomisés, incorporent une entrée aléatoire.

Le concept d’algorithme existe depuis des siècles et l’utilisation du concept peut être attribuée aux mathématiciens grecs, par exemple le crible d’Eratosthène et l’algorithme d’Euclide; le terme algorithme lui-même dérive du mathématicien du 9ème siècle Muḥammad ibn Mūsā al’Khwārizmī, latinisé «Algoritmi». Une formalisation partielle de ce qui deviendrait la notion moderne d’algorithme a commencé avec des tentatives de résoudre le problème de décision posé par David Hilbert en 1928. Les formalisations ultérieures ont été conçues comme des tentatives de définir la «calculabilité effective» ou la «méthode efficace». ; ces formalisations incluaient les fonctions récursives de Gödel-Herbrand-Kleene de 1930, 1934 et 1935, le lambda-calcul de l’Église d’Alonzo de 1936, la Formulation 1 d’Emil Post de 1936 et les machines Turing d’Alan Turing de 1936-7 et 1939.

Étymologie
Le mot «algorithme» a ses racines dans la latinisation du nom de Muhammad ibn Musa al-Khwarizmi dans un premier temps à algorismus. Al-Khwārizmī (Perse: خوارزمی, vers 780-850) était un mathématicien persan, astronome, géographe et érudit à la Maison de la Sagesse à Bagdad, dont le nom signifie «l’originaire de Khwarezm», une région qui faisait partie de Grand Iran et est maintenant en Ouzbékistan.

Vers 825, al-Khwarizmi a écrit un traité en langue arabe sur le système numéral hindou-arabe, qui a été traduit en latin au 12ème siècle sous le titre Algoritmi de numero Indorum. Ce titre signifie « Algoritmi sur les nombres des Indiens », où « Algoritmi » était la latinisation du traducteur du nom d’Al-Khwarizmi. Al-Khwarizmi était le mathématicien le plus lu en Europe à la fin du Moyen Âge, principalement à travers un autre de ses livres, l’algèbre. Dans le latin médiéval tardif, algorismus, «algorismo» anglais, la corruption de son nom, signifiait simplement le «système de nombre décimal». Au XVe siècle, sous l’influence du mot grec «numberριθμός» («arithmétique»), le mot latin a été modifié en algorithmes, et le terme anglais correspondant «algorithm» est attesté au XVIIe siècle; le sens moderne a été introduit au 19ème siècle.

En anglais, il a été utilisé pour la première fois vers 1230 puis par Chaucer en 1391. Les anglais ont adopté le terme français, mais ce n’est qu’à la fin du XIXe siècle que «algorithm» a pris le sens qu’il a en anglais moderne.

Une autre utilisation précoce du mot est à partir de 1240, dans un manuel intitulé Carmen de Algorismo composé par Alexandre de Villedieu. Cela commence ainsi:

Haec algorismus ars praesens dicitur, dans qua / Talibus Indorum fruimur bis quinque figuris.

qui se traduit par:

L’algorisme est l’art par lequel nous utilisons actuellement ces chiffres indiens, qui sont deux fois cinq.

Le poème est de quelques centaines de lignes et résume l’art de calculer avec le nouveau style de dés indiens, ou Talibus Indorum, ou chiffres hindous.

Définition informelle
Pour une présentation détaillée des différents points de vue sur la définition de « algorithme », voir Caractérisations d’algorithmes.
Une définition informelle pourrait être «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. Généralement, un programme est seulement un algorithme s’il s’arrête finalement.

Un exemple prototypique d’un algorithme est l’algorithme euclidien pour déterminer le diviseur commun maximal de deux nombres entiers; un exemple (il y en a d’autres) est décrit par l’organigramme ci-dessus et comme exemple dans une section ultérieure.

Boolos, Jeffrey & 1974, 1999 offrent une signification informelle du mot dans la citation suivante:

Aucun être humain ne peut écrire assez vite, ou assez longtemps, ou assez petit † († « plus petit et plus petit sans limite … vous essaieriez d’écrire sur des molécules, sur des atomes, sur des électrons ») pour lister tous les membres d’un infiniment infini en écrivant leurs noms, les uns après les autres, dans une certaine notation. Mais les humains peuvent faire quelque chose d’aussi utile, dans le cas de certains ensembles infiniment infinis: Ils peuvent donner des instructions explicites pour déterminer le nième membre de l’ensemble, pour des n finis arbitraires. De telles instructions doivent être données de façon très explicite, sous une forme dans laquelle elles pourraient être suivies par une machine de calcul, ou par un humain qui n’est capable de réaliser que des opérations très élémentaires sur les symboles.

Un « ensemble infiniment infini » est celui dont les éléments peuvent être mis en correspondance biunivoque avec les entiers. Ainsi, Boolos et Jeffrey disent qu’un algorithme implique des instructions pour un processus qui « crée » des entiers de sortie à partir d’un entier « d’entrée » arbitraire ou d’entiers qui, en théorie, peuvent être arbitrairement grands. Ainsi, un algorithme peut être une équation algébrique telle que y = m + n – deux «variables d’entrée» arbitraires m et n qui produisent une sortie y. Mais les tentatives de différents auteurs de définir la notion indiquent que le mot implique beaucoup plus que cela, quelque chose de l’ordre de (pour l’exemple d’addition):

Des instructions précises (dans un langage compris par « l’ordinateur ») pour un processus rapide, efficace, « bon » qui spécifie les « mouvements » de « l’ordinateur » (machine ou humain, équipé des informations et capacités internes nécessaires) pour trouver , décoder, puis traiter arbitrairement les entiers / symboles d’entrée m et n, les symboles + et = … et produire « efficacement », dans un temps « raisonnable », l’entier de sortie y à un endroit spécifié et dans un format spécifié.
Le concept d’algorithme est également utilisé pour définir la notion de décidabilité. Cette notion est centrale pour expliquer comment les systèmes formels naissent d’un petit ensemble d’axiomes et de règles. En logique, le temps que nécessite un algorithme ne peut être mesuré, car il n’est apparemment pas lié à notre dimension physique habituelle. De telles incertitudes, qui caractérisent le travail en cours, sont à l’origine de l’indisponibilité d’une définition de l’algorithme qui convient à la fois à l’utilisation concrète (dans un certain sens) et à l’utilisation abstraite du terme.

Formalisation
Les algorithmes sont essentiels à la façon dont les ordinateurs traitent les données. De nombreux programmes informatiques contiennent des algorithmes qui détaillent les instructions spécifiques qu’un ordinateur doit exécuter (dans un ordre spécifique) pour exécuter une tâche spécifique, comme le calcul des chèques de paie des employés ou l’impression des bulletins des étudiants. Ainsi, un algorithme peut être considéré comme n’importe quelle séquence d’opérations pouvant être simulée par un système Turing-complet. Les auteurs qui affirment cette thèse incluent Minsky (1967), Savage (1987) et Gurevich (2000):

Minsky: « Mais nous maintiendrons aussi, avec Turing … que toute procédure qui pourrait » naturellement « être qualifiée d’efficace, peut en réalité être réalisée par une machine (simple). ses faveurs sont difficiles à réfuter « .

Gurevich: « … L’argument informel de Turing en faveur de sa thèse justifie une thèse plus forte: chaque algorithme peut être simulé par une machine de Turing … selon Savage [1987], un algorithme est un processus de calcul défini par une machine de Turing » .

Généralement, lorsqu’un algorithme est associé à des informations de traitement, les données peuvent être lues à partir d’une source d’entrée, écrites sur un périphérique de sortie et stockées pour un traitement ultérieur. Les données stockées sont considérées comme faisant partie de l’état interne de l’entité exécutant l’algorithme. En pratique, l’état est stocké dans une ou plusieurs structures de données.

Pour un tel processus de calcul, l’algorithme doit être rigoureusement défini: spécifié de la façon dont il s’applique dans toutes les circonstances possibles qui pourraient survenir. Autrement dit, toutes les étapes conditionnelles doivent être systématiquement traitées, au cas par cas; les critères pour chaque cas doivent être clairs (et calculables).

Parce qu’un algorithme est une liste précise d’étapes précises, l’ordre de calcul est toujours crucial pour le fonctionnement de l’algorithme. Les instructions sont généralement supposées être listées explicitement, et sont décrites comme commençant « par le haut » et allant « vers le bas », une idée qui est décrite plus formellement par le flux de contrôle.

Jusqu’à présent, cette discussion de la formalisation d’un algorithme a assumé les prémisses de la programmation impérative. C’est la conception la plus courante, et elle tente de décrire une tâche de manière discrète, « mécanique ». L’opération d’assignation, qui définit la valeur d’une variable, est unique à cette conception des algorithmes formalisés. Il dérive de l’intuition de « mémoire » comme un bloc-notes. Il y a un exemple ci-dessous d’une telle affectation.

Pour d’autres conceptions de ce qui constitue un algorithme, voir la programmation fonctionnelle et la programmation logique.

Exprimer des algorithmes
Les algorithmes peuvent être exprimés dans de nombreux types de notation, y compris les langages naturels, les pseudocodes, les organigrammes, les diagrammes drakon, les langages de programmation ou les tables de contrôle (traités par des interprètes). Les expressions en langage naturel des algorithmes ont tendance à être verbeuses et ambiguës et sont rarement utilisées pour des algorithmes complexes ou techniques. Le pseudocode, les organigrammes, les diagrammes drakon et les tables de contrôle sont des moyens structurés d’exprimer des algorithmes qui évitent beaucoup des ambiguïtés communes dans les énoncés en langage naturel. Les langages de programmation sont principalement destinés à exprimer des algorithmes sous une forme pouvant être exécutée par un ordinateur, mais sont souvent utilisés pour définir ou documenter des algorithmes.

Il y a une grande variété de représentations possibles et on peut exprimer un programme donné de machine de Turing comme une séquence de tables machine (voir plus sur machine à états finis, table de transition d’état et table de contrôle), comme organigrammes et drakons. diagramme d’état), ou comme une forme de code machine rudimentaire ou un code d’assemblage appelé « ensembles de quadruples » (voir plus à la machine de Turing).

Les représentations d’algorithmes peuvent être classées en trois niveaux acceptés de description de machine de Turing:

1 Description de haut niveau
« … en prose pour décrire un algorithme, en ignorant les détails de l’implémentation A ce niveau, nous n’avons pas besoin de mentionner comment la machine gère sa bande ou sa tête. »
2 Description de l’implémentation
« … la prose utilisée pour définir la façon dont la machine de Turing utilise sa tête et la façon dont elle stocke les données sur sa bande.A ce niveau, nous ne donnons pas de détails sur les états ou la fonction de transition. »
3 Description formelle
Le plus détaillé, « niveau le plus bas », donne la « table d’état » de la machine de Turing.
Pour un exemple de l’algorithme simple « Ajouter m + n » décrit dans les trois niveaux, voir Algorithme # Exemples.

la mise en oeuvre
La plupart des algorithmes sont destinés à être implémentés en tant que programmes informatiques. Cependant, des algorithmes sont également mis en œuvre par d’autres moyens, tels que dans un réseau neuronal biologique (par exemple, le cerveau humain mettant en œuvre l’arithmétique ou un insecte à la recherche de nourriture), dans un circuit électrique ou dans un dispositif mécanique.

Algorithmes informatiques
Dans les systèmes informatiques, un algorithme est essentiellement une instance de logique écrite dans un logiciel par des développeurs de logiciels pour être efficace pour le ou les ordinateurs « cibles » voulus afin de produire une sortie à partir d’une entrée donnée (peut-être nulle). Un algorithme optimal, même exécuté sur du matériel ancien, produirait des résultats plus rapides qu’un algorithme non optimal (complexité plus élevée) dans le même but, fonctionnant dans un matériel plus efficace; c’est pourquoi les algorithmes, comme le matériel informatique, sont considérés comme de la technologie.

Programmes « élégants » (compacts), programmes « bons » (rapides): La notion de « simplicité et d’élégance » apparaît de façon informelle chez Knuth et précisément chez Chaitin:

Knuth: « … nous voulons de bons algorithmes dans un sens esthétique vaguement défini Un critère … est la durée de l’algorithme … D’autres critères sont l’adaptabilité de l’algorithme aux ordinateurs, sa simplicité et son élégance. , etc »
Chaitin: « … un programme est » élégant « , c’est-à-dire que c’est le programme le plus petit possible pour produire le résultat »
Chaitin préfigure sa définition avec: « Je vais montrer que vous ne pouvez pas prouver qu’un programme est » élégant « – une telle preuve résoudrait le problème de l’Halting (ibid).

Algorithme versus fonction calculable par un algorithme: Pour une fonction donnée, plusieurs algorithmes peuvent exister. Ceci est vrai, même sans étendre le jeu d’instructions disponible au programmeur. Rogers observe qu ‘«il est … important de distinguer entre la notion d’algorithme, c’est-à-dire la procédure et la notion de fonction calculable par algorithme, c’est-à-dire la cartographie générée par procédure.

Malheureusement, il peut y avoir un compromis entre la bonté (vitesse) et l’élégance (compacité) – un programme élégant peut prendre plus de mesures pour compléter un calcul qu’un moins élégant. Un exemple utilisant l’algorithme d’Euclide apparaît ci-dessous.

Ordinateurs (et computeurs), modèles de calcul: Un ordinateur (ou «computeur» humain) est un type restreint de machine, un «dispositif mécanique déterministe discret» qui suit aveuglément ses instructions. Les modèles primitifs de Melzak et Lambek ont ​​réduit cette notion à quatre éléments: (i) des emplacements discrets et distincts, (ii) des compteurs discrets et indiscernables (iii) un agent, et (iv) une liste d’instructions efficaces par rapport à la capacité du agent.

Simulation d’un algorithme: langage informatique (computor): Knuth conseille au lecteur que « la meilleure façon d’apprendre un algorithme est de l’essayer … prendre immédiatement un stylo et du papier et travailler sur un exemple ». Mais qu’en est-il une simulation ou une exécution de la chose réelle? Le programmeur doit traduire l’algorithme dans un langage que le simulateur / ordinateur / computeur peut effectivement exécuter. Stone en donne un exemple: en calculant les racines d’une équation quadratique, le computeur doit savoir prendre une racine carrée. Si ce n’est pas le cas, l’algorithme, pour être efficace, doit fournir un ensemble de règles pour extraire une racine carrée.

Cela signifie que le programmeur doit connaître un « langage » efficace par rapport à l’agent informatique cible (ordinateur / ordinateur).

Analyse algorithmique
Il est souvent important de savoir quelle quantité d’une ressource particulière (comme le temps ou le stockage) est théoriquement nécessaire pour un algorithme donné. Des méthodes ont été développées pour l’analyse d’algorithmes afin d’obtenir de telles réponses quantitatives (estimations); par exemple, l’algorithme de tri ci-dessus a une exigence de temps de O (n), en utilisant la grande notation O avec n comme la longueur de la liste. À tout moment, l’algorithme n’a besoin que de se souvenir de deux valeurs: le plus grand nombre trouvé jusqu’à présent, et sa position actuelle dans la liste d’entrée. Par conséquent, il est dit avoir une exigence d’espace de O (1), si l’espace requis pour stocker les nombres d’entrée n’est pas compté, ou O (n) s’il est compté.

Formel versus empirique
L’analyse et l’étude des algorithmes est une discipline de l’informatique, et est souvent pratiquée de manière abstraite sans l’utilisation d’un langage de programmation spécifique ou de mise en œuvre. En ce sens, l’analyse algorithmique ressemble à d’autres disciplines mathématiques en ce qu’elle se concentre sur les propriétés sous-jacentes de l’algorithme et non sur les spécificités d’une implémentation particulière. Habituellement, le pseudocode est utilisé pour l’analyse car c’est la représentation la plus simple et la plus générale. Cependant, au final, la plupart des algorithmes sont généralement implémentés sur des plates-formes matérielles / logicielles particulières et leur efficacité algorithmique est finalement mise à l’épreuve en utilisant du code réel. Pour résoudre un problème «unique», l’efficacité d’un algorithme particulier peut ne pas avoir de conséquences significatives (sauf si n est extrêmement important), mais pour les algorithmes conçus pour un usage scientifique interactif, commercial ou de longue durée, il peut être critique. La mise à l’échelle de n petit à grand n expose fréquemment des algorithmes inefficaces qui sont par ailleurs bénins.

Efficacité d’exécution
Pour illustrer les améliorations potentielles possibles même dans des algorithmes bien établis, une innovation significative récente, relative aux algorithmes FFT (fortement utilisés dans le traitement d’image), peut réduire le temps de traitement jusqu’à 1000 fois pour des applications comme l’imagerie médicale. En général, les améliorations de vitesse dépendent des propriétés spéciales du problème, qui sont très courantes dans les applications pratiques. Les accélérations de cette ampleur permettent aux appareils informatiques qui utilisent largement le traitement d’image (comme les appareils photo numériques et les équipements médicaux) de consommer moins d’énergie.

Classification
Il existe différentes façons de classer les algorithmes, chacun avec ses propres mérites.

Par implémentation
Une façon de classifier les algorithmes est par des moyens de mise en œuvre.

Récursivité
Un algorithme récursif est un algorithme qui invoque (fait référence à) lui-même à plusieurs reprises jusqu’à ce qu’une certaine condition (également appelée condition de terminaison) concorde, ce qui est une méthode commune à la programmation fonctionnelle. Les algorithmes itératifs utilisent des constructions répétitives comme des boucles et parfois des structures de données supplémentaires comme des piles pour résoudre les problèmes donnés. Certains problèmes sont naturellement adaptés à une implémentation ou à l’autre. Par exemple, les tours de Hanoi sont bien comprises en utilisant une implémentation récursive. Chaque version récursive a une version itérative équivalente (mais éventuellement plus ou moins complexe), et vice versa.

Logique
Un algorithme peut être vu comme une déduction logique contrôlée. Cette notion peut être exprimée comme suit: Algorithm = logic + control. La composante logique exprime les axiomes qui peuvent être utilisés dans le calcul et la composante de contrôle détermine la manière dont la déduction est appliquée aux axiomes. C’est la base du paradigme de la programmation logique. Dans les langages de programmation logiques purs, le composant de contrôle est fixe et les algorithmes sont spécifiés en ne fournissant que le composant logique. L’attrait de cette approche est la sémantique élégante: un changement dans les axiomes a un changement bien défini dans l’algorithme.

Série, parallèle ou distribué
Les algorithmes sont généralement discutés en supposant que les ordinateurs exécutent une instruction d’un algorithme à la fois. Ces ordinateurs sont parfois appelés ordinateurs série. Un algorithme conçu pour un tel environnement est appelé un algorithme en série, par opposition aux algorithmes parallèles ou aux algorithmes distribués. Les algorithmes parallèles tirent parti des architectures informatiques où plusieurs processeurs peuvent travailler sur un problème en même temps, alors que les algorithmes distribués utilisent plusieurs machines connectées à un réseau informatique. Les algorithmes parallèles ou distribués divisent le problème en sous-problèmes plus symétriques ou asymétriques et rassemblent les résultats ensemble. La consommation de ressources dans de tels algorithmes n’est pas seulement des 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 leurs frais de communication sont élevés. Les algorithmes itératifs sont généralement parallélisables. Certains problèmes n’ont pas d’algorithmes parallèles et sont appelés par nature des problèmes sériels.

Déterministe ou non-déterministe
Les algorithmes déterministes résolvent le problème avec une décision exacte à chaque étape de l’algorithme, tandis que les algorithmes non déterministes résolvent les problèmes par devinettes, bien que les estimations typiques soient plus précises grâce à l’utilisation d’heuristiques.

Exact ou approximatif
Alors que de nombreux algorithmes atteignent une solution exacte, les algorithmes d’approximation recherchent une approximation plus proche de la vraie solution. L’approximation peut être atteinte soit en utilisant une stratégie déterministe ou aléatoire. De tels algorithmes ont une valeur pratique pour de nombreux problèmes difficiles. L’un des exemples d’un algorithme approximatif est le problème Knapsack. Le problème Knapsack est un problème où il existe un ensemble d’éléments donnés. Le but du problème est d’emballer le sac pour obtenir la valeur totale maximale. Chaque article a un poids et une certaine valeur. Le poids total que nous pouvons transporter n’est pas plus élevé que le nombre X fixé. Nous devons donc considérer le poids des articles ainsi que leur valeur.

Algorithme quantique
Ils fonctionnent sur un modèle réaliste de calcul quantique. Le terme est généralement utilisé pour les algorithmes qui semblent intrinsèquement quantique, ou utilise une caractéristique essentielle du calcul quantique, comme la superposition quantique ou l’intrication quantique.

Par le paradigme du design
Une autre façon de classifier les algorithmes est par leur méthodologie de conception ou paradigme. Il y a un certain nombre de paradigmes, chacun différent de l’autre. De plus, chacune de ces catégories comprend de nombreux types d’algorithmes différents. Certains paradigmes communs sont:

Brute-force ou recherche exhaustive
C’est la méthode naïve d’essayer toutes les solutions possibles pour voir ce qui est le meilleur.

Diviser et conquérir
Un algorithme de division et de conquête réduit de façon répétée une instance d’un problème à une ou plusieurs instances plus petites du même problème (généralement récursivement) jusqu’à ce que les instances soient suffisamment petites pour être résolues facilement. Un tel exemple de division et de conquête est le tri par fusion. Le tri peut être effectué sur chaque segment de données après la division des données en segments et le tri des données entières peut être obtenu dans la phase de conquête en fusionnant les segments. Une variante plus simple de diviser pour régner est appelée un algorithme de diminution et de conquête, qui résout un sous-problème identique et utilise la solution de ce sous-problème pour résoudre le plus gros problème. Diviser pour régner divise le problème en plusieurs sous-problèmes et donc l’étape de la conquête est plus complexe que la réduction et la conquête des algorithmes. Un exemple d’algorithme de diminution et de conquête est l’algorithme de recherche binaire.

Recherche et énumération
De nombreux problèmes (comme jouer aux échecs) peuvent être modélisés comme des problèmes sur les graphiques. Un algorithme d’exploration de graphique spécifie des règles pour se déplacer autour d’un graphique et est utile pour de tels problèmes. Cette catégorie inclut également les algorithmes de recherche, l’énumération de branches et de liens et le retour arrière.
Algorithme randomisé

Réduction de la complexité
Cette technique consiste à résoudre un problème difficile en le transformant en un problème mieux connu pour lequel nous avons (espérons-le) des algorithmes asymptotiquement optimaux. Le but est de trouver un algorithme réducteur dont la complexité n’est pas dominée par l’algorithme réduit résultant. Par exemple, un algorithme de sélection pour trouver la médiane dans une liste non triée implique d’abord de trier la liste (la partie la plus chère) puis d’extraire l’élément central de la liste triée (la partie bon marché). Cette technique est également connue comme transformer et conquérir.

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

Programmation linéaire
Lors de la recherche de solutions optimales à une fonction linéaire liée à des contraintes linéaires d’égalité et d’inégalité, les contraintes du problème peuvent être directement utilisées pour produire les solutions optimales. Il y a des algorithmes qui peuvent résoudre n’importe quel problème dans cette catégorie, tel que l’algorithme simplex populaire. Les problèmes qui peuvent être résolus avec la programmation linéaire incluent le problème de débit maximum pour les graphes orientés. Si un problème nécessite en outre qu’une ou plusieurs des inconnues doivent être un entier, alors il est classé en programmation entière. 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é, en fonction de la difficulté du problème.
Programmation dynamique

Lorsqu’un problème présente des sous-structures optimales – ce qui signifie que la solution optimale à un problème 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 différents problèmes. ont déjà été calculés. Par exemple, l’algorithme de Floyd-Warshall, le chemin le plus court vers un but à partir d’un sommet dans un graphe pondéré peut être trouvé en utilisant le plus court chemin vers le but à partir de tous les sommets adjacents. La programmation dynamique et la mémoisation vont de pair. La principale différence entre la programmation dynamique et la division et la conquête réside dans le fait que les sous-problèmes sont plus ou moins indépendants dans la division et la conquête, alors que les sous-problèmes se chevauchent dans la programmation dynamique. La différence entre la programmation dynamique et la récursion directe réside dans la mise en cache ou la mémorisation des appels récursifs. Lorsque les sous-problèmes sont indépendants et qu’il n’y a pas de répétition, la mémo n’aide pas; par conséquent, la programmation dynamique n’est pas une solution pour tous les problèmes complexes. En utilisant la mémoisation ou en maintenant une table de sous-problèmes déjà résolus, la programmation dynamique réduit la nature exponentielle de nombreux problèmes à la complexité polynomiale.

La méthode gourmande
Un algorithme glouton est similaire à un algorithme de programmation dynamique en ce qu’il fonctionne en examinant les sous-structures, dans ce cas non pas du problème mais d’une solution donnée. De tels algorithmes commencent par une solution, qui peut être donnée ou construite d’une manière ou d’une autre, et l’améliorer en apportant de petites modifications. Pour certains problèmes, ils peuvent trouver la solution optimale tandis que pour d’autres, ils s’arrêtent à des optimums locaux, c’est-à-dire à des solutions qui ne peuvent pas être améliorées par l’algorithme mais qui ne sont pas optimales. L’utilisation la plus populaire des algorithmes gloutons est de trouver l’arbre couvrant minimal où trouver la solution optimale est possible avec cette méthode. Huffman Tree, Kruskal, Prim, Sollin sont des algorithmes gourmands qui peuvent résoudre ce problème d’optimisation.

La méthode heuristique
Dans les problèmes d’optimisation, des algorithmes heuristiques peuvent être utilisés pour trouver une solution proche de la solution optimale dans les cas où trouver la solution optimale est irréalisable. Ces algorithmes fonctionnent en se rapprochant de la solution optimale à mesure qu’ils progressent. En principe, s’ils sont exécutés pendant une durée infinie, ils trouveront la solution optimale. Leur mérite est qu’ils peuvent trouver une solution très proche de la solution optimale dans un temps relativement court. De tels algorithmes comprennent la recherche locale, la recherche de tabous, le recuit simulé et les algorithmes génétiques. Certains d’entre eux, comme le recuit simulé, sont des algorithmes non déterministes alors que d’autres, comme la recherche tabou, sont déterministes. Lorsqu’une limite de l’erreur de la solution non optimale est connue, l’algorithme est encore catégorisé comme un algorithme d’approximation.

Par domaine d’études
Chaque domaine de la science a ses propres problèmes et a besoin d’algorithmes efficaces. Des problèmes connexes dans un domaine sont souvent étudiés ensemble. Exemples de classes: algorithmes de recherche, algorithmes de tri, algorithmes de fusion, algorithmes numériques, algorithmes de graphes, algorithmes de chaînes, algorithmes géométriques computationnels, algorithmes combinatoires, algorithmes médicaux, apprentissage automatique, cryptographie, algorithmes de compression de données et techniques d’analyse syntaxique.

Les champs ont tendance à se chevaucher et l’algorithme avancé dans un domaine peut améliorer ceux d’autres champs, parfois complètement indépendants. Par exemple, la programmation dynamique a été inventée pour optimiser la consommation de ressources dans l’industrie, mais elle est maintenant utilisée pour résoudre un large éventail de problèmes dans de nombreux domaines.

Par complexité
Les algorithmes peuvent être classés en fonction de la quantité de temps qu’ils doivent remplir par rapport à leur taille d’entrée:

Temps constant: si le temps nécessaire à l’algorithme est le même, quelle que soit la taille de l’entrée. Par exemple un accès à un élément de tableau.
Temps linéaire: si le temps est proportionnel à la taille d’entrée. Par exemple, la traversée d’une liste.
Heure logarithmique: si l’heure est une fonction logarithmique de la taille d’entrée. Par exemple, un algorithme de recherche binaire.
Temps polynomial: si l’heure est une puissance de la taille d’entrée. Par exemple, l’algorithme de tri à bulles a une complexité temporelle quadratique.
Temps exponentiel: si l’heure est une fonction exponentielle de la taille d’entrée. Par exemple, recherche Brute-force.
Certains problèmes peuvent avoir plusieurs algorithmes de complexité différente, alors que d’autres problèmes peuvent ne pas avoir d’algorithmes ou d’algorithmes efficaces connus. Il existe également des mappings de certains problèmes à d’autres problèmes. En raison de cela, il a été jugé plus approprié de classer les problèmes eux-mêmes au lieu des algorithmes dans des classes d’équivalence basées sur la complexité des meilleurs algorithmes possibles pour eux.

Algorithmes continus
L’adjectif « continu » lorsqu’il est appliqué au mot « algorithme » peut signifier:

Un algorithme fonctionnant sur des données qui représentent des quantités continues, même si ces données sont représentées par des approximations discrètes – de tels algorithmes sont étudiés en analyse numérique; ou
Un algorithme sous la forme d’une équation différentielle qui fonctionne en continu sur les données, s’exécutant sur un ordinateur analogique.