Théorie des graphes (semestre 4, année 2013-2014)
Ces informations sont à titre indicatif et susceptibles de changer au fil du module.
Plan du cours
- Semaine 1 : Introduction, définitions de base -- [Matériel]
- Semaine 2 : Ordres de grandeurs et complexité -- [Matériel]
- Semaine 3 : Arbres couvrants (BFS, DFS) et Dijkstra (salle machine) -- [Sujet, DFS.java, Dijkstra.java]
- Semaine 4 : Suite de la semaine 3 (TP ramassé)
- Semaine 5 : Interro (30mn) + Structures de données pour les graphes -- [Matériel]
- Semaine 6 : Problèmes difficiles et classes de problèmes (P vs NP) -- [Matériel]
- Semaine 7 : Marches aléatoires et algorithme PageRank (Google) -- [Matériel]
- Semaine 8 : Interactions dans une flotte de robots mobiles (salle machine, TP ramassé)
Evaluation
La note finale aura trois composantes :
- Interro de mi-parcours (20%)
- Travaux pratiques (30%)
- Devoir surveillé (50%)
Notes de cours
Les transparents projetés au fur et à mesure seront ajoutés ici. Mais attention, ils ne représentent qu'une petite partie du contenu à assimiler. La majorité du contenu est à acquérir par la prise de notes pendant les cours.
Travaux pratiques
Les travaux pratiques se feront avec la plateforme JBotSim. Les ressources concernées seront déposées ici au fur et à mesure.