TP 1 : révisions

Itération

Exercice 1 (Décomposition en produit de facteurs premiers) :

Écrivez une fonction dec_fac_prem : int -> unit qui écrit la décomposition en produit de facteurs premiers de l’argument, sous la forme :

                         510510 = 2 * 3 * 5 * 7 * 11 * 13 * 17

Exercice 2 (Crible d’Eratosthène) :

1. Un entier naturel n étant donné, on veut tous les nombres premiers qui lui sont inférieurs ou égaux.

On utilise pour cela la méthode du crible d’Eratosthène :

• On écrit tous les nombres de 2 à n.

• On cherche le premier nombre non rayé (au départ 2), et on raye tous ses multiples.

• On recommence l’étape précédente jusqu’à ce qu’on ait exploré toute la table. Les nombres non barrés sont alors les nombres premiers inférieurs à n.

Écrivez une fonction crible : int -> unit qui écrit à l’écran tous les nombres premiers inférieurs ou égaux à l’argument.

2. En constatant que mis à part 2, tous les nombres premiers sont impairs, et que si p est premier, le premier multiple de p non déjà rayé est p^{2}, améliorez la fonction précédente.

3. Application graphique

Cet question relève plutôt du sujet d’étude. Comptez au moins une heure et demi pour la mise au point.

La spirale d’Ulam est un tableau dans lequel les nombres entiers sont écrits en escargot, et dont les nombres premiers sont noircis (voir figure ci-dessous). Les alignements constatés correspondent à des valeurs de polynômes à coefficients entiers.

Écrivez une fonction utilisant la bibliothèque graphique, et traçant une telle figure.

Récursion

Exercice 3 :

1. Écrivez un programme calculant C_{n}^{p} pour n et p entiers naturels en utilisant la formule de Pascal :

C_{n}^{p} = C_{n−1}^{p} + C_{n−1}^{p−1}

Déterminez le nombre d’appels récursifs provoqués par le calcul de C_{n}^{p} à l’aide de ce programme (vous pourrez éventuellement vérifier votre résultat en “traçant” l’exécution du programme, à la main ou avec la directive

trace).

2. Essayez d’améliorer ce programme de calcul des combinaisons, en trouvant d’autres formules de récurrence.

Exercice 4 :

1. Un maire soucieux des problèmes de circulation dans sa ville dont le plan est donné ci-dessous souhaite calculer le nombre de chemins reliant A et B, sachant que des sens interdits n’autorisent que les mouvements vers le nord et vers l’est (les routes diagonales sont impraticables dans cette question). Écrivez un programme récursif pour l’aider.

2. Le maire décide d’ouvrir les routes diagonales, en autorisant la circulation vers le nord-est (un chemin autorisé est dessiné en gras sur la figure précédente). Écrivez un programme tenant compte de cette nouvelle règle.

Exercice 5 (Recherche dichotomique dans un dictionnaire) :

On cherche à savoir si un mot se trouve dans un dictionnaire classé par ordre alphabétique. Pour cela, on compare le mot recherché au mot situé au milieu du dictionnaire. Si ils coïncident, on a terminé. Sinon, on recherche le mot dans la seule moitié du dictionnaire dans laquelle il peut éventuellement se trouver.

1. Implémenter cet algorithme en une fonction dico_dicho : string -> bool.

2. Évaluer l’efficacité de cet algorithme. Cet algorithme est-il utilisable pour trier une liste plutôt qu’un tableau ?

Travail avec les listes

Exercice 6 (Tri par insertion) :

On rappelle le principe du tri par insertion d’une liste d’entiers :

• si la liste est vide, on ne fait rien ;

• si la liste est de la forme t::q, on commence par trier q, puis on insère t au bon endroit.

1. Écrivez une fonction récursive insère : int -> int list -> int list qui insère son premier argument dans la liste supposée triée passée en deuxième argument.

2. Écrivez une fonction récursive tri_insertion : int list -> int list qui trie une liste donnée en argument et utilisant la fonction insère.

3. Étudiez la complexité de cette fonction.

Exercice 7 (Tri fusion) :

Cet algorithme est une application du principe diviser pour régner.

