5. Paradigmes et méthodes de résolution

1. Paradigme itératif.
   L'itérativité construit directement chaque étape de l'algorithme, soit de manière linéaire d'une instruction à la suivante, soit avec des schémas alternatifs ou répétitifs (si-alors-sinon, pour, tantque, ...).
2. Paradigme récursif.
   La récursivité se prête bien à une approche descriptive de la solution d'un problème, notamment avec une fonction. : si une condition d'arrêt est validée, la fonction retourne immédiatement la solution, sinon la fonction est relancée. Il est essentiel de vérifier que la condition d'arrêt est atteinte après un nombre borné d'opérations et que l'arrêt est effectif.

1. Droit au but : méthode vorace (=gloutonne, greedy algorithms).
   Cette méthode, généralement simple et efficace, consiste à explorer un ensemble de candidats, pour décider à chaque étape s'il faut retenir ou pas le candidat étudié. L'algorithme ne remet jamais en cause un choix fait précédemment.
   Schéma algorithmique VORACE
   Donnée : un ensemble K de candidats solutions au problème.
   Résultat : une solution S⊂K du problème.

   S←∅;
   Tantque C≠∅ et S n'est pas solution du problème faire
   // Il faut donc un critère de validation de S
   

   Choisir dans C le meilleur candidat x;
   // Le choix doit être simple et rapide pour être efficace
   Si x est acceptable alors ajouter x à S;
   // Il faut donc un critère d'acceptabilité des candidats

   Si S est une solution

   alors retourner S
   sinon retourner ∅.
   Exemple d'utilisation : recherche de la valeur maximale d'un tableau.
2. Décomposer le problème.
   • Diviser pour résoudre (=diviser pour régner, divide and conquer).
     On utilise une stratégie descendante (top-down) en décomposant la donnée pour résoudre le problème par morceaux puis en réassemblant les morceaux. On utilise généralement la même méthode de résolution sur les différents morceaux ; de ce fait un algorithme récursif est souvent utilisé, un seuil de décomposition ultime décidant l'arrêt de la récursivité. L'analyse de complexité des algorithmes récursifs utilise généralement des équations de récursivité.
     Schéma algorithmique DPR

     Si la donnée n'est pas élémentaire alors

     Décomposer la donnée;
     Traiter (itérativement ou récursivement) chaque élément de la décomposition;
     Recomposer la donnée.
     Exemple d'utilisation : recherche ou tri dichotomique dans un tableau.
   • Programmation dynamique.
     On utilise une stratégie ascendante en examinant d'abord les plus petites parties de la donnée avant de les regrouper par étapes successives. La solution est obtenue à la fin sur la donnée entière.
     Schéma algorithmique PDYN

     Choisir les données élémentaires de D à utiliser Δ={D_1,..., D_k};
     Tantque Δ n'a pas recomposé la donnée D faire

     Traiter Δ;
     Recomposer Δ.
     Exemples d'utilisation : Triangle de Pascal, Suite de Fibonacci.
3. Simplifier le problème.
   • Méthodes heuristiques.
     On recherche une solution approchée, généralement pour obtenir une solution plus rapide au problème. Dans les problèmes d'optimisation, on cherchera une solution suffisamment proche de la solution optimale pour être satisfaisante, soit en se fixant préalablement une solution acceptable, soit en fixant un nombre maximal d'étapes à l'algorithme.
   • Méthodes probabilistes.
     Une solution approchée est recherchée non plus selon un critère de satisfaction basé non plus sur une critère a priori, mais sur des probabilités afin d'obtenir des solutions statistiquement acceptables. On peut utiliser des analyses de complexité en moyenne basées sur des échantillons de données ou sur des propriétés structurelles des données.
4. Transformer le problème.
   En modélisant la donnée d'une autre manière ou en trouvant une équivalence avec un autre domaine de données, on peut utiliser des solutions algorithmes d'un autre domaine.