---

Algorithmique de graphes.

L3 Informatique, L3 Maths-Info.

GLIN 501

---

   Correction de l'examen janvier 2012:

Enoncé  
Correction: page 1   page 2  page 3 

   Notes de Controle continu:

Notes
Ces notes correspondent au contrôle continu écrit du 22 novembre plus une bonification (de +0 à +3) ajoutée à cette note lors du Tp noté du 13 décembre

Correction du C.C. écrit:
page 1   page 2  page 3  page 4

   TP noté:

Le MARDI 13 DECEMBRE au bâtiment 6:
  - A 9h45: les personnes ayant un numéro d'étudiant pair.
  - A 11h30: les personnes ayant un numéro d'étudiant impair.
Vous serez interogés d'une part sur le travail effectué jusqu'ici en tp, et d'autre part sur des exercices que vous réaliserez pendant l'heure et demi. La note est une bonification sur la note obtenue au C.C. écrit du 22 novembre.

   Calendrier:

Les cours ont lieu le mardi de 8h00 à 9h30 en amphi A 5.06. Début des cours: le mardi 13 septembre 2011.
Les TD ont lieu le mardi de 9h45 à 11h15, les tp à la suite, le mardi de 11h30 à 13h00, voir le planning de la FDS. Début des TD/TP: le mardi 20 septembre 2011.

- Groupe A: (encadrant: S. Bessy) TD salle: TD 19.01
- Groupe B: (encadrant: D. Goncalves) TD salle: SC 1.01
- Groupe C: (encadrant: C. Paul) TD salle: SC 25.01 (sauf le ma 22 nov: TD 1.01)
- Encadrant de tp supplémentaire: T. Kaced.

Tps au bâtiment 6, voir planning sur Rezufr.

   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.

Notes de cours (manuscrites):
En pdf: cours 1, cours 2, cours 3, cours 4, cours 5, cours 6, cours 7, cours 8, cours 9.
En ps: cours 1, cours 2, cours 3, cours 4, cours 5, cours 6, cours 7, cours 8, cours 9.

Récapitulatif des algos du cours (Attention, il y a des coquilles dans le poly distribué, notamment:
  - les tests des algos 1 et 2 sont comp(x)≠ comp(y) et pas comp(x)=comp(y)).
  - il manque le calcul des niveaux dans le parcours en largeur.
  - il y a un problème dans l'initialisation de l'algorithme de Dijkstra.)
Version corrigée: Algo

   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.
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 22 novembre.
• Une partie TP qui bonifiera la note précédente, 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:

• Contrôle continu, novembre 2008
• Examen, janvier 2007 et sa correction.
• Seconde session, mai 2008

   (petite) Bibliographie:

Cormen, Leiserson, Rivest et Stein : Introduction à l'algorithmique (Dunod).

---