Prépa:Informatique/Diviser pour régner

Fiche d'exemple : code OCaml et C avec coloration. Modifie-la ou supprime-la librement.

Principe

DéfinitionDiviser pour régner

On découpe un problème de taille $n$ en $a$ sous-problèmes de taille $n/b$, on les résout récursivement, puis on combine les solutions.

Tri fusion (OCaml)

let rec scinder = function
  | [] -> [], []
  | [x] -> [x], []
  | x :: y :: q -> let a, b = scinder q in x :: a, y :: b

let rec fusion l1 l2 = match l1, l2 with
  | [], l | l, [] -> l
  | x :: q1, y :: q2 ->
    if x <= y then x :: fusion q1 l2 else y :: fusion l1 q2

let rec tri_fusion = function
  | ([] | [_]) as l -> l
  | l -> let a, b = scinder l in fusion (tri_fusion a) (tri_fusion b)

FormuleComplexité du tri fusion

$$C(n)=2C(n/2)+\mathrm{\Theta }(n)⟹C(n)=\mathrm{\Theta }(n\log n)$$

Recherche dichotomique (C)

/* Renvoie un indice de x dans t (trié, de taille n), ou -1. */
int dichotomie(const int *t, int n, int x) {
    int g = 0, d = n - 1;
    while (g <= d) {
        int m = g + (d - g) / 2;   /* évite le dépassement de g + d */
        if (t[m] == x) return m;
        if (t[m] < x) g = m + 1; else d = m - 1;
    }
    return -1;
}

MéthodeProuver la terminaison et la correction

• Terminaison : le variant $d-g$ est un entier qui décroît strictement à chaque tour tant que $g\le d$.
• Correction : invariant « si $x$ est dans $t$, il est dans $t[g..d]$ ».

On peut aussi écrire du code dans une phrase : List.map (fun x -> x * x) l.