Algorithme

Récursivité

Un algorithme récursif s'exécute de manière répétée jusqu'à ce qu'une condition d'arrêt soit satisfaite ; c'est une technique courante en programmation fonctionnelle . Les algorithmes itératifs utilisent des répétitions, comme des boucles ou des structures de données telles que les piles, pour résoudre des problèmes. Certains problèmes se prêtent mieux à l'une ou l'autre implémentation. Les tours de Hanoï sont un exemple de casse-tête souvent résolu par une implémentation récursive. À chaque version récursive correspond une version itérative équivalente (plus ou moins complexe), et inversement.

En série, en parallèle ou distribué

On aborde généralement les algorithmes en supposant que les ordinateurs exécutent une instruction à la fois sur des systèmes séquentiels. Les algorithmes séquentiels sont conçus pour ces environnements, contrairement aux algorithmes parallèles ou distribués . Les algorithmes parallèles tirent parti des architectures informatiques où plusieurs processeurs peuvent traiter un problème simultanément. Les algorithmes distribués utilisent plusieurs machines connectées via un réseau. Les algorithmes parallèles et distribués divisent le problème en sous-problèmes et regroupent ensuite les résultats. La consommation de ressources de ces algorithmes inclut non seulement les cycles processeur de chaque processeur, mais aussi les communications entre les processeurs. Certains algorithmes de tri peuvent être parallélisés efficacement, mais leurs communications sont coûteuses. Les algorithmes itératifs sont généralement parallélisables, mais certains problèmes ne possèdent pas d'algorithmes parallèles et sont dits intrinsèquement séquentiels.

Déterministe ou non déterministe

Les algorithmes déterministes résolvent le problème en prenant des décisions exactes à chaque étape ; tandis que les algorithmes non déterministes le résolvent par conjecture. Ces conjectures sont généralement affinées grâce à l’utilisation d’ heuristiques .

Exact ou approximatif

Alors que de nombreux algorithmes convergent vers une solution exacte, les algorithmes d'approximation recherchent une approximation proche de la solution véritable. Ces algorithmes présentent un intérêt pratique pour de nombreux problèmes complexes. Par exemple, le problème du sac à dos , où l'objectif est de remplir un sac à dos avec un ensemble d'objets afin d'obtenir une valeur totale maximale. Chaque objet a un poids et une valeur. Le poids total transportable est limité à une valeur fixe X. La solution doit donc prendre en compte à la fois le poids et la valeur des objets.

Algorithme quantique

Les algorithmes quantiques s'appuient sur un modèle réaliste de calcul quantique . Ce terme est généralement employé pour désigner les algorithmes qui semblent intrinsèquement quantiques ou qui utilisent certaines caractéristiques essentielles du calcul quantique, telles que la superposition quantique ou l'intrication quantique .

Une autre façon de classer les algorithmes consiste à se baser sur leur méthodologie ou paradigme de conception . Voici quelques paradigmes courants :

Recherche par force brute ou exhaustive

La force brute est une méthode de résolution de problèmes qui consiste à tester systématiquement toutes les options possibles jusqu'à trouver la solution optimale. Cette approche peut s'avérer très chronophage, car elle implique de tester toutes les combinaisons de variables possibles. Elle est souvent utilisée lorsque d'autres méthodes sont indisponibles ou trop complexes. La force brute permet de résoudre divers problèmes, comme trouver le chemin le plus court entre deux points et déchiffrer des mots de passe.

Diviser pour mieux régner

Un algorithme de type « diviser pour régner » réduit itérativement un problème à une ou plusieurs instances plus petites de lui-même (généralement de manière récursive ) jusqu'à ce que ces instances soient suffisamment petites pour être résolues facilement. Le tri fusion est un exemple d'algorithme de ce type : une liste non triée est divisée en listes plus petites, triées de la même manière, puis fusionnées. Une variante plus simple, appelée algorithme d'élagage et de recherche (ou algorithme de réduction pour régner) , résout une instance plus petite du problème et ne nécessite pas d'étape de fusion. L'algorithme de recherche dichotomique est un exemple d'algorithme d'élagage et de recherche .

Recherche et énumération

De nombreux problèmes (comme jouer aux échecs ) peuvent être modélisés comme des problèmes de graphes . Un algorithme d'exploration de graphes définit des règles de déplacement et est utile pour ce type de problèmes. Cette catégorie inclut également les algorithmes de recherche , l'énumération par séparation et évaluation , et le retour arrière .

