TP 5 : Tableaux et complexité

Petites questions¶

Exercice

1. Écrire une fonction somme pour calculer la somme des éléments d'un tableau d'entiers.
2. Écrire une fonction maximum pour calculer le maximum d'un tableau d'entiers. On pourra utiliser la fonction max renvoyant le maximum de 2 nombres.
3. Écrire une fonction list_of_array transformant un tableau en liste.
4. Tester si un tableau est trié par ordre croissant.

Solution

In [2]:

(* 1 *)
let somme t = 
    let res = ref 0 in
    for i=0 to Array.length t - 1 do
        res := !res + t.(i)
    done;
    !res in
somme [|3; 1; 7|];;

(* 2 *)
let maximum t = 
    let m = ref t.(0) in
    for i=1 to Array.length t - 1 do
        m := max t.(i) !m
    done;
    !m;;
maximum [|3; 1; 7|];;

(* 3 *)
let list_of_array t = 
    let rec aux i = (* transforme t.(0), ..., t.(i) en liste *)
        if i = -1 then []
        else t.(i)::aux (i - 1) in
    aux (Array.length t - 1);;
    
list_of_array [|4; 3; 9; 1|];;

(* 4 *)
let croissant t =
    let res = ref true in
    for i=0 to Array.length t - 2 do
        if t.(i) > t.(i + 1)
        then res := false
    done;
    !res;;

(* 1 *) let somme t = let res = ref 0 in for i=0 to Array.length t - 1 do res := !res + t.(i) done; !res in somme [|3; 1; 7|];; (* 2 *) let maximum t = let m = ref t.(0) in for i=1 to Array.length t - 1 do m := max t.(i) !m done; !m;; maximum [|3; 1; 7|];; (* 3 *) let list_of_array t = let rec aux i = (* transforme t.(0), ..., t.(i) en liste *) if i = -1 then [] else t.(i)::aux (i - 1) in aux (Array.length t - 1);; list_of_array [|4; 3; 9; 1|];; (* 4 *) let croissant t = let res = ref true in for i=0 to Array.length t - 2 do if t.(i) > t.(i + 1) then res := false done; !res;;

Out[2]:

- : int = 11

Out[2]:

val maximum : 'a array -> 'a = <fun>

Out[2]:

- : int = 7

Out[2]:

val list_of_array : 'a array -> 'a list = <fun>

Out[2]:

- : int list = [1; 9; 3; 4]

Out[2]:

val croissant : 'a array -> bool = <fun>

Maximum local dans un tableau¶

Exercice

Un maximum local dans un tableau t est un indice i tel que t.(i) >= t.(i+1) et t.(i) >= t.(i-1). Pour les extrémités, qu'une seule de ces conditions doit être vérifiée (si t.(i-1) ou t.(i+1) n'existe pas).

1. Montrer qu'il existe forcément un minimum local dans t.
2. Écrire une fonction max_local1 trouvant un maximum local dans un tableau en regardant chaque élément un par un (recherche séquentielle). Quelle est sa complexité ?
3. Écrire une fonction max_local2 faisant la même chose mais avec une méthode par dichotomie (en divisant par 2 la taille du problème à chaque itération), pour avoir une complexité logarithmique.
   Aide : soit t.(m) le milieu du tableau. Que peut-on dire si t.(m) < t.(m+1) ? Si t.(m) < t.(m-1) ?

Solution

1. Soit t.(k) le maximum de t. Alors k est un maximum local. Par contre il n'est pas forcément unique : par exemple dans [|1; 3; 2; 4|], les indices 1 (correspondant à t.(1) = 3) et 3 (correspondant à t.(3) = 4).

Solution

In [1]:

(* 2 *)
let max_local1 t = 
    let k = ref (-1) in (* on demande l'indice d'un minimum local *)
    let n = Array.length t in
    if t.(0) >= t.(1) then k := 0;
    if t.(n - 1) >= t.(n - 2) then k := n - 1;
    for i=1 to Array.length t - 2 do (* complexité O(n) où n est la taille de t, à cause de cette boucle *)
        if t.(i) >= max t.(i + 1) t.(i - 1)
        then k := i
    done;
    !k in
