formations:masters:ue:m1:alg7 [UFR Informatique]

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.

====== 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.

Outils pour utilisateurs

Outils du site

Outils de la page