#Slides Algorithmique 1
Fiches de révision, une par bloc du module:
- Complexité des algorithmes: définitions quantifiées de O, Ω, Θ; hiérarchie et ordres de grandeur pour n = 1000; Master Theorem et ses trois cas; coût amorti par potentiel (tableau dynamique).
- Algorithmes de tri: borne inférieure Ω(n log n) par arbre de décision; invariant et coûts de chaque tri (insertion, sélection, fusion, rapide, tas); stabilité et place; tris non comparatifs et leurs conditions.
- Stratégies fondamentales: critères d'emploi décisoires pour chaque paradigme: diviser pour régner (sous-problèmes indépendants), glouton (choix glouton prouvé par échange), programmation dynamique (chevauchements + sous-structure optimale).
- Complexité des problèmes: P, NP, NP-complet; certificats et vérificateurs; réductions polynomiales; parades pratiques devant un problème NP-complet (restriction, petite taille, approximation, heuristique, paramétrisation).
Systématique sur chaque fiche: l'invariant ou la récurrence, le coût au pire cas, et un exemple tracé à savoir refaire de mémoire.