Aller au contenu

DS 3 — Exponentiation rapide et tri du crêpier

MP2I, année 2021-2022. Devoir surveillé 3 du 16 décembre 2021, partie écrite. Durée totale 2h. La partie pratique sur machine est sur une page séparée.

Tout document interdit. Tout dispositif électronique interdit.

On vous demande d'écrire lisiblement et de bien présenter. Les programmes en particulier doivent être bien indentés et lisibles. Utilisez de préférence plusieurs couleurs. Commentez votre code dès que ce qu'il fait n'est pas évident.

Pirelli

On considère la fonction suivante :

let expo_naive x n =
  let p = ref 1 in
  for i = 1 to n do
    p := !p * x
  done;
  !p

Q01. Montrer que la fonction précédente calcule \(x^n\) en considérant sa terminaison acquise.

Corrigé

Ici, c'est une boucle for donc on a l'indice géré pour nous ce qui peut compliquer la vérification de l'invariant. On pourrait le réécrire ainsi :

let expo_naive x n =
  let p = ref 1 in
  let i = ref 1 in
  while !i <= n do
    p := !p * x;
    i := !i + 1
  done;
  !p

En pratique, on dira donc qu'on considère dans une boucle for i = a to b que \(i\) vaut \(a\) avant la première itération, qu'on incrémente \(i\) à la fin de l'itération et ainsi que \(i\) vaut \(b+1\) en sortie.

En faisant cela, on considère la propriété \(I(i, p) := p = x^{i-1}\).

  • Init : avant la boucle, on peut considérer que \(i = 1\) et on a bien \(p = 1 = x^0\) donc \(I(i,p)\) est vérifié.
  • Her : si \(I(i,p)\) est vérifié en début d'itération on a \(p = x^{i-1}\) et donc \(p \times x = x^i\) donc on a bien \(I(i+1,p \times x)\) vérifié.

Ainsi, la propriété est vérifiée tout au long de la boucle : c'est un invariant. En sortie de boucle, on a \(p = x^{n+1-1} = x^n\).

Q02. Combien de multiplications effectue cette fonction pour calculer \(x^n\) ?

Corrigé

On effectue une multiplication par itération donc \(n\) multiplications.

On considère maintenant la fonction :

let expo_binaire x n =
  let p = ref 1 in
  let a = ref x in
  let k = ref n in
  while !k > 0 do
    if !k mod 2 = 1
    then p := !p * !a;
    a := !a * !a;
    k := !k / 2
  done;
  !p

Q03. Donner l'état des variables à chaque itération dans l'appel de expo_binaire 3 15.

Corrigé
\(p\) \(a\) \(k\)
1 3 15
3 9 7
27 81 3
2187 6561 1
14348907 43046721 0

Q04. Prouver la correction de cette fonction :

  1. sa terminaison ;
  2. le fait qu'elle calcule \(x^n\).
