Lernzettel: Paradigmes algorithmiques et stratégies efficaces

📋 Plan du Cours

1. Paradigmes algorithmiques et objectifs
2. Stratégie gloutonne et propriété du choix
3. Programmation dynamique mémoïsation et tabulation
4. Diviser pour mieux régner et analyse
5. Force brute et limites de complexité
6. Retour sur trace et élagage
7. Heuristiques et métaheuristiques
8. Comparaison des paradigmes et optimalité
9. Dijkstra sur graphe et complexité
10. Sac à dos fractionnaire et 0-1
11. Fibonacci : comparaison récursion et DP
12. Validation des pistes pour DaariNova

📖 1. Paradigmes algorithmiques et objectifs

🔑 Notions clés & Définitions

• Paradigme glouton : Un paradigme glouton construit une solution en choisissant à chaque étape l’option localement la plus avantageuse, sans revenir en arrière.
• Diviser-pour-régner : Un paradigme diviser-pour-régner résout un problème en le décomposant en sous-problèmes plus petits, puis en combinant leurs solutions.
• Programmation dynamique : La programmation dynamique résout un problème en exploitant des sous-problèmes récurrents, stockés pour éviter les recalculs.
• Force brute : La force brute cherche une solution en testant systématiquement toutes les possibilités jusqu’à trouver une solution valide.

📝 Points essentiels

• Les objectifs d’apprentissage portent sur la description des paradigmes glouton, diviser-pour-régner, programmation dynamique et force brute.
• Le choix d’une stratégie dépend de la nature du problème (structure, sous-problèmes, possibilité de choix local, ou besoin d’exploration exhaustive).
• L’analyse de complexité doit utiliser les notations asymptotiques O, Ω et Θ pour comparer les performances selon le paradigme.
• Un algorithme glouton simple doit être justifié par ses choix locaux à chaque étape.
• Un algorithme diviser-pour-régner doit être conçu récursivement et sa complexité doit être analysée.
• La programmation dynamique peut être réalisée en version descendante (récursive) ou ascendante (itérative).

💡 Astuce mémo

Glouton = choix local; Diviser-pour-régner = découper puis combiner; Programmation dynamique = mémoriser les sous-problèmes; Force brute = tout essayer.

📖 2. Stratégie gloutonne et propriété du choix

🔑 Notions clés & Définitions

• Stratégie gloutonne : Une stratégie gloutonne choisit à chaque étape l’option localement la plus avantageuse, sans revenir en arrière.
• Heuristiques : Les heuristiques sont des règles pratiques qui guident la recherche d’une bonne solution sans garantir l’optimalité.
• Paradigmes algorithmiques : Les paradigmes algorithmiques regroupent des familles de méthodes de résolution selon leur logique et leur domaine d’usage.
• Retour sur trace : Le retour sur trace est une méthode qui explore des choix successifs et revient en arrière quand une branche ne mène pas à une solution.

📝 Points essentiels

• Une stratégie gloutonne vise un choix local à chaque étape pour obtenir une solution rapidement sous contrainte de temps.
• Les heuristiques servent à orienter la recherche quand l’exploration exhaustive serait trop coûteuse en délais.
• Les paradigmes algorithmiques permettent de classer les stratégies (gloutonne, programmation dynamique, force brute) selon leur approche et leur complexité.
• Le retour sur trace contraste avec le glouton : il explore plusieurs branches et corrige les choix via un retour en arrière.
• Dans le contexte de la cité intelligente, l’optimisation doit produire des décisions dans des délais acceptables pour le fonctionnement de la ville.

💡 Astuce mémo

Glouton = « meilleur à l’instant » (local) ; Backtracking = « je reviens si ça coince » (retour en arrière).

📖 3. Programmation dynamique mémoïsation et tabulation

🔑 Notions clés & Définitions