max_local1 [|1; 3; 5; 2|];;

(* 3 *)
(* On regarde le milieu t.(m) de t. 
Si t.(m) >= max t.(m - 1) t.(m + 1) alors m est un maximum local
Si t.(m) < t.(m - 1) alors t a un maximum local à gauche de m. En effet soit t.(i) un maximum de t.(0), ... t.(m). Alors i est différent de m (car t.(m) < t.(m - 1)) donc est un maximum local.
Si t.(m) < t.(m + 1) alors, de même, t a un maximum local à droite de m. *)

let max_local2 t = 
    let n = Array.length t in
    let rec aux i j = (* cherche un max local entre les indices i et j de t *)
        let m = (i + j)/2 in
        if (m = 0 || t.(m) >= t.(m-1)) && (m = n - 1 || t.(m) >= t.(m+1))
        then m (* m est un max local *)
        else if t.(m) < t.(m - 1) then aux i (m - 1)
        else aux (m + 1) j in
    aux 0 (n - 1);;
max_local2 [|1; 3; 5; 2|]

(* 2 *) let max_local1 t = let k = ref (-1) in (* on demande l'indice d'un minimum local *) let n = Array.length t in if t.(0) >= t.(1) then k := 0; if t.(n - 1) >= t.(n - 2) then k := n - 1; for i=1 to Array.length t - 2 do (* complexité O(n) où n est la taille de t, à cause de cette boucle *) if t.(i) >= max t.(i + 1) t.(i - 1) then k := i done; !k in max_local1 [|1; 3; 5; 2|];; (* 3 *) (* On regarde le milieu t.(m) de t. Si t.(m) >= max t.(m - 1) t.(m + 1) alors m est un maximum local Si t.(m) < t.(m - 1) alors t a un maximum local à gauche de m. En effet soit t.(i) un maximum de t.(0), ... t.(m). Alors i est différent de m (car t.(m) < t.(m - 1)) donc est un maximum local. Si t.(m) < t.(m + 1) alors, de même, t a un maximum local à droite de m. *) let max_local2 t = let n = Array.length t in let rec aux i j = (* cherche un max local entre les indices i et j de t *) let m = (i + j)/2 in if (m = 0 || t.(m) >= t.(m-1)) && (m = n - 1 || t.(m) >= t.(m+1)) then m (* m est un max local *) else if t.(m) < t.(m - 1) then aux i (m - 1) else aux (m + 1) j in aux 0 (n - 1);; max_local2 [|1; 3; 5; 2|]

Out[1]:

- : int = 2

Out[1]:

val max_local2 : 'a array -> int = <fun>

Out[1]:

- : int = 2

Tri par comptage¶

Exercice

Écrire une fonction tri_comptage : ’a array -> unit qui trie un tableau t de taille $n$ dont les entrées sont des entiers entre 0 et $M$ (où $M$ est le maximum de t), en complexité O($n + M$).
Pour cela :

• Créer un autre tableau compte de taille $M + 1$ (avec Array.make), initialement rempli de 0
• Remplir compte pour que compte.(i) contienne le nombre d'apparitions de i dans t
• Recopier les éléments de compte dans t dans l'ordre croissant pour obtenir un tableau trié

Solution

In [38]:

let tri_comptage t =
    let m = maximum t in
    let compte = Array.make (m+1) 0 in
    let n = Array.length t in
    for i=0 to n - 1 do
        compte.(t.(i)) <- compte.(t.(i)) + 1
    done;
    let k = ref 0 in (* k est la position où on va ajouter le prochain élément dans t *)
    for i=0 to m do
        for j=1 to compte.(i) do
            t.(!k) <- i;
            incr k
        done
    done;; (* pas besoin de renvoyer un tableau car on modifie t en dehors de la fonction *)
    
let t = [|1; 9; 5; 3; 4|] in
tri_comptage t;
t

let tri_comptage t = let m = maximum t in let compte = Array.make (m+1) 0 in let n = Array.length t in for i=0 to n - 1 do compte.(t.(i)) <- compte.(t.(i)) + 1 done; let k = ref 0 in (* k est la position où on va ajouter le prochain élément dans t *) for i=0 to m do for j=1 to compte.(i) do t.(!k) <- i; incr k done done;; (* pas besoin de renvoyer un tableau car on modifie t en dehors de la fonction *) let t = [|1; 9; 5; 3; 4|] in tri_comptage t; t

