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)
Compétences à acquérir
Évaluer la complexité et la correction d’une solution algorithmique (15%).
Mettre en œuvre des algorithmes et des structures de données (15%).
Choisir, sur des critères objectifs, les structures de données et construire ou sélectionner les algorithmes les mieux adaptés à un problème donné (20%).
Concevoir un algorithme en utilisant des stratégies algorithmiques adaptées aux problèmes (20%).
Modéliser un problème concret sous la forme d'un problème algorithmique connu (15%).
Faire preuve d'esprit critique vis-à-vis d'une solution technique pour en vérifier son efficacité, sa fiabilité et sa robustesse dans son contexte d'utilisation (15%).