• Programmation dynamique : La programmation dynamique est un paradigme d’optimisation qui résout un problème en sous-problèmes qui se recouvrent et qui possèdent une sous-structure optimale.
• Sous-problèmes qui se chevauchent : Les sous-problèmes qui se chevauchent sont des parties du problème dont les solutions sont recalculées plusieurs fois si on utilise une approche naïve.
• Sous-structure optimale : La sous-structure optimale signifie que la solution optimale du problème global s’obtient à partir de solutions optimales de ses sous-problèmes.
• Mémoïsation : La mémoïsation est une variante top-down qui stocke les résultats intermédiaires pendant l’exécution récursive pour éviter les recalculs.
• Tabulation : La tabulation est une variante bottom-up qui calcule les solutions en remplissant un tableau de façon itérative.

📝 Points essentiels

• La programmation dynamique s’appuie sur deux propriétés : des sous-problèmes qui se chevauchent et une sous-structure optimale.
• La mémorisation des résultats intermédiaires évite les recalculs redondants présents dans une récursion naïve.
• La mémoïsation suit une logique descendante (top-down) : on résout en appelant récursivement, puis on stocke.
• La tabulation suit une logique ascendante (bottom-up) : on remplit un tableau itérativement jusqu’à obtenir la solution finale.
• La différence clé entre mémoïsation et tabulation est l’ordre de calcul : à la demande avec mémoïsation, progressivement avec tabulation.
• Mémoïsation et tabulation sont deux façons d’exploiter la même idée centrale : réutiliser des résultats déjà obtenus.

💡 Astuce mémo

Chevauchement = on recalcule trop ; Mémoïsation = on mémorise en descendant ; Tabulation = on remplit en montant.

📖 4. Diviser pour mieux régner et analyse

🔑 Notions clés & Définitions

• Diviser pour mieux régner : Le paradigme diviser pour mieux régner décompose un problème en sous-problèmes de même nature, les résout récursivement, puis combine leurs résultats pour obtenir la solution finale.
• Programmation dynamique : La programmation dynamique résout un problème en mémorisant des résultats afin d’éviter de recalculer des sous-problèmes qui se recouvrent.
• Tri fusion : Le tri fusion est un algorithme diviser pour mieux régner qui trie en séparant la liste, en triant chaque moitié, puis en fusionnant les deux parties triées.
• Tri rapide : Le tri rapide est un algorithme diviser pour mieux régner qui partitionne le tableau autour d’un pivot, trie récursivement les sous-parties, puis combine implicitement les résultats.
• Recherche binaire : La recherche binaire est une méthode diviser pour mieux régner qui réduit l’espace de recherche en comparant au milieu et en ne gardant qu’une moitié.

📝 Points essentiels

• Dans diviser pour mieux régner, les sous-problèmes sont indépendants et ne se chevauchent pas, contrairement à la programmation dynamique.
• Le schéma général est diviser le problème, résoudre récursivement les sous-problèmes, puis combiner leurs résultats.
• Le tri fusion suit la logique diviser puis fusionner deux moitiés triées.
• Le tri rapide suit la logique de partition autour d’un pivot puis tri récursif des segments obtenus.
• La recherche binaire réduit l’espace de recherche à chaque étape en ne conservant qu’une moitié.
• Des exemples de diviser pour mieux régner incluent la puissance d’un nombre, la multiplication de matrices (Strassen) et le calcul de sous-problèmes de même nature.

💡 Astuce mémo

Diviser = même type de problème, Régner = récursion, Combiner = assemblage; si ça se chevauche, c’est plutôt la programmation dynamique.

📖 5. Force brute et limites de complexité

🔑 Notions clés & Définitions

• Heuristique : Une heuristique est une méthode de résolution approchée qui vise une bonne solution rapidement sans garantir l’optimalité.
• Problème NP-difficile : Un problème NP-difficile est un problème pour lequel trouver une solution optimale exacte est généralement trop coûteux en temps de calcul.
• TSP : Le TSP est le problème du voyageur de commerce consistant à trouver un itinéraire de coût minimal passant par toutes les villes.
• Complexité O(n²) : Une complexité O(n²) décrit un temps de calcul qui croît proportionnellement au carré de la taille n de l’entrée.
• Flux de données : Un flux de données correspond au mouvement continu et ordonné d’informations entre capteurs, centres décisionnels et réseaux.

