Ce cours a pour objectif d'étudier les grandes familles d'algorithmes: backtracking, diviser pour régner, programmation dynamique et algorithmes gloutons.
Dans chaque cas, on étudiera plusieurs exemples classiques, on s'intéressera aux preuves de correction et à l'analyse de complexité.
En fin de semestre, on s'intéressera à la complexité amortie.
Une bonne maitrise de l'algorithmique est requise: algorithmes de tri, arbres binaires de recherche, algorithmes dans les graphes… Notions de complexité dans le pire cas (notations O, Theta) et en moyenne.
Dans la Licence de l'UFR, cela correspond aux cours Éléments d'algorithmique 1 (S3), Éléments d'algorithmique 2 (S4), et Algorithmique (S5).
Une bonne pratique de la programmation est indispensable pour ce cours.