Algorithme aléatoire

Ces algorithmes effectuent certains choix de manière aléatoire (ou pseudo-aléatoire). Ils trouvent des solutions approchées lorsque la recherche de solutions exactes est impraticable (voir la méthode heuristique ci-dessous). Pour certains problèmes, les approximations les plus rapides nécessitent une part d'aléatoire . La question de savoir si les algorithmes randomisés de complexité polynomiale peuvent être les plus rapides 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 fournissent une réponse correcte avec une forte probabilité. Par exemple, RP est une sous-classe de ces algorithmes 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 limité que de manière probabiliste, par exemple ZPP .

Réduction de la complexité

Cette technique transforme des problèmes complexes en problèmes plus connus, résolubles par des algorithmes (idéalement) asymptotiquement optimaux . L'objectif est de trouver un algorithme de réduction dont la complexité n'est pas dominée par celle des algorithmes réduits obtenus. 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 extrayant l'élément central de la liste triée (la partie peu coûteuse). Cette technique est également connue sous le nom de « transformer pour régner » .

Retour en arrière

Dans cette approche, plusieurs solutions sont construites progressivement et abandonnées lorsqu'il est déterminé qu'elles ne peuvent pas aboutir à une solution complète et 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

Lorsqu'on recherche des solutions optimales pour une fonction linéaire soumise à des contraintes d'égalité et d'inégalité linéaires, ces contraintes peuvent être utilisées directement pour obtenir ces solutions optimales. Il existe des algorithmes capables de résoudre tout problème de cette catégorie, comme le célèbre algorithme du simplexe . Parmi les problèmes résolubles par programmation linéaire figure le problème du flot maximal pour les graphes orientés. Si un problème impose également que certaines inconnues soient des entiers , il relève alors de la programmation linéaire en nombres entiers . Un algorithme de programmation linéaire peut résoudre un tel problème s'il est possible de démontrer que toutes les restrictions sur 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, on utilise un algorithme spécialisé ou un algorithme de recherche de solutions approchées, selon la difficulté du problème.

Programmation dynamique

Lorsqu'un problème présente des sous-structures optimales (c'est-à-dire que la solution optimale peut être construite à partir des solutions optimales de sous-problèmes) et des sous-problèmes qui se chevauchent (c'est-à-dire que les mêmes sous-problèmes servent à résoudre plusieurs instances différentes du problème), une approche plus rapide appelée programmation dynamique évite de recalculer les solutions. Par exemple, l'algorithme de Floyd-Warshall permet de trouver le plus court chemin entre un sommet de départ et un sommet d'arrivée dans un graphe pondéré en utilisant le plus court chemin vers l'arrivée depuis tous les sommets adjacents. La programmation dynamique et la mémoïsation sont étroitement liées. Contrairement à l'approche « diviser pour régner », les sous-problèmes de la 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émoïsation des appels récursifs. Lorsque les sous-problèmes sont indépendants et ne se répètent pas, la mémoïsation est inutile ; la programmation dynamique n'est donc pas applicable à tous les problèmes complexes. Grâce à la mémoïsation, la programmation dynamique réduit la complexité de nombreux problèmes d'exponentielle à polynomiale.

La méthode avide

Les algorithmes gloutons , à l'instar de la programmation dynamique, fonctionnent en examinant des sous-structures, non pas du problème lui-même, mais d'une solution donnée. Ces algorithmes partent d'une solution et l'améliorent par petites modifications. Pour certains problèmes, ils trouvent toujours la solution optimale, tandis que pour d'autres, ils peuvent s'arrêter à des optima locaux . L'application la plus courante des algorithmes gloutons est la recherche d'arbres couvrants minimaux de graphes sans cycles négatifs. Les algorithmes de Huffman , de Kruskal , de Prim et de Sollin sont des exemples d'algorithmes gloutons capables de 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 cette dernière est impraticable. Ces algorithmes s'en approchent progressivement. En principe, s'ils étaient exécutés indéfiniment, ils finiraient par trouver la solution optimale. Idéalement, ils peuvent trouver une solution très proche de l'optimum en un temps relativement court. Parmi ces algorithmes, on trouve la recherche locale , la recherche tabou , le recuit simulé et les algorithmes génétiques . Certains, comme le recuit simulé, sont non déterministes, tandis que d'autres, comme la recherche tabou, sont déterministes. Lorsqu'une borne supérieure de l'erreur de la solution non optimale est connue, l'algorithme est alors qualifié d' algorithme d'approximation .