Comment reconnaître un exercice de programmation dynamique ?

Un exercice de programmation dynamique présente souvent des sous-problèmes qui se répètent, une relation de récurrence, et une optimisation (maximum, minimum, nombre de combinaisons). Par exemple, calculer le nombre de façons de monter un escalier ou le rendu de monnaie. Les mots-clés comme "mémorisation", "sous-problèmes", "réutilisation" sont des indices.

Comment reconnaître un exercice de graphe ?

Un exercice de graphe parle de relations entre entités : villes et routes, amis dans un réseau, dépendances entre tâches. On cherche souvent un chemin, une connexion, un cycle, ou on applique des parcours (BFS, DFS) ou des algorithmes comme Dijkstra. Les mots-clés sont "sommets", "arêtes", "nœuds", "liens".

Peut-on utiliser la programmation dynamique sur un graphe ?

Oui, dans certains cas. Par exemple, pour trouver le plus court chemin dans un graphe orienté acyclique (DAG), on peut utiliser une approche de programmation dynamique en traitant les sommets dans l'ordre topologique. Mais ce n'est pas systématique : pour les graphes avec cycles, on utilise plutôt Dijkstra ou Bellman-Ford.

Quels sont les algorithmes de programmation dynamique au programme de NSI ?

Au programme de terminale NSI, on étudie principalement le rendu de monnaie, le problème du sac à dos (version simple), et parfois la plus longue sous-séquence commune. Ces problèmes illustrent la méthode de mémorisation (top-down) et la méthode itérative (bottom-up).

Comment réviser efficacement la programmation dynamique et les graphes pour le bac NSI ?

Pour bien réviser, il faut comprendre les concepts et s'entraîner sur des exercices types. Utilise des fiches de révision, des annales, et implémente les algorithmes en Python. Le site nsi-lycee.fr propose des cours et exercices. N'hésite pas à consulter des plateformes comme AlloBac pour un soutien supplémentaire.

Programmation dynamique vs graphes : ne plus confondre en NSI

Q: Quelle est la différence entre programmation dynamique et graphe en NSI ?

La programmation dynamique est une technique algorithmique qui résout un problème en le décomposant en sous-problèmes et en mémorisant leurs solutions pour éviter de les recalculer. Un graphe est une structure de données qui modélise des relations entre des objets (sommets et arêtes). On les utilise pour des types de problèmes différents : la PD pour des problèmes d'optimisation avec sous-problèmes imbriqués, les graphes pour des problèmes de parcours, de chemins, de connexité.

En spécialité NSI, tu croises des notions qui semblent proches mais qui n'ont rien à voir. La programmation dynamique et les graphes sont deux exemples parfaits. Souvent, on les confond parce qu'on les aborde en terminale et qu'ils servent tous les deux à résoudre des problèmes complexes. Pourtant, leurs principes sont très différents. Dans cet article, on va clarifier tout ça ensemble, avec des exemples Python concrets et des astuces pour ne plus jamais les mélanger.

Qu'est-ce que la programmation dynamique ?

La programmation dynamique (souvent abrégée PD) est une technique algorithmique qui consiste à décomposer un problème en sous-problèmes plus petits, résoudre chaque sous-problème une seule fois, et mémoriser les résultats pour les réutiliser. C'est une façon intelligente d'éviter de refaire les mêmes calculs. On l'utilise quand un problème a une structure de sous-problèmes imbriqués et que les solutions des sous-problèmes sont réutilisées plusieurs fois.

Prenons un exemple classique : le calcul du n-ième terme de la suite de Fibonacci. La définition récursive naïve est simple :

def fibo(n):
    if n <= 1:
        return n
    return fibo(n-1) + fibo(n-2)

Mais cette version fait énormément de calculs inutiles. Pour fibo(40), elle appelle fibo(39) et fibo(38), qui chacun rappellent plein de fois les mêmes valeurs. La complexité est exponentielle. Avec la programmation dynamique, on va mémoriser les résultats intermédiaires.

Version avec mémorisation (top-down) :

def fibo_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibo_memo(n-1, memo) + fibo_memo(n-2, memo)
    return memo[n]

Ou version itérative (bottom-up) :

def fibo_iter(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a + b
    return b

Ces deux versions sont de la programmation dynamique car elles réutilisent des résultats déjà calculés. La complexité devient linéaire. C'est ça, l'idée clé : mémoriser pour ne pas recalculer.

Qu'est-ce qu'un graphe ?

Un graphe est une structure de données qui modélise des relations entre des objets. Il est composé de sommets (ou nœuds) et d'arêtes (ou liens) qui relient ces sommets. Les graphes servent à représenter des réseaux : routes, amitiés sur les réseaux sociaux, dépendances entre tâches, etc.

En NSI, tu apprends à les représenter en Python, par exemple avec une liste d'adjacence :

graphe = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A'],
    'D': ['B']
}

Ou avec une matrice d'adjacence :

# sommets : A, B, C, D
matrice = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 0],
    [0, 1, 0, 0]
]

Sur un graphe, on applique des algorithmes comme le parcours en largeur (BFS), en profondeur (DFS), ou le calcul du plus court chemin avec Dijkstra. Mais attention : un graphe n'est pas un algorithme, c'est une structure de données. La programmation dynamique, elle, est une méthode algorithmique. C'est une différence fondamentale.

Les points de convergence : quand la programmation dynamique utilise des graphes