1. On dispose de deux listes d’entiers l1 et l2 triées par ordre croissant. On veut les réunir en une seule liste triée. Écrire une fonction fusion : int list -> int list -> int list réalisant ceci.

2. Écrire une fonction partition : int list -> int list * int list qui partitionne une liste en deux listes approximativement de mêmes longueurs.

3. Pour trier une liste l, on procède de la façon suivante :

(a) on partitionne la liste l en deux sous-listes l1 et l2 ; (b) on trie récursivement les deux listes l1 et l2 ;

(c) enfin on fusionne les listes l1 et l2.

Construire une fonction tri_fusion : int list -> int list qui trie une liste en utilisant ce principe.

4. Analysez la complexité du tri par fusion, en supposant d’abord que n est une puissance de 2.

Des exercices plus longs

Sujet d’étude 1 (Algorithmes compte-gouttes) :

1. Ces algorithmes permettent d’obtenir les décimales de certains nombres “au compte-gouttes”, c’est-à-dire une à une. Voici le procédé pour obtenir des décimales de π :

• Écrire sur une première ligne A les entiers de 1 à n, sur une deuxième ligne B les nombres impairs à partir de 3, et sur une troisième ligne (appelée ligne des restes) des 2 et un 2 placé devant.

• Répéter n + 1 fois les opérations suivantes :

– Multiplier chaque nombre de la ligne des restes par 10, l’écrire en dessous dans une ligne X.

– Placer un 0 dans la ligne en dessous, appelée ligne des retenues.

– Partant de la droite du tableau, pour toutes les colonnes :

∗ Ajouter le nombre de la ligne X à celui de la ligne retenue, placer le résultat dans la ligne S.

∗ Calculer le reste r et le quotient q de la division du nombre de la ligne S par celui de la ligne B. Le reste est écrit dans la ligne des restes, et on multiplie le quotient par le nombre placé dans la ligne A. Ce nombre constitue la retenue de la colonne précédente.

– Quand on arrive à gauche, le chiffre des dizaines de la dernière somme donne une nouvelle décimale, le chiffre des unités est conservé comme reste.

– On démarre alors l’étape suivante en prenant comme nouvelle ligne des restes celle qui vient d’être construite.

Voici un début de calcul :

A  1 2 3  4 5
B  3 5 7  9 11
π  2 2 2 2  2 2
×10  20 20 20 20 20 20
Retenue 10 12 12 8  5 0
Somme 30 32 32 28 25 20
Reste 0 2 2 0 7 9
×10  0 20 20 0 70 90
Retenue 11 14 18 48 40 0
Somme 11 34 38 48 110 90
Reste  1 1 3 6  2 2

Les nombres en gras sont les décimales obtenues. L’étape suivante fournirait un 2, il faut plus de colonnes à notre tableau pour obtenir plus de décimales.

La question est bien sûr d’implémenter cet algorithme en une fonction Caml.

2. Pour e, il suffit d’écrire dans la première ligne des 1, dans la deuxième les entiers à partir de 2, et dans la troisième un 2 suivi de 1. Implémentez ce nouvel algorithme.

3. En fait, l’algorithme donné pour π échoue à la 32^{ème} décimale (le vérifier !). Stanley Rabinowitz, en 1991, a fournit un algorithme modifié de la façon suivante : si le nombre obtenu est différent de 9, on l’écrit. Si il est égal à 9, on le stocke dans une liste de pré-chiffres, et on conserve ces pré-chiffres tant qu’on trouve des 9. Si on finit par tomber sur un quotient inférieur à 9, on écrit tous les pré-chiffres et le nouveau chiffre obtenu. Par contre, si on finit par tomber sur un quotient égal à 10, on transforme tous les pré-chiffres en 0, et on met en place un nouveau pré-chiffre à 0.

Mettez en place cette nouvelle méthode, et contrôlez-la.

4. Que pouvez-vous dire de l’efficacité de cet algorithme ? Connaissez vous des méthodes pour calculer π ou e plus rapidement ?

Sujet d’étude 2 (Tranche minimale d’un tableau d’entiers) :

Considérons un tableau A d’entiers relatifs, A = (a_{1}, …, a_{n}). On appelle tranche ou coupe de A une suite extraite notée A[i..j] où i ⩽ j et A[i..j] = (a_{i}, …, a_{j}). Nous noterons σ(i, j) la somme des termes de la tranche A[i..j] :

