Skip to content

Séquence 2

L'objectif de la séquence est d'introduire la notion de complexité et de preuve associées à un algorithme. On poura lire les chapitres 2 et 3 de l'ouvrage

Algorithmique par Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein Dunod 3ième édition 2010 lien des versions plus anciennes sont accessibles partiellement sur internet.

Question 1

Dans l'algorithme du calcul de \(x^n\) avec la méthode diviser pour régner récursif, la fonction puissance_DR (x,n) prend en entrée un élément x (dont la taille est fixe).

  1. La taille du second paramètre n en entrée est \(\log_2n\), \(n\), \(n^2\) ou \(2^n\)
  2. La taille de l'espace mémoire necessaire pour effectuer puissance_DR (x,n) est \(\mathcal{O}(taille(x))\), \(\mathcal{O}(taille(x).\log_2(n))\), \(\mathcal{O}(taille(x).\log_2(n))\), \(\mathcal{O}(taille(x).n)\), \(\mathcal{O}(taille(x).2^n)\), ou cela dépend.

réponses (éléments)

  1. \(n\) est un nombre entier donc codé sur \(int(\log_2 n) +1\) bits (avec \(int(x)\) la partie entière de \(x\)). Donc il faut faire attention à l'usage des noms de variable et la notation \(n\) utilisée ici peut être source d'erreur.
  2. La taille de l'espace mémoire utilisée dépend de l'opérateur de multiplication utilisé. Si on multiplie des entiers, à chaque itération on double la taille de variable dans l'accumulateur p. Donc la taille nécessaire sera \(\mathcal{O}(taille(x).n)\). Si par contre on fait des opérations de multiplication modulo \(m\) (comme c'est le cas dans l'algorithme RSA), on a besoin d'un espace mémoire ne dépendant pas de \(n\) donc de l'ordre de \(\mathcal{O}(taille(x))\)

Question 2

Calculer le nombre d'opérations effectuées pour calculer \(x^1\), \(x^2\), \(x^3\), jusqu'à \(x^{10}\). Écrire la représentation binaire des entiers de \(1\) à \(10\)

On note \(B(n)\) le nombre de bits de la représentation binaire du nombre \(n\) et \(H(n)\) le nombre de '1' dans la représentation binaire de \(n\) (poids binaire de Hamming).

Le nombre d'opérations de multiplications effectuées par l'algorithme de calcul de \(x^n\) est (pour \(n>0\))

  1. \(B(n)\)
  2. \(H(n)\)
  3. \(B(n) + H(n)\)
  4. \(B(n)+H(n)-1\)
  5. \(B(n)+H(n)-2\)

réponses (éléments)

n Binaire B(n) H(n) C(n)
0 0 1 0 0
1 1 1 1 0
2 10 2 1 1
3 11 2 2 2
4 100 3 1 2
5 101 3 2 3
6 110 3 2 3
7 111 3 3 4
8 1000 4 1 3
9 1001 4 2 4
10 1010 4 2 4

La bonne réponse est la 5, on peut faire la preuve par récurrence à partir de l'algorithme.

Question 3

On peut parler de réduction de complexité entre un algorithme A1 et A2, lorsque la complexité passe de

  1. \(O(n)\) pour A1 à \(O(\log(n))\) pour A2
  2. \(O(5n)\) pour A1 à \(O(n/2)\) pour A2
  3. \(O(2^n)\) pour A1 à \(O(n^n)\) pour A2
  4. \(O(log(n))\) pour A1 à \(O(\sqrt{n})\) pour A2
  5. \(O(n.\sqrt{n})\) pour A1 à \(O(n.\log(n))\) pour A2

réponses (éléments)

  1. Vrai. car \(\log(n)\) devient négligeable devant \(n\) pour \(n\) grand
  2. Faux. Les ordres de grandeur sont les mêmes, on a du \(O(\log(n))\), le coût peut être réduit mais la croissance reste du même ordre
  3. Faux. \(n^n\) croit beaucoup plus rapidement que \(2^n\)
  4. Faux. \(\sqrt{n}\) croit beaucoup plus rapidement que \(\log(n)\)

