Analyser boucles et récurrences
Passer d'un code à son coût par le calcul : nombre de tours de boucles dépendantes, récurrence d'un algorithme récursif, arbre de récursion, théorème maître et coût amorti.
- 26 cartes
- 4 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
Quelques cartes du deck
Récurrence de coût : de quoi s'agit-il ?
Voir la réponse
Équation qui exprime le coût d'un algorithme récursif sur une entrée de taille n à l'aide de son coût sur des entrées plus petites.
Le tri fusion donne T(n) = 2T(n/2) + n : deux appels sur la moitié, plus un travail linéaire pour fusionner. On la pose en lisant le code, puis on la résout.
Quelle récurrence décrit le coût de cette fonction ?
```python
def chercher(t, x, lo, hi):
if lo >= hi:
return -1
m = (lo + hi) // 2
if t[m] == x:
return m
if t[m] < x:
return chercher(t, x, m + 1, hi)
return chercher(t, x, lo, m)`T(n) = T(n/2) + 1T(n) = 2T(n/2) + 1T(n) = T(n - 1) + 1T(n) = T(n/2) + n
Voir la réponse
T(n) = T(n/2) + 1Un seul appel récursif est exécuté, sur la moitié des cases, avec un travail constant (un calcul de milieu et deux comparaisons). Les deux appels écrits dans le code ne s'exécutent jamais ensemble. Résultat : O(log n).
Dans T(n) = aT(n/b) + f(n), le théorème maître compare f(n) à …, le coût cumulé des … de l'arbre.
Voir la réponse
Dans T(n) = aT(n/b) + f(n), le théorème maître compare f(n) à n^(log_b a), le coût cumulé des feuilles de l'arbre.
L'arbre a log_b n niveaux et a^(log_b n) = n^(log_b a) feuilles. Pour 4T(n/2) + n, on compare n à n² : les feuilles dominent et T(n) = Θ(n²).
Diviser pour régner : de quoi s'agit-il ?
Voir la réponse
Méthode qui découpe un problème en sous-problèmes de même nature plus petits, les résout récursivement, puis combine leurs résultats.
Le coût vient de trois choses : le nombre de sous-problèmes a, leur taille n/b et le travail de découpe et de combinaison f(n). La récurrence T(n) = aT(n/b) + f(n) les rassemble.