NSI Terminale • Programme français, lycées de Montréal

Fiche de révision : diviser pour régner, programmation dynamique et graphes

Le chapitre d'algorithmique avancée est celui où les résultats se retiennent facilement et où les conditions d'application s'oublient : la dichotomie veut un tableau trié, le tri rapide n'est rapide qu'en moyenne, un glouton se démontre, Dijkstra refuse les poids négatifs. Presque tous les points perdus le sont sur une condition oubliée.

Cette fiche liste les neuf erreurs qui reviennent dans les copies, avec la phrase exacte à écrire à la place et ce que chacune coûte au barème.

Le fil du chapitre

Diviser pour régner et programmation dynamique répondent à la même question, « ai-je déjà résolu ce sous-problème ? » : la première répond non par construction, la seconde répond oui et le retient.

Ce chapitre fait partie de NSI en Terminale

Avant ce chapitre

Cette fiche suppose ces notions acquises. Si une méthode ci-dessous reste opaque, c'est presque toujours l'une d'elles qui manque, pas la fiche.

Structures de données : piles, files, arbres et graphes Fiche

Remonter plus loin : la chaîne complète (4 chapitres) ↓

Le chemin de remédiation, du plus ancien au plus proche. Un élève qui reprend ce chapitre de zéro le reprend dans cet ordre.

L'essentiel

Les coûts à savoir citer, avec leur condition

• Recherche dichotomique : tableau TRIÉ obligatoire, $\lfloor \log_{2} n \rfloor + 1$ comparaisons, soit 10 pour mille éléments.
• Tri fusion : $n \log_{2} n$ GARANTI, stable, mais mémoire supplémentaire linéaire.
• Tri rapide : $n \log_{2} n$ EN MOYENNE, $n^{2}$ au pire, en place, non stable.
• Parcours de graphe : $O(n + m)$ avec des listes d'adjacence, $O(n^{2})$ avec une matrice.

Dans une question de coût, écrire la condition en même temps que le résultat : « $n \log_{2} n$ en moyenne » vaut le point, « $n \log_{2} n$ » seul ne le vaut pas toujours.

Lire une récurrence de coût

• La récurrence se lit sur l'algorithme : combien d'appels, sur quelle taille, plus quel travail de recombinaison.
• $C(n) = 2C(n/2) + n$ décrit le tri fusion : deux moitiés, plus une fusion linéaire, d'où $n \log_{2} n$ .
• $C(n) = C(n/2) + 1$ décrit la dichotomie : une seule moitié, plus une comparaison, d'où $\log_{2} n$ .
• Méthode de l'arbre : au niveau $k$ il y a $a^{k}$ sous-problèmes de taille $n/b^{k}$ ; on somme le travail par niveau, puis on multiplie par le nombre de niveaux.

À chaque niveau, les morceaux rétrécissent mais leur total reste

n

: le coût est donc

n

multiplié par le nombre de niveaux, c'est-à-dire

n \log_{2} n

Glouton, dynamique, et ce qui les sépare

• Un algorithme GLOUTON fait le choix localement le meilleur et ne revient jamais dessus. Il est rapide et souvent FAUX.
• Un glouton doit être DÉMONTRÉ : sans preuve, il n'est qu'une heuristique, et le sujet demande un contre-exemple.
• La programmation dynamique s'applique quand le problème vérifie le PRINCIPE D'OPTIMALITÉ : une solution optimale est faite de solutions optimales de ses sous-problèmes.
• Elle range chaque valeur dans une table remplie de bas en haut, ce qui garantit que chaque sous-problème n'est résolu qu'une fois.

Le sac à dos, et son coût trompeur

• Relation : $V(i, c) = \max(V(i-1, c),\ v_{i} + V(i-1, c - p_{i}))$ quand l'objet $i$ tient dans la capacité $c$ , et $V(i-1, c)$ sinon.
• La table a $n$ lignes et $C+1$ colonnes : le coût est $nC$ .
• Ce coût est PSEUDO-POLYNOMIAL : il dépend de la VALEUR de la capacité, pas seulement du nombre d'objets, alors que la capacité s'écrit avec $\log_{2} C$ bits.
• La reconstruction de la solution se lit à rebours dans la table, en comparant chaque case à celle du dessus.

Dijkstra