📝 Points essentiels

• Une heuristique ne garantit pas l’optimalité mais cherche une solution de bonne qualité en un temps raisonnable.
• Les heuristiques sont utilisées quand le problème est NP-difficile et que la solution exacte est trop coûteuse à calculer.
• Le TSP est cité comme exemple de problème NP-difficile où une approche exacte peut être prohibitive.
• L’heuristique gloutonne pour le TSP est annoncée en O(n²) et ne fournit pas de garantie d’optimalité.
• Dans DaariNova, l’efficacité des flux de données dépend du paradigme algorithmique qui les orchestre.
• Le paradigme diviser pour mieux régner permet de partitionner et traiter des flux en parallèle dans les centres décisionnels.

💡 Astuce mémo

Heuristique = « vite et bien » : pas d’optimalité, mais un bon résultat en temps raisonnable.

📖 6. Retour sur trace et élagage

🔑 Notions clés & Définitions

• Récursion naïve : Une approche récursive sans mémorisation qui recalcule plusieurs fois les mêmes sous-problèmes.
• Mémoïsation : Une technique qui mémorise les résultats de sous-problèmes pour éviter des recalculs lors d’une récursion.
• Tabulation : Une technique de programmation dynamique qui remplit un tableau de bas en haut pour réutiliser les résultats déjà calculés.
• Programmation dynamique : Une méthode qui décompose un problème en sous-problèmes et exploite leurs résultats pour obtenir une solution efficace.
• Élagage : Une réduction de l’espace de recherche qui coupe des branches du calcul quand elles ne peuvent plus mener à une solution optimale.

📝 Points essentiels

• La récursion naïve peut exploser en nombre d’appels car elle recalcule les mêmes sous-problèmes à répétition.
• Pour Fibonacci, la récursion naïve passe d’une complexité exponentielle à une complexité linéaire avec mémoïsation ou tabulation.
• Pour le sac à dos 0-1, on utilise un tableau $dp[i][w]$ donnant la valeur maximale avec les $i$ premiers objets et une capacité $w$.
• Le sac à dos 0-1 a une complexité $O(nW)$ en temps et $O(nW)$ en espace avec la table $dp$.
• La programmation dynamique est adaptée quand les décisions présentes influencent les possibilités futures, comme pour une allocation optimale de ressources (serveurs, capacités).
• La stratégie gloutonne n’est optimale que si le problème vérifie la propriété du choix glouton (choix local optimal ⇒ solution globale optimale).

💡 Astuce mémo

Récursion naïve = « re-calcul en boucle » ; Mémoïsation/Tabulation = « on stocke puis on réutilise ».

📖 7. Heuristiques et métaheuristiques

🔑 Notions clés & Définitions

• Retour sur trace : Le retour sur trace est une exploration de l’espace de recherche en arbre, qui avance par affectations partielles puis revient en arrière en cas de contrainte violée.
• Pruning (élagage) : Le pruning est un mécanisme qui supprime des branches entières de l’arbre de recherche quand une solution partielle ne peut plus mener à une solution valide.
• Heuristique constructive : Une heuristique constructive construit une solution progressivement, en ajoutant des éléments un par un pour obtenir une solution complète.
• Métaheuristique : Une métaheuristique est un algorithme général d’optimisation combinatoire, guidé par des mécanismes d’exploration pour trouver de bonnes solutions.
• Heuristique du plus proche voisin : L’heuristique du plus proche voisin est une heuristique gloutonne pour le TSP qui choisit à chaque étape la ville la plus proche non encore visitée.

📝 Points essentiels

• La force brute pour le TSP devient impraticable car le nombre de permutations $n!$ explose, par exemple $20!\approx 2{,}4\times 10^{18}$ opérations.
• Avec un temps de 1 ns par opération, $20!$ correspond à environ 76 ans, rendant la méthode totalement irréalisable en pratique.
• Pour $n\ge 19$, la force brute dépasse 1 jour, car $19!$ est déjà de l’ordre de $8{,}64\times 10^{13}$ ns.
• Le backtracking reste exponentiel au pire cas, mais peut être beaucoup plus efficace en pratique grâce à des fonctions de pruning.
• Pour les N-reines, le backtracking place une reine colonne par colonne et revient en arrière dès qu’un conflit est détecté.
• Les heuristiques sont utilisées pour des problèmes d’optimisation NP-difficiles quand une solution optimale est trop coûteuse à obtenir exactement.

