Exercices : calcul de complexité

Cours/Algorithmie/Exercices : calcul de complexité

Quelques exercices non corrigé de calculs 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: [entier], x: réel) → réel:
    (v := réel) ← 0
    pour chaque (i := entier) de [0 .. P.longueur[:
        m := P[i]
        pour chaque (i := entier) 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 multiplication utilisée par l'algorithme valeur_naif
le nombre d'additions utilisée par l'algorithme valeur_naif

Algorithme puissances itérées

algorithme valeur_itéré(P: [entier], x: réel) → réel:
    (v := réel) ← P[0]
    xi ← x
    pour chaque (i := entier) 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 multiplication utilisée par l'algorithme valeur_itéré
le nombre d'additions utilisée par l'algorithme valeur_itéré

Algorithme de Horner

Méthode de Horner

algorithme valeur_horner(P: [entier], x: entier) → entier:
    i := P.longueur -1
    (v := réel) ← P[i]
    tant que i > 0:
        v ← v * x
        i ← i - 1
        v ← v + P[i]
    
    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 multiplication utilisée par l'algorithme valeur_itéré
le nombre d'additions utilisée par l'algorithme valeur_itéré

$k$-ème plus petit élément

On considère le pseudo-code suivant :

fonction copie(T: [entier]) → [entier]:

    T' := [entier]{longueur: T.longueur}
    T' ← T[:]

    rendre T'


fonction maximum(T: [entier]) → entier:
    m := 0
    pour chaque (i := entier) de [0 .. T.longueur[:
        if T[m] < T[i]:
            m ← i
    rendre m


fonction minimum(T):
    m := 0
    pour chaque (i := entier) de [0 .. T.longueur[:
        if T[m] > T[i]:
            m ← i
    rendre m


algorithme recherche(T: [entier], k: entier) → entier:
    max_value := T[maximum(T)]
    min := 0

    T_copie := copie(T)
    pour chaque (i := entier) de [0 .. k - 1[:
        min ← minimum(T_copie)
        T_copie[min] := max_value + 1

    rendre minimum(T_copie)

1

Donnez la complexité de l'algorithme recherche(T, k)

Pour calculer la complexité de l'algorithme, il vous faudra également calculer les complexités des fonctions utilisées par celui-ci.

2

Quel est l'intérêt de la fonction copie(T) ?

3

Démontrez que l'algorithme recherche(T, k) rend l'indice du $k$ème plus petit élément de $T$.

Pour démontrer ce que fait recherche, il vous faudra également trouver et démontrer ce que font les fonctions utilisées par celui-ci.

4

Utilisez recherche(T, k) pour créer un algorithme déterminant l'indice de la médiane d'un tableau. Quelle est sa complexité ?

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: entier, k: entier) → entier:
    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: entier, k: entier) → entier 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} \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écursion.

En examinant la signature de cet algorithme, pourquoi ne peut-on pas vraiment l'utiliser en pratique ?