Exercices : calcul de complexité

Quelques exercices non corrigés de calcul de complexité.

Polynômes

En complément de :

Le but de cette partie est d'estimer le nombre (en $\mathcal{O}$) de multiplications et d'additions du calcul d'une valeur d'un polynôme.

Problème algorithmique

  • NOM : valeur

  • ENTRÉES :

    • une liste de $n+1$ réels $[a_0, \dots, a_n]$ $n \geq 0$
    • un réel $x$
  • SORTIE : $\sum_{i=0}^na_i x^i$

Contraintes : on suppose que l'on ne possède pas de fonction puissance, uniquement la multiplication et l'addition.

Algorithme naïf

algorithme valeur_naif(P: []int, x: float) → float:
    ref v ← 0
    ref m int
    pour chaque i de [0 .. P.longueur[:
        m ← P[i]
        pour chaque _ de [0 .. i[:
            m ← m * x
        v ← v + m
    
    rendre v

Prouver que l'algorithme valeur_naif est une solution au problème algorithmique valeur.

Donnez, en utilisant la notation $\mathcal{O}$ avec comme paramètre la longueur du polynôme :

  • la complexité de l'algorithme valeur_naif
  • le nombre de multiplications utilisées par l'algorithme valeur_naif
  • le nombre d'additions utilisées par l'algorithme valeur_naif

Algorithme puissances itérées

algorithme valeur_itéré(P: []int, x: float) → float:
    ref v, xi ← P[0], x

    pour chaque i de [1 .. P.longueur[:
        v ← v + P[i] * xi
        xi ← xi * x
    
    rendre v

Prouver que l'algorithme valeur_itéré est une solution au problème algorithmique valeur.

Donnez, en utilisant la notation $\mathcal{O}$ avec comme paramètre la longueur du polynôme :

  • la complexité de l'algorithme valeur_itéré
  • le nombre de multiplications utilisées par l'algorithme valeur_itéré
  • le nombre d'additions utilisées par l'algorithme valeur_itéré

Algorithme de Horner

algorithme valeur_horner(P: []int, x: int) → int:
    ref i ← P.longueur - 1
    ref v ← P[i]
    tant que i > 0:
        v ← v * x
        i ← i - 1
        v ← v + P[i]
    
    rendre v

Prouver que l'algorithme valeur_horner est une solution au problème algorithmique valeur.

Donnez, en utilisant la notation $\mathcal{O}$ avec comme paramètre la longueur du polynôme :

  • la complexité de l'algorithme valeur_horner
  • le nombre de multiplications utilisées par l'algorithme valeur_horner
  • le nombre d'additions utilisées par l'algorithme valeur_horner

Triangle de Pascal

Formule du coefficient binomial dit du triangle de Pascal, avec $1\leq k \leq n$ :

$$ \binom{n}{k} = \binom{n-1}{k-1} \mathrel{+} \binom{n-1}{k} $$

et :

$$ \binom{n}{0} = \binom{n}{n} = 1 \text{ pour tout } n\geq 0 $$

Algorithme v1

algorithme binom(n: int, k: int) → int:
    si (n == k) ou (k == 0):
        rendre 1
    sinon:
        rendre binom(n-1, k-1) + binom(n - 1, k)

Démontrez que l'algorithme binom(n: int, k: int) → int calcule bien la binomiale.

Montrez que la complexité de l'algorithme binom est en $\Omega(\binom{n}{k})$.

Nous allons montrer que cette complexité est rédhibitoire pour la plupart des calculs.

Montrez que :

$$ \begin{array}{lcl} \binom{2n}{n} &\geq & 2\cdot\binom{2n-2}{n-1}\\ \end{array} $$

En déduire que :

$$ \begin{array}{lcl} \binom{2n}{n} & \geq & 2^{n}\\ \end{array} $$

Que pensez-vous de cette complexité ?

Algorithme v2

Montrez en utilisant l'équation de récursion que :

$$ \binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{n}{k} \cdot \binom{n-1}{k-1} $$

Utilisez le résultat précédent pour créer un algorithme récursif de complexité $\mathcal{O}(n)$ pour calculer $\binom{n}{k}$.

En utilisant le fait que $\binom{n}{k} = \binom{n}{n-k}$, donnez une borne exacte au nombre de récursions.

La division $\frac{n}{k}$ ne rendant pas forcément un entier, pourquoi ne peut-on pas vraiment utiliser directement la formule de récurrence en pratique ?

Modifier l'algorithme pour qu'il utilise tout le temps des entiers.

Vous pourrez remarquer que si $\frac{n}{k}$ n'est pas entier, une autre division l'est forcément.

Multiplication d'entiers

On supposera dans tout cet exercice que nos entiers sont positifs.

Multiplication naïve

algorithme mul(x: int, y: int) → int:
    ref r ← 0
    tant que x ≠ 0:
        x ← x - 1
        r ← r + y
    
    rendre r

Donnez la complexité de l'algorithme mul en fonction de x.

Démontrez que mul(x, y) = x * y.

Multiplication russe

Une petite variation (astucieuse) de l'algorithme naïf :

programme mul_russe(x: int, y: int) → int:
    ref r ← 0
    tant que x ≠ 0:
        si x est impair:
            x ← x - 1
            r ← r + y
        x ← x / 2
        y ← y * 2
    
    rendre r

Donnez la complexité de l'algorithme mul_russe en fonction de x.

Vous pourrez utiliser le fait que $x = \sum_{0\leq i \leq p} x_i 2^i$ avec $x_i \in \{0, 1\}$, et $p = \lfloor \log_2(x)\rfloor$

Démontrez que mul(x, y) = x * y.

Vous pourrez utiliser l'invariant : X * Y = r + x * y avec X et Y les paramètres initiaux.

Multiplication binaire

Dans le calcul de la complexité précédent on a considéré, comme toujours, que la multiplication de deux entiers est effectuée en une opération et que le stockage d'un entier ne prend qu'une case mémoire. En réalité nos entiers sont codés sous la forme de tableaux $T$ de bits (0 ou 1) tels que :

$$ x = \sum_{0\leq i < T.\mbox{\tiny longueur}}2^i\cdot T[i] $$
algorithme mul2(T: []bit):
    pour chaque i de [1 .. T.longueur - 1]:
        T[i] ← T[i-1]
    T[0] ← 0

Quelle est la complexité de l'algorithme mul2(T: []bit) ?

Montrez que l'algorithme mul2(T: []bit) multiplie par deux l'entier représenté par $T$ si $T[-1] = 0$.

Donnez un algorithme div2(T: []bit) ainsi que sa complexité permettant de diviser par deux en place (en modifiant le tableau) un entier représenté par $T$ si $T[0] = 0$.

Si les tableaux $T_x$ et $T_y$ représentant respectivement deux entiers x et y sont tels que $T_x[-1] = T_y[-1] = 1$, quelle est la taille du tableau représentant l'entier $x\cdot y$ ?

Modifiez l'algorithme mul(x: int, y: int) → int de la question 1 pour qu'il soit de signature : mul(Tx: []bit, Ty: []bit) → []bit

Donnez la complexité de ce nouvel algorithme par rapport à Tx.longueur et Ty.longueur.