• À chaque tour, on sélectionne le sommet NON TRAITÉ de plus petite distance provisoire, jamais le voisin le plus proche du dernier sommet traité.
• On relâche ensuite chaque arête sortante : si passer par le sommet choisi raccourcit, on met à jour la distance et le prédécesseur.
• Les poids doivent être POSITIFS : un poids négatif peut améliorer un sommet déjà traité, ce que l'algorithme n'envisage plus.
• Un parcours en largeur est exactement Dijkstra avec toutes les arêtes de poids 1.

Les pièges qui coûtent des points

Les erreurs ci-dessous sont celles que je corrige le plus souvent en séance. Chacune coûte des points sur une copie, même quand le raisonnement est juste.

1. Faire une dichotomie sans dire que le tableau est trié

2 points, et l'algorithme renvoie une réponse fausse sans erreur

Ce qu'il ne faut pas écrire

« Je cherche la valeur par dichotomie dans le tableau des relevés. »

Ce qu'il faut écrire

« La dichotomie exige un tableau TRIÉ : je le trie d'abord, ou je justifie qu'il l'est déjà. Le coût est alors $\lfloor \log_{2} n \rfloor + 1$ comparaisons. »

Pourquoi : Sur un tableau non trié, la dichotomie élimine une moitié qui pouvait contenir la valeur : elle répond « absent » alors que la valeur est là. Rien ne le signale.

2. Annoncer un tri rapide en $n \log_{2} n$ sans réserve

2 points, et c'est la question de comparaison des tris

Ce qu'il ne faut pas écrire

« Le tri rapide coûte $n \log_{2} n$ , comme le tri fusion. »

Ce qu'il faut écrire

« $n \log_{2} n$ EN MOYENNE. Au pire, avec un pivot fixe sur un tableau déjà trié, les partitions sont de tailles $n-1$ et $0$ : le coût devient $n^{2}$ , soit 28 comparaisons pour $n = 8$ . »

Le même tableau de huit éléments : un pivot médian divise à chaque tour, un pivot fixe sur un tableau déjà trié n'enlève qu'un élément et produit huit niveaux au lieu de quatre.

Pourquoi : Le tri rapide n'a aucune garantie : c'est le choix du pivot qui décide de la forme de la récursion. Le tri fusion, lui, garantit ses $n \log_{2} n$ quelle que soit l'entrée.

3. Croire que le tri fusion trie en place

1 point sur la question de comparaison, qui attend un critère par ligne

Ce qu'il ne faut pas écrire

« Le tri fusion est meilleur que le tri rapide sur tous les critères. »

Ce qu'il faut écrire

« Le tri fusion garantit $n \log_{2} n$ et il est stable, mais il consomme une mémoire supplémentaire linéaire. Le tri rapide trie en place. »

Pourquoi : Aucun tri n'est meilleur sur tous les critères : coût garanti, stabilité, mémoire, comportement en pratique. Le sujet demande toujours de comparer selon plusieurs critères nommés.

4. Appliquer un algorithme glouton sans le démontrer

2 points, et le contre-exemple est explicitement demandé

Ce qu'il ne faut pas écrire

« Je prends à chaque fois la plus grande pièce possible, donc j'obtiens le nombre minimal de pièces. »

Ce qu'il faut écrire

« Le glouton n'est optimal que pour certains systèmes de pièces. Avec les pièces 1, 3 et 4 et la somme 6, il donne $4 + 1 + 1$ , soit trois pièces, alors que $3 + 3$ en suffit deux. »

La même somme rendue deux fois : le choix local de la plus grosse pièce interdit ensuite le découpage à deux pièces, et rien dans le déroulement glouton ne le signale.

Pourquoi : Un choix localement optimal peut fermer la porte à une meilleure solution globale. C'est exactement ce que la programmation dynamique évite, en examinant les deux possibilités à chaque étape.

5. Remplir la table de programmation dynamique dans le mauvais sens

1 point, et la complexité annoncée devient fausse

Ce qu'il ne faut pas écrire

« Je calcule $V(n, C)$ , puis les cases dont il dépend, et ainsi de suite. »

Ce qu'il faut écrire

« La table se remplit de BAS EN HAUT : chaque case n'utilise que des cases déjà calculées. Sinon on refait de la récursion, et le gain disparaît. »

Pourquoi : Tout l'intérêt de la programmation dynamique est que chaque sous-problème est résolu UNE fois. Remplir dans le désordre équivaut à une récursion sans mémoïsation.

6. Croire le sac à dos polynomial

