TD — Séance 2 — Analyse algorithmique

Compter, borner, mesurer : le coût d’un algorithme

TD de la séance 2 de Structures de données et algorithmes avancés : compter, borner, mesurer : le coût d’un algorithme.
Auteur

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

ImportantObjectif

Appliquer à la main, sur des fragments et des données nouvelles, les outils de la séance : compter les opérations d’un fragment, compter les tours d’une boucle, prouver une borne asymptotique, classer des fonctions par leur croissance, dérouler une recherche dichotomique, résoudre une récurrence et interpréter des durées mesurées. Chaque réponse se donne sous la forme demandée (tableau, valeur, inégalité, classe) et se justifie en une ou deux phrases.

Conventions. Les opérations se comptent comme dans le cours : une affectation, une comparaison ou un accès t[i] vaut 1 ; s = s + i, i++, i += 2 et c = c + 1 valent 2 (une addition, une affectation) ; le test d’une boucle est évalué une fois de plus que la boucle ne fait de tours. La déclaration de \(n\) et l’affichage restent hors du compte. log2 désigne le logarithme en base 2, et \(\lceil x\rceil\) le plus petit entier supérieur ou égal à \(x\). La recherche dichotomique est celle du cours, écrite ici avec une boucle : tant que \(lo\leq hi\), elle examine la case \(mid=lo+(hi-lo)/2\) (division entière), rend \(mid\) si t[mid] \(=x\), continue sur \([mid+1, hi]\) si t[mid] \(<x\), sur \([lo, mid-1]\) sinon, et rend \(-1\) quand \(lo>hi\).

Exercice 1 : compter deux fragments

Fragment A

int s = 0;
for (int i = 0; i < n; i += 2) {
    s = s + i;
}

Fragment B

int c = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        c = c + 1;
    }
}

  1. Pour le fragment A, remplir le tableau pour \(n=6\) et \(n=7\), puis donner \(f(n)\) pour \(n\) pair et pour \(n\) impair, et sa classe \(\Theta\).

    instruction exécutions, \(n=6\) opérations, \(n=6\) exécutions, \(n=7\) opérations, \(n=7\)
    s = 0
    i = 0
    i < n
    s = s + i
    i += 2
    total

  2. Pour le fragment B, donner le nombre d’exécutions de chaque instruction en fonction de \(n\), puis \(f(n)\) et sa classe \(\Theta\) ; vérifier pour \(n=6\) en complétant le tableau.

    c = 0 i = 0 i < n i++ j = 0 j < i c = c + 1 j++ total
    exécutions
    opér., \(n=6\)

  3. Que vaut la variable c à la fin du fragment B pour \(n=6\) ? Par combien \(f\) est-elle multipliée quand \(n\) passe de 1 000 à 2 000 ? Comparer à \(2^2\).

Exercice 2 : compter les tours

Pour chaque fragment, donner le nombre de tours du corps (le nombre d’exécutions de t++) pour les valeurs de \(n\) indiquées, puis la classe \(\Theta\) de ce nombre en fonction de \(n\).

fragment tours classe
(a) for (int i = 1; i < n; i = i * 2) t++; \(n=64\) :  \(n=100\) :  \(n=1\,000\) :
(b) for (int i = 1; i * i <= n; i++) t++; \(n=50\) : \(n=1\,000\) :
(c) for (int i = 0; i < n; i++) \(n=16\) : \(n=20\) :
for (int j = 1; j < n; j = j * 2) t++;
(d) trois boucles imbriquées i, j, k, chacune de 0 à \(n-1\) \(n=10\) :
(e) deux boucles successives, chacune de 0 à \(n-1\) \(n=10\) :

Pour (a), écrire les valeurs successives de i pour \(n=100\). Pour (c), comparer la classe obtenue à \(\Theta(n)\) et à \(\Theta(n^2)\).

Exercice 3 : prouver une borne

Soit \(f(n)=4n^2+30n+70\).

  1. Montrer que \(f(n)\in\mathcal{O}(n^2)\) avec \(n_0=1\), en exhibant une constante \(c\) et en rédigeant l’inégalité.

  2. Pour \(c=6\) puis \(c=5\), déterminer le plus petit \(n_0\) tel que \(f(n)\leq c\,n^2\) pour tout \(n\geq n_0\) ; vérifier l’inégalité en \(n_0-1\) et en \(n_0\).

    \(c\) plus petit \(n_0\) \(f(n_0-1)\) \(c\,(n_0-1)^2\) \(f(n_0)\) \(c\,n_0^2\)
    6
    5

  3. Existe-t-il un \(n_0\) pour \(c=4\) ? Montrer que \(f(n)\in\Omega(n^2)\), puis conclure sur \(\Theta\).

  4. Montrer par l’absurde que \(n^3\notin\mathcal{O}(n^2)\).

