NSI · Terminale · Contrôle n°1
Paradigme diviser pour régner
Un contrôle de NSI de 60 minutes sur le paradigme diviser pour régner : ses trois étapes, les deux conditions sans lesquelles il ne fait rien gagner, les trois exemples classiques et ce que chacun illustre, et le calcul de complexité par récurrence. Vingt points, barème détaillé, et une correction qui dit pourquoi à chaque question.
Imprimer le contrôle
Deux PDF à imprimer, sur papier A4. Gratuit, sans inscription.
Avant de commencer
- Vérifier les deux conditions avant d’annoncer la moindre complexité.
- Le paradigme est une méthode de conception, pas une garantie de performance.
- Couper en un élément et le reste ramène au parcours linéaire.
- Si recoller coûte autant que résoudre, le découpage n’apporte rien.
- La combinaison du tri rapide est gratuite ; l’équilibre, lui, dépend du pivot.
- Poser la récurrence plutôt qu’annoncer une complexité par reconnaissance de forme.
Exercice 1 — Le principe
4 pts · 11 minÉnoncer le paradigme
Réponds à chaque question.
1.Que fait le paradigme diviser pour régner ?
1 ptVoir la correction
Il décompose un problème en sous-problèmes de même nature mais de taille moindre, les résout, puis combine les solutions partielles.
La résolution se fait le plus souvent par récurrence.
2.Quelles sont ses trois étapes ?
1 ptVoir la correction
Diviser, régner, combiner.
Les trois se suivent dans cet ordre.
3.D’où vient le gain ?
1 ptVoir la correction
Du fait que la somme des coûts des sous-problèmes plus le coût de combinaison soit inférieure au coût direct.
Il ne vient donc pas de la division en elle-même.
4.Le paradigme garantit-il une meilleure performance ?
1 ptVoir la correction
Non : c’est une méthode de conception, pas une garantie.
Annoncer une complexité parce qu’on reconnaît le paradigme confond la forme et le coût.
Exercice 2 — Les deux conditions
5 pts · 14 minVérifier les conditions d'efficacité
Réponds à chaque question.
1.Quelle est la première condition ?
1 ptVoir la correction
Les sous-problèmes doivent être de tailles comparables.
Couper en deux moitiés égales fait chuter la profondeur à log n.
2.Que se passe-t-il si l’on coupe en un élément et le reste ?
1 ptVoir la correction
On retombe sur un parcours linéaire.
Le découpage ne réduit alors la taille que d’une unité à chaque étape.
3.Quelle est la seconde condition ?
1 ptVoir la correction
L’étape de combinaison doit rester peu coûteuse.
Si recoller coûte autant que résoudre, le découpage n’apporte rien.
4.Quel exemple montre qu’un découpage déséquilibré annule le gain ?
1 ptVoir la correction
Le tri rapide mal pivoté, qui dégénère en O(n²).
Il devient alors aussi coûteux qu’un tri élémentaire.
5.Que faut-il faire avant d’annoncer la moindre complexité ?
1 ptVoir la correction
Vérifier les deux conditions.
La reconnaissance du paradigme ne dit rien du coût réel.
Exercice 3 — Trois exemples
4 pts · 11 minAnalyser trois algorithmes
Réponds à chaque question.
1.Pourquoi la recherche dichotomique n’a-t-elle rien à combiner ?
1 ptVoir la correction
Parce qu’elle divise l’espace de recherche en deux et n’en garde qu’une moitié.
D’où sa complexité en O(log n).
2.Qu’est-ce qui donne au tri fusion sa garantie en O(n log n) dans tous les cas ?
1 ptVoir la correction
La garantie de tailles égales et une combinaison bon marché, la fusion se faisant en temps linéaire.
Les deux conditions y sont donc satisfaites d’avance.
3.Quel avantage le tri rapide a-t-il sur le tri fusion ?
1 ptVoir la correction
Sa combinaison est gratuite : après partition, les deux parties sont déjà à leur place relative.
Le tri fusion, lui, doit fusionner explicitement.
4.De quoi dépend l’équilibre des tailles dans le tri rapide, et avec quelles conséquences ?
1 ptVoir la correction
Du pivot : bien choisi, O(n log n) en moyenne ; systématiquement mal choisi, O(n²).
D’où les stratégies de choix de pivot, qui sont tout l’enjeu de son implémentation.
Exercice 4 — Calculer la complexité
4 pts · 13 minPoser une récurrence de complexité
Réponds à chaque question.
1.Comment la complexité se calcule-t-elle ?
1 ptVoir la correction
Par une relation de récurrence : le coût pour une entrée de taille n s’exprime en fonction du coût des sous-problèmes et du coût de combinaison.
C’est cette relation qu’il faut poser avant de conclure.
2.Que donne l’équation de maître ?
1 ptVoir la correction
Le résultat selon lequel des deux termes l’emporte.
Elle départage les sous-problèmes et la combinaison.
3.Quels sont les trois cas possibles ?
1 ptVoir la correction
La combinaison domine et fixe la complexité ; les sous-problèmes dominent et la fixent ; ou ils s’équilibrent et un facteur logarithmique apparaît.
Le troisième cas est celui du tri fusion.
4.Sur un million d’éléments, combien vaut environ n log n, et n² ?
1 ptVoir la correction
Environ 20 millions pour n log n, et 10¹² pour n².
Le rapport entre les deux dépasse cinquante mille.
Exercice 5 — Trouve l'erreur
3 pts · 11 minRepérer une erreur et la corriger
Chaque affirmation est fausse. Écris ce qu’il fallait dire.
1.« Mon algorithme divise le problème : il est donc plus efficace qu’une approche directe. »
1 ptVoir la correction
Le paradigme est une méthode de conception, pas une garantie de performance.
Il faut vérifier les tailles comparables et le coût de la combinaison.
2.« Je découpe mon tableau en un élément d’un côté et tout le reste de l’autre : c’est bien diviser pour régner. »
1 ptVoir la correction
Les sous-problèmes doivent être de tailles comparables ; ce découpage ramène au parcours linéaire.
La profondeur ne chute à log n qu’avec des moitiés égales.
3.« Le tri rapide garantit une complexité en O(n log n). »
1 ptVoir la correction
Il l’atteint en moyenne avec un bon pivot ; systématiquement mal pivoté, il dégénère en O(n²).
C’est le tri fusion qui offre la garantie dans tous les cas.
Barème — ce que le correcteur regarde
Les lignes chiffrées couvrent les 5 exercices et totalisent 20 points.
Ex.1Le principe et ses trois étapes
4 points — 1 par question
Point perdu si : Le gain attribué à la division elle-même.
Ex.2Les deux conditions
5 points — 1 par question
Point perdu si : Une condition sur deux énoncée.
Ex.3Les trois exemples
4 points — 1 par question
Point perdu si : Le tri rapide crédité d’une garantie qu’il n’a pas.
Ex.4Calculer la complexité
4 points — 1 par question
Point perdu si : Une complexité annoncée sans récurrence.
Ex.5L’erreur repérée, et la réponse juste donnée
3 points — 1 par ligne
Point perdu si : Une correction qui confond la forme de l’algorithme et son coût.
Et maintenant ?
- 16 à 20
- Le chapitre est acquis. Entraîne-toi maintenant à concevoir en cinq temps : le découpage de même nature, les tailles comparables vérifiées, le cas de base écrit, la combinaison estimée, et la récurrence posée.
- 10 à 15
- Refais l'exercice 2 en te demandant chaque fois laquelle des deux conditions est en cause.
- moins de 10
- Reprends la fiche de cours et retiens d'où vient le gain : non de la division, mais du fait que la somme des coûts des sous-problèmes plus la combinaison soit inférieure au coût direct.
Les autres contrôles de nsi Terminale
Programme de terminale générale, enseignement de spécialité — BO spécial n°8 du 25 juillet 2019 · Contrôle rédigé pour ProgresSchool, version 2026.1.