Capsule Vidéo — Le Cours & Exemples Résolus Pas à Pas au Tableau Blanc
Pédagogie progressive (style Yvan Monka & Paul Olivier) : intuition, formules expliquées mot à mot et exemples chiffrés résolus en direct
1. Le paradigme « Diviser pour régner »
Le paradigme Diviser pour régner et son principe
1° Les trois étapes du paradigme
- Diviser : décomposer le problème initial en sous-problèmes indépendants de même nature mais de taille réduite.
- Régner : résoudre les sous-problèmes récursivement (ou directement s'ils sont de taille élémentaire).
- Combiner : fusionner les solutions partielles pour construire la solution du problème global.
- Se distingue de la récursion simple car les sous-problèmes divisent la taille par un facteur k ≥ 2 (division dichotomique).
2° Équation de récurrence et coût
- Exemple de la recherche dichotomique : T(n) = T(n/2) + O(1) ⟹ complexité en O(log n).
- Exemple de l'exponentiation rapide : calcul de xⁿ en O(log n) multiplications au lieu de O(n).
- Multiplication de Karatsuba ou algorithme de Strassen pour le produit de matrices.
- Permet de transformer des algorithmes polynomiaux lents en procédures quasi-linéaires ultra-rapides.
2. Algorithme du Tri Fusion (Merge Sort)
Le Tri Fusion (Merge Sort) et sa complexité optimale
1° Algorithme et étape de fusion
- Cas de base : si len(T) ≤ 1, la liste est déjà triée, on la renvoie immédiatement.
- Division : on coupe la liste en deux au milieu m = len(T) // 2.
- La fonction fusion(gauche, droite) réunit deux listes déjà triées en une seule liste triée en temps linéaire O(n).
- On compare les têtes des deux listes et on extrait la plus petite à chaque étape.
2° Analyse de la complexité en O(n log n)
- À chaque niveau de l'arbre d'appels, la fusion de l'ensemble des sous-listes coûte exactement O(n).
- Le nombre de niveaux de division par deux vaut log₂(n).
- Coût total dans le pire, meilleur et cas moyen : O(n log n), optimal pour un tri par comparaison !
- Le tri fusion est stable (préserve l'ordre des éléments égaux) mais nécessite O(n) mémoire supplémentaire.
3. Programmation dynamique et sous-problèmes chevauchants
La Programmation Dynamique : mémoïsation et tabulation
1° Échec de la récursion naïve et sous-problèmes redondants
- En récursif pur, les mêmes sous-calculs sont répétés des millions de fois (explosion combinatoire).
- La programmation dynamique s'applique lorsque les sous-problèmes se chevauchent (overlapping subproblems).
- Richard Bellman (1953) : principe d'optimalité où la solution optimale se compose de sous-solutions optimales.
- Règle d'or : ne jamais recalculer ce qui a déjà été résolu !
2° Mémoïsation (Top-Down) vs Tabulation (Bottom-Up)
- Approche descendante (mémoïsation) : on conserve la structure récursive mais on stocke les résultats dans une table/dictionnaire.
- Approche ascendante (tabulation) : on remplit itérativement un tableau depuis les cas de base jusqu'à la solution finale.
- Transforme un algorithme exponentiel en O(2ⁿ) en un algorithme linéaire O(n) temps et mémoire !
- Utilisé en bio-informatique (alignement de séquences ADN Needleman-Wunsch) et traitement du langage.
4. Le problème du rendu de monnaie optimal
Application : le problème du rendu de monnaie optimal
1° Échec de l'algorithme glouton
- L'algorithme glouton (choisir toujours la plus grande pièce possible) ne fournit pas toujours la solution minimale.
- Un système monétaire est dit canonique si le glouton est toujours optimal (cas de l'Euro).
- Pour un système non canonique, seule la programmation dynamique garantit le nombre minimal absolu de pièces.
- On définit nb_pieces(s) = 1 + min(nb_pieces(s - p)) pour toutes les pièces p ≤ s.
2° Résolution par programmation dynamique ascendante
- Cas de base : T[0] = 0 (zéro pièce pour rendre une somme nulle).
- Pour chaque somme intermédiaire s de 1 à S, on teste chaque pièce disponible p ≤ s.
- Complexité en temps : O(S × k) où S est la somme à rendre et k le nombre de pièces du système.
- En conservant la pièce choisie à chaque minimum, on reconstitue exactement le détail des pièces à rendre.
5. Algorithme de Dijkstra (Plus court chemin)
L'algorithme de Dijkstra pour les graphes pondérés
1° Principe et relaxation des arêtes
- Edsger Dijkstra (1959) : calcule la distance minimale depuis un sommet source vers tous les autres sommets.
- Tous les poids d'arêtes doivent être strictement positifs ou nuls (w ≥ 0).
- On maintient un tableau de distances d[s] initialisé à 0 pour la source et à +∞ pour tous les autres sommets.
- On utilise un ensemble de sommets non encore traités.
2° Déroulement de l'algorithme et complexité
- À chaque étape, on extrait le sommet u non visité ayant la plus petite distance d[u] provisoire.
- Pour chaque voisin v de u : si d[u] + w(u, v) < d[v], on met à jour d[v] et son prédécesseur parent[v] = u.
- Le sommet u est alors définitivement figé (sa distance optimale ne changera plus jamais).
- Complexité en O((V + E) log V) avec file de priorité (tas binaire). C'est le cœur du protocole réseau OSPF et des GPS !
💻 Simulateur 1 : Visualiseur Interactif du Tri Fusion (Merge Sort)
Manipulez les paramètres algorithmiques et observez en temps réel l'exécution de la structure de données.
⚡ Simulateur 2 : Solveur Interactif de Dijkstra sur Graphe Pondéré
Explorez les algorithmes et protocoles systèmes complémentaires.
📊 Analyse Algorithmique & Courbes de Complexité
Données expérimentales de benchmarks et complexités asymptotiques.
🎓 Quiz Bac Terminale — 4 Questions à Choix Multiples (QCM)
Score : 0 / 4Testez votre maîtrise des concepts clés du chapitre. Chaque bonne réponse valide immédiatement votre progression.
Q1. Quelles sont les trois étapes incontournables caractérisant le paradigme algorithmique « Diviser pour régner » ?
Q2. Quelle est la complexité temporelle du Tri Fusion (Merge Sort) pour un tableau de n éléments, dans le pire des cas ?
Q3. Pourquoi l'algorithme glouton échoue-t-il sur le problème du rendu de monnaie avec le système de pièces [1, 3, 4] pour rendre la somme de 6 ?
Q4. Quelle condition fondamentale est impérative sur les poids des arêtes pour que l'algorithme de Dijkstra calcule correctement les plus courts chemins ?