💡 Astuce mémo

Backtracking = arbre + affectation partielle + retour arrière; Heuristique = construire vite; Métaheuristique = explorer intelligemment.

📖 8. Comparaison des paradigmes et optimalité

🔑 Notions clés & Définitions

• Force brute : Paradigme qui teste toutes les possibilités pour trouver la meilleure solution, sans structure de réduction du problème.
• Diviser pour régner : Paradigme qui décompose le problème en sous-problèmes plus petits, souvent indépendants, puis combine leurs solutions.
• Stratégie gloutonne : Paradigme qui choisit à chaque étape une option localement optimale en espérant que cela mène à l’optimum global.
• Programmation dynamique : Paradigme qui résout un problème en mémorisant les solutions de sous-problèmes pour éviter les recalculs.

📝 Points essentiels

• Force brute : énumération exhaustive avec complexité typique $O(n!)$ ou exponentielle et garantie d’optimalité sur petites instances.
• Diviser pour régner : complexité typique $O(n\log n)$ (ou similaire) via décomposition en sous-problèmes indépendants et garantie selon la structure du problème.
• Glouton : complexité souvent $O(n\log n)$ ou $O(n^2)$ et optimalité seulement sous conditions (ex. graphes, ordonnancement, certains problèmes d’optimisation).
• Programmation dynamique : complexité souvent polynomiale grâce à la mémoïsation et garantie d’optimalité quand la propriété de sous-structure optimale s’applique.
• Tableau comparatif : Force brute (énumération, $O(n!$)/exponentiel, garantie petites instances) ; Diviser pour régner (décomposition, $O(n\log n)$ typique, garantie) ; Glouton (choix local, $O(n\log n)$ ou $O(n^2)$, non-

💡 Astuce mémo

Force brute = « tout essayer » ; Diviser pour régner = « couper puis recoller » ; Glouton = « meilleur choix maintenant » ; Prog. dynamique = « mémoriser pour ne pas refaire ».

📖 9. Dijkstra sur graphe et complexité

🔑 Notions clés & Définitions

• Dijkstra : Algorithme de plus courts chemins qui calcule, à partir d’une source, les distances minimales vers tous les sommets en élargissant progressivement l’ensemble des sommets “fixés”.
• Graphe pondéré : Structure de sommets reliés par des arêtes, où chaque arête porte un coût (poids) utilisé pour additionner les distances.
• Complexité en temps : Mesure du nombre d’opérations (ou de la croissance) que l’algorithme effectue en fonction de la taille du graphe.
• Complexité en espace : Mesure de la mémoire supplémentaire consommée par l’algorithme en fonction de la taille du graphe.

📝 Points essentiels

• La complexité de Dijkstra dépend fortement de la structure de données utilisée pour sélectionner le prochain sommet à traiter (file de priorité, etc.).
• La complexité en espace inclut typiquement les tableaux de distances et la structure de gestion des sommets à explorer.
• Dijkstra est adapté au calcul de plus courts chemins sur graphe pondéré lorsque les poids respectent les hypothèses nécessaires à la correction de l’algorithme (sinon, le résultat peut être faux).
• Dans l’exemple de validation “diviser pour mieux régner”, la réduction de complexité transforme un coût quadratique en coût quasi-linéaire (tri fusion : O(n log n) au lieu de O(n²)).
• La comparaison “Fibonacci” illustre que la programmation dynamique réduit les recalculs : la mémoïsation passe de O(2^n) à O(n) en stockant les résultats, tandis que l’itératif atteint O(n) temps avec O(1) espace.

💡 Astuce mémo

Dijkstra = “distances minimales fixées une par une” ; Fibonacci = “moins de recalculs” (naïf O(2^n) → mémoïsation O(n) → itératif O(n) et O(1)).

📖 10. Sac à dos fractionnaire et 0-1

🔑 Notions clés & Définitions

• Sac à dos fractionnaire : Le sac à dos fractionnaire autorise de prendre une fraction d’un objet, ce qui rend une stratégie par ratio possible.
• Sac à dos 0-1 : Le sac à dos 0-1 impose de prendre un objet soit entièrement soit pas du tout, ce qui casse la logique gloutonne en général.
• Stratégie gloutonne par ratio : La stratégie gloutonne par ratio choisit les objets selon la valeur par unité de poids, en remplissant progressivement la capacité.
• Programmation dynamique : La programmation dynamique résout des sous-problèmes en tenant compte des interdépendances, souvent nécessaire quand les choix ne sont pas indépendants.

📝 Points essentiels

• La réduction de complexité de type $O(n\log n)$ vs $O(n^2)$ est significative à grande échelle, mais elle suppose des sous-problèmes indépendants.
• La force brute garantit l’optimalité absolue mais n’est applicable qu’à des instances de petite taille, typiquement quand le nombre de variables est faible (environ $n\le 15$).
• La force brute devient impraticable pour de grandes tailles (ex. 50 serveurs, 200 tâches, 15 points), donc il faut passer à des approches plus efficaces.
• La stratégie gloutonne par ratio est optimale pour le sac à dos fractionnaire et donne ici 280 600 FCFA.
• Pour le sac à dos 0-1, la stratégie gloutonne n’est pas optimale en général, même si elle peut tomber sur l’optimal par chance dans l’exemple (ici 261 000 FCFA).
• La programmation dynamique est plus adaptée quand les décisions sont couplées (ex. contraintes de capacité avec objets indivisibles), contrairement au cas où un choix glouton reste valide.

💡 Astuce mémo

Fractionnaire = fractions autorisées → ratio valeur/poids marche ; 0-1 = tout ou rien → glouton casse, DP prend le relais.

📖 11. Fibonacci : comparaison récursion et DP

🔑 Notions clés & Définitions

• Fibonacci : Suite définie par une relation de récurrence où chaque terme dépend des deux précédents.
• Récursion naïve : Méthode récursive qui recalcule plusieurs fois les mêmes sous-problèmes avant de combiner les résultats.
• Mémoïsation : Technique de programmation dynamique qui stocke les résultats de sous-problèmes pour éviter les recalculs.
• Programmation dynamique : Approche qui résout un problème en exploitant des sous-problèmes récurrents, souvent via mémoïsation ou tableau.

📝 Points essentiels

• La récursion naïve de Fibonacci engendre une explosion du nombre d’appels car les sous-problèmes se répètent massivement.
• La mémoïsation transforme la récursion en calcul avec stockage, ce qui réduit fortement le nombre de sous-problèmes évalués.
• L’exemple de Fibonacci sert de modèle pour comprendre comment une logique de DP peut convertir une complexité exponentielle en complexité polynomiale en évitant les recalculs.
• La DP est particulièrement adaptée quand il existe une structure de sous-problèmes réutilisables, comme dans Fibonacci.
• La comparaison avec d’autres paradigmes (ex. glouton) illustre que l’efficacité locale ne suffit pas toujours pour garantir l’optimalité globale.

💡 Astuce mémo

Fibonacci naïf = « je recalcule encore » ; DP = « je garde en mémoire » (mémoïsation).

📖 12. Validation des pistes pour DaariNova

🔑 Notions clés & Définitions

• Stratégie gloutonne : Une stratégie gloutonne choisit à chaque étape la meilleure option locale, sans revenir en arrière.
• Optimalité globale : L’optimalité globale signifie que la solution obtenue est la meilleure possible pour tout le problème, pas seulement localement.
• Propriété du choix glouton : La propriété du choix glouton garantit qu’un choix local optimal peut appartenir à une solution globale optimale.
• Sous-structure optimale : La sous-structure optimale indique que les sous-problèmes d’une solution optimale sont eux-mêmes optimaux.
• Programmation dynamique : La programmation dynamique résout un problème en décomposant en sous-problèmes et en réutilisant leurs résultats.

📝 Points essentiels

• L’efficacité locale d’un algorithme glouton ne suffit pas à assurer l’optimalité globale sur des problèmes complexes.
• Un glouton est optimal quand la propriété du choix glouton est vraie et que le problème possède une sous-structure optimale.
• L’étude du glouton met en évidence une tension classique : choisir vite peut empêcher d’atteindre le meilleur résultat global.
• Les compétences acquises servent à modéliser un nouveau problème en identifiant sa structure et en choisissant le paradigme adapté.
• Dans l’apprentissage automatique, le gradient descent est présenté comme une forme d’approche gloutonne, tandis que la rétropropagation est associée à la programmation dynamique.
• Les problèmes de DaariNova sont reliés à des familles classiques (sac à dos, plus court chemin, ACM) pour permettre une modélisation et une résolution formelles.

💡 Astuce mémo

Glouton = Local meilleur, Global garanti seulement si Choix glouton + Sous-structure optimale.

📊 Tableaux de synthèse

Comparaison des quatre paradigmes

⚠️ Pièges & confusions fréquents

1. Confondre backtracking et force brute : le backtracking construit des solutions partielles et revient en arrière avec pruning, alors que la force brute énumère exhaustivement sans réduction.
2. Croire que la stratégie gloutonne est toujours optimale : elle n’est garantie que si la propriété du choix glouton est vérifiée (sinon, solution sous-optimale).
3. Mélanger programmation dynamique et diviser pour régner : en DP les sous-problèmes se chevauchent, alors qu’en diviser pour régner ils ne se chevauchent pas.
4. Inverser l’ordre de calcul mémoïsation vs tabulation : mémoïsation est top-down à la demande, tabulation est bottom-up en remplissant un tableau.
5. Penser que la récursion naïve et la DP ont la même complexité : la DP évite les recalculs redondants (ex. Fibonacci).
6. Appliquer la gloutonnerie au sac à dos 0-1 comme au fractionnaire : le 0-1 casse la logique par ratio et nécessite DP pour garantir l’optimum.
7. Sous-estimer la force brute : oublier que le nombre de permutations explose (ex. TSP : 15!, 20!) et devient impraticable en pratique.

✅ Checklist Examen

1. Définir les quatre paradigmes (force brute, diviser pour régner, stratégie gloutonne, programmation dynamique) et expliquer leur logique générale.
2. Justifier le choix d’un paradigme selon la nature du problème (indépendance des sous-problèmes, chevauchement, besoin d’exploration exhaustive, choix local).
3. Analyser la complexité avec notations asymptotiques O, Ω, Θ et relier la complexité au paradigme utilisé.
4. Mettre en œuvre un algorithme glouton simple et justifier ses choix locaux à chaque étape.
5. Concevoir un algorithme récursif diviser pour régner et analyser sa complexité via la relation de récurrence (ex. T(n)=2T(n/2)+O(n)).
6. Résoudre un problème avec programmation dynamique en précisant la variante (mémoïsation top-down ou tabulation bottom-up) et en reliant aux propriétés (sous-structure optimale + chevauchement).
7. Construire une solution par force brute ou par retour sur trace, puis identifier clairement les limites (exponentiel, impraticable, ou amélioré par pruning).
8. Comparer plusieurs approches sur un même problème et conclure quelle stratégie est la plus efficace selon la structure et la complexité.
9. Expliquer pourquoi Dijkstra est un algorithme glouton et décrire le mécanisme (extraire le sommet non visité de distance minimale puis relaxer).
10. Donner les conditions d’application de la stratégie gloutonne dans les exemples (Kruskal/ACM, sac à dos fractionnaire par ratio, Dijkstra) et expliquer l’échec en sac à dos 0-1 sans DP.
11. Pour le sac à dos 0-1, définir la table dp[i][w] et donner la complexité O(nW) en temps et en espace.
12. Pour Fibonacci, comparer récursion naïve, mémoïsation et itératif, et relier la réduction de complexité au fait d’éviter les recalculs.