Il y a des cas où les deux notions se rencontrent. Par exemple, le plus court chemin dans un graphe peut être résolu par programmation dynamique si le graphe est un DAG (graphe orienté acyclique). On peut alors appliquer un algorithme de relaxation dans l'ordre topologique. C'est un mélange des deux.

Mais dans la plupart des exercices de bac, on te demande soit de reconnaître un problème de graphe (et d'utiliser BFS/DFS ou Dijkstra), soit un problème de programmation dynamique (et d'utiliser la mémorisation ou le bottom-up). Il faut donc savoir les distinguer.

Exemple : le problème du rendu de monnaie (combien de pièces pour une somme donnée) est typiquement résolu par programmation dynamique, car il y a des sous-problèmes qui se répètent. On ne parle pas de graphe ici.

À l'inverse, le problème de la détection de cycles dans un réseau social est un problème de graphe, et on utilise DFS.

Comment les distinguer en pratique ?

Voici une méthode simple :

Si le problème parle de relations entre objets (routes, amis, dépendances), alors c'est un problème de graphe. On cherche souvent un chemin, une connexion, un cycle.
Si le problème demande une optimisation (maximum, minimum, nombre de façons) et qu'il peut se découper en sous-problèmes réutilisés, alors c'est de la programmation dynamique.
Demande-toi : est-ce que je peux résoudre ce problème en décomposant en plus petits morceaux qui se recoupent ? Si oui, c'est de la PD. Est-ce que je dois explorer des voisins ? Alors c'est un graphe.

Prenons deux exercices types :

Exercice 1 : On te donne un labyrinthe, tu dois trouver s'il existe un chemin de l'entrée à la sortie. Ici, les cases sont des sommets, les passages sont des arêtes. C'est un graphe (parcours BFS ou DFS).

Exercice 2 : On te donne un escalier de n marches, tu peux monter 1 ou 2 marches à la fois. Combien de façons différentes d'arriver en haut ? Ici, chaque marche dépend des précédentes : c'est une suite, on peut utiliser la programmation dynamique (f(n) = f(n-1) + f(n-2)).

Ces deux exemples sont très différents, même si les deux utilisent des tableaux ou des structures.

Exemple concret : le sac à dos (programmation dynamique) vs le plus court chemin (graphe)

Le problème du sac à dos : tu as des objets avec un poids et une valeur, et un sac avec une capacité maximale. Tu veux maximiser la valeur totale sans dépasser la capacité. C'est un problème classique de programmation dynamique. On construit un tableau à deux dimensions où chaque case représente la valeur maximale qu'on peut obtenir avec les i premiers objets et une capacité j.

def sac_a_dos(poids, valeurs, capacite):
    n = len(poids)
    dp = [[0]*(capacite+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for w in range(1, capacite+1):
            if poids[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-poids[i-1]] + valeurs[i-1])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][capacite]

Ce code utilise un tableau dp pour mémoriser les solutions des sous-problèmes. C'est de la programmation dynamique.

Le problème du plus court chemin : dans un graphe pondéré, tu veux la distance minimale entre deux sommets. On utilise l'algorithme de Dijkstra, qui est un algorithme de graphe, pas de la programmation dynamique (bien qu'il ait des similitudes).

import heapq

def dijkstra(graphe, depart):
    distances = {sommet: float('inf') for sommet in graphe}
    distances[depart] = 0
    file = [(0, depart)]
    while file:
        dist_actuelle, sommet = heapq.heappop(file)
        if dist_actuelle > distances[sommet]:
            continue
        for voisin, poids in graphe[sommet].items():
            nouvelle_dist = dist_actuelle + poids
            if nouvelle_dist < distances[voisin]:
                distances[voisin] = nouvelle_dist
                heapq.heappush(file, (nouvelle_dist, voisin))
    return distances

Ici, on explore les sommets et on met à jour les distances. C'est un algorithme de graphe.

Conseils pour le bac NSI et tes révisions

Au bac, on peut te demander de reconnaître ces notions. Voici comment t'y préparer :

Révise les définitions : programmation dynamique = technique de résolution avec mémorisation ; graphe = structure de données relationnelle.
Entraîne-toi sur des exercices types : rendu de monnaie, plus long sous-séquence, etc. pour la PD ; parcours de graphe, détection de cycle, etc. pour les graphes. Tu peux trouver des exercices sur https://www.nsi-lycee.fr/exercices.
Utilise des fiches de révision qui comparent les deux notions. Par exemple, sur https://www.nsi-lycee.fr/fiches tu as des synthèses.
Implémente les algorithmes en Python pour bien comprendre. Le cours sur https://www.nsi-lycee.fr/cours peut t'aider.
Pense aux annales : les sujets de bac tombent souvent sur ces thèmes. Analyse les énoncés et repère les mots-clés comme « mémorisation », « sous-problèmes » pour la PD, et « sommets », « arêtes » pour les graphes.

Un dernier conseil : ne te décourage pas. Ces notions sont difficiles au début, mais avec de la pratique, tu vas les maîtriser. Et si tu as besoin d'aide supplémentaire, des sites comme https://www.allobac.fr ou https://www.allolycee.com proposent des ressources et du soutien.

Conclusion

Pour résumer : la programmation dynamique est une technique pour optimiser des calculs en mémorisant des résultats, tandis qu'un graphe est une structure de données pour modéliser des relations. Ils peuvent se combiner, mais ils ne sont pas interchangeables. En gardant ces définitions en tête et en t'entraînant régulièrement, tu ne les confondras plus. Alors, lance-toi, explore les exercices, et fais-toi confiance. Tu es capable de maîtriser ces concepts !