Seconde · Première · Terminale LaboBac.fr
🏠 Portail Terminale
Terminale Spé • Thème 2 : Algorithmique des Graphes et Paradigmes Avancés

Chapitre 5 — Paradigmes algorithmiques : diviser pour régner (tri fusion), programmation dynamique (mémoïsation) et plus court chemin de Dijkstra

1. Paradigme « Diviser pour régner » : étapes Diviser, Régner, Combiner · 2. Le Tri Fusion (Merge Sort) et sa complexité optimale O(n log n) · 3. Programmation dynamique : sous-problèmes chevauchants, mémoïsation et itération ascendante · 4. Problème du rendu de monnaie optimal · 5. Algorithme de Dijkstra : plus court chemin dans un graphe pondéré positif.

🎬 Capsule Vidéo Tableau Blanc (Cours Vidéo Animé) 💻 Simulateur 1 : Visualiseur Interactif du Tri Fusion (Merge Sort) ⚡ Simulateur 2 : Solveur Interactif de Dijkstra sur Graphe Pondéré 🎓 Quiz Bac Terminale 4 QCM

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

🔊 Audio Français + Tableau Animé
Cliquez sur « Lancer le Cours Vidéo » pour démarrer l'explication complète de NSI Terminale au tableau blanc.
00:00 / 05:30

1. Le paradigme « Diviser pour régner »

Le paradigme Diviser pour régner et son principe

1° Les trois étapes du paradigme

$$1. Diviser en sous-problèmes ⟶ 2. Régner (résoudre) ⟶ 3. Combiner les solutions$$
  • 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

$$T(n) = a · T(n/b) + f(n) ⟶ Gain spectaculaire d'efficacité$$
  • 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

$$tri_fusion(T) : diviser en deux moitiés T1 et T2 ⟶ fusionner(tri(T1), tri(T2))$$
  • 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)

$$Hauteur de l'arbre de récursion = ⌈log₂ n⌉ × Travail par niveau = O(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

$$Fibonacci naïf : F(n) = F(n-1) + F(n-2) ⟶ Complexité exponentielle catastrophique O(2ⁿ)$$
  • 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)

$$Mémoïsation : dictionnaire mémoire | Tabulation : tableau itératif rempli de 0 à n$$
  • 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

$$Système de pièces [1, 3, 4] ⟶ Pour rendre 6 : Glouton donne 4 + 1 + 1 (3 pièces), Optimum = 3 + 3 (2 pièces)$$
  • 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

$$Tableau T[s] de 0 à Somme : T[s] = 1 + min( T[s - p] ) pour chaque pièce p ≤ s$$
  • 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

$$Graphe pondéré à poids positifs w(u, v) ≥ 0 | d[v] = min(d[v], d[u] + w(u, v))$$
  • 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é

$$Sélectionner u de distance minimale ⟶ Relâcher tous ses voisins ⟶ Marquer u comme traité$$
  • À 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.

Opérations / État Calcul en cours...
Complexité théorique O(1)
Validation / Invariant Conforme au programme officiel NSI

⚡ Simulateur 2 : Solveur Interactif de Dijkstra sur Graphe Pondéré

Explorez les algorithmes et protocoles systèmes complémentaires.

Indicateur clé Prêt
Rendement / Coût Optimal
Résultat d'exécution Succès

📊 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 / 4

Testez 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 ?