Diviser pour régner

Cours · informatique (MP2I/MPI), chapitre 15 · MP2I et MPI · le début du chapitre, la suite sur Adloun

15.1 Trois temps

Le chapitre précédent énumérait ; celui-ci découpe. La méthode se dit en trois temps :

Diviser le problème en sous-problèmes de même nature, plus petits ;
Régner : les résoudre récursivement, jusqu'à un cas de base traité directement ;
Combiner leurs solutions en une solution du problème initial.

Le gain vient d'un fait arithmétique : diviser la taille par deux à chaque étape ne laisse que $lo g_{2} n$ étages. Encore faut-il que le troisième temps soit bon marché — c'est là que tout se joue, et c'est ce que la récurrence du chapitre chap:recursivite mesure :

$T (n) = a T (n / b) + f (n) .$

15.2 La dichotomie

Définition 15.1Recherche dichotomique

Chercher $v$ dans un tableau trié : on compare $v$ à l'élément médian, ce qui élimine la moitié du tableau.


(* Renvoie Some i tel que t.(i) = v, ou None.
   Précondition : t est trié par ordre croissant. *)
let recherche t v =
  let rec aux g d =
    if g > d then None
    else
      let m = g + (d - g) / 2 in
      if t.(m) = v then Some m
      else if t.(m) < v then aux (m + 1) d
      else aux g (m - 1)
  in
  aux 0 (Array.length t - 1)

Ici $a = 1$ : un seul sous-problème est résolu, et la combinaison est vide. $T (n) = T (n /2) + O (1) = Θ (lo g n)$ .

ImportantCe que

lo g_{2} n

veut dire

$n$	recherche linéaire	dichotomie
$1 0^{3}$	1 000	10
$1 0^{6}$	1 000 000	20
$1 0^{9}$	1 000 000 000	30

Multiplier la taille par mille n'ajoute que dix comparaisons. C'est le rendement le plus spectaculaire de tout le livre, et il ne coûte qu'une chose : que le tableau soit trié.

15.2.1 La dichotomie là où on ne l'attend pas

Le programme insiste : « on présente un exemple de dichotomie où son recours n'est pas évident : par exemple, la couverture de $n$ points de la droite par $k$ segments égaux de plus petite longueur ».

Méthode : Dichotomiser sur la RÉPONSE, et non sur les données

Le problème ne parle d'aucun tableau trié. L'idée est ailleurs : on ne cherche pas dans les données, on cherche la valeur de la réponse, et l'on s'appuie sur une propriété de monotonie.

Le problème. $n$ points $x_{1} \leq \dots \leq x_{n}$ sur une droite, $k$ segments de même longueur $L$ . Quelle est la plus petite $L$ permettant de tout couvrir ?

L'observation décisive. Si une longueur $L$ suffit, alors toute longueur $L^{'} > L$ suffit aussi. La propriété « $L$ suffit » est donc monotone en $L$ : fausse jusqu'à un seuil, vraie ensuite. Un seuil dans une suite monotone se cherche par dichotomie.

Le test, glouton et linéaire. Pour une $L$ donnée, on couvre au plus vite : le premier segment commence au premier point non couvert, et l'on recommence.


(* Nombre minimal de segments de longueur L couvrant les points triés x. *)
let segments_necessaires x l =
  let n = Array.length x in
  let compte = ref 0 and i = ref 0 in
  while !i < n do
    let debut = x.(!i) in
    incr compte;
    while !i < n && x.(!i) <= debut +. l do incr i done
  done;
  !compte

(* Plus petite longueur permettant de couvrir x avec k segments, à eps près.
   Précondition : x trié, non vide, k >= 1. *)
let plus_petite_longueur x k eps =
  let bas = ref 0.0 and haut = ref (x.(Array.length x - 1) -. x.(0)) in
  while !haut -. !bas > eps do
    let milieu = (!bas +. !haut) /. 2.0 in
    if segments_necessaires x milieu <= k then haut := milieu   (* ça suffit *)
    else bas := milieu                                          (* trop court *)
  done;
  !haut

Complexité. Chaque test est $Θ (n)$ , et la dichotomie divise l'intervalle par deux : $O (n lo g \frac{x _{n} - x _{1}}{ε})$ .

Exercices du chapitre

La dichotomie entière qui ne se termine pas corrigé
Dichotomiser sur la réponse : la racine carrée entière corrigé
Dichotomiser sur les valeurs candidates, et non sur les réels corrigé
Une ligne qui coûte un ordre de grandeur corrigé
Trois récurrences, trois régimes corrigé
Karatsuba : trois produits au lieu de quatre corrigé

La suite du cours · Tous les exercices du chapitre