Chapitre 12 — Diviser pour régner
Décomposer un problème, résoudre ses parties et reconstruire efficacement une solution
| Idée directrice — Le paradigme « diviser pour régner » transforme un problème difficile en sous-problèmes de même nature, plus petits et plus simples. Son efficacité dépend de la qualité de la division, du coût de combinaison et de la profondeur de la récursion. |
| Schéma général |
| PROBLÈME DE TAILLE n | +-- DIVISER -> sous-problèmes plus petits | +-- RÉSOUDRE -> récursivement ou directement | +-- COMBINER -> solution du problème initial |
Fiche pédagogique du chapitre
Objectifs d’apprentissage
À la fin de ce chapitre, l’étudiant devra être capable de :
- expliquer les trois phases du paradigme « diviser pour régner » ;
- déterminer un cas de base garantissant la terminaison ;
- décomposer un problème en sous-problèmes de taille maîtrisée ;
- identifier les sous-problèmes indépendants et les résultats à combiner ;
- écrire un algorithme récursif selon ce paradigme ;
- tracer l’arbre des appels et suivre la reconstruction du résultat ;
- analyser la taille et le nombre des sous-problèmes ;
- évaluer le coût de la phase de combinaison ;
- établir et interpréter une relation de récurrence simple ;
- comparer une solution « diviser pour régner » à une solution directe.
Prérequis
- Fonctions, paramètres et valeurs retournées.
- Récursivité, cas de base et pile des appels.
- Tableaux, indices et intervalles.
- Recherche dichotomique, tri fusion et tri rapide.
- Notions de complexité O(1), O(log n), O(n), O(n log n) et O(n²).
Organisation proposée
Partie | Contenu | Durée indicative |
|---|---|---|
| 12.1 | Principe, division, résolution et combinaison | 2 h |
| 12.2 | Cinq exemples fondamentaux | 3 h |
| 12.3 | Analyse et relations de récurrence simples | 2 h |
| Applications | Conception, traces et choix de stratégie | 1 h 30 |
| TD | Analyse et conception guidées | 2 h |
| TP | Implémentation et comparaison expérimentale | 3 h |
| Positionnement dans le parcours — Le chapitre relie la récursivité à l’analyse de complexité. Il prépare l’étude des algorithmes gloutons, du retour sur trace et de la programmation dynamique. |
Introduction
Face à un problème de grande taille, une stratégie naturelle consiste à le découper en problèmes plus petits. Cette idée devient un véritable paradigme algorithmique lorsque les sous-problèmes ont la même forme que le problème initial, qu’ils peuvent être résolus indépendamment et que leurs résultats peuvent être recombinés de manière systématique.
La recherche dichotomique élimine la moitié de l’espace de recherche à chaque étape. Le tri fusion divise un tableau en deux moitiés, trie chacune puis fusionne les résultats. Le tri rapide partitionne les données autour d’un pivot avant de trier les deux zones. Ces algorithmes paraissent différents, mais partagent la même architecture conceptuelle.
| Point essentiel — Une décomposition n’est utile que si les sous-problèmes sont strictement plus petits et si le coût de leur résolution et de leur combinaison reste inférieur à celui d’une approche naïve. |
Vocabulaire du chapitre
Terme | Signification |
|---|---|
| Problème initial | Instance complète de taille n à résoudre |
| Sous-problème | Instance plus petite du même problème ou d’un problème associé |
| Cas de base | Instance suffisamment petite pour être résolue directement |
| Division | Construction des sous-problèmes |
| Combinaison | Assemblage des solutions partielles |
| Récurrence | Équation exprimant le coût T(n) à partir de coûts plus petits |
| Arbre de récursion | Représentation des appels et de leurs tailles |
12.1 Principe
12.1.1 Les trois phases
Le paradigme « diviser pour régner » repose sur trois phases. Leur importance varie selon les problèmes, mais chacune doit être explicitement identifiée.
Phase | Question à se poser | Résultat attendu |
|---|---|---|
| Diviser | Comment réduire la taille du problème ? | Deux ou plusieurs sous-problèmes plus petits |
| Résoudre | Comment traiter chaque sous-problème ? | Solutions partielles obtenues directement ou récursivement |
| Combiner | Comment reconstruire la solution globale ? | Solution du problème initial |
| PSEUDO-CODE — Gabarit générique du paradigme |
| Fonction DiviserPourRegner(problème) : Solution Si problème est un cas de base Alors Retourner RésoudreDirectement(problème) FinSi sousProblèmes ← Diviser(problème) solutions ← collection vide Pour chaque sousProblème dans sousProblèmes Faire Ajouter(DiviserPourRegner(sousProblème), solutions) FinPour Retourner Combiner(solutions) FinFonction |
| Remarque — Certains algorithmes ne conservent qu’un sous-problème ; d’autres en créent deux ou davantage. |
12.1.2 Diviser le problème
La division doit produire des instances strictement plus petites. Une réduction trop faible, par exemple de n à n − 1, peut conduire à une profondeur linéaire. Une division équilibrée, de n à n/2, produit généralement une profondeur logarithmique.
- Déterminer précisément la taille des sous-problèmes.
- Éviter les recouvrements inutiles entre sous-problèmes.
- Préserver toutes les informations nécessaires à la solution.
- Chercher une division équilibrée lorsque cela est possible.
- Définir les indices et les bornes sans ambiguïté.
| Exemples de divisions |
| Recherche dichotomique : conserver une moitié du tableau Tri fusion : créer deux moitiés de taille proche Tri rapide : deux zones définies par un pivot Maximum récursif : deux moitiés du tableau Puissance rapide : réduire l’exposant de n à n / 2 |
12.1.3 Résoudre les sous-problèmes
La résolution peut être récursive ou directe. La récursion s’arrête lorsque la taille atteint un seuil choisi. Pour des instances très petites, une méthode directe peut être plus efficace, car elle évite le coût des appels récursifs.
| Seuil pratique — Dans une implémentation hybride, un seuil pratique peut remplacer le cas de base minimal. Un tri avancé utilise parfois le tri par insertion lorsque la taille devient inférieure à 16 ou 32 éléments. |
12.1.4 Combiner les résultats
La combinaison peut être triviale, constante, linéaire ou plus coûteuse. Son coût influence directement la complexité globale.
Algorithme | Résultats partiels | Combinaison |
|---|---|---|
| Recherche dichotomique | Résultat d’une seule moitié | Aucune combinaison réelle : O(1) |
| Maximum récursif | Maximum gauche et maximum droit | Une comparaison : O(1) |
| Tri fusion | Deux moitiés triées | Fusion linéaire : O(n) |
| Tri rapide | Deux zones triées | Pas de fusion ; pivot déjà placé |
| Puissance rapide | Valeur x^(n/2) | Une ou deux multiplications : O(1) |
12.1.5 Cas de base et terminaison
La terminaison exige deux propriétés : un cas de base atteignable et une réduction stricte de la taille à chaque appel. Une erreur dans les bornes peut empêcher la taille de diminuer et provoquer une récursion infinie.
Algorithme | Cas de base possible | Mesure qui diminue |
|---|---|---|
| Recherche dichotomique | gauche > droite | Nombre de cases de l’intervalle |
| Tri fusion | gauche ≥ droite | Longueur du sous-tableau |
| Tri rapide | gauche ≥ droite | Longueur de la zone à trier |
| Maximum | Un seul élément | Nombre d’éléments |
| Puissance rapide | n = 0 | Valeur entière de l’exposant |
12.1.6 Conditions favorables au paradigme
- Les sous-problèmes sont de même nature que le problème initial.
- Ils sont plus petits et leur taille est facile à contrôler.
- Ils sont indépendants ou partagent peu de calculs.
- La combinaison des résultats reste raisonnable.
- La division élimine une grande partie du travail.
- La récursivité produit une structure claire et justifiable.
| Limite importante — Lorsque les mêmes sous-problèmes sont recalculés de nombreuses fois, la programmation dynamique est souvent plus appropriée. « Diviser pour régner » suppose généralement des sous-problèmes indépendants. |
12.2 Exemples
12.2.1 Recherche dichotomique
La recherche dichotomique s’applique à un tableau trié. Elle compare la valeur recherchée à l’élément central, puis élimine une moitié de l’intervalle. Un seul sous-problème est conservé à chaque étape.
| PSEUDO-CODE — Recherche dichotomique récursive |
| Fonction RechercheDichotomique(T, valeur, gauche, droite) : Entier Si gauche > droite Alors Retourner -1 FinSi milieu ← gauche + (droite - gauche) div 2 Si T[milieu] = valeur Alors Retourner milieu SinonSi valeur < T[milieu] Alors Retourner RechercheDichotomique(T, valeur, gauche, milieu - 1) Sinon Retourner RechercheDichotomique(T, valeur, milieu + 1, droite) FinSi FinFonction |
Appel | Intervalle | Milieu | Valeur centrale | Décision |
|---|---|---|---|---|
| 1 | [0, 8] | 4 | 23 | Chercher à gauche |
| 2 | [0, 3] | 1 | 7 | Chercher à droite |
| 3 | [2, 3] | 2 | 12 | Valeur trouvée |
| Analyse — À chaque appel, la taille est approximativement divisée par deux. La profondeur est donc logarithmique et la complexité temporelle est O(log n). |
12.2.2 Tri fusion
Le tri fusion crée deux sous-problèmes de tailles voisines, trie récursivement chaque moitié, puis combine les résultats par une fusion ordonnée. Les sous-problèmes sont indépendants, mais la combinaison coûte O(n).
| PSEUDO-CODE — Tri fusion — structure récursive |
| Procédure TriFusion(T, gauche, droite) Si gauche < droite Alors milieu ← gauche + (droite - gauche) div 2 TriFusion(T, gauche, milieu) TriFusion(T, milieu + 1, droite) Fusionner(T, gauche, milieu, droite) FinSi FinProcédure |
| Arbre de division pour 8 éléments |
| T[0..7] |-- T[0..3] | |-- T[0..1] | +-- T[2..3] +-- T[4..7] |-- T[4..5] +-- T[6..7] Profondeur : log2(8) = 3 niveaux de division |
| Analyse — Chaque niveau traite au total n éléments pendant les fusions. Avec log n niveaux, le coût total est Θ(n log n). |
12.2.3 Tri rapide
Le tri rapide partitionne les éléments autour d’un pivot. La division dépend des valeurs et peut être équilibrée ou fortement déséquilibrée. Après le partitionnement, le pivot est à sa position définitive et aucune fusion n’est nécessaire.
| PSEUDO-CODE — Tri rapide — structure récursive |
| Procédure TriRapide(T, gauche, droite) Si gauche < droite Alors positionPivot ← Partitionner(T, gauche, droite) TriRapide(T, gauche, positionPivot - 1) TriRapide(T, positionPivot + 1, droite) FinSi FinProcédure |
Situation | Tailles obtenues | Profondeur | Conséquence |
|---|---|---|---|
| Pivot proche de la médiane | ≈ n/2 et n/2 | O(log n) | Temps moyen O(n log n) |
| Pivot toujours extrême | 0 et n − 1 | O(n) | Pire cas O(n²) |
| Pivot aléatoire | Variable | O(log n) attendue | Pire cas très improbable |
| Idée clé — Le tri rapide montre qu’une mauvaise division peut annuler le bénéfice du paradigme. Le choix du pivot contrôle directement l’équilibre des sous-problèmes. |
12.2.4 Recherche du maximum
Le maximum d’un tableau peut être obtenu en divisant l’intervalle en deux, en calculant le maximum de chaque moitié puis en comparant les deux résultats.
| PSEUDO-CODE — Maximum par division en deux |
| Fonction MaximumDC(T, gauche, droite) : Nombre Si gauche = droite Alors Retourner T[gauche] FinSi milieu ← gauche + (droite - gauche) div 2 maxGauche ← MaximumDC(T, gauche, milieu) maxDroite ← MaximumDC(T, milieu + 1, droite) Si maxGauche > maxDroite Alors Retourner maxGauche Sinon Retourner maxDroite FinSi FinFonction |
Niveau | Sous-tableaux | Comparaisons de combinaison |
|---|---|---|
| 0 | [5, 2, 9, 4, 7, 1, 8, 3] | 1 au sommet |
| 1 | [5, 2, 9, 4] et [7, 1, 8, 3] | 2 |
| 2 | Quatre paires | 4 |
| Total | Huit feuilles | 7 = n − 1 |
| Interprétation — La complexité reste Θ(n), identique au parcours séquentiel. L’intérêt principal est la structure parallèle : les deux moitiés peuvent être traitées simultanément. |
12.2.5 Exponentiation rapide
Calculer xⁿ par n multiplications conduit à O(n). La propriété xⁿ = (x^(n/2))² pour n pair permet de réduire l’exposant de moitié à chaque appel. Pour n impair, on multiplie en plus par x.
| PSEUDO-CODE — Exponentiation rapide récursive |
| Fonction PuissanceRapide(x, n) : Nombre Si n = 0 Alors Retourner 1 FinSi demi ← PuissanceRapide(x, n div 2) Si n mod 2 = 0 Alors Retourner demi × demi Sinon Retourner x × demi × demi FinSi FinFonction |
| Trace pour 3¹³ |
| PuissanceRapide(3, 13) +-- PuissanceRapide(3, 6) +-- PuissanceRapide(3, 3) +-- PuissanceRapide(3, 1) +-- PuissanceRapide(3, 0) = 1 Reconstruction : 3 -> 27 -> 729 -> 1 594 323 |
Méthode | Nombre d’appels / multiplications | Complexité |
|---|---|---|
| Méthode naïve | Proportionnel à n | O(n) |
| Exponentiation rapide | Proportionnel à log₂ n | O(log n) |
12.2.6 Comparaison des exemples
Algorithme | Sous-problèmes par appel | Taille | Combinaison | Complexité |
|---|---|---|---|---|
| Recherche dichotomique | 1 | n/2 | O(1) | O(log n) |
| Tri fusion | 2 | n/2 | O(n) | Θ(n log n) |
| Tri rapide moyen | 2 | ≈ n/2 | Partition O(n) | O(n log n) |
| Maximum DC | 2 | n/2 | O(1) | Θ(n) |
| Puissance rapide | 1 | n/2 | O(1) | O(log n) |
12.3 Analyse
12.3.1 Les paramètres déterminants
L’analyse d’un algorithme « diviser pour régner » commence par l’identification de quatre informations : la taille du problème, le nombre de sous-problèmes, leur taille et le coût de la division ou de la combinaison.
Symbole | Signification |
|---|---|
| n | Taille du problème initial |
| a | Nombre de sous-problèmes créés à chaque appel |
| n/b | Taille approximative de chaque sous-problème |
| f(n) | Coût de division, combinaison et travail hors récursion |
| T(n) | Coût total pour une instance de taille n |
| Forme générale |
| T(n) = a × T(n / b) + f(n) Exemples : Recherche dichotomique : T(n) = T(n/2) + O(1) Tri fusion : T(n) = 2T(n/2) + O(n) Maximum divisé : T(n) = 2T(n/2) + O(1) |
12.3.2 Taille des sous-problèmes
La vitesse de réduction contrôle la profondeur. Si la taille est divisée par deux, le nombre de niveaux est logarithmique. Si elle ne diminue que d’une unité, la profondeur devient linéaire.
Évolution de taille | Profondeur approximative | Exemple |
|---|---|---|
| n, n/2, n/4, …, 1 | log₂ n | Recherche dichotomique |
| n, n − 1, n − 2, …, 1 | n | Tri rapide très déséquilibré |
| n, n/3, n/9, …, 1 | log₃ n | Division en tiers |
12.3.3 Nombre d’appels
Le nombre total d’appels dépend du nombre de branches de l’arbre de récursion. Un seul sous-problème par niveau produit une chaîne d’appels. Deux sous-problèmes équilibrés produisent un arbre binaire dont le nombre de feuilles peut être proportionnel à n.
| Deux formes d’arbres |
| Un sous-problème : Deux sous-problèmes : n n | / \ n/2 n/2 n/2 | / \ / \ n/4 ... ... ... ... | 1 |
12.3.4 Coût de combinaison
Une profondeur logarithmique ne garantit pas automatiquement une complexité logarithmique. Le travail réalisé à chaque niveau doit être additionné. Dans le tri fusion, toutes les fusions d’un même niveau coûtent au total Θ(n), d’où Θ(n log n).
Récurrence | Travail par niveau | Nombre de niveaux | Ordre final |
|---|---|---|---|
| T(n)=T(n/2)+O(1) | O(1) | O(log n) | O(log n) |
| T(n)=2T(n/2)+O(1) | Croît jusqu’à O(n) | O(log n) | O(n) |
| T(n)=2T(n/2)+O(n) | O(n) | O(log n) | O(n log n) |
| T(n)=T(n−1)+O(n) | Décroît de n à 1 | O(n) | O(n²) |
12.3.5 Relations de récurrence simples
Une relation de récurrence exprime le coût d’une instance en fonction du coût d’instances plus petites. Elle doit être accompagnée d’une condition initiale, par exemple T(1)=Θ(1).
Algorithme | Récurrence simplifiée | Solution intuitive |
|---|---|---|
| Recherche dichotomique | T(n)=T(n/2)+c | Θ(log n) |
| Puissance rapide | T(n)=T(n/2)+c | Θ(log n) |
| Maximum divisé | T(n)=2T(n/2)+c | Θ(n) |
| Tri fusion | T(n)=2T(n/2)+cn | Θ(n log n) |
| Tri rapide pire cas | T(n)=T(n−1)+cn | Θ(n²) |
12.3.6 Méthode par développement
Pour une récurrence simple, on peut remplacer successivement T par son expression jusqu’au cas de base.
| Développement de T(n)=T(n/2)+c |
| T(n) = T(n/2) + c = T(n/4) + 2c = T(n/8) + 3c = ... = T(1) + c log₂(n) Donc T(n) = Θ(log n). |
| Développement de T(n)=T(n−1)+cn |
| T(n) = T(n−1) + cn = T(n−2) + c(n−1) + cn = ... = T(1) + c(2 + 3 + ... + n) La somme est Θ(n²). |
12.3.7 Arbre de récursion
L’arbre de récursion visualise le coût de chaque appel et permet de sommer le travail par niveau. Cette méthode est particulièrement pédagogique pour les récurrences de la forme aT(n/b)+f(n).
| Arbre du tri fusion |
| Niveau 0 : cn -> cn Niveau 1 : c(n/2) + c(n/2) -> cn Niveau 2 : 4 appels de coût c(n/4) -> cn ... Niveau log n : n cas de base de coût constant -> cn Total : cn × log n + O(n) = Θ(n log n) |
12.3.8 Correction et preuve
La correction d’un algorithme « diviser pour régner » se démontre souvent par induction sur la taille n.
- Montrer que l’algorithme est correct pour le cas de base.
- Supposer que les appels récursifs sont corrects pour toutes les tailles strictement inférieures à n.
- Montrer que la division produit des sous-problèmes valides.
- Montrer que la combinaison de solutions correctes donne une solution correcte pour la taille n.
- Vérifier que la mesure de taille diminue afin de garantir la terminaison.
| Exemple de preuve — Pour le tri fusion, l’hypothèse d’induction affirme que chaque moitié est correctement triée. La procédure de fusion doit ensuite être prouvée correcte pour obtenir un tableau globalement trié. |
12.3.9 Avantages et limites
Avantages | Limites |
|---|---|
| Structure claire et modulaire | Coût des appels récursifs |
| Réduction rapide de la taille | Mémoire de la pile |
| Analyse souvent structurée par récurrence | Risque de mauvaise division |
| Sous-problèmes parfois parallélisables | Combinaison potentiellement coûteuse |
| Très efficace pour recherche et tri | Inadapté aux sous-problèmes fortement recouvrants |
Applications guidées
Application 1 — Identifier les trois phases
Pour chacun des problèmes suivants, identifier la division, la résolution et la combinaison : recherche d’une valeur, calcul du maximum, tri d’un tableau et calcul d’une puissance.
Problème | Diviser | Résoudre | Combiner |
|---|---|---|---|
| Recherche dichotomique | Choisir une moitié | Chercher dans la moitié conservée | Retourner directement le résultat |
| Maximum | Couper en deux | Maximum de chaque moitié | Comparer les deux maxima |
| Tri fusion | Couper en deux | Trier les moitiés | Fusionner |
| Puissance rapide | Diviser n par 2 | Calculer x^(n/2) | Élever au carré et ajuster si impair |
Application 2 — Comparer deux algorithmes de puissance
La méthode naïve multiplie x par lui-même n fois. L’exponentiation rapide réutilise une seule valeur calculée pour n/2. Pour n=1 000 000, l’écart entre n et log₂ n est considérable.
n | Méthode naïve | Méthode rapide |
|---|---|---|
| 16 | 16 multiplications | 4 niveaux environ |
| 1 024 | 1 024 multiplications | 10 niveaux environ |
| 1 000 000 | ≈ 1 000 000 multiplications | ≈ 20 niveaux |
Application 3 — Division équilibrée ou déséquilibrée
Comparer deux versions d’un même algorithme récursif : la première divise en deux moitiés, la seconde retire un seul élément. La première a une profondeur logarithmique ; la seconde une profondeur linéaire. Toutefois, le coût total dépend aussi du nombre de branches et de la combinaison.
| Comparaison des profondeurs pour n = 1 024 |
| Division par deux : 1 024 -> 512 -> ... -> 1 Profondeur ≈ 10 Réduction de un : 1 024 -> 1 023 -> ... -> 1 Profondeur ≈ 1 023 |
Application 4 — Concevoir un algorithme min-max
On souhaite calculer simultanément le minimum et le maximum d’un tableau. La division en deux permet de combiner deux couples (min, max). Cette stratégie peut réduire le nombre de comparaisons par rapport à deux parcours indépendants.
| PSEUDO-CODE — Minimum et maximum par division |
| Fonction MinMax(T, gauche, droite) : Couple Si gauche = droite Alors Retourner (T[gauche], T[gauche]) FinSi Si droite = gauche + 1 Alors Si T[gauche] < T[droite] Alors Retourner (T[gauche], T[droite]) Sinon Retourner (T[droite], T[gauche]) FinSi FinSi milieu ← gauche + (droite - gauche) div 2 (minG, maxG) ← MinMax(T, gauche, milieu) (minD, maxD) ← MinMax(T, milieu + 1, droite) Retourner (minimum(minG, minD), maximum(maxG, maxD)) FinFonction |
Méthode de conception et erreurs fréquentes
Démarche de conception
1. Définir précisément la taille n et la représentation du problème.
2. Choisir un cas de base simple et correct.
3. Définir une division produisant des sous-problèmes strictement plus petits.
4. Écrire les appels récursifs avec des bornes cohérentes.
5. Définir la combinaison des résultats.
6. Vérifier la terminaison sur les tailles minimales et impaires.
7. Établir la relation de récurrence.
8. Comparer la solution obtenue à une approche directe.
Erreurs fréquentes
Erreur | Conséquence | Correction |
|---|---|---|
| Cas de base absent | Récursion infinie | Définir la taille minimale |
| Sous-problème de même taille | Aucune progression | Réduire strictement les bornes |
| Milieu mal calculé | Case oubliée ou répétée | Utiliser gauche + (droite−gauche) div 2 |
| Résultat récursif recalculé | Complexité inutilement élevée | Stocker le résultat dans une variable |
| Combinaison incorrecte | Résultat global faux | Définir un invariant de combinaison |
| Division très déséquilibrée | Profondeur et temps élevés | Choisir une division plus équilibrée |
| Sous-problèmes recouvrants | Calculs répétés | Envisager la mémoïsation |
Travaux dirigés
TD 1 — Reconnaître le paradigme
Pour chaque description, préciser si elle relève de « diviser pour régner » et justifier : parcours séquentiel, recherche dichotomique, tri fusion, Fibonacci récursif naïf, calcul du maximum par moitiés.
TD 2 — Trace de recherche dichotomique
Tracer les appels pour rechercher 31 dans le tableau [3, 7, 12, 18, 23, 31, 42, 57, 68]. Donner les intervalles successifs et la profondeur.
TD 3 — Arbre du tri fusion
Construire l’arbre de division du tableau [8, 3, 6, 2, 7, 1, 5, 4], puis écrire les fusions réalisées lors de la remontée.
TD 4 — Effet du pivot
Comparer les partitions du tableau [1, 2, 3, 4, 5, 6, 7, 8] lorsque le pivot est le premier élément, puis lorsqu’il est choisi au centre. Expliquer les complexités attendues.
TD 5 — Maximum récursif
Écrire une version récursive du maximum divisant le tableau en deux, puis établir sa relation de récurrence et son nombre exact de comparaisons.
TD 6 — Exponentiation rapide
Calculer 2¹³ en traçant les appels et les valeurs retournées. Comparer le nombre de multiplications à la méthode naïve.
TD 7 — Établir une récurrence
Établir la récurrence des algorithmes suivants : recherche dichotomique, tri fusion, maximum par moitiés et algorithme qui crée trois sous-problèmes de taille n/3 avec une combinaison linéaire.
TD 8 — Résoudre par développement
Résoudre intuitivement : a) T(n)=T(n/2)+1 ; b) T(n)=2T(n/2)+1 ; c) T(n)=2T(n/2)+n ; d) T(n)=T(n−1)+n.
TD 9 — Corriger un algorithme
Un étudiant utilise milieu=(gauche+droite) div 2 puis appelle récursivement [gauche, milieu] et [milieu, droite]. Identifier le risque et proposer des bornes correctes.
TD 10 — Conception MinMax
Appliquer l’algorithme MinMax au tableau [9, 4, 12, 2, 15, 7, 1, 10]. Construire l’arbre des couples retournés et compter les comparaisons.
Corrigés indicatifs des travaux dirigés
Correction du TD 1
Méthode | Diviser pour régner ? | Justification |
|---|---|---|
| Parcours séquentiel | Non | Pas de sous-problèmes ni de combinaison |
| Recherche dichotomique | Oui | Réduction à une moitié de même nature |
| Tri fusion | Oui | Deux moitiés indépendantes et fusion |
| Fibonacci récursif naïf | Pas au sens efficace | Sous-problèmes recouvrants recalculés |
| Maximum par moitiés | Oui | Deux maxima combinés par une comparaison |
Correction du TD 2
Appel | Intervalle | Milieu | Valeur | Action |
|---|---|---|---|---|
| 1 | [0,8] | 4 | 23 | Aller à droite |
| 2 | [5,8] | 6 | 42 | Aller à gauche |
| 3 | [5,5] | 5 | 31 | Trouvé |
La profondeur est de trois appels, ce qui est cohérent avec O(log n).
Correction du TD 3
| Division et remontée |
| Division : [8,3,6,2,7,1,5,4] -> [8,3,6,2] | [7,1,5,4] -> [8,3] [6,2] [7,1] [5,4] -> éléments seuls Fusions : [8]+[3] -> [3,8] [6]+[2] -> [2,6] [7]+[1] -> [1,7] [5]+[4] -> [4,5] [3,8]+[2,6] -> [2,3,6,8] [1,7]+[4,5] -> [1,4,5,7] Résultat -> [1,2,3,4,5,6,7,8] |
Correction du TD 4
Avec le premier élément comme pivot sur un tableau déjà trié, chaque partition donne une zone vide et une zone de taille n−1 : la profondeur est n et le temps Θ(n²). Un pivot central produit deux zones équilibrées, une profondeur O(log n) et un temps O(n log n).
Correction du TD 5
| PSEUDO-CODE — Maximum récursif — correction |
| Fonction MaximumDC(T, g, d) : Nombre Si g = d Alors Retourner T[g] FinSi m ← g + (d - g) div 2 a ← MaximumDC(T, g, m) b ← MaximumDC(T, m + 1, d) Retourner maximum(a, b) FinFonction |
Récurrence : T(n)=2T(n/2)+O(1), donc Θ(n). Le nombre exact de comparaisons entre valeurs est n−1.
Correction du TD 6
| Calcul de 2¹³ |
| P(2,13) -> P(2,6) -> P(2,3) -> P(2,1) -> P(2,0)=1 P(2,1)=2 P(2,3)=2 × 2² = 8 P(2,6)=8² = 64 P(2,13)=2 × 64² = 8192 |
La profondeur est de cinq appels en comptant le cas n=0. La méthode naïve demanderait 13 multiplications successives ; la méthode rapide en demande un nombre proportionnel à log n.
Correction du TD 7
Algorithme | Récurrence |
|---|---|
| Recherche dichotomique | T(n)=T(n/2)+O(1) |
| Tri fusion | T(n)=2T(n/2)+O(n) |
| Maximum par moitiés | T(n)=2T(n/2)+O(1) |
| Trois sous-problèmes + combinaison linéaire | T(n)=3T(n/3)+O(n) |
Correction du TD 8
Récurrence | Ordre | Justification intuitive |
|---|---|---|
| T(n)=T(n/2)+1 | Θ(log n) | Une chaîne logarithmique |
| T(n)=2T(n/2)+1 | Θ(n) | Nombre total de nœuds proportionnel à n |
| T(n)=2T(n/2)+n | Θ(n log n) | n par niveau, log n niveaux |
| T(n)=T(n−1)+n | Θ(n²) | Somme 1+2+…+n |
Correction du TD 9
L’appel [milieu, droite] peut conserver exactement le même intervalle lorsque droite=gauche+1, car milieu=gauche. Il faut définir des intervalles disjoints : [gauche, milieu] et [milieu+1, droite], ou exclure explicitement le pivot selon le problème.
Correction du TD 10
| Couples retournés |
| [9,4] -> (4,9) [12,2] -> (2,12) [15,7] -> (7,15) [1,10] -> (1,10) Gauche : (min(4,2), max(9,12)) = (2,12) Droite : (min(7,1), max(15,10)) = (1,15) Global : (min(2,1), max(12,15)) = (1,15) |
Pour n=8, cette version effectue 10 comparaisons de valeurs avec le cas spécial de deux éléments, contre 14 comparaisons pour deux parcours indépendants.
Travail pratique — Étude expérimentale de « diviser pour régner »
Objectifs
- Implémenter plusieurs algorithmes du chapitre.
- Instrumenter les appels récursifs et les opérations élémentaires.
- Comparer les mesures aux complexités théoriques.
- Observer l’effet d’une division équilibrée ou déséquilibrée.
- Présenter les résultats dans des tableaux et graphiques.
Travail demandé
1. Implémenter la recherche dichotomique récursive.
2. Implémenter le maximum par division en deux.
3. Implémenter la puissance naïve et l’exponentiation rapide.
4. Ajouter des compteurs d’appels, de comparaisons et de multiplications.
5. Tester des tailles croissantes : 16, 64, 256, 1 024 et 4 096.
6. Pour le tri rapide, comparer un pivot extrême et un pivot aléatoire sur données triées.
7. Tracer les temps ou nombres d’opérations en fonction de n.
8. Rédiger une conclusion reliant mesures, récurrences et complexités.
Architecture proposée
| PSEUDO-CODE — Programme expérimental |
| Algorithme ComparerDiviserPourRegner Variables tailles : Tableau d’Entiers n, appels, opérations : Entier Début tailles ← [16, 64, 256, 1024, 4096] Pour chaque n dans tailles Faire Générer des données de taille n RéinitialiserCompteurs() Exécuter MaximumDC Enregistrer(n, appels, opérations) RéinitialiserCompteurs() Exécuter RechercheDichotomique Enregistrer(n, appels, opérations) RéinitialiserCompteurs() Exécuter PuissanceRapide Enregistrer(n, appels, opérations) FinPour AfficherTableauxEtGraphiques() FinAlgorithme |
Jeux d’essai minimaux
Test | Donnée | Résultat attendu |
|---|---|---|
| Recherche réussie | Tableau trié, valeur présente | Indice valide |
| Recherche absente | Tableau trié, valeur absente | -1 |
| Maximum minimal | Un seul élément | Cet élément |
| Maximum général | Valeurs positives et négatives | Plus grande valeur |
| Puissance zéro | x⁰ | 1 |
| Exposant pair | 3¹⁰ | 59 049 |
| Exposant impair | 2¹³ | 8 192 |
| Tri rapide défavorable | Tableau trié + pivot extrême | Profondeur proche de n |
Résultats attendus
Algorithme | Tendance attendue |
|---|---|
| Recherche dichotomique | Le nombre d’appels augmente très lentement : log n |
| Maximum divisé | Le nombre de feuilles et de comparaisons est linéaire |
| Puissance naïve | Le nombre de multiplications suit n |
| Puissance rapide | Le nombre d’appels suit log n |
| Tri rapide équilibré | Profondeur proche de log n |
| Tri rapide déséquilibré | Profondeur proche de n et temps quadratique |
Grille d’évaluation
Critère | Points |
|---|---|
| Correction des implémentations | 5 |
| Instrumentation et compteurs | 3 |
| Qualité des jeux d’essai | 3 |
| Présentation des résultats | 3 |
| Analyse théorique et expérimentale | 4 |
| Qualité du code et du rapport | 2 |
| Total | 20 |
Synthèse du chapitre
Élément | À retenir |
|---|---|
| Diviser | Créer des sous-problèmes strictement plus petits et si possible équilibrés |
| Résoudre | Utiliser un cas de base puis des appels récursifs |
| Combiner | Assembler correctement les solutions partielles |
| Terminaison | Faire diminuer une mesure entière positive |
| Analyse | Identifier a, n/b et f(n) dans la récurrence |
| Profondeur | Division par un facteur constant : profondeur logarithmique |
| Sous-problèmes | Indépendants de préférence ; sinon envisager la programmation dynamique |
| Exemples | Recherche dichotomique, tris fusion et rapide, maximum, puissance rapide |
| Conclusion — Le paradigme est puissant parce qu’il associe une idée de conception, une structure récursive et une méthode d’analyse. La qualité de la division et de la combinaison détermine son efficacité réelle. |
Glossaire
Terme | Définition |
|---|---|
| Cas de base | Instance résolue directement sans nouvel appel récursif |
| Combinaison | Construction du résultat global à partir des solutions partielles |
| Division équilibrée | Découpage produisant des sous-problèmes de tailles comparables |
| Arbre de récursion | Arbre représentant les appels et le coût associé à chaque nœud |
| Relation de récurrence | Équation reliant T(n) à des valeurs T de tailles inférieures |
| Profondeur | Nombre maximal d’appels imbriqués avant le cas de base |
| Sous-problèmes indépendants | Sous-problèmes ne recalculant pas les mêmes états |
| Travail hors récursion | Coût de division, partition, comparaison ou combinaison |
Auto-évaluation
Je suis capable de… | Oui | À renforcer |
|---|---|---|
| Identifier les phases diviser, résoudre et combiner | ☐ | ☐ |
| Définir un cas de base correct | ☐ | ☐ |
| Tracer un arbre d’appels récursifs | ☐ | ☐ |
| Écrire une recherche dichotomique récursive | ☐ | ☐ |
| Expliquer les différences entre tri fusion et tri rapide | ☐ | ☐ |
| Écrire une exponentiation rapide | ☐ | ☐ |
| Établir une relation de récurrence simple | ☐ | ☐ |
| Estimer une complexité par niveaux | ☐ | ☐ |
| Détecter une division déséquilibrée | ☐ | ☐ |
| Choisir entre diviser pour régner et une autre méthode | ☐ | ☐ |