Décision, optimisation, instance

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 25 — Algorithmes probabilistes, approximation, séparation et évaluation

Énoncé

Pour chacun des trois problèmes suivants, énoncer la version décision et la version optimisation, dire quelle est la fonction de coût, et donner une instance.

La couverture des sommets d'un graphe.
Le sac à dos.
Le couplage dans un graphe biparti.

Corrigé

Problème	Décision	Optimisation
Couverture	« Existe-t-il une couverture de taille $\leq k$ ? »	« Quelle est la plus petite couverture ? »
[2pt] Sac à dos</td><td style="text-align:left;padding:8px 12px;color:#34332D;vertical-align:top">« Peut-on atteindre une valeur $\geq V$ sans dépasser la capacité $C$ ? »</td><td style="text-align:left;padding:8px 12px;color:#34332D;vertical-align:top">« Quelle est la valeur maximale ? »</td></tr><tr style="border-bottom:1.5px solid #2E2C26"><td style="text-align:left;padding:8px 12px;color:#34332D;vertical-align:top">[2pt] Couplage</td><td style="text-align:left;padding:8px 12px;color:#34332D;vertical-align:top">« Existe-t-il un couplage de cardinal $\geq k$ ? »</td><td style="text-align:left;padding:8px 12px;color:#34332D;vertical-align:top">« Quel est le cardinal maximum ? »</td></tr></table></div> Les fonctions de coût : le nombre de sommets pris (à minimiser) ; la valeur totale des objets (à maximiser) ; le cardinal du couplage (à maximiser). Les instances — une instance est une donnée, pas un problème : le triangle $K_{3}$ avec $k = 2$ ; les objets de poids $(3, 1)$ et de valeurs $(6, 1)$ avec $C = 2$ ; le graphe biparti ${u_{1} v_{1}, u_{1} v_{2}, u_{2} v_{2}}$ avec $k = 2$ . Pourquoi la distinction compte. Les deux versions ont exactement la même difficulté à un facteur logarithmique près : si l'on sait décider, on trouve l'optimum par dichotomie sur $k$ , en $O (lo g)$ appels. La théorie de la complexité — chapitre chap:decidabilite — se formule sur les problèmes de décision, parce qu'une réponse par oui ou non se compare plus commodément ; mais c'est l'optimisation qui intéresse le praticien. Et c'est la version optimisation qui donne un sens à l'approximation : « rendre une couverture au plus deux fois trop grande » a un sens, « répondre oui deux fois trop » n'en a aucun. Une approximation n'existe que pour un problème d'optimisation. Les autres exercices de ce chapitre Le cours du chapitre Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse. Adloun — cours, exercices corrigés et annales du bac, du lycée aux classes préparatoires. Découvrir la plateforme · Tous les exercices d'informatique (MP2I/MPI) · Annales du bac Mentions légales · CGV · Confidentialité

Problème

Décision

Optimisation

Couverture

« Existe-t-il une couverture de taille

\leq k

? »

« Quelle est la plus petite couverture ? »

[2pt]

Sac à dos</td><td style="text-align:left;padding:8px 12px;color:#34332D;vertical-align:top">« Peut-on atteindre une valeur $\geq V$ sans dépasser la capacité $C$ ? »</td><td style="text-align:left;padding:8px 12px;color:#34332D;vertical-align:top">« Quelle est la valeur maximale ? »</td></tr><tr style="border-bottom:1.5px solid #2E2C26"><td style="text-align:left;padding:8px 12px;color:#34332D;vertical-align:top">[2pt] Couplage</td><td style="text-align:left;padding:8px 12px;color:#34332D;vertical-align:top">« Existe-t-il un couplage de cardinal $\geq k$ ? »</td><td style="text-align:left;padding:8px 12px;color:#34332D;vertical-align:top">« Quel est le cardinal maximum ? »</td></tr></table></div>

Les fonctions de coût : le nombre de sommets pris (à minimiser) ; la valeur totale des objets (à maximiser) ; le cardinal du couplage (à maximiser).

Les instances — une instance est une donnée, pas un problème : le triangle $K_{3}$ avec $k = 2$ ; les objets de poids $(3, 1)$ et de valeurs $(6, 1)$ avec $C = 2$ ; le graphe biparti ${u_{1} v_{1}, u_{1} v_{2}, u_{2} v_{2}}$ avec $k = 2$ .

Pourquoi la distinction compte. Les deux versions ont exactement la même difficulté à un facteur logarithmique près : si l'on sait décider, on trouve l'optimum par dichotomie sur $k$ , en $O (lo g)$ appels. La théorie de la complexité — chapitre chap:decidabilite — se formule sur les problèmes de décision, parce qu'une réponse par oui ou non se compare plus commodément ; mais c'est l'optimisation qui intéresse le praticien.

Et c'est la version optimisation qui donne un sens à l'approximation : « rendre une couverture au plus deux fois trop grande » a un sens, « répondre oui deux fois trop » n'en a aucun. Une approximation n'existe que pour un problème d'optimisation.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.