2 points sur la question de recul, où le vocabulaire est noté

Ce qu'il ne faut pas écrire

« La table fait $n \times C$ cases, donc l'algorithme est polynomial. »

Ce qu'il faut écrire

« Il est PSEUDO-polynomial : $C$ est une valeur, pas une taille d'entrée. La capacité s'écrit sur $\log_{2} C$ bits, donc le coût est exponentiel en la taille de l'écriture de $C$ . »

Pourquoi : La complexité se mesure en fonction de la TAILLE de l'entrée, c'est-à-dire du nombre de bits. Une capacité d'un milliard tient sur trente bits et donne pourtant un milliard de colonnes.

7. Sélectionner dans Dijkstra le voisin le plus proche du dernier sommet

toute la question de déroulé, souvent 5 points

Ce qu'il ne faut pas écrire

« Je viens de traiter B, donc je continue par son voisin le plus proche. »

Ce qu'il faut écrire

« On sélectionne le sommet NON TRAITÉ de plus petite distance PROVISOIRE À LA SOURCE, où qu'il se trouve dans le graphe. »

Pourquoi : Dijkstra construit un arbre de plus courts chemins depuis la SOURCE, pas un chemin qui avance de proche en proche. Suivre le dernier sommet, c'est faire un glouton local, et il est faux.

8. Appliquer Dijkstra avec des poids négatifs

2 points, et la justification demandée en fin de sujet

Ce qu'il ne faut pas écrire

« Une arête vaut $-2$ , mais l'algorithme marche quand même, il suffit de dérouler. »

Ce qu'il faut écrire

« Dijkstra exige des poids POSITIFS : un sommet est définitivement fixé dès qu'il est traité, et un poids négatif pourrait encore l'améliorer ensuite. »

Pourquoi : La correction de Dijkstra repose sur le fait qu'aucun détour ne peut raccourcir un chemin. Un poids négatif détruit cette propriété, et il faut alors un autre algorithme.

9. Oublier le travail de recombinaison dans la récurrence

2 points sur la question de récurrence, celle qui demande de raisonner

Ce qu'il ne faut pas écrire

« Le tri fusion coupe en deux à chaque fois, donc $C(n) = 2C(n/2)$ , soit un coût linéaire. »

Ce qu'il faut écrire

« Il faut ajouter la FUSION, qui parcourt les $n$ éléments : $C(n) = 2C(n/2) + n$ , d'où $n \log_{2} n$ . »

Pourquoi : C'est ce terme additif qui distingue le tri fusion de la dichotomie : dans un cas on recombine tout, dans l'autre on jette une moitié. La récurrence est le seul endroit où cette différence se voit.

Quelle méthode choisir

Quelle stratégie, selon la forme des sous-problèmes

Regarder si les sous-problèmes se recoupent, et si un choix local peut se démontrer optimal.

Si les sous-problèmes sont DISJOINTS → diviser pour régner

Exemple : tri fusion, dichotomie

aucune valeur n'est calculée deux fois, donc rien à mémoriser
Si les sous-problèmes SE RECOUPENT → programmation dynamique, avec une table

Exemple : rendu de monnaie, sac à dos
Si un choix local se démontre optimal → glouton, avec la preuve

Exemple : le rendu de monnaie du système euro
Si un choix local semble optimal sans preuve → chercher un contre-exemple avant tout

Exemple : pièces 1, 3, 4 et somme 6

c'est ce que le sujet attend, pas une justification vague

Si aucune branche ne s'applique, il reste l'exploration exhaustive, à ne proposer qu'en disant son coût.

Quel algorithme de graphe, selon la question

Le mot de l'énoncé, et la présence ou non de poids sur les arêtes.

Si « le moins d'étapes », arêtes non pondérées → parcours en largeur, avec une file

Exemple : sortir d'un labyrinthe
Si « le chemin le plus court », poids positifs → Dijkstra

Exemple : un trajet avec des durées
Si « existe-t-il un chemin », « les composantes » → parcours en profondeur

Exemple : tester la connexité
Si des poids négatifs apparaissent → Dijkstra est disqualifié, il faut le dire

Exemple : un gain sur une arête

le programme n'exige pas l'algorithme de remplacement, seulement le refus motivé

Un parcours en largeur est le cas particulier de Dijkstra où toutes les arêtes valent 1 : le dire rapporte souvent un demi-point.

La rédaction attendue

