« INFO632 : algorithmes de graphes » : différence entre les versions
Aller à la navigation
Aller à la recherche
Aucun résumé des modifications |
Aucun résumé des modifications |
||
| Ligne 49 : | Ligne 49 : | ||
== Déroulement (2013-2014) == |
== Déroulement (2013-2014) == |
||
* (Cours 1): |
* (Cours 1): Graphes (vocubulaire et définitions de bases), degré et adjacence, isomorphie de graphes. |
||
* (Cours 2): Chemin, chemin simple, cycle, composante (fortement) connexe. Arbre et forêt. Représentation de graphes ( matrice vs listes ). |
|||
Version du 21 janvier 2014 à 15:47
Cours du semestre 6 de la licence STIC INFO.
- Responsable pour 2010--2011: Pierre Hyvernat.
- Responsable pour 2011--2012: Xavier Provençal.
- Responsable pour 2012--2013: Xavier Provençal.
- Responsable pour 2013--2014: Xavier Provençal.
- Xavier Provençal (C/TD/TP).
Références
La partie « Algorithmes sur les graphes » du livre « Introduction à l'algorithmique » de Cormen, Leiserson et Rivest est un bon complément. Il contient des exemples, applications et preuves de certaines propriétés des algorithmes étudiés en cours...
Déroulement (2013-2014)
- (Cours 1): Graphes (vocubulaire et définitions de bases), degré et adjacence, isomorphie de graphes.
- (Cours 2): Chemin, chemin simple, cycle, composante (fortement) connexe. Arbre et forêt. Représentation de graphes ( matrice vs listes ).
Déroulement (2012-2013)
- (Cours 1): 12 septembre. Graphes (vocubulaire et définitions de bases), degré et adjacence, isomorphie de graphes.
- (Cours 2): 18 septembre. Lemme des poignées de mains, représentations de graphes (listes VS matrice), composantes connexes.
- (TD 1): 19 septembre. Représentation de graphes, propriétés élémentaires de graphes, modélisation par des graphes.
- (Cours 3): 25 septembre. Arbres, forêts et arbres couvrants. Parcours en largeur.
- (TD 2): 26 septembre. Parcours en largeur : connexité, graphes bipartis, détection de cycles.
- (Cours 4): 2 octobre. Parcours en profondeur, graphes valués, arbres couvrants de poids minimal (I).
- (TD 3): 9 octobre. Parcours en profonder : détection de cycles, tri topologique. Algorithmes de Kruskal (I).
- (Cours 5): 16 octobre. Algorithmes de Prim, Dijkstra et Floyd-Warshall.
- (TP 1): 24 octobre. Familiarisation avec Sagemath et sa bibliothèque de graphes. Conversion de représentations, graphe de dépendances.
- (TD 4): Chemins de longueur minimales.
- (Cours 6): Réseaux de transport et calcul du flot maximal. Algorithme de Ford-Fulkerson.
- (TD 5): Réseaux de tarnsport et flot maximal.
- (TD 6): Misc. ( Recherche guidée, chemin eulériens et clôture transitive )