Exercices corrigés — Algorithmes, programmes et complexité (informatique (MP2I/MPI))

15 exercices avec corrigé rédigé, du plus simple au plus exigeant.

• Algorithme, ou programme ?
• Six boucles, six ordres de grandeur
• Une boucle sans variant connu
• L'exponentiation rapide, prouvée et comptée
• Le milieu qui déborde
• Trois divergences flottantes
• Pire cas, cas moyen, coût amorti
• Trois Fibonacci, trois complexités
• Un $\Theta (n^2)$ qui bat un $\Theta (n\log n)$
• La taille d'une entrée n'est pas sa valeur
• Probleme – Le tri par sélection, prouvé et compté
• Probleme – La dichotomie, jusqu'au nombre exact de tours
• Probleme – Le compteur binaire, et son coût amorti
• Probleme – Sommer un million de termes, et l'ordre qui change tout
• Probleme – De $\Theta (n^2)$ à $\Theta (n)$, et la mesure qui le confirme

Lire le cours de ce chapitre