σ(i, j) = ∑_{k=i}^{j} a_{k}

On s’intéresse à la recherche du minimum des σ(i, j) pour 1 ⩽ i ⩽ j ⩽ n.

1. On considère pour commencer l’algorithme naïf explorant toutes les tranches possibles :

S := a_{1}

pour j de 1 à n faire pour i de 1 à j faire S := min(S, σ(i, j)) fin pour fin pour renvoyer S

Le traduire en une fonction tranche_naif : int vect -> int.

Étudiez la complexité de cet algorithme. Vous paraît-elle satisfaisante ?

2. En constatant que dans l’algorithme naïf, on calcule plusieurs (!) fois les mêmes sommes. Or ce sont ces sommes qui prédominent dans le calcul de complexité. Modifiez votre algorithme de sorte que dans la boucle interne le calcul de σ(i, j) soit remplacé par une simple addition, et calculez la nouvelle complexité.

Traduisez cet algorithme en une nouvelle fonction tranche_moins_naif.

3. On essaie d’améliorer notre analyse du problème en introduisant un raisonnement par récurrence. Considérons donc la suite A_{n} = (a_{1}, …, a_{n}) et supposons n ⩾ 2. Les tranches de A_{n} sont de deux types :

• celles qui ne contiennent pas a_{n} : ce sont les tranches de A_{n−1} ;

• celles qui contiennent a_{n} : il s’agit de la tranche A_{n}[n..n] et des tranches de la forme A_{n}[i..n] (i < n) qui s’obtiennent en ajoutant a_{n} à la tranche A_{n−1}[i..n − 1] de A_{n−1}.

Ceci nous invite à introduire la notion de tranche finale pour désigner les tranches dont le deuxième indice est l’indice du dernier terme de la suite considérée. Notons alors m(A_{n}) le minimum des sommes des tranches de A_{n} (c’est ce qui nous intéresse) et mf(A_{n}) le minimum des sommes des tranches finales. On a alors :

m(A_{1}) = mf(A_{1}) = a_{1} et \begin{matrix}m(A_{n}) = min(mf(A_{n}), m(A_{n−1})) \\ mf(A_{n}) = min(mf(A_{n−1}) + a_{n}, a_{n}) \end{matrix}

Implémentez cet algorithme en une fonction tranche_recur, et déterminez la nouvelle complexité.

4. Le dernier calcul ne doit pas nous faire perdre espoir : il suffit de l’envisager sous un angle itératif. Construisez un algorithme non récursif exploitant les constatations précédentes, et traduisez-le en une fonction tranche_qui_decoiffe. Vous devriez trouver une complexité en O(n).

Corrigé (partiel) du premier TP : révisions

Question 1 :

On va tester la divisibilité du nombre à factoriser avec 2 et tous les nombres impairs d inférieurs ou égaux à la racine carrée de ce qui reste.. En effet, si ceux-ci ne sont pas premiers, leurs facteurs ont déjà été éliminés de n. On s’arrêtera lorsque n = 1 ou lorsque n > d^{2}. Voir le programme 1.

Remarquez que le code du programme est très documenté. Les commentaires peuvent servir à raconter des bêtises, mais ils sont essentiellement utiles pour rendre clair un code qui ne l’est pas. Vous devez savoir qu’on fait beaucoup de fautes de frappes. L’interpréteur (ou le compilateur) corrigera les erreurs de syntaxes, mais il n’est pas conçu pour détecter les failles de raisonnement. Un petit commentaire illustrant le fonctionnement permet de corriger la plupart de ces erreurs.

Question 2 :

1. Voici un programme qui imprime le résultat du crible. Vous trouverez en commentaires des instructions permettant de contrôler le bon fonctionnement du programme... ou de corriger un dysfonctionnement (beaucoup plus fréquent, d’après la célèbre loi de Murphy) (voir le programme 1 ).

2. Le programme précédent tient compte des remarques de cette question.

3. Le programme 1 utilise les capacités graphiques de l’interface graphique. A priori, si j’ai correctement lu la documentation, il doit tourner sans problèmes sous Windows.