Le correcteur coche des étapes. Les voici dans l'ordre, avec la phrase de conclusion qu'il attend mot pour mot.

Dérouler Dijkstra dans un tableau

Quand l'utiliser : L'énoncé donne un graphe pondéré et demande le plus court chemin depuis un sommet.

1 Vérifier et écrire que tous les poids sont positifs : c'est la condition d'application, elle vaut un point.
2 Dresser un tableau avec une colonne par sommet, une ligne par tour, et une colonne pour le sommet sélectionné.
3 Initialiser : distance nulle pour la source, infinie pour les autres, aucun sommet traité.
4 À chaque tour, sélectionner le sommet non traité de plus petite distance, l'écrire, puis relâcher chacune de ses arêtes sortantes.
5 Conclure par la distance demandée ET par le chemin, reconstruit à rebours grâce aux prédécesseurs.

Phrase de conclusion

« Tous les poids étant positifs, l'algorithme de Dijkstra s'applique. Les sommets sont fixés dans l'ordre A, C, B, E, D, et la distance de A à D vaut 9, par le chemin A, C, E, D lu à rebours grâce aux prédécesseurs. »

Le piège : Ne pas noter les prédécesseurs au fur et à mesure : la distance sera juste, le chemin sera impossible à reconstituer et la moitié des points partira.

Barème : 1 point pour la condition sur les poids, 2 points pour le tableau, 1 point pour le chemin reconstruit.

Réfuter un algorithme glouton

Quand l'utiliser : L'énoncé demande si une stratégie gloutonne est optimale.

1 Énoncer précisément la stratégie gloutonne, en une phrase : quel choix est fait à chaque étape.
2 Chercher une instance petite où le premier choix ferme une meilleure solution.
3 Dérouler le glouton sur cette instance, et donner son résultat.
4 Exhiber une meilleure solution sur la même instance, et comparer les deux valeurs.
5 Conclure que la stratégie n'est pas optimale, et indiquer la méthode qui l'est.

Phrase de conclusion

« Avec les pièces 1, 3 et 4, la stratégie gloutonne rend 6 par $4 + 1 + 1$ , soit trois pièces, alors que $3 + 3$ n'en demande que deux : elle n'est donc pas optimale. La programmation dynamique, qui examine les deux possibilités à chaque étape, donne le minimum. »

Le piège : Affirmer que le glouton est faux sans exhiber d'instance : la question demande un contre-exemple, et lui seul est noté.

Barème : 1 point pour l'instance, 1 point pour le déroulé glouton, 1 point pour la meilleure solution, 1 point pour la conclusion.

Vérifier avant de rendre

Cinq minutes de vérification récupèrent plus de points qu'un exercice de plus commencé à la hâte.

Vérifier une dichotomie par le nombre de comparaisons

Le nombre de comparaisons doit valoir $\lfloor \log_{2} n \rfloor + 1$ . Bien plus, et l'intervalle n'est pas divisé par deux à chaque tour.

Mille éléments demandent 10 comparaisons : en annoncer 20 signale une borne mal mise à jour.
Vérifier une récurrence de coût sur un petit cas

Prendre $n = 8$ , dérouler la récurrence à la main, et comparer au nombre d'opérations comptées sur l'algorithme.

$C(8) = 2C(4) + 8$ donne 24 pour un tri fusion, ce qui coïncide avec $8 \times \log_{2} 8$ .
Tester un glouton sur la plus petite instance possible

Trois valeurs et une somme inférieure à dix suffisent presque toujours à faire apparaître un contre-exemple, s'il en existe un.

Pièces 1, 3 et 4, somme 6 : le contre-exemple tient en une ligne.
Contrôler une table de programmation dynamique par ses bords

La première ligne et la première colonne doivent valoir la valeur triviale, souvent zéro. Une case remplie avant celles dont elle dépend est une erreur de sens de remplissage.

Une case $V(3, 5)$ calculée avant $V(2, 5)$ signale un remplissage de haut en bas.
Vérifier un déroulé de Dijkstra par la croissance des distances

Les distances des sommets fixés forment une suite CROISSANTE dans l'ordre de sélection. Une distance fixée plus petite que la précédente est nécessairement fausse.

Fixer un sommet à 5 après en avoir fixé un à 7 signale que la sélection n'a pas pris le plus petit non traité.

L'exercice type décortiqué

Le rendu de monnaie : glouton contre programmation dynamique