Question 4

On considère l'algorithme suivant

mystère(n:entier)
  ploum = Faux
  i = 1
  tant que i < n-1 et not ploum
    i = i + 1
    ploum = (i divise n)
  renvoyer ploum

Une spécification correcte de la fonction mystère pourrait être

  1. mystère(n) renvoie ploum
  2. mystère(n) renvoie la valeur de ploum
  3. mystère(n) renvoie Faux si la valeur de n est un nombre premier (c'est à dire si la valeur de n n'est divisible que par 1 et elle-même)
  4. mystère(n) renvoie Vrai si la valeur de n est un nombre composé
  5. aucune de ces spécifications ne convient

réponses (éléments)

  1. Faux. ploumest un nom de variable et pas une valeur de retour (ici un booléen)
  2. Faux. ploumest une variable interne à l'algorithme et il n'y a pas de lien entre la valeur de ploum et la valeur de n, une spécification définit le lien entre la valeur des paramètres d'entrée et la valeur de retour de la fonction.
  3. Faux. Une fonction qui répondrait toujours Faux vérifierait cette spécification, et ne correspondrait pas à ce que fait l'algorithme
  4. Faux. pour les mêmes raisons que la question précédente
  5. Vrai. Il faudrait combiner les 2 dernières affirmations: d'abord la fonction mystère prend en argument un entier positif plus grad que 2 (pour éviter de dire si 1 est premier ou pas), ensuite la valeur de retour est Vrai si et seulement si la valeur de n est un nombre est composé. Ce qui est équivalent à la valeur de retour est Faux si et seulement si la valeur de n est un nombre premier.

Question 5

Pour prouver la correction de l'algorithme ci-dessus on utilise un/des invariant(s) pour la boucle tant que. Cet invariant doit permettre de démontrer que l'algorithme répond bien à la spécification (cf. réponse 5 de la question précédente).

I1: La valeur de i est un entier

I2: La valeur de i est un entier compris entre 1 et la valeur de n -1

I3: Si la valeur de ploum est Vrai, alors la valeur de i divise la valeur de n.

I4: Si la valeur de ploum est Faux alors pour entier k > 1 et k inférieur ou égal à la valeur de i k ne divise pas la valeur de n

  1. I1 est-il un invariant ?
  2. I2 est-il un invariant ?
  3. I3 est-il un invariant ?
  4. I4 est-il un invariant ?
  5. Parmis les invariants éventuels I1, I2, I3, I4 lesquels sont suffisants pour garantir la corrextion.

réponses (éléments)

  1. Vrai. I1 est un invariant, vrai lors de l'entrée dans la boucle et vrai en fin de bloc du tant que, en tant que tel il n'offre que peu d'intérêt si ce n'est de savoir la nature des variables utilisées).
  2. Vrai. I2 est également un invariant il permet en plus d'avoir une garantie sur la valeur de i qui ne peut atteindre la valeur de n
  3. Vrai. c'est un invariant, si la valeur de ploumest Faux et invariant est vérifié, il est donc toujours vrai en entrée de l'itération. Il est également vrai en fin de bloc car soit i ne divise pas n et donc plouma la valeur Faux, soit i divise n et plouma la valeur Vrai(on ne rentrera plus dans la boucle
  4. Vrai. On accumule les résultats précédents, le fait d'itérer jusqu'à i donne une information sur toutes les valeurs déjà testées
  5. Aucun des invariants proposés n'est suffisant en lui-même, il faut les combiner pour obtenir un invariant suffisant. Un tel invariant pourrait être : (ploum est Faux et pout tout k, 1 < k <=i, k ne divise pas n) ou (ploum est Vrai et i divise n et 1 < i < n)