Il utilise une version modifiée du crible d’Eratosthène (le programme 1). L’effet est joli, mais on pourrait l’améliorer en dessinant des points plus gros, ou bien en changeant la forme de la spirale. Les alignements diagonaux correspondent aux valeurs prises par des polynômes à coefficients entiers (lesquels ?).

Question 3 :

1. Le programme 1, récursif, exploite directement la formule.

Notons T (n, p) le nombre d’appels à la fonction binome. On a :

T (n, 0) = T (n, n) = 1 et T (n, p) = 1 + T (n − 1, p) + T (n − 1, p − 1) si 0 < p < n

En posant alors T′(n, p) = T (n, p) + 1, on obtient :

T′(n, 0) = T′(n, n) = 2 et T′(n, p) = T′(n − 1, p) + T′(n − 1, p − 1) si 0 < p < n

Ainsi, T′(n, p) = 2 C_{n}^{p}, et donc T (n, p) = 2 C_{n}^{p} −1 . La fonction fait donc à peu près deux fois plus de calculs que le résultat qu’elle renvoie. On pourrait donc faire le calcul avec l’horloge interne de l’ordinateur. Vous pouvez vérifier ce résultat avec la directive trace "binome", ou en mettant à jour une variable globale dans le corps de la fonction.

2. On va plutôt utiliser cette récurrence simple : C_{n}^{p} = \frac{n}{p} C_{n−1}^{p−1}. D’où le nouveau programme 1, linéaire en p :

Vous constaterez que ce nouveau programme n’est pas entièrement satisfaisant : comme on calcule d’abord n * binome(n-1, p-1) avant de diviser par p, il se peut que le résultat déborde du cadre des entiers (ce qui, rappelons le, ne provoque pas d’arrêt du programme). On ne peut se permettre de diviser d’abord par p, ne sachant pas si la division va “tomber juste”.

Il est clair que ce programme exécute exactement p appels à la fonction binome.

Question 4 :

1. Soit N(n, p) le résultat cherché. Compte tenu des sens uniques, on a :

N(0, p) = N(n, 0) = 1 et N(n, p) = N(n − 1, p) + N(n, p − 1)

