Classification des algorithmes

Sur Scriptol.org, les algorithmes sont classés par finalité, mais il y a d'autres façons de les classer.

Contenu Par finalité Par implémentation Selon le paradigme de conception Selon la complexité

Classification par finalité

Chaque algorithme à un but. Par exemple, la finalité de l'algorithme Quick Sort est de trier les données en ordre ascendant ou descendant. Mais les buts sont en nombre infini aussi on les regroupe par genre:

• Textuel
• Graphisme
• Mathématique
• Routine commune
• Cryptographie
• Compression de données
• Listes: classement, recherche
• Parsing

Classification par implémentation

Le même algorithme peut être implémenté selon des principes de base différents.

• Récursion or itération
  Un algorithme récursif s'appelle lui-même répétitivement, jusqu'à ce qu'une condition soit remplie. C'est une méthode courante en programmation fonctionnelle.
  Les algorithmes itératifs utilisent des boucles .
  Selon le problème, l'une ou l'autre implémentation convient le mieux. Par exemple, le problème des tours de Hanoi se comprend mieux sous forme récursive. Mais toute version récursive à un équivalent itératif et vice versa.

• Logique ou procédure
  Un algorithme peut aussi être vu comme une déduction logique contrôlée.
  Un composant logique exprime les axiomes qu'utilisera le traitement et un composant de contrôle définit la façon dont les déductions sont appliquées aux axiomes.
  C'est la base de la programmation logique. Les langages de pure programmation logique ont un contrôle prédéfini, seuls les axiomes restent à exprimer.

• Série ou parallèle
  En général on suppose que les instructions des algorithms soient exécutés une par une, et on parle d'algorithme en série, mais ils peuvent aussi être parallèles, quand l'architecture de l'ordinateur permet de traiter plusieurs instructions en même temps.
  Dans ce cas le problème est divisé en sous-problèmes affectés à des processeurs différents. Les algorithmes itératifs sont parallélisable, et surtout les algorithmes de tri.

• Déterministe ou non
  Les algorithmes déterministes accomplissent un processus prédéfini pour résoudre un problème tandis que les algorithmes non-déterministes doivent deviner à chaque étape la meilleure solution à l'aide d'heuristiques.

Classification selon le paradigme de conception

Le paradigme de conception est un domaine de recherche ou une classe de problèmes requérant un type d'algorithme adapté.

• Diviser pour régner
  le principe "diviser pour régner", de façon récursive réduit un problème à un cas plus simple ou un ensemble de sous-problèmes, jusqu'à atteindre un niveau de simplicité suffisant pour pouvoir le résoudre facilement. L'algorithme merge sort en est un exemple. La liste à trier est divisée en sous-listes, triées séparément.
  L'algorithme de recherche dicchotomique est un autre exemple selon le même principe.
   
• Programmation dynamique
  Le plus court chemin sur un graphe valué peut être trouvé en utilisant le plus court chemin entre arcs adjacents.
  Quand la solution optimale d'un problème s'obtient à partir des solutions optimales de sous-problèmes, la programmation dynamique permet d'éviter de recalculer les solutions déja traitée.
  - La principale différence avec l'approche "diviser pour régner", est que dans la seconde les sous-problèmes sont indépendant tandis qu'une superposition est possible en programmation dynamique.
  - Programmation dynamique et mémorisation vont de pair. La différence avec une récursion directe est dans la mise en cache, ou mémorisation des appels récursifs. Cela ne sert à rien quand les sous-problèmes sont indépendants. Sinon la mémorisation d'une table des problèmes déja résolus réduit la complexité exponentielle en complexité polynomiale.
   
• La méthode gourmande
  Elle est proche de la programmation dynamique avec cette différence que les solutions des sous-problèmes n'ont pas besoin d'être connues à chaque étape du traitement. Au contraire un choix "gourmand" est fait qui consiste à prendre la meilleure décision possible à cet instant. L'algorithme de Kruskal est un exemple.
   
• Programmation linéaire
  Le problème est exprimé sous forme d'un ensemble d'inégalités linéaires, puis l'on essaie de maximiser ou minimiser les entrées. Cela peut résoudre de nombreux problèmes, dont celui-ci du flot maximal sur un graphe orienté, notamment en utilisant l'algorithme du simplexe.
  Une variante appelée programmation entière consiste à réstreindre l'espace de solution aux nombres entiers.
   
• Réduction.
  Consiste à transformer un problème en un autre, plus simple à résoudre.
  Un exemple simple, trouver la médiane d'une liste non ordonnée consiste à trier la liste d'abord pour en tirer directement la valeur médiane qui est au milieu de liste! On voit que le but est de trouver la transformation la plus évidente.
   
• Utilisation des graphes
  On peut résoudre beaucoup de problèmes, notamment le jeu d'échec, en le modélisant sous forme de graphe. On fait appel à des algorithmes d'exploration de graphes. Cela inclut les algorithmes de recherche et de "backtracking".
   
• Probabilistes et heuristiques
  
  
  1. Probabilistiques
     Ils font des choix aléatoires.
  2. Génétiques
     Recherche la solution d'un problème en imitant les processus d'évolution biologiques, avec des générations successibles qui sont des solutions intermédiaires. En fait cela reproduit le principe de survie des meilleurs.
  3. Heuristiques
     Le but n'est pas de trouver une solution optimale, mais une bonne solution si la meilleure requérerait trop de temp ou de ressources.
     

Classification selon la complexité

Des algorithmes s'achèvent selon une durée linéaire, d'autres requèrent une durée exponentielle, d'autres ne s'achèvent jamais.