Pourquoi l'approche gloutonne ne fonctionne-t-elle pas toujours pour le rendu de monnaie ?

Elle prend toujours la plus grande pièce possible, ce qui n'est pas toujours optimal

La différence entre programmation dynamique et diviser pour régner est :

En diviser pour régner, les sous-problèmes sont indépendants ; en prog dynamique, ils se chevauchent

Dans l'approche bottom-up pour Fibonacci, on :

Remplit un tableau de fib(0) à fib(n) itérativement

L'algorithme de Boyer-Moore améliore la recherche textuelle en :

Sautant des positions grâce aux caractères non-correspondants

Pourquoi l'approche gloutonne ne fonctionne-t-elle pas toujours pour le rendu de monnaie ?

Elle prend toujours la plus grande pièce possible, ce qui n'est pas toujours optimal. L'approche gloutonne prend toujours la plus grande pièce possible, mais ce choix local peut empêcher d'atteindre l'optimum global. Ex : pièces 1,3,4, somme 6 → glouton donne 3 pièces (4+1+1) au lieu de 2 (3+3).

Quelle est la complexité de la recherche textuelle naïve ?

O(n × m). L'algorithme naïf teste chaque position de départ (n-m+1 positions) et compare jusqu'à m caractères pour chaque position, soit O(n × m) dans le pire cas.

La différence entre programmation dynamique et diviser pour régner est :

En diviser pour régner, les sous-problèmes sont indépendants ; en prog dynamique, ils se chevauchent. En diviser pour régner (tri fusion, recherche dichotomique), les sous-problèmes ne se recoupent pas. En programmation dynamique, les mêmes sous-problèmes apparaissent plusieurs fois, d'où l'intérêt de la mémoïsation.

Dans l'approche bottom-up pour Fibonacci, on :

Remplit un tableau de fib(0) à fib(n) itérativement. L'approche bottom-up remplit un tableau itérativement en partant des cas de base (fib(0)=0, fib(1)=1) et en calculant chaque valeur suivante à partir des deux précédentes.

Pour le rendu de monnaie en programmation dynamique, nb[0] vaut :

0. nb[0] = 0 car il faut 0 pièce pour obtenir la somme 0. C'est le cas de base de la programmation dynamique pour ce problème.

L'algorithme de Boyer-Moore améliore la recherche textuelle en :

Sautant des positions grâce aux caractères non-correspondants. Boyer-Moore compare le motif de droite à gauche et utilise les informations sur les caractères non-correspondants pour sauter plusieurs positions, ce qui le rend très efficace en pratique.

NSI (Spé) — Algorithmique

Programmation dynamique et recherche textuelle

Q: La programmation dynamique s'applique quand les sous-problèmes :

Se chevauchent (les mêmes apparaissent plusieurs fois). La programmation dynamique est utile quand les sous-problèmes se chevauchent : les mêmes calculs reviennent plusieurs fois. La mémoïsation évite de les refaire.

Q: Quelle est la complexité du calcul récursif naïf de Fibonacci ?

O(2ⁿ). L'appel récursif naïf de fib(n) engendre un arbre d'appels de taille exponentielle O(2ⁿ), car fib(n) appelle fib(n-1) et fib(n-2), et ces appels se dédoublent.

Q: Avec la mémoïsation, quelle est la complexité du calcul de fib(n) ?

O(n). Avec la mémoïsation, chaque valeur fib(k) n'est calculée qu'une seule fois et stockée. Il y a n valeurs à calculer, d'où une complexité O(n).

Principe de la programmation dynamique, mémoïsation, exemples classiques, algorithme de recherche textuelle naïve

Résumé synthétiqueFiche en 4 sectionsQuiz de 10 questionsGratuit, sans pub

Résumé