Constatons immédiatement, au vu de l’exercice précédent, que la méthode récursive, si elle donne un texte de programme très court, n’est absolument pas efficace. On fait en effet très souvent des calculs déjà faits (voir programme 1 Pour ne pas faire plusieurs fois les mêmes calculs, on va stocker les résultats intermédiaires dans une colonne, comme dans le programme 1.

On sent nettement l’amélioration dés que n et p valent aux alentours de 10.

Programme 1 Décomposition en produit de facteurs premiers

let dec_fac_prem n =
let facprem = make_vect 10 (0, 0) (* tableau (facteur * exposant) *)
and m = ref n (* pour pouvoir le diviser *)
and u = ref 0 (* puissance du facteur courant *)
and r = ref 0 (* nombre de facteurs *)
and facteur m p = (* cherche la plus grande puissance de p divisant n *)
let k = ref 0 (* au depart, c'est 0 *) in
while (!m mod p = 0) do (* tant qu'on peut diviser *)
m := !m / p; (* on ne se prive pas *)
k := !k + 1 (* et on augmente l'exposant *)
done;
!k; (* enfin, on renvoie l'exposant cherche *)
in
u := facteur m 2; (* on commence par le seul premier pair *)
if (!u <> 0) then (* si 2 est facteur *)
begin
facprem.(0) <- (2, !u); (* on le range avec son exposant *)
r := 1 (* et on passe à la case suivante *)
end;
for i = 1 to int_of_float(sqrt(float_of_int(!m))) / 2 do
u := facteur m (2 * i + 1);      (* puis tous les entiers impairs *)
if (!u <> 0) then (* jusqu'a racine de m *)
begin
  facprem.(!r) <- (2 * i + 1, !u); (* memes operations que pour 2 *)
  r := !r + 1
end
done;
print_newline (); (* on passe a l'affichage : changement de ligne *)
if !r = 0 then (* on n'a pas trouve de facteurs *)
begin
print_string ("Le nombre ");
print_int n;
print_string (" est premier.") (* donc n est premier *)
end
else (* sinon *)
begin
print_int n;
print_string (" = ");
print_int (fst facprem.(0));
if (snd (facprem.(0)) > 1) then (* si la puissance n'est pas 1 *)
  begin
    print_string ("ˆ");
    print_int (snd (facprem.(0))) (* on l'affiche *)
  end;
u := 1; (* deuxieme case du tableau *)
while (fst (facprem.(!u)) <> 0) do (* tant qu'il reste des facteurs *)
  print_string (" * ");
  print_int (fst (facprem.(!u))); (* on les affiche *)
  if (snd (facprem.(!u)) > 1) then
    begin
      print_string ("ˆ");
      print_int (snd (facprem.(!u))) (* avec leurs exposants *)
    end;
  u := !u + 1 (* puis on passe au facteur suivant *)
done;
if !m <> 1 then (* s'il reste un facteur *)
  begin
    print_string (" * "); (* il est forcement premier *)
    print_int !m;  (* on l'affiche *)
  end;
end;
print_newline ();; (* enfin, on passe a la ligne pour faire joli *)

Programme 2 Crible d'Eratosthène (avec contrôle du fonctionnement)

(* Crible d'Eratosthène *)
let eratosthene = function n ->
let crible = make_vect (n+1) true
and r = int_of_float(sqrt(float_of_int n))
and compte = ref 0
in
begin
for i = 2 to r do
  if crible.(i) then (* Si i n'a pas été rayé (il est premier) *)
    begin            (* on raye tous les multiples de i *)
      (* print_string("je raye les multiples de ");
         print_int(i);
         print_newline(); *)
      let j = ref (i * i) (* à partir de iˆ 2 *)
      and pasfini = ref true
      in
        while !pasfini do
          crible.(!j) <- false;
          (* print_int(i);
             print_string("  "); *)
          compte := !compte + 1;
          j := !j + i;
          pasfini := (n >= !j); (* et ce jusqu'à ce que j *)
        done;                   (* soit supérieur à n *)
        (* print_newline(); *)
    end
done;
for i = 2 to n do
  if crible.(i) then
    begin
      print_int(i);
      print_string("  ");
    end
done;
print_newline();
(* print_string(" j'ai rayé ");
   print_int(!compte);
   print_string(" nombres.");
   print_newline(); *)
end;;

Programme 3 spirale d'Ulam : la fonction crible

#open "graphics";;
open_graph " 501x501+50+50";;
let eratosthene = function n ->
let crible = make_vect (n+1) true
and r = int_of_float(sqrt(float_of_int n))
and compte = ref 0
in
begin
for i = 2 to r do
if crible.(i) then (* Si i n'a pas été rayé (il est premier) *)
begin            (* on raye tous les multiples de i *)
(* print_string("je raye les multiples de ");
print_int(i);
print_newline(); *)
let j = ref (i * i) (* à partir de iˆ2 *)
and pasfini = ref true
in
while !pasfini do
crible.(!j) <- false;
(* print_int(i);
   print_string("  "); *)
compte := !compte + 1;
j := !j + i;
pasfini := (n >= !j); (* et ce jusqu'à ce que j *)
done;                   (* soit supérieur à n *)
(* print_newline(); *)
end
done;
crible;
end;;

Programme 4 spirale d'Ulam : la fonction de tracé

let ulam () =
let u = ref 250
and v = ref 250
and n = ref 1
and crible = eratosthene 251001
in
for i = 1 to 250 do
u := !u + 1;
n := !n + 1;
if crible.(!n) then plot !u !v;
for j = 1 to (2 * i - 1) do
n := !n + 1;
v := !v + 1;
if crible.(!n) then plot !u !v;
done;
for j = 1 to (2 * i) do
n := !n + 1;
u := !u - 1;
if crible.(!n) then plot !u !v;
done;
for j = 1 to (2 * i) do
n := !n + 1;
v := !v - 1;
if crible.(!n) then plot !u !v;
done;
for j = 1 to (2 * i) do
n := !n + 1;
u := !u + 1;
if crible.(!n) then plot !u !v;
done;
done;;

Programme 5 Calcul des combinaisons, première version

let rec binome(n, p) =
if ((p = 0) or (p = n)) then 1
else binome(n - 1, p) + binome(n - 1, p - 1);;

Programme 6 Calcul des combinaisons, deuxième version

let rec binome_rapide(n,p) =
match p with
| 0 -> 1
| _-> (n * binome_rapide(n-1, p-1)) / p;;

Programme 7 Nombre de chemins, première règle

let Nchemins_0(n,p) =
if (n=0) or (p=0) then 1
else
;;

Programme 8 Nombre de chemins, première règle

      let Nchemins_1(n,p) =
        let colonne = make_vect (p+1) 1 (* colonne.(j) = N(i,j) *)
        in
          for i = 1 to n do
            for j = 1 to p do
              (* ici, colonne.(0) = N(i,0) ... colonne.(j-1) = N(i,j-1),
               * et   colonne.(j) = N(i-1,j) ... colonne.(p) = N(i-1,p)
               * de plus, !v = N(i-1,j-1) *)
              colonne.(j) <- colonne.(j) + colonne.(j-1);
            done;
          done;
          colonne.(p) (* le résultat attendu *)
      ;;

2. Cette fois ci, la récurrence est :

N(0, p) = N(n, 0) = 1 et N(n, p) = N(n − 1, p) + N(n, p − 1) + N(n − 1, p − 1)

Le programme 1 est un tout petit peu plus technique : Pour pouvoir calculer N(n, p), il faut actualiser

Programme 9 Nombre de chemins, deuxième règle

      let Nchemins_2(n,p) =
        let colonne = make_vect (p+1) 1 (* colonne.(j) = N(i,j) *)
        and v = ref 1
        in
          for i = 1 to n do
            v := 1;
            for j = 1 to p do
              (* ici, colonne.(0) = N(i,0) ... colonne.(j-1) = N(i,j-1),
               * et   colonne.(j) = N(i-1,j) ... colonne.(p) = N(i-1,p)
               * de plus, !v = N(i-1,j-1) *)
              let w = colonne.(j) in
                colonne.(j) <- colonne.(j) + !v + colonne.(j-1);
                v := w;
            done;
          done;
          colonne.(p);; (* le résultat attendu *)

la colonne n + 1 fois (en comptant l’initialisation), ce qui revient à remplir un tableau de (n + 1) × (p + 1) cases. La complexité est donc en O(np).

Question 5 :

On verra cet exemple plus tard, lorsqu’on traitera des arbres binaires de recherche.

Question 6 :

1. Les listes se traitent très souvent avec des fonctions récursives, utilisant la décomposition d’une liste en sa tête et sa queue. Le programme 1 ne fait pas défaut à cette règle :

Remarquez qu’on essaie de faire le minimum d’appels récursifs en plaçant n le plus tôt possible dans la liste.

2. La fonction tri_insertion est elle aussi récursive, d’après sa définition (voir programme 1).

3. Pour trier une liste à n éléments, on commence par trier la queue, composée de n − 1 éléments, puis on insère la tête dans la liste triée. L’opération élémentaire que nous utiliserons comme instrument de mesure est la comparaison.

Programme 10 insertion dans une liste ordonnée

      let rec insere n l =
        match l with
            [] -> [n]
          | t::q -> if n <= t then n::l
                    else t::(insere n q);;

Programme 11 tri par insertion d'une liste

      let rec tri_insertion l =
        match l with
            [] -> []
          | t::q -> insere t (tri_insertion q);;

Notons T (n) le nombre maximum de comparaisons qu’on doit effectuer pour trier une liste de n éléments. Pour insérer un élément dans une liste de n élément, il faut effectuer au pire n comparaisons. T (n) vérifie donc la relation de récurrence :

T (0) = 0 et T (n) = T (n − 1) + n − 1

On en déduit que

T (n) = ∑_{i=0}^{n−1} i = \frac{n(n − 1)}{2}

La complexité de cet algorithme dans le pire cas est donc en Θ(n^{2}).

Remarquons que si l’on suppose que pour une liste quelconque de n , il faudra en moyenne n/2 comparaisons pour insérer un élément, alors la complexité temporelle est seulement divisée par 2, et la complexité moyenne est donc elle aussi en Θ(n^{2}).

Question 7 :

1. La fusion de deux listes ne pose pas de problèmes particuliers. On distingue trois cas : ceux où l’une des deux listes est vide, et le cas général (voir programme 1).

Programme 12 fusion de deux listes ordonnées

      let rec fusion l1 l2 =
        match (l1,l2) with
            ([],_) -> l2
          | (_,[]) -> l1
          | (h1::r1,h2::r2) ->
              if h1 <= h2
              then h1::(fusion r1 l2)
              else h2::(fusion l1 r2);;

2. Le partage est un peu plus problématique. On va encore distinguer trois cas, selon que la liste est vide, a un élément ou en a plus de deux (voir programme 1). Ce programme fait en fait exactement ce que ferait un joueur voulant séparer un paquet de cartes en deux : il en jette alternativement une à gauche et une à droite jusqu’à épuisement du paquet.

3. Dés lors que les deux fonctions fusion et partition sont implémentées, le reste n’est que routine (voir programme 1).

4. Mettons-nous dans le cas le plus simple : le cas ou la liste a une longueur égale à 2^{p}. Appelons T (p) le nombre d’opérations élémentaires effectuées pour trier cette liste.

Programme 13 partition d'une liste en deux sous-listes de mêmes tailles

        let rec partition l =
          match l with
              [] -> ([],[])
            | [x] -> ([x],[])
            | h1::h2::r -> match partition r with
                  (r1,r2) -> (h1::r1,h2::r2);;

Programme 14 tri par fusion d'une liste

        let rec tri_fusion = function
            [] -> []
          | [x] -> [x]
          | l -> match partition l with
                (l1,l2) -> fusion (tri_fusion l1) (tri_fusion l2);;

Le coût de la partition en deux sous-listes de longueur 2^{p−1} et celui de la fusion de ces deux listes une fois triées est de l’ordre de k ×2^{p}, k étant une constante. Le coût du tri des deux sous-listes de longueurs 2^{p−1} est 2×2^{p−1}. Ainsi :

T (p) = 2T (p − 1) + k2^{p}

En posant U(p) = T (p)/2^{p}, on arrive à :

U(p) = U(p − 1) + k

Ainsi, U(p) = pk, et

T (p) = kp2^{p}

On revenant à la signification de p, on voit que cet algorithme a une complexité temporelle dans le pire cas de l’ordre de Θ(n ln_{2} n). Ce résultat subsiste quand la liste est de longueur quelconque.

Sujet d’étude 1 Je vous présente un programme (le programme 1) implémentant le premier algorithme, qui tombe en défaut à la 32^{ème} décimale. Vous l’adapterrez à vos besoins.

Il est très simple à adapter au cas de e, mais la méthode corrigée (dont l’énoncé que je vous ai donné est d’ailleurs faux) est plus difficile à implémenter : il faut trouver une structure adéquate pour stocker les chiffres de garde, sachant qu’on devra les modifier si on tombe sur un reste égal à 10 (on doit alors tous les augmenter de 1, et non les changer en 0).

Sujet d’étude 2 :

Nous corrigerons ce sujet d’étude en TD de façon détaillée.

Programme 15 compte-gouttes : première version (incorrecte) pour π

let compte_goutte_1 n =
let m = 10 * n / 3
in
let A = make_vect (m+1) 0
and B = make_vect (m+1) 0
and C = make_vect (m+1) 2
and X = make_vect (m+1) 20
and R = make_vect (m+1) 0
and S = make_vect (m+1) 0
in
for i = 1 to m do
A.(i) <- i;
B.(i) <- (2 * i) + 1;
done;
for iteration = 1 to n do
R.(m) <- 0;
(* print_string ("Itération numéro "); *)
(* print_int (i); *)
(* print_newline (); *)
for j = m downto 1 do
  X.(j) <- C.(j) * 10;
  S.(j) <- X.(j) + R.(j);
  R.(j-1) <- (S.(j) / B.(j)) * A.(j);
  C.(j) <- S.(j) mod B.(j);
done;
X.(0) <- C.(0) * 10;
S.(0) <- X.(0) + R.(0);
print_int (S.(0) / 10);
if (iteration = 1) then print_string (",");
C.(0) <- S.(0) mod 10;
done;
print_newline ();;