Exercice 4 : classer des fonctions

  1. Ranger les neuf fonctions suivantes de la plus lente à la plus rapide en croissance (pour \(n\) grand) : \[n\log_2 n, 1\,000, n^2/10, \sqrt n, 2^n, 3n+100, n!, \log_2 n, n^{1{,}5}.\]

  2. À partir de quelle valeur de \(n\) la fonction \(n^2/10\) devient-elle strictement supérieure à \(3n+100\) ? Que vaut chacune des deux en \(n=50\) ?

  3. Le plus petit \(n_0\) tel que \(2^n>n^3\) pour tout \(n\geq n_0\) ? Donner \(2^n\) et \(n^3\) en \(n_0-1\) et en \(n_0\). L’inégalité est-elle vraie en \(n=1\) ? Ce résultat change-t-il la réponse ?

  4. Vrai ou faux ? Justifier chaque réponse en une ligne.

    affirmation V / F justification
    1 \(3^n\in\mathcal{O}(2^n)\)
    2 \(\log_2 n\in\Theta(\log_{10} n)\)
    3 \(n^2+1\,000n\in\Omega(n^3)\)
    4 un algorithme en \(\Theta(n^2)\) est plus lent qu’un algorithme en \(\Theta(n)\), pour tout \(n\)

Exercice 5 : la dichotomie sur quinze valeurs

Le tableau trié t contient 15 valeurs, aux indices 0 à 14 :

indice 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
t 11 17 24 29 35 42 48 53 61 66 72 79 85 90 97

  1. Dérouler la dichotomie pour \(x=66\), puis pour \(x=40\) : une ligne par tour de boucle, et une dernière ligne pour le test final quand \(x\) est absent.

    \(x\) \(lo\) \(hi\) \(mid\) t[mid] décision
    66
    40

  2. Combien de cases chaque recherche examine-t-elle ? Combien en examinerait la recherche séquentielle pour les mêmes valeurs ?

  3. Pour chacune des 15 valeurs présentes, combien de cases la dichotomie examine-t-elle ? Donner le nombre de valeurs trouvées en 1, 2, 3 et 4 cases, et en déduire le coût moyen d’une recherche réussie, en supposant chaque valeur cherchée avec la même probabilité.

  4. Combien de cases la dichotomie examine-t-elle au plus pour \(n=15\) ? pour \(n=16\) ? Donner la formule générale.

  5. Ajouter la valeur 50 au tableau en le gardant trié : combien d’éléments faut-il décaler ? Quel est le coût d’une insertion au pire cas, en fonction de \(n\) ?

Exercice 6 : récurrences

  1. Pour chaque récurrence, donner \(a\), \(b\), \(\alpha=\log_b a\), le cas du théorème maître qui s’applique (en vérifiant la condition de régularité pour le cas 3), et la classe de \(T(n)\) ; écrire « hors du théorème » si aucun cas ne s’applique, et résoudre alors la récurrence en la déroulant.

    récurrence \(a\) \(b\) \(\alpha\) cas \(T(n)\)
    1 \(T(n)=8T(n/2)+\Theta(n^2)\)
    2 \(T(n)=T(n/2)+\Theta(n)\)
    3 \(T(n)=2T(n/4)+\Theta(\sqrt n)\)
    4 \(T(n)=3T(n/4)+\Theta(n^2)\)
    5 \(T(n)=T(n-1)+\Theta(1)\)

  2. Pour \(T(n)=3T(n/2)+n\) et \(T(1)=1\), avec \(n=16\), remplir le tableau des coûts par niveau de l’arbre des appels, puis vérifier le total en calculant \(T(16)\) par la récurrence.

    niveau \(j\) 0 1 2 3 4 total
    nombre d’appels
    taille de chaque appel
    coût du niveau

    Quel niveau coûte le plus ? Quel cas du théorème maître cela illustre-t-il ? Par combien \(T\) devrait-il être multiplié quand \(n\) double, pour \(n\) grand ?

Exercice 7 : lire une expérience de doublement

Deux méthodes Java ont été chronométrées sur la machine du cours (médiane de 5 exécutions, après chauffe), sur des tableaux d’entiers tirés au hasard. La méthode A compte les triplets d’indices \(i<j<k\) dont les valeurs ont une somme nulle, par trois boucles imbriquées ; la méthode B trie une copie du tableau (Arrays.sort(a.clone()) : la copie est comprise dans la durée).

méthode A (triplets) méthode B (Arrays.sort)
\(n\) \(T(n)\), ms \(n\) \(T(n)\), ms
250 0,67 250 000 17,97
500 4,90 500 000 32,40
1 000 45,06 1 000 000 77,22
2 000 341,22 2 000 000 166,15
4 000 000 366,55
  1. Calculer chaque rapport \(T(2n)/T(n)\) et son logarithme en base 2.
  2. En déduire l’exposant \(b\) du modèle \(T(n)\approx a\,n^b\) pour chaque méthode. Le nombre de triplets examinés par A vaut \(\binom{n}{3}=n(n-1)(n-2)/6\) : l’exposant mesuré est-il compatible ?
  3. Les rapports de B sont voisins de 2. Calculer \(\dfrac{2n\log_2(2n)}{n\log_2 n}\) pour \(n=10^6\). Ces mesures permettent-elles de distinguer un coût en \(n\) d’un coût en \(n\log n\) ?
  4. Prévoir la durée de A pour \(n=4\,000\) et celle de B pour \(n=8\,000\,000\). Quelle taille \(n\) la méthode A peut-elle traiter en une minute, d’après le modèle ?
  5. Pourquoi une durée de moins d’une milliseconde (première ligne de A) donne-t-elle un rapport peu fiable ? Le rapport de A le plus éloigné de 8 est-il celui-là ? Citer deux autres causes d’écart entre un rapport mesuré et \(2^b\).

Pour cette séance

Le cours

Les slides

À lire en ligne

À télécharger

Retour au sommet