« 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 46 : | Ligne 46 : | ||
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... |
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... |
||
=== Documents remis en classe === |
|||
[http://lama.univ-savoie.fr/~provencal/INFO526/parcours.pdf Parcours de graphes, en largeur et en profondeur.] |
|||
== Déroulement (2013-2014) == |
== Déroulement (2013-2014) == |
||
Version du 27 janvier 2014 à 07:32
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...
Documents remis en classe
Parcours de graphes, en largeur et en profondeur.
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 )