On dispose des pièces de valeurs 1, 3 et 4, en quantité illimitée, et l'on veut rendre une somme $S$ avec le moins de pièces possible.

Tester la stratégie gloutonne sur $S = 6$ , puis écrire la solution par programmation dynamique et donner son coût.

Étape 1

Glouton sur $S = 6$ : la plus grosse pièce possible est 4, il reste 2, puis 1 et 1. Résultat : trois pièces.

Pourquoi

Dérouler avant de juger : c'est le déroulé qui donne le contre-exemple, et le contre-exemple est ce que la question note. Affirmer sans dérouler ne rapporte rien.

Étape 2

Meilleure solution : $3 + 3$ , soit deux pièces. Le glouton n'est donc pas optimal pour ce système.

Pourquoi

Il faut exhiber la solution concurrente, pas seulement affirmer qu'elle existe. Deux nombres suffisent à clore la question.

Étape 3

Table : $m[s]$ est le nombre minimal de pièces pour la somme $s$ , avec $m[0] = 0$ .

Pourquoi

Nommer la table et sa signification en français est la première ligne du barème. Une table dont on ne dit pas ce qu'elle contient ne peut pas être justifiée ensuite.

Étape 4

Relation : $m[s] = 1 + \min(m[s - 1],\ m[s - 3],\ m[s - 4])$ , en n'utilisant que les termes dont l'indice est positif ou nul.

Pourquoi

La relation traduit le principe d'optimalité : la meilleure façon de rendre $s$ passe par la meilleure façon de rendre le reste après une pièce. C'est la phrase que le correcteur cherche.

Étape 5

Remplissage de bas en haut : $m[1] = 1$ , $m[2] = 2$ , $m[3] = 1$ , $m[4] = 1$ , $m[5] = 2$ , $m[6] = 2$ .

Pourquoi

Le sens de remplissage garantit que chaque case n'utilise que des cases déjà connues. C'est aussi le contrôle : $m[6] = 2$ retrouve la solution $3 + 3$ que le glouton avait manquée.

Étape 6

Coût : une case par somme de 0 à $S$ , et trois comparaisons par case, soit $O(S)$ ici, et $O(S \times p)$ pour $p$ types de pièces.

Pourquoi

Le coût dépend de la VALEUR de $S$ , pas du nombre de chiffres qui l'écrivent : c'est le même caractère pseudo-polynomial que le sac à dos, et le dire vaut le point de recul.

Conclusion rédigée

« La stratégie gloutonne rend 6 par $4 + 1 + 1$ , soit trois pièces, alors que $3 + 3$ en suffit deux : elle n'est pas optimale pour ce système. La programmation dynamique, fondée sur $m[s] = 1 + \min(m[s-1], m[s-3], m[s-4])$ et remplie de bas en haut, donne $m[6] = 2$ , pour un coût proportionnel à $S$ multiplié par le nombre de types de pièces. »

L'erreur classique sur cet exercice : Conclure que le glouton est faux « en général » sans exhiber l'instance : la question demande un contre-exemple, et une affirmation générale ne vaut aucun point.

À savoir par cœur

• Dichotomie : tableau TRIÉ, $\lfloor \log_{2} n \rfloor + 1$ comparaisons.
• Tri fusion : $n \log_{2} n$ GARANTI, stable, mémoire linéaire. Tri rapide : $n \log_{2} n$ EN MOYENNE, $n^{2}$ au pire, en place.
• Récurrence : ne jamais oublier le terme de recombinaison. $2C(n/2) + n$ et non $2C(n/2)$ .
• Un glouton se DÉMONTRE. Contre-exemple type : pièces 1, 3, 4 et somme 6.
• Programmation dynamique : principe d'optimalité, table remplie de BAS EN HAUT.
• Sac à dos : coût $nC$ , PSEUDO-polynomial car $C$ est une valeur, pas une taille.
• Dijkstra : le plus proche NON TRAITÉ depuis la source, poids POSITIFS obligatoires.
• Le parcours en largeur est Dijkstra avec toutes les arêtes de poids 1.

Questions fréquentes

Pourquoi la recherche dichotomique exige-t-elle un tableau trié ?

Parce qu'elle élimine une moitié du tableau à chaque comparaison, en se fondant sur l'ordre : si la valeur cherchée est plus petite que celle du milieu, elle ne peut être que dans la moitié gauche. Sans tri, cette déduction est fausse et l'algorithme répond que la valeur est absente alors qu'elle est présente, sans lever la moindre erreur.

