Cet enseignement prolonge celui d'Algorithmique 1, en accentuant les aspects de conception des algorithmes à partir de techniques générales.
- Parcours de graphes, propriétés des parcours de graphes
- Application des parcours de graphes (notamment tri topologique, composantes fortement connexes)
- Flots maximum dans un graphe, coupe minimum, algorithme de chemins augmentants
- Flots de coût minimum
- Programmation dynamique, principes et exemples (alignement de séquences, distance d'édition, plus court chemin dans un graphe acyclique,…)
- Diviser-pour-régner, utilisation du master theorem pour le calcul de complexité (on ne démontre pas le théorème)
- Algorithmes gloutons et algorithmes d'approximation. On montrera des algorithmes gloutons optimaux, non-optimaux, et des algorithmes gloutons trouvant des solutions à ratio d'approximation constant
- Algorithmes randomisés (sélection, quicksort, collectionneur de vignettes)
- Recherche de motifs
- Analyse amortie (exemples : itérateur sur un arbre, incrément binaire, algorithme de Knuth-Morris-Pratt)
- Géométrie algorithmique (algorithmes par balayage, algorithmes incrémentaux)