La programmation dynamique résout des problèmes en les décomposant en sous-problèmes qui se chevauchent, et en stockant les résultats intermédiaires pour éviter de les recalculer. L'exemple le plus classique est le calcul de Fibonacci : l'approche récursive naïve recalcule fib(3) de nombreuses fois (complexité exponentielle O(2ⁿ)), tandis que la mémoïsation stocke les résultats déjà calculés dans un dictionnaire (complexité O(n)). Le rendu de monnaie est un autre problème classique : trouver le nombre minimum de pièces pour atteindre une somme donnée. La recherche textuelle naïve consiste à chercher un motif dans un texte en testant chaque position de départ possible. Pour un texte de longueur n et un motif de longueur m, la complexité est O(n × m) dans le pire cas. L'algorithme de Boyer-Moore améliore cela en pratique en sautant des positions.

Thème complet

Voir tous les chapitres « Algorithmique et programmation » de la Seconde à la Terminale

Ce thème dans une autre classe

Seconde — Mathématiques

Algorithmique et programmation

Première — Mathématiques

Algorithmique et programmation Python

Première — Maths (Spé)

Algorithmique et programmation Python

Articles utiles

Spécialités

Bac NSI 2026 : comment réussir l'épreuve écrite et pratique

Questions fréquentes

Les points clés à retenir sur Programmation dynamique et recherche textuelle, extraits du quiz de révision.

La programmation dynamique s'applique quand les sous-problèmes :

Réponse : Se chevauchent (les mêmes apparaissent plusieurs fois)

La programmation dynamique est utile quand les sous-problèmes se chevauchent : les mêmes calculs reviennent plusieurs fois. La mémoïsation évite de les refaire.

Quelle est la complexité du calcul récursif naïf de Fibonacci ?

Réponse : O(2ⁿ)

L'appel récursif naïf de fib(n) engendre un arbre d'appels de taille exponentielle O(2ⁿ), car fib(n) appelle fib(n-1) et fib(n-2), et ces appels se dédoublent.

La mémoïsation consiste à :

Réponse : Stocker les résultats déjà calculés pour ne pas les recalculer

La mémoïsation stocke les résultats des sous-problèmes dans une structure (dictionnaire, tableau) pour les réutiliser directement si le même sous-problème se présente.

Avec la mémoïsation, quelle est la complexité du calcul de fib(n) ?

Réponse : O(n)

Avec la mémoïsation, chaque valeur fib(k) n'est calculée qu'une seule fois et stockée. Il y a n valeurs à calculer, d'où une complexité O(n).

Résumé

Questions fréquentes

Les points clés à retenir sur Programmation dynamique et recherche textuelle, extraits du quiz de révision.

La programmation dynamique s'applique quand les sous-problèmes :

Réponse : Se chevauchent (les mêmes apparaissent plusieurs fois)

La programmation dynamique est utile quand les sous-problèmes se chevauchent : les mêmes calculs reviennent plusieurs fois. La mémoïsation évite de les refaire.

Quelle est la complexité du calcul récursif naïf de Fibonacci ?

Réponse : O(2ⁿ)

L'appel récursif naïf de fib(n) engendre un arbre d'appels de taille exponentielle O(2ⁿ), car fib(n) appelle fib(n-1) et fib(n-2), et ces appels se dédoublent.

La mémoïsation consiste à :

Réponse : Stocker les résultats déjà calculés pour ne pas les recalculer

La mémoïsation stocke les résultats des sous-problèmes dans une structure (dictionnaire, tableau) pour les réutiliser directement si le même sous-problème se présente.

Avec la mémoïsation, quelle est la complexité du calcul de fib(n) ?

Réponse : O(n)

Avec la mémoïsation, chaque valeur fib(k) n'est calculée qu'une seule fois et stockée. Il y a n valeurs à calculer, d'où une complexité O(n).

Programmation dynamique et recherche textuelle

Résumé

Principe de la programmation dynamique

Fibonacci et mémoïsation

Rendu de monnaie (programmation dynamique)

Recherche textuelle

Quiz - Programmation dynamique et recherche textuelle

Ce thème dans une autre classe

Articles utiles

Questions fréquentes

Programmation dynamique et recherche textuelle

Résumé

Principe de la programmation dynamique

Fibonacci et mémoïsation

Rendu de monnaie (programmation dynamique)

Recherche textuelle

Quiz - Programmation dynamique et recherche textuelle

Ce thème dans une autre classe

Articles utiles

Questions fréquentes