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

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

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

Lire le cours de ce chapitre