Algorithmique — l’essentiel du chapitre
3 leçons, ce qu’il faut en retenir, et un test pour vérifier.
1 La complexité : compter les opérations, pas les secondes
Mesurer un algorithme au chronomètre revient à mesurer une machine, un jour donné, sur un jeu d'essai donné. Changez de machine, la mesure change.
- La complexité compte les opérations selon la taille n, pas les secondes sur une machine
- On garde l'ordre de grandeur : le terme dominant, sans ses constantes
- Deux boucles imbriquées sur les mêmes données donnent du n au carré
- Une complexité exponentielle est condamnée dès quelques dizaines de données
2 La récursivité : un algorithme qui s'appelle lui-même
Un algorithme RÉCURSIF résout un problème en s'appelant lui-même sur un problème PLUS PETIT.
- Un algorithme récursif s'appelle sur un problème strictement plus petit
- Il lui faut un cas de base, sinon la descente ne s'arrête jamais
- La descente empile les appels, la remontée calcule les résultats en sens inverse
- La récursivité s'impose sur les structures récursives, pas partout : elle peut coûter très cher
3 Pourquoi une boucle s'arrête et pourquoi elle est juste
Essayer un programme sur quelques cas ne prouve rien : les essais montrent la présence de bogues, jamais leur absence.
- Terminaison et correction sont deux questions distinctes, à prouver séparément
- Le variant est un entier positif qui décroît strictement : il force l'arrêt
- L'invariant est vrai avant la boucle et conservé par chaque tour, donc vrai à la sortie
- Invariant plus condition de sortie donnent le résultat, pour toute donnée et sans essai
Je me teste
Un algorithme en O(n²) traite 1 000 éléments en 1 seconde. Et 10 000 ? (La complexité : compter les opérations, pas les…)
- Environ 1 seconde
- Environ 100 secondes
- Environ 10 secondes
Que manque-t-il à « factorielle(n) vaut n fois factorielle(n moins 1) » ? (La récursivité : un algorithme qui s'appelle lu…)
- Un compteur pour les tours de boucle
- Le cas de base pour arrêter la descente
- Une variable pour stocker le total
Que doit être un variant de boucle ? (Pourquoi une boucle s'arrête et pourquoi elle e…)
- Une propriété vraie à chaque tour
- Un entier positif qui décroît strictement
- Une variable qui compte les tours
Réponses : 1. B · 2. B · 3. B