Out[38]:

val tri_comptage : int array -> unit = <fun>

Out[38]:

- : int array = [|1; 3; 4; 5; 9|]

Tranche maximum¶

Exercice

Écrire une fonction tranche_max : int array -> int qui renvoie en O($n$) la somme maximum d'éléments consécutifs d'un tableau de taille $n$. Par exemple, tranche_max [|1; -2; 6; -3; 2; 4; -8; 7|] doit renvoyer $9$, correspondant aux éléments 6; -3; 2; 4.

Indice : parcourir le tableau t avec une boucle for. Stocker 2 variables m et m_cur telles que, au $i$ème passage dans la boucle for :

• m contient la somme maximum d'éléments consécutifs parmi les $i$ premiers éléments du tableau
• m_cur contient la somme maximum d'éléments consécutifs finissant en t.(i).
  Par exemple, lorsque tranche_max [|1; -2; 6; -3; 2; 4; -8; 7|] exécute la $3$ème itération de la boucle for (c'est à dire que -3 est considéré), m contient 6 (correspondant au seul élément 6) et m_cur contient 3 (correspondant à 6; -3).

Solution

In [41]:

let tranche_max t =
    let m = ref t.(0) in
    let m_cur = ref t.(0) in
    for i = 1 to Array.length t - 1 do
        m_cur := max (!m_cur + t.(i)) t.(i);
        m := max !m !m_cur
    done;
    !m;;
    
tranche_max [|1; -2; 6; -3; 2; 4; -8; 7|]

let tranche_max t = let m = ref t.(0) in let m_cur = ref t.(0) in for i = 1 to Array.length t - 1 do m_cur := max (!m_cur + t.(i)) t.(i); m := max !m !m_cur done; !m;; tranche_max [|1; -2; 6; -3; 2; 4; -8; 7|]

Out[41]:

val tranche_max : int array -> int = <fun>

Out[41]:

- : int = 9

Inversions dans un tableau¶

Exercice

Étant donné un tableau t, une inversion de t est un couple d'indices $(i, j)$ tels que $i < j$ et t.$(i)$ > t.$(j)$. Par exemple, [|4; 1; 5; 2|] possède 3 inversions: $(0, 1)$, $(0, 3)$ et $(2, 3)$.

1. Écrire une fonction inv en O($n^2$) déterminant le nombre d'inversions d'un tableau de taille $n$. Justifier que la complexité est bien O$(n^2$).
2. Écrire une fonction inv_triee telle que, si t1 et t2 sont deux tableaux triés par ordre croissant, inv_triee t1 t2 renvoie le nombre de couples $(i, j)$ tels que t1.(i) > t2.(j). La complexité de inv_triee doit être linéaire en le nombre total d'éléments de t1 et t2.
3. (Difficile) Écrire une fonction inv2 telle que, si t est un tableau de taille $n$, inv2 t renvoie le nombre d'inversions de t en complexité O($n\log(n)$).
   On modifiera le tri fusion pour renvoyer le nombre d'inversions en plus de la liste triée.

Solution

In [11]:

(* 1 *)
let inv t =
    let res = ref 0 in
    let n = Array.length t in
    for i=0 to n - 1 do  (* répété n fois *)
        for j=i+1 to n - 1 do (* répété au plus n fois *)
            if t.(i) > t.(j) then res := !res + 1 (* répété au plus n² fois, donc complexité O(n²) *)
        done
    done;
    !res;;

inv [|4; 1; 3; 2|];; (* test *)

(* 1 *) let inv t = let res = ref 0 in let n = Array.length t in for i=0 to n - 1 do (* répété n fois *) for j=i+1 to n - 1 do (* répété au plus n fois *) if t.(i) > t.(j) then res := !res + 1 (* répété au plus n² fois, donc complexité O(n²) *) done done; !res;; inv [|4; 1; 3; 2|];; (* test *)

Out[11]:

val inv : 'a array -> int = <fun>

Out[11]:

- : int = 4