====== Algorithmique (M1, semestre 1) ======


===== Description =====


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.


===== Syllabus =====
==== Sujets centraux ====


  - Backtracking 
  - Diviser pour régner
      * Master theorem
  - Programmation dynamique
  - Algorithmes gloutons


==== Sujets potentiellement traités ====

  - Complexité amortie

===== Pré-requis =====

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 [[..:..:..:licence:2024-2025:ue:l2:ea3|Éléments d'algorithmique 1 (S3)]],
Éléments d'algorithmique 2 (S4), et
 [[..:..:..:licence:2024-2025:ue:l3:al5|Algorithmique (S5)]]. 

Une bonne pratique de la programmation est indispensable pour ce cours.