Question transversaleMathsNSIAlgorithmes et complexité

Pourquoi le problème du sac à dos résiste-t-il à la puissance des ordinateurs ?

Q: Combien de jours pour 2⁵⁰ essais à 10⁹ par seconde ?

$1,13×10⁶$ s, divisé par $86 400$ : environ 13 jours.

Choisir des objets de valeur maximale sans dépasser un poids, c'est explorer jusqu'à 2ⁿ sous-ensembles : 2⁵⁰ ≈ 1,1 × 10¹⁵, treize jours à un milliard d'essais par seconde. La programmation dynamique, en n × W opérations pour une capacité entière W, contourne l'explosion quand W est petit.

Grand oral session 2027 : exposé de 10 minutes debout, puis 10 minutes d'échange, sans calculatrice. Plan prévu pour 9,5 min.

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

En préparant un sac de randonnée, j'ai dû choisir quoi emporter sans dépasser un poids raisonnable, en gardant les objets les plus utiles. J'ai découvert en NSI que ce problème du quotidien est un problème célèbre, réputé difficile. J'ai voulu comprendre d'où vient sa difficulté et comment on le résout malgré tout.

L'enjeu et les notions du programme

Dénombrer les sous-ensembles d'un ensemble, puis construire une relation de récurrence qui évite de les énumérer.

Mathématiques

Nombre de parties d'un ensemble à n éléments (terminale)
Suites et tableaux définis par récurrence (première)
Croissance exponentielle (terminale)

Numérique et sciences informatiques

Algorithmes gloutons (première)
Programmation dynamique (terminale)

Le plan de l'exposé en 9,5 min

1. Introduction
1 min
On dispose de $n$ n objets, chacun avec un poids et une valeur, et d'un sac de capacité $W$ W. Problématique : comment choisir les objets de valeur totale maximale sans dépasser $W$ W, et pourquoi est-ce si difficile ?
2. Mathématiques : explosion combinatoire
4 min
Un choix d'objets est un sous-ensemble de l'ensemble des $n$ n objets. Pour chaque objet, deux possibilités (pris ou non) : il y a $2^{n}$ 2ⁿ sous-ensembles. Pour $n = 50$ n=50, $2^{50} \approx 1, 1 \times 1 0^{15}$ 2⁵⁰≈1,1×10¹⁵ ; à $1 0^{9}$ 10⁹ essais par seconde, environ 13 jours. Pour $n = 60$ n=60, 1 024 fois plus : 36 ans.
Le glouton (prendre d'abord les objets de meilleur rapport valeur/poids) est rapide mais pas toujours optimal : avec une capacité de 10, un objet A (poids 6, valeur 9) et deux objets B et C (poids 5, valeur 7 chacun), le glouton prend A (rapport 1,5) et ne peut plus rien ajouter, valeur 9 ; alors que B + C donne 14.
Programmation dynamique : soit $V (i, w)$ V(i,w) la meilleure valeur avec les $i$ i premiers objets et une capacité $w$ w. Ou bien on ne prend pas l'objet $i$ i : $V (i - 1, w)$ V(i-1,w) ; ou bien on le prend : $v_{i} + V (i - 1, w - p_{i})$ vᵢ+V(i-1,w-pᵢ). On garde le maximum.
3. NSI : un tableau au lieu d'une énumération
3 min
On remplit un tableau de $(n + 1) \times (W + 1)$ (n+1)×(W+1) cases, chacune en temps constant : environ $n \times W$ n× W opérations. Pour 50 objets et une capacité de 1 000 (en grammes entiers), 50 000 opérations au lieu de $1 0^{15}$ 10¹⁵.
Mais ce gain dépend de $W$ W : si les poids sont des nombres à 30 chiffres, le tableau devient gigantesque. On ne connaît aucun algorithme rapide dans tous les cas : le sac à dos fait partie des problèmes « NP-complets ». Il intervient dans le chargement de conteneurs, la gestion d'un budget ou la découpe de matériaux.
4. Conclusion
1,5 min
Le sac à dos résiste parce que le nombre de choix possibles est $2^{n}$ 2ⁿ. La programmation dynamique évite l'énumération quand les poids sont de petits entiers, mais aucune méthode n'est rapide en toute généralité. J'ouvre sur la question P = NP, l'un des problèmes du millénaire.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

2^{50} \approx 1, 1 \times 1 0^{15} sous-ensembles \frac{1 , 1 \times 1 0 ^{15}}{1 0 ^{9}} s \approx 13 jours 2⁵⁰\approx1,1\times10¹⁵ sous-ensembles 1,1\times10¹⁵/10⁹ s \approx13 jours V (i, w) = max (V (i - 1, w), v_{i} + V (i - 1, w - p_{i})) co \overset{u}{ˆ} t \approx n \times W V(i,w)=max(V(i-1,w), vᵢ+V(i-1,w-pᵢ)) coût \approx n\times W

Conclusion : la réponse à la question

Le nombre de sous-ensembles croît comme $2^{n}$ 2ⁿ : l'énumération est vite impossible. Une relation de récurrence bien choisie remplace l'énumération par un tableau, sans pour autant rendre le problème facile dans tous les cas.

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Pourquoi 2^n sous-ensembles ?

Pour chaque objet, deux choix indépendants : le principe multiplicatif donne 2 × 2 × … × 2.

Que vaut V(0, w) ?

0 : sans objet, la valeur est nulle.

Combien de jours pour 2⁵⁰ essais à 10⁹ par seconde ?

$1, 13 \times 1 0^{6}$ 1,13×10⁶ s, divisé par $86400$ 86 400 : environ 13 jours.

Le glouton est-il optimal si l'on peut couper les objets ?

Oui : pour le sac à dos fractionnaire, le glouton par rapport valeur/poids est optimal.

Que veut dire NP-complet, en une phrase ?

Un problème dont on vérifie vite une solution, mais pour lequel on ne connaît pas d'algorithme rapide, et auquel tous les problèmes de ce type se ramènent.

Les pièges qui coûtent des points

Croire que le glouton par rapport valeur/poids est toujours optimal.
Dire que la programmation dynamique résout tout rapidement : son coût dépend de W.
Confondre nombre de sous-ensembles (2ⁿ) et nombre d'ordres (n!).

Revoir les notions

Autres questions : algorithmes et complexité

Toutes les questions maths-nsi →

Préparer l'oral, pas seulement le contenu

Gestion des 20 minutes de préparation, usage du tableau, posture debout, réponses au jury : la méthode complète, conforme aux règles de la session 2027.

Méthode : traiter une question de Grand oral →

Continuer la préparation

Le Grand oral 2027 →Méthode : traiter une question →Toutes les questions, par combinaison →Questions de maths seules →Questions maths-physique-chimie →Questions maths-SES →Questions maths-SVT →Questions maths-SI →Questions maths-HGGSP →Questions maths-anglais →