Algorithmique de graphes
HLIN 501 (L3 Informatique, L3 Maths-Info) - Année 2017-2018
Contenu du cours
15h Cours, 18h TD, 16h30 TP
- Chap.1 : Définitions de base : graphe, connexité, calcul des composantes connexes.
- Chap.2 : Arbres couvrants : définition, propriétés, arbres couvrants de poids minimum.
- Chap.3 : Parcours: définitions, parcours en largeur, arbre des plus courts chemins, parcours en profondeur.
- Chap.4 : Graphes orientés : définitions, graphes acycliques.
- Chap.5 : Plus courts chemins : retour sur le chapitre 3, plus courts chemins pour toutes paires de sommets.
Calendrier
Les cours ont lieu le mardi de 8h00 à 9h30 en amphi 5.05. Début des cours: le mardi 12 septembre 2017. Les tp ont lieu le mardi de 9h45 à 11h15 au bâtiment 6 (sauf les Math-Infos qui ont tp le vendredi matin 9h45-11h15), et les td à la suite, le mardi de 11h30 à 13h00, voir le planning de la FDS. Début des TD/TP: le mardi 19 septembre 2017.
- Groupe A : encadrant : M. Montassier, TD salle : TD 16.06
- Groupe B + Maths-Info: encadrant : S. Bessy, TD salle : TD 5.19
- Groupe C : encadrant : J. Thiebaut, TD salle : TD 1.06
- Math-Infos : en TD avec le groupe B, encadrant de TP : Lucas Isenmann
Tps au bâtiment 6, voir planning sur le site du SIF.
Modalités de contrôle des connaissances
L'évaluation comportera un examen final et un contrôle continu. Les épreuves écrites se feront sans document.
Le contrôle continu se déroulera en deux parties :
- Une partie examen sur feuille, de type exercices de TD, d'une durée de 1 heure, sur un créneau de cours, vraisemblablement le mardi 28 novembre.
- Une partie TP où, entre autre, vous présenterez le travail réalisé en TP le long du semestre, d'une durée de 1 heure 30, sur un créneau de TD et un de TP, vraisemblablement le mardi 12 décembre.
La note finale sera max{ Exam ; 2/3 Exam + 1/3 CC}.
Notes de cours
Exemples d'examens : première session 2016, seconde session 2016.
Cours, TD et TP
Semainier (objectifs de chaque semaine (cours, td, tp))
Fiche TD 1 - Fiche TP 1, code associé Fiche TD 2 - Fiche TP 2, code associé Fiche TD 3 - Fiche TP 3, code associé Fiche TD 4 - Fiche TP 4, code associé Fiche TD 5 - Fiche TP 5, tp5.cc, villes.cc
Codes complémentaires : Matrice.cc, Affichage.cc
(petite) Bibliographie
- Cormen, Leiserson, Rivest et Stein : Introduction à l'algorithmique (Dunod): 'le' bouquin d'algo, très clair et en français, de nombreux exemplaires sont disponibles à la BU.
- Bondy Murty: Graph Theory: un super bouquin de graphes, un exemplaire en français est disponible ici.