Probleme – Un même problème, trois méthodes, trois compromis

Exercice · niveau 3 (difficile) · informatique (MP2I/MPI), chapitre 15 — Diviser pour régner

Énoncé

La somme d'un sous-ensemble est citée par le programme dans ce chapitre et dans le suivant. On la traite ici de trois façons.

L'exhaustif, la rencontre au milieu, et le calcul par table du chapitre chap:dynamique.
Donner la complexité de chacune en temps et en mémoire.
Mesurer, puis dire laquelle choisir selon $n$ et selon la cible $c$ .

Corrigé

1. Les trois programmes.


(* (a) EXHAUSTIF : on énumère les 2^n masques. Précondition : 0 <= n < 62. *)
let brute t c =
  let n = Array.length t and vu = ref false in
  for masque = 0 to (1 lsl n) - 1 do
    let s = ref 0 in
    for i = 0 to n-1 do
      if (masque lsr i) land 1 = 1 then s := !s + t.(i) done;
    if !s = c then vu := true
  done; !vu

(* (b) RENCONTRE AU MILIEU : deux moitiés, puis dichotomie. *)
(* (voir le cours ; 2 * 2^(n/2) sommes construites, puis un tri et 2^(n/2) recherches *)

(* (c) PAR TABLE : acc.(s) est vrai ssi la somme s est atteignable.
   Précondition : les t.(i) sont positifs, et c >= 0.
   Complexité : Theta(n c) en temps, Theta(c) en mémoire. *)
let par_table t c =
  let n = Array.length t in
  let acc = Array.make (c + 1) false in
  acc.(0) <- true;
  for i = 0 to n - 1 do
    (* on parcourt s en DÉCROISSANT pour n'employer chaque objet qu'une fois *)
    for s = c downto t.(i) do
      if acc.(s - t.(i)) then acc.(s) <- true done
  done;
  acc.(c)

Le sens de la boucle intérieure de (c) est le point délicat : parcourue en croissant, elle autoriserait à réutiliser le même élément plusieurs fois — ce qui résout un autre problème, celui du rendu de monnaie. Un downto à la place d'un to change le problème résolu, sans rien changer au type ni à la terminaison.

2. Les complexités.

Méthode	Temps	Mémoire	Contrainte
(a) exhaustif	$Θ (n 2^{n})$	$Θ (1)$	$n ≲ 25$
(b) rencontre au milieu	$Θ (n 2^{n /2})$	$Θ (2^{n /2})$	$n ≲ 50$
(c) par table	$Θ (n c)$	$Θ (c)$	$c$ modéré ; entiers positifs

3. La mesure, sur $n = 20$ entiers de somme totale $490$ , les trois méthodes s'accordant sur chaque réponse :

cible	(a) exhaustif	(b) rencontre au milieu	(c) par table
$1$ (impossible)	$20971520$	$2046$	$0$
$100$	$20971520$	$2046$	$1530$
$250$	$20971520$	$2046$	$4530$

(Opérations élémentaires comptées. Le $0$ de la dernière colonne vient de ce que tous les éléments dépassent $1$ : la boucle intérieure ne s'exécute pas.)

Le choix, et il n'y a pas de gagnant.

(c) est la meilleure quand $c$ est petit : elle est ici quatre mille fois plus rapide que l'exhaustif. Mais son coût ne dépend pas de $n$ seulement : si $c$ vaut $1 0^{15}$ , la table est irréalisable, alors que $n$ peut rester à $20$ .
(b) est la meilleure quand $c$ est grand et $n$ modéré : son coût ignore complètement $c$ . C'est la seule des trois qui accepte des entiers négatifs ou fractionnaires sans rien changer.
(a) ne gagne jamais, sinon en simplicité — et c'est une raison suffisante quand $n \leq 20$ et qu'on écrit le programme une fois.

Le point de méthode. $Θ (n c)$ n'est pas polynomial en la taille de l'entrée : écrire $c$ ne demande que $lo g_{2} c$ bits. On dit pseudo-polynomial. C'est pourquoi la méthode (c) ne contredit pas le fait que le problème soit np-complet (chapitre chap:decidabilite) — et pourquoi la question « quelle est la meilleure méthode ? » n'a pas de réponse sans connaître les ordres de grandeur des deux paramètres.

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.