Vous êtes ici

  1. Accueil
  2. UE ALGO : Algorithmique

UE ALGO : Algorithmique

UE ALGO : Algorithmique

En pratique :

Volume horaire de cours : 20
Volume horaire global de TD : 20
Langue principale : français
Nombre de crédits européens : 4

Description du contenu de l'enseignement

Ce cours a pour but d’apprendre aux étudiants à modéliser des situations diverses et complexes sous forme de graphes, ainsi qu’à concevoir et adapter des algorithmes pour résoudre les problèmes qui y sont liés.

  1. Généralités sur les graphes ; exemples, notions de base, représentation, structures de données associées.
  2. Analyse des algorithmes : notions de complexité (ordre de grandeur des fonctions), comportement du meilleur, du moyen et du pire cas.
  3. Parcours en profondeur et en largeur.
  4. Composantes fortement connexes.
  5. Le problème du plus court chemin (algorithme de Dijkstra , algorithme de Bellman-Ford, le problème du plus court chemin dans un DAG (graphe orienté acyclique)).
  6. Algorithmes gourmands pour l’arbre couvrant minimum (ACM) : algorithme de Prim et algorithme de Kruskal.
  7. Le problème du flot maximum (algorithme de Ford-Fulkerson).
  8. Programmation linéaire appliquée aux problèmes des graphes.

Compétences à acquérir

À l’issue du cours, les étudiants seront en mesure de :

  • Modéliser une situation donnée sous forme de graphe.
  • Identifier en fonction du problème posé un type d’algorithme qui y répond (le chemin le plus court, le chemin le plus long, composantes fortement connexes, arbre couvrant minimum, flot maximum).
  • Manipuler la structure de données graphe.
  • Concevoir ou adapter des algorithmes efficaces selon leur besoin (écriture et lecture du pseudo code).
  • Evaluer la complexité d’un algorithme afin de l’améliorer ou de le comparer à d’autres.
  • Modéliser sous la forme d’un programme linéaire des problèmes d’optimisation simples.

Modalités d’organisation et de suivi

4h de présentiel par semaine, 2h de travail maison (compréhension du cours, préparation d’exercices fournis à l’avance).

 


Bibliographie, lectures recommandées

  • Algorithms, S. Dasgupta, C. H. Papadimitriou, et U. V. Vazirani, McGraw-Hill 2006
     
  • Graphes et algorithmes, Michel Gondran et Michel Minoux, Eyrolles, 1995

 


Pré-requis

Pré-requis obligatoires

Des notions fondamentales de mathématiques discrètes (ensembles, relations, inductions) et avoir suivi une UE d’initiation algorithmique et une UE de programmation impérative.