Corrigé
  1. La quantité \(k\) est un variant de boucle car elle est entière, positive et dans une boucle, \(k > 0\) donc \(\lfloor k / 2 \rfloor < k\) et elle diminue strictement à chaque itération. Ainsi, la boucle termine car elle admet un variant.

  2. On va montrer que la propriété \(I(a,p,k) := a^k p = x^n\) est un invariant de boucle.

    Init : avant la première itération, on a \(a^k p = x^n \times 1 = x^n\) donc \(I(x,1,n)\) est vérifié.

    Her : si \(I(a,p,k)\) est vérifié au début d'une itération :

    • soit \(k = 2k'\) et \(x^n = a^k p = (a^2)^{k'} p\) donc \(I(a^2,p,k')\) est vérifié ;
    • soit \(k = 2k'+1\) et \(x^n = a^k p = (a^2)^{k'} (a p)\) donc \(I(a^2,a p,k')\) est vérifié.

    Dans tous les cas, \(I(a,p,k)\) est vérifié en fin d'itération avec les nouvelles valeurs des variables.

    \(I\) est donc un invariant et en sortie de boucle, on a \(I(a,p,0)\) vérifié donc \(x^n = a^0 p = p\). On renvoie bien \(x^n\).

Soit \(n \in \N\), on note

  • \(\lfloor \log_2 n \rfloor\) l'unique entier \(p\) tel que \(2^{p} \le n < 2^{p+1}\).
  • \(\lceil \log_2 n \rceil\) l'unique entier \(p\) tel que \(2^{p-1} < n \le 2^{p}\).
  • \(\nu(n)\) le nombre de \(1\) dans l'écriture binaire de \(n\). Plus précisément, si \(n = a_0 + a_1 2 + a_2 4 + \dots + a_{d-1} 2^{d-1}\) avec \(a_0,\dots,a_{d-1} \in \{0,1\}\) alors il y a exactement \(\nu(n)\) des \(a_i\) qui valent \(1\).

Q05. On suppose que \(n > 0\). Montrer que la fonction expo_binaire effectue \(\lceil \log_2 n \rceil + \nu(n)\) multiplications pour calculer \(x^n\).

Corrigé

On écrit \(n = \overline{1a_{d-2}\dots a_0}^2\) avec \(d\) chiffres en binaire, c'est-à-dire \(n = a_0 + a_1 2 + \dots + a_{d-2} 2^{d-2} + 2^{d-1}\) avec \(a_0,\dots,a_{d-2} \in \{0,1\}\). On a \(2^{d-1} \le n < 2^d\), donc \(d = \lfloor \log_2 n \rfloor + 1\).

À chaque étape, on décale dans \(k\) l'écriture binaire de \(n\) vers la droite :

\[ \overline{1a_{d-2}\dots a_0}^2 \rightarrow \overline{1a_{d-2}\dots a_1}^2 \dots \rightarrow \overline{1a_{d-2}}^2 \rightarrow \overline{1}^2 \rightarrow 0 \]

On effectue donc exactement \(d\) itérations, et k mod 2 va prendre les valeurs \(a_0, a_1, \dots, a_{d-2}, 1\) : on aura bien \(\nu(n)\) valeurs 1 entraînant une multiplication.

Au final, on a donc \(\nu(n)\) multiplications issues du test et \(d\) multiplications dues à la mise au carré de \(a\), soit \(\lfloor \log_2 n \rfloor + 1 + \nu(n)\) multiplications en tout.

  • Si \(n\) n'est pas une puissance de 2, on a \(2^{d-1} < n < 2^d\), donc \(d = \lceil \log_2 n \rceil\) et on obtient bien \(\lceil \log_2 n \rceil + \nu(n)\) multiplications.
  • Si \(n = 2^{d-1}\), on a \(\lceil \log_2 n \rceil = d-1\) et \(\nu(n) = 1\) : la fonction effectue \(d+1 = \lceil \log_2 n \rceil + \nu(n) + 1\) multiplications, une de plus que la formule de l'énoncé (par exemple 2 multiplications pour \(n = 1\) : \(1 \times x\) puis \(x \times x\)).

Note : c'est un \(O(\log_2 n)\).

L'algorithme précédent effectue des multiplications non nécessaires pour gérer les variables : le premier calcul \(1 \times x\) et la dernière mise au carré. Si on effectue ce principe à la main, pour calculer \(x^{15}\) on place \(x\) dans \(p\) (pas de multiplications cf. remarque), puis on calcule \(x^2\), on place \(x^3 = x \times x^2\) dans \(p\), puis on calcule \(x^4\), on place \(x^7 = x^3 \times x^4\) dans \(p\), on calcule \(x^8\) et on place \(x^{15} = x^7 \times x^8\) dans \(p\). Cette méthode de décomposition en binaire calcule ainsi \(x^{15}\) en six multiplications.

On peut faire mieux, en effet, on peut remarquer que \(15 = 3 \times 5\). Pour cela, on peut calculer \(x^3 = x \times x \times x = y\) en deux multiplications et \(x^{15} = y^5 = (y^2)^2 \times y\) en trois multiplications en calculant \(x^6 = x^3 \times x^3\), \(x^{15} = x^6 \times x^6 \times x^3\). Au total, on aura ainsi effectué cinq multiplications.

La méthode qu'on vient d'utiliser est appelée la méthode du facteur :

  • si \(n\) est non premier et \(> 1\), on écrit \(n = p \times q\) avec \(p\) le plus petit facteur premier de \(n\). On a alors \(q > 1\). Pour calculer \(x^n\), on commence par calculer \(x^p = y\) puis \(y^q = (x^p)^q = x^{pq} = x^n\) par cette méthode.
  • si \(n\) est premier, on écrit \(x^n = x \times x^{n-1}\) et on applique la méthode à \(n-1\).
  • si \(n = 1\), on a directement \(x = x^1\).

Q06. Comparer les deux méthodes pour \(n = 55\) et \(n=33\). Que peut-on en conclure ?

Corrigé

Pour \(n = 55\) :

  • binaire : comme \(55 = \overline{110111}^2\), on calcule \(x^2\) qui place \(x^3 = x^2 \times x\) dans \(p\), \(x^4\) qui place \(x^7 = x^3 \times x^4\), \(x^8\), \(x^{16}\) qui place \(x^{23} = x^{16} \times x^7\) dans \(p\), \(x^{32}\) qui place \(x^{55} = x^{32} \times x^{23}\) dans \(p\). Au total, on a effectué \(5\) mises au carré et \(4\) mises à jour de \(p\), donc \(9\) multiplications. C'est bien \(\lceil \log_2 55 \rceil + \nu(55) - 2\) car on a omis les deux multiplications inutiles \(p = 1 \times x\) et la mise au carré finale.

    Si on reprend les puissances calculées on a donc \(x^2, x^3, x^4, x^7, x^8, x^{16}, x^{23}, x^{32}, x^{55}\), à chaque fois avec une multiplication.

  • facteur : comme \(55 = 5 \times 11\) on calcule \(x^5 = x \times x^4 = x \times (x \times x)^2\), on a donc calculé \(x^2, x^4, x^5\) avec 3 multiplications. Pour calculer \(x^{55} = (x^5)^{11} = a^{11}\) on écrit \(a^{11} = a \times a^{10}= a\times (a^2)^{5}\), donc une fois calculé \(a^2\), pour calculer \((a^2)^{5}\) on doit encore effectuer 3 multiplications. On a donc, en tout, \(3 + 2 + 3 = 8\) multiplications.

    Si on reprend les puissances calculées on a donc \(x^2, x^4, x^5, x^{10}, x^{20}, x^{40}, x^{50}, x^{55}\), à chaque fois avec une multiplication.

Pour \(n = 33\) :

  • binaire : comme \(33 = \overline{100001}^2\), on calcule \(x^2\), \(x^4\), \(x^8\), \(x^{16}\), \(x^{32}\), \(x^{33}\) et on a donc effectué 6 multiplications.
  • facteur : on a \(33 = 3 \times 11\) donc, en suivant le calcul précédent, on calcule \(x^2, x^3, x^6, x^{12}, x^{24}, x^{30}, x^{33}\) et on a donc effectué 7 multiplications.

Conclusion : aucune des méthodes n'est meilleure que l'autre.

Pour noter ces calculs de puissances, on peut considérer la suite finie des exposants utilisés. Ainsi, pour calculer \(x^{15}\) par la méthode binaire on obtient la chaine \((1, 2, 3, 4, 7, 8, 15)\) qui est de longueur 7. En effectuant la méthode du facteur, on obtient la chaine \((1,2,3,6,12,15)\) de longueur 6.

Q07. Donner, sans les justifier, les chaines correspondant aux deux méthodes pour 16, 27 et 125.

Corrigé
  • pour 16 : \((1, 2, 4, 8, 16)\) dans les deux cas.
  • pour 27 : \((1, 2, 3, 4, 8, 11, 16, 27)\) avec la méthode binaire et \((1, 2, 3, 6, 9, 18, 27)\) avec la méthode du facteur.
  • pour 125 : \((1, 2, 4, 5, 8, 13, 16, 29, 32, 61, 64, 125)\) avec la méthode binaire et \((1, 2, 4, 5, 10, 20, 25, 50, 100, 125)\) avec la méthode du facteur.

Définition

Une suite finie \((n_0,\dots,n_r)\) est appelée une chaine de calcul pour \(x^n\) si :

  • \(n_0 = 1\)
  • \(n_r = n\)
  • \(\forall k \in \range{1}{r}, \exists i,j \in \range{0}{k-1}, n_k = n_i + n_j\)

La dernière condition exprime le fait qu'on a pu calculer \(x^{n_k} = x^{n_i} \times x^{n_j}\).

Q08.

  1. Montrer par récurrence sur \(r\) que toute chaine \((n_0,\dots,n_r)\) de calcul pour \(x^n\) vérifie

    \[ \forall k \in \range{0}{r}, n_k \le 2^k \]

  2. En déduire que tout calcul de \(x^n\) effectue au moins \(\lceil \log_2 n \rceil\) multiplications.

  3. Donner une infinité de valeurs de \(n\) pour lesquelles ce minorant est atteint.
Corrigé

  1. On raisonne par récurrence sur \(r\).

    • Init : si \(r = 0\) la seule chaine est \((1)\) et on a bien \(1 \le 2^0\).
    • Her : si c'est vrai pour \(r-1 \geqslant 0\), soit \((n_0,\dots,n_r)\) une chaine de calcul ; on a \((n_0,\dots,n_{r-1})\) chaine de calcul donc \(\forall k \in \range{0}{r-1}, n_k \le 2^{k}\) et ainsi par hypothèse on a une décomposition \(n_r = n_i + n_j \le 2^i + 2^j \le 2 \times 2^{r-1} = 2^r\). Donc, on a bien l'hypothèse au rang \(r\).

    On a validé la récurrence.

  2. On remarque que toute chaine de longueur \(r+1\) effectue \(r\) multiplications. Comme \(n_r = n \le 2^r\) on a \(\log_2 n \le r\) et comme \(r\) est un entier \(\lceil \log_2 n \rceil \le r\).

  3. C'est atteint pour les \(2^r\) où on a une chaine \((1,2,4,\cdots,2^{r-1},2^r)\) qui effectue \(r = \log_2 (2^r)\) multiplications.

Breizhsort

Si t est un tableau et \(0 \le i \le j < |t|\) des indices, on notera t[i:j] le sous-tableau de t composé des valeurs entre les indices \(i\) et \(j\) inclus.

On va définir dans la suite du sujet une fonction

retourner : 'a array -> int -> int -> unit

telle que retourner t i j retourne le sous-tableau t[i:j].

Ainsi, si t = [| 1; 2; 3; 4; 5; 6 |] alors retourner t 2 4 change t en [| 1; 2; 5; 4; 3; 6 |] car t[2:4] = [| 3; 4; 5 |].

Q09. Quel est le contenu de t à l'issue du programme suivant ?

let t = [| 5; 8; 2; 0; 3; 6; 5; 2; 1 |];;
retourner t 1 7;;

Note : vous pouvez ignorer les ;; ils ne sont là que pour s'assurer qu'on puisse avoir cette interaction dans un toplevel OCaml.

Corrigé

[| 5; 2; 5; 6; 3; 0; 2; 8; 1 |]

On considère les fonctions suivantes :

let echanger t i j =
  let temp = t.(i) in
  t.(i) <- t.(j);
  t.(j) <- temp

let rec retourner t i j =
  if i < j
  then begin
    echanger t i j;
    retourner t (i+1) (j-1)
  end

Q10. Montrer que retourner termine.

Corrigé

On remarque que \(j - i\) est entière ; si elle est négative ou nulle on termine, sinon on effectue un appel tel que \((j-1)-(i+1) = j-i - 2 < j-i\) donc elle diminue strictement.

Ainsi, il ne peut y avoir qu'un nombre fini d'appels récursifs, la fonction termine.

Q11. Montrer que retourner correspond bien à la spécification de l'énoncé. On pourra montrer par récurrence sur \(j-i+1\) (le \(+1\) n'est là que pour déplacer l'initialisation au cas de base) que

\[ \forall k \in \range{i}{j}, \texttt{t.(k)} = \texttt{t'.(i+j-k)} \]

où t' est la valeur initiale de t.

Corrigé

On suit l'énoncé, par récurrence forte sur \(j-i+1\).

  • Init : pour \(j-i+1 \le 1\) on a \(j \le i\), donc soit \(\range{i}{j} = \emptyset\), soit \(i = j\) et la propriété \(\texttt{t.(i)} = \texttt{t'.(i)}\) est vérifiée car on ne fait rien.

  • Her : si la propriété est vérifiée pour toutes les valeurs de \(j-i+1\) inférieures ou égales à \(n\), avec \(n \ge 1\), on considère \(i,j\) tels que \(j-i+1 = n+1\), c'est-à-dire que \(j-i = n \ge 1\) et donc \(i < j\). On échange les valeurs aux indices \(i\) et \(j\), ce qui donne la propriété pour \(k = i\) et \(k = j\), puis on appelle retourner t (i+1) (j-1) avec \((j-1)-(i+1)+1 = n-1\) : par hypothèse, on a alors

    \[ \forall k \in \range{i+1}{j-1}, \texttt{t.(k)} = \texttt{t'.(i+1+j-1-k)} = \texttt{t'.(i+j-k)} \]

    (les cases d'indices \(i+1\) à \(j-1\) n'ayant pas été modifiées par l'échange). On a donc la propriété voulue.

On considère maintenant les fonctions suivantes :

let indice_max t k =
  let m = ref 0 in
  for i = 1 to k do
    if t.(!m) < t.(i)
    then m := i
  done;
  !m

let placer t k =
  let i = indice_max t k in
  if i <> k
  then begin
    retourner t 0 i;
    retourner t 0 k
  end

Q12. Montrer qu'en sortie de l'appel à placer t k le tableau t vérifie :

\[ \forall i \in \range{0}{k}, \texttt{t.(i)} \le \texttt{t.(k)} \]
Corrigé

  • On commence par montrer que la fonction indice_max fait ce qu'on attend d'elle. Pour cela, on considère la propriété

    \[ I(i,m) := \texttt{t.(m)} = \max_{0 \le j < i} \texttt{t.(j)} \]

    dont on montre facilement que c'est un invariant de boucle. En sortie, on a donc \(I(k+1,m) := \texttt{t.(m)} = \max_{0 \le j \le k} \texttt{t.(j)}\) donc \(m\) est bien l'indice d'un maximum de \(t\) entre les indices \(0\) et \(k\).

  • Pas de boucle ici, donc on va juste utiliser les propriétés précédentes. Si \(i = k\), c'est direct, t.(k) est le maximum.

    Sinon, c'est que le maximum est à l'indice \(i\). Suite au premier appel à retourner on place ce maximum à l'indice 0 et suite au second on le place à l'indice \(k\), ce qui permet ainsi d'assurer la propriété voulue.

On en déduit alors un algorithme de tri, dit tri du crêpier car il consiste à faire des retournements successifs comme une pile de crêpes.

let rumman t =
  for k = Array.length t - 1 downto 0 do
    placer t k
  done

Q13. Donner l'état du tableau à chaque itération dans l'appel à rumman t où t = [| 0; 5; 7; 1; 2 |].

Corrigé
  • [| 0; 5; 7; 1; 2 |]
  • \(k=4\) : \(\rightarrow\) [| 7; 5; 0; 1; 2 |] \(\rightarrow\) [| 2; 1; 0; 5; 7 |]
  • \(k=3\) : pas de changement
  • \(k=2\) : \(\rightarrow\) [| 2; 1; 0; 5; 7 |] \(\rightarrow\) [| 0; 1; 2; 5; 7 |]
  • \(k=1\) : pas de changement
  • \(k=0\) : pas de changement

Q14. En utilisant un invariant de boucle, montrer que la fonction rumman trie le tableau passé en argument dans l'ordre croissant.

Corrigé

On commence par remarquer que les seules modifications du tableau sont effectuées par retourner et que cette modification ne fait que permuter des éléments. Donc, à l'issue de rumman les valeurs ont juste été permutées.

On montre alors que la propriété suivante est un invariant de boucle :

\[ I(k) := t[k+1:n-1] \text{ est trié et } \forall i \in \range{0}{k}, \forall j \in \range{k+1}{n-1}, \texttt{t.(i)} \le \texttt{t.(j)} \]

où \(|t|=n\), en raisonnant sur l'indice comme auparavant : on le décrémente en fin d'itération.

Note : on aurait pu simplifier l'invariant en indiquant que t.(k+1) est plus grand que les valeurs précédentes, mais l'indice \(k+1\) est invalide au départ.

  • Init : au départ \(k = n-1\) et donc \(t[k+1:n-1] = \emptyset\) et la seconde partie de la propriété est triviale.
  • Her : si la propriété est vérifiée au début d'une itération, on sait que \(t[k+1:n-1]\) est trié et que suite à l'appel à placer t k on va avoir à l'indice \(k\) le maximum des valeurs aux indices de 0 à \(k\) qui sont elles-mêmes plus petites que t.(k+1) par hypothèse. Donc on a bien la propriété en fin d'itération.

En sortie de boucle, on a donc \(t\) trié.

Q15. Donner, en les justifiant, les complexités temporelles dans le pire des cas des fonctions retourner, placer, indice_max et rumman.

Corrigé
  • retourner t i j effectue des appels en enlevant \(2\) à \(j-i\) à chaque appel, on a donc \(O(j-i)\) appels, chacun en temps constant.
  • indice_max t k est directement en \(O(k)\) par la boucle.
  • placer est en (indice, retourne, retourne) \(O(k)+O(i)+O(k) = O(k)\) car \(i \le k\).
  • rumman est en \(\sum_{k=0}^{n-1} O(k) \le C \sum_{k=0}^{n-1} k = C \frac{n(n-1)}{2}\) donc en \(O(n^2)\).