Du seuil à l'optimum

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 31 — Décidabilité et classes de complexité

Énoncé

Un problème d'optimisation demande le coût minimal d'une solution, un entier compris entre $0$ et $M$ . On dispose d'un algorithme qui décide « existe-t-il une solution de coût $\leq k$ ? ».

Comment obtenir l'optimum ?
Combien d'appels sont nécessaires ?
Que conclure sur la difficulté des deux versions ?

Corrigé

1. Par dichotomie sur le seuil. La fonction $k \mapsto$ « existe-t-il une solution de coût $\leq k$ ? » est croissante au sens booléen : fausse jusqu'à l'optimum, vraie ensuite. C'est exactement la situation de la recherche dichotomique du chapitre chap:diviser.


inf <-- 0 ; sup <-- M
tant que inf < sup
    m <-- (inf + sup) / 2
    si decide(m) alors sup <-- m sinon inf <-- m + 1
rendre inf

Invariant : l'optimum est toujours dans $[inf, sup]$ . Variant : $sup - inf$ , qui décroît strictement — de moitié à chaque tour.

2. $⌈ lo g_{2} (M + 1)⌉$ appels. Mesuré, en cherchant un optimum placé au tiers de l'intervalle :

Intervalle	Appels	$⌈ lo g_{2} (M + 1)⌉$
$[0, 100]$	$7$	$7$
$[0, 1 0^{3}]$	$10$	$10$
$[0, 1 0^{6}]$	$20$	$20$
$[0, 1 0^{9}]$	$30$	$30$

3. Le nombre d'appels est logarithmique en $M$ , donc linéaire en la taille de $M$ . Si la version décision est polynomiale, la version optimisation l'est aussi. Les deux versions ont donc la même difficulté, et c'est ce qui autorise à ne parler que de problèmes de décision — comme le fait la définition de $P$ .

Une précaution. L'argument suppose que $M$ s'écrit en un nombre polynomial de bits, ce qui est le cas dès que les coûts sont des entiers donnés en entrée. Il tombe si l'optimum peut prendre des valeurs sans borne écrite dans l'instance.

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.