Exercices : calcul de complexité

Cours/Algorithmie/Mesures de complexités/Exercices : calcul de complexité

Quelques exercices non corrigé de calculs de complexité.

Polynômes

En complément de :

Prérequis

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
    pour chaque i de [0 .. P.longueur[:
        ref m ← P[i]
        pour chaque i 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: []int, x: float) → float:
    ref v ← P[0]
    xi ← 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 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: []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_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: []int) → []int:

    ref T' ← []int{longueur: T.longueur}
    T' ← T[:]

    rendre T'


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


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


algorithme recherche(T: []int, k: int) → int:
    ref max_value ← T[maximum(T)]
    ref min ← 0

    ref T_copie ← copie(T)
    pour chaque i 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: 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écursion.

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.