Algorithmes et applications dans les graphes

Crédit : 4 ECTS

Volume horaire

• CM : 36 h
• Volume horaire global (hors stage) : 36 h

Compétences à acquérir

Fournir les concepts de base concernant les graphes. Souligner l’apport des graphes en informatique en tant qu’outil de modélisation. Présenter certains algorithmes fondamentaux et techniques de preuves. Programmation de ces algorithmes.

Description du contenu de l'enseignement

Introduction à la théorie des graphes. Étude et résolution des problèmes suivants : Connexité dans un graphe (BFS, DFS), connexité forte, fermeture transitive. Plus court chemin (algorithmes de Bellman, de Dijkstra, de Ford et de Floyd). Arbre couvrant de poids minimum (algorithmes de Prim et de Kruskal) Flot maximum (algorithme de Ford et Fulkerson). Programmation de ces algorithmes en Python (lorsque le graphe est situé sur un serveur distant, pour résoudre graphiquement un labyrinthe...). Potentiellement lecture d'article scientifique et recherche d'algorithme en projet.

Pré-requis obligatoires

Bases de l'algorithmique et de maths discrètes : notion de complexité, structures de données (tables de hachage, tas binaire...), preuves par recurrence et contradiction...

Bibliographie, lectures recommandées

Introduction to algorithms / Cormen et al. Algorithms / Jeff Erickson (chapitres 5 à 11) Graphes et algorithmes / Gondran Minoux

Enseignant responsable

FLORIAN SIKORA