Le tri rapide est-il vraiment plus rapide que le tri fusion ?

En moyenne oui, en pratique, parce qu'il trie en place et manipule bien la mémoire. Mais il n'offre aucune garantie : avec un pivot fixe sur un tableau déjà trié, son coût devient quadratique. Le tri fusion garantit son coût quelle que soit l'entrée et il est stable, au prix d'une mémoire supplémentaire proportionnelle à la taille.

Comment savoir si un algorithme glouton est optimal ?

Il faut le démontrer, jamais le supposer. La démarche attendue au bac est inverse : on cherche d'abord une petite instance où le choix local ferme une meilleure solution. Avec les pièces 1, 3 et 4, rendre 6 donne quatre plus un plus un, soit trois pièces, alors que trois plus trois n'en demande que deux. Le glouton est alors réfuté en trois lignes.

Quelle différence entre diviser pour régner et programmation dynamique ?

Diviser pour régner découpe en sous-problèmes disjoints, si bien qu'aucune valeur n'est calculée deux fois et qu'il n'y a rien à mémoriser. La programmation dynamique s'applique quand les sous-problèmes se recoupent : elle range chaque résultat dans une table, remplie de bas en haut, pour ne jamais recalculer la même chose.

Pourquoi Dijkstra refuse-t-il les poids négatifs ?

Parce qu'un sommet est définitivement fixé dès qu'il est sélectionné, en supposant qu'aucun détour ne pourra le raccourcir. Cette supposition n'est vraie que si tous les poids sont positifs : une arête négative rencontrée plus tard pourrait améliorer un sommet déjà traité, que l'algorithme ne réexamine jamais.

Passer à la pratique

Exercices corrigés : Diviser pour régner, programmation dynamique et graphes

Une méthode se prouve sur une copie, pas sur une fiche. La série du même chapitre reprend chacun de ces pièges dans un exercice, avec le corrigé rédigé étape par étape.

15 exercices corrigés
150 points
255 minutes

Faire les exercices

Fiche précédente Récursivité, objet, mise au point et calculabilité

Voir aussi

Toutes les fiches Tous les exercices Tutorat NSI NSI : algorithmique et complexité NSI : les structures de données Terminale

Vous cherchez un tuteur en NSI à Montréal ?

Contactez-moi pour une première séance. On reprend les points de méthode qui font perdre des points en évaluation, puis on les met à l'épreuve sur des exercices du niveau réel de l'examen.

Me contacter WhatsApp

Site par Studio Squalli

Fiche de révision : diviser pour régner, programmation dynamique et graphes

L'essentiel

Les coûts à savoir citer, avec leur condition

Lire une récurrence de coût

Glouton, dynamique, et ce qui les sépare

Le sac à dos, et son coût trompeur

Dijkstra

Les pièges qui coûtent des points

1. Faire une dichotomie sans dire que le tableau est trié

2. Annoncer un tri rapide en nlog⁡2nn \log_{2} nnlog2​n sans réserve

3. Croire que le tri fusion trie en place

4. Appliquer un algorithme glouton sans le démontrer

5. Remplir la table de programmation dynamique dans le mauvais sens

6. Croire le sac à dos polynomial

7. Sélectionner dans Dijkstra le voisin le plus proche du dernier sommet

8. Appliquer Dijkstra avec des poids négatifs

9. Oublier le travail de recombinaison dans la récurrence

Quelle méthode choisir

Quelle stratégie, selon la forme des sous-problèmes

Quel algorithme de graphe, selon la question

La rédaction attendue

Dérouler Dijkstra dans un tableau

Réfuter un algorithme glouton

Vérifier avant de rendre

L'exercice type décortiqué

Le rendu de monnaie : glouton contre programmation dynamique

À savoir par cœur

Questions fréquentes

Pourquoi la recherche dichotomique exige-t-elle un tableau trié ?

Le tri rapide est-il vraiment plus rapide que le tri fusion ?

Comment savoir si un algorithme glouton est optimal ?

Quelle différence entre diviser pour régner et programmation dynamique ?

Pourquoi Dijkstra refuse-t-il les poids négatifs ?

Exercices corrigés : Diviser pour régner, programmation dynamique et graphes

Voir aussi

Vous cherchez un tuteur en NSI à Montréal ?

2. Annoncer un tri rapide en $n \log_{2} n$ sans réserve