---

Algorithmique de graphes.

L3 Informatique, L3 Maths-Info.

HLIN 501

---

   Actualités:

• Examen le 11 janvier 2017 à 8h30 comme indiqué sur le site de la fds...
  Aucun document autorisé.
  
  
• Sujet de CC et son corrigé
  
  
• Controle continu en tp le mardi 15/12 au bat.6 Les étudiants de maths-info sont convoqués à 8h00, ceux d'info dont le nom commence par une lettre entre A et J à 9h45 et ceux d'info dont le nom commence par une lettre entre K et Z à 11h30.
  
  
• Controle continu sur table le mardi 15/11 à 8h00 sur le créneau de cours (tp puis td après comme d'hab). Chapitre 1,2,3, sans document.
  
  

   Calendrier:

• Les cours ont lieu le mardi de 8h00 à 9h30 en amphi SC5.05. Début des cours: le mardi 6 septembre 20156
  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 13 septembre 2016.
  
  - Groupe A: encadrant: F. Dross, TD salle: TD5.21
  - Groupe B + Maths-Info: encadrant: S. Bessy, TD salle: TD1.06
  - Groupe C: encadrant: M. Montassier, TD salle: TD4.04
  - Math-Infos: en TD avec le groupe B, encadrant de TP: F. Barbero
  
  Tps au bâtiment 6, voir planning sur le site du SIF.
  
  

   Contenu du cours:

15h Cours, 18h TD, 18h 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 pairs de sommets.

Exceptionnellement, pour les personnes arrivées tardivement, je mets mes notes (partielles) des 2 premiers cours en ligne:
Cours1.pdf     Cours2.pdf

Fiche d'algos

   Fiches de Td:

Fiche de TD1      Fiche de TD2      Fiche de TD3
Fiche de TD4      Fiche de TD5

   Fiches de Tp:

Fiche de TP1 et le début du code.
Fiche de TP2 et le début du code.
Fiche de TP3 et le début du code.
   BonusTrack!!! Un algo récursif de parcours en profondeur implémenté en Python (merci à Guillaume Guégan).
Fiche de TP4 et le début du code.
Fiche de TP5, le début du code et un réseau plus grand pour s'amuser.

Routine pour les TPs:

• TP1: Gestion de matrices.
• TP2: Affichage de graphes.

   Modalités de contrôle:

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 15 novembre. Le programme porte sur les chapitres 1,2 et 3.
• 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 13 décembre.

La note finale sera max{ Exam ; 2/3 Exam + 1/3 CC}

   Quelques annales:

• Controle continu novembre 2015 et sa correction
• Examen de janvier 2016
• Examen de seconde session juin 2016

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

---