NSI programmation dynamique

Qu'est-ce que la programmation dynamique ?

C'est une méthode algorithmique pour résoudre des problèmes en décomposant en sous-problèmes plus simples.

Vrai ou faux : La programmation dynamique évite les calculs redondants.

Vrai. Elle stocke les résultats intermédiaires pour réduire le temps de calcul.

Quelles sont les deux techniques principales de la programmation dynamique ?

1. Mémoïsation 2. Programmation tabulaire

Complétez : La programmation dynamique est souvent utilisée pour les problèmes de __________.

optimisation.

Qu'est-ce que la mémoïsation ?

C'est une technique où les résultats des sous-problèmes sont stockés pour éviter de les recalculer.

Vrai ou faux : La programmation dynamique nécessite toujours une complexité exponentielle.

Faux. Elle vise à réduire la complexité, souvent à polynomial.

Comparaison : Mémoïsation vs. programmation tabulaire.

Mémoïsation : top-down, utilise la récursion. Programmation tabulaire : bottom-up, construit une table.

Exemple de problème classique résolu par programmation dynamique ?

Le problème du sac à dos.

Qu'est-ce qu'un sous-problème optimal ?

C'est un sous-problème dont la solution est optimale et contribue à la solution globale.

Vrai ou faux : La programmation dynamique ne fonctionne que pour les problèmes discrets.

Faux. Elle peut être utilisée pour des problèmes continus aussi.

Complétez : Les résultats de la programmation dynamique sont souvent enregistrés dans __________.

une table ou un tableau.

Qu'est-ce qu'un tableau dynamique ?

C'est une structure de données utilisée pour stocker les résultats des sous-problèmes.

Comment la programmation dynamique aide-t-elle à réduire la complexité ?

Elle évite les recalculs en stockant les résultats intermédiaires.

Qu'est-ce qu'un problème de décision ?

C'est un problème où la réponse est un oui ou un non, souvent résolu par DP.

Vrai ou faux : La programmation dynamique ne nécessite pas de structure de données spécifique.

Faux. Elle utilise des tableaux ou des matrices pour stocker des résultats.

Quel rôle joue l'optimalité sous-structure dans la programmation dynamique ?

Elle permet de construire une solution optimale à partir de solutions optimales de sous-problèmes.

Qu'est-ce que le problème du sac à dos ?

Un problème d'optimisation combinatoire où l'on doit maximiser la valeur d'objets placés dans un sac avec une capacité limitée.

Quelles sont les caractéristiques de la programmation dynamique ?

1. Découpage en sous-problèmes. 2. Optimalité des sous-solutions. 3. Mémorisation pour éviter les recalculs.

Vrai ou faux : la programmation dynamique est toujours plus efficace que la récursivité.

Faux : La programmation dynamique est plus efficace dans les cas où les sous-problèmes se chevauchent.

Comparaison : programmation dynamique vs. approche récursive.

Programmation dynamique : mémorisation, plus rapide. Approche récursive : simple, mais plus lente.

Complétez : Dans le problème du sac à dos, on maximise la ___.

valeur totale des objets.

Quel est l'algorithme de base pour le sac à dos ?

On utilise un tableau pour stocker les valeurs maximales pour chaque capacité jusqu'à la capacité du sac.

Qu'est-ce que la plus longue sous-séquence ?

C'est la plus longue séquence d'éléments qui apparaît dans le même ordre, mais pas nécessairement consécutifs.

Exemple de calcul : longue sous-séquence dans 'ABCBDAB'.

La plus longue sous-séquence est 'BCAB' (longueur 4).

Quel est l'usage des tableaux dans la programmation dynamique ?

Ils permettent de stocker les résultats des sous-problèmes pour éviter les recalculs.

Vrai ou faux : la programmation dynamique nécessite toujours un tableau à deux dimensions.

Faux : Un tableau à une dimension peut suffire dans certains cas.

Quelles sont les étapes pour résoudre un problème avec programmation dynamique ?

1. Définir les sous-problèmes. 2. Établir la relation de récurrence. 3. Mémoriser et construire la solution.

Remplissez le tableau pour le sac à dos : capacité 5, objets (valeurs, poids).

Exemple : (60, 10), (100, 20), (120, 30) → Remplissage selon les valeurs maximales.

Qu'est-ce qui caractérise un problème résoluble par programmation dynamique ?

Les sous-problèmes doivent se chevaucher et l'optimalité des solutions doit s'appliquer.

Illustration : relation de récurrence pour le sac à dos.

$\displaystyle V(i, j) = ext{max}(V(i-1, j), V(i-1, j - poids[i]) + valeur[i])$

Problème du voyageur de commerce ?

Il s'agit de trouver le chemin le plus court pour visiter plusieurs villes et revenir à la ville de départ. Utilise la programmation dynamique pour réduire le temps de calcul.

Vrai ou faux : La programmation dynamique ne peut pas résoudre le problème du sac à dos.

Faux. La programmation dynamique est très efficace pour résoudre le problème du sac à dos en optimisant le poids et la valeur.

Écrire la formule de la sous-séquence commune la plus longue.

Soit $\displaystyle L(i,j)$ la longueur de la plus longue sous-séquence commune de deux chaînes. On a : - Si $\displaystyle A[i] = B[j]$ alors $\displaystyle L(i,j) = L(i-1,j-1) + 1$. - Sinon, $\displaystyle L(i,j) = max(L(i-1,j), L(i,j-1))$.

Compléter : La programmation dynamique est utilisée pour _______.

optimiser des problèmes d'allocations de ressources et de cheminement.

Comparer : Programmation dynamique vs. programmation récursive.

La programmation dynamique évite la redondance en mémorisant les résultats intermédiaires, alors que la programmation récursive peut recalculer les mêmes valeurs plusieurs fois.

Exemple pratique : Planification d'itinéraire.

Pour planifier un itinéraire optimisé entre plusieurs destinations, la programmation dynamique permet de simuler toutes les combinaisons possibles et de sélectionner le meilleur chemin.

Quel est l'impact de la programmation dynamique sur le temps de résolution ?

Elle réduit le temps de résolution en évitant les calculs redondants, ce qui rend des problèmes complexes gérables.

Définir le problème de la coupe de tige.

Le problème consiste à déterminer la meilleure façon de couper une tige pour maximiser le profit généré par la vente des morceaux, en utilisant la programmation dynamique.

Quelles applications pratiques utilise-t-on pour la programmation dynamique ?

Allocations de ressources, traitements de chaînes, optimisation de chemins, et planification d'itinéraires.

Vrai ou faux : La programmation dynamique est uniquement pour les problèmes de graphes.

Faux. Elle s'applique également à des problèmes de séquences, d'optimisation et de combinatoire.

Quel est le résultat de la multiplication de matrices ?

La multiplication de matrices peut être optimisée par la programmation dynamique pour minimiser le nombre d'opérations nécessaires.

Décrire une application de la programmation dynamique dans le traitement des chaînes.

Elle est utilisée pour des problèmes comme la recherche de la plus longue sous-séquence ou la correction automatique dans les éditeurs de texte.

Remplir : Pour le problème de la somme de sous-ensembles, la programmation dynamique permet de _______.

déterminer si une somme particulière peut être atteinte avec un sous-ensemble donné.

Expliquer l'importance de la mémoire dans la programmation dynamique.

La mémoire permet de stocker les résultats intermédiaires, évitant ainsi les calculs redondants et améliorant l'efficacité de l'algorithme.