« INFO631 : Graphes et algorithmes » : différence entre les versions
Aller à la navigation
Aller à la recherche
Aucun résumé des modifications |
|||
| (16 versions intermédiaires par le même utilisateur non affichées) | |||
| Ligne 7 : | Ligne 7 : | ||
=== Documents remis en classe === |
=== Documents remis en classe === |
||
[http://lama.univ-savoie.fr/~provencal/enseignement/INFO631/parcours.pdf Algorithmes |
[http://lama.univ-savoie.fr/~provencal/enseignement/INFO631/parcours.pdf Algorithmes de parcours (largeur et profondeur)] |
||
[http://lama.univ-savoie.fr/~provencal/enseignement/INFO631/algoMinimisation.pdf Quelques algorithmes de minimisation Kruskal, Prim, Dijkstra, Floyd-Warshall.] |
|||
<!-- |
<!-- |
||
| Ligne 22 : | Ligne 24 : | ||
===Logiciel utilisé lors des TP=== |
===Logiciel utilisé lors des TP=== |
||
[http://sagemath.org http://sagemath.org] |
[http://sagemath.org http://sagemath.org] |
||
===TP=== |
|||
[http://lama.univ-savoie.fr/~provencal/enseignement/INFO631/TP/ Lien vers la page de TP] |
|||
| Ligne 28 : | Ligne 33 : | ||
- CM1 : Introduction aux graphes, orienté vs non-orienté, adjacence, degré, chemins, cycles et composantes connexes. |
- CM1 : Introduction aux graphes, orienté vs non-orienté, adjacence, degré, chemins, cycles et composantes connexes. |
||
- [http://lama.univ-savoie.fr/~provencal/enseignement/INFO631/presentationCM1.pdf Présentation d'introduction aux graphes] |
- [http://lama.univ-savoie.fr/~provencal/enseignement/INFO631/presentationCM1.pdf Présentation d'introduction aux graphes] |
||
- CM2 : Arbres et forêts, représentations de graphes (matrice VS listes), coût des primitives en fonctions de la représentation, parcours en largeur. |
|||
- TD1 : [http://lama.univ-savoie.fr/~provencal/enseignement/INFO631/TD1.pdf Feuille TD1 (pdf)] |
|||
- CM3 : Parcours en profondeur, graphe pondérés, arbre couvrant minimum (début). |
|||
- TD2 : [http://lama.univ-savoie.fr/~provencal/enseignement/INFO631/TD2.pdf Feuille TD2 (pdf)] |
|||
- CM4 : Arbre couvrant minimum (fin), algorithmes de Kruskal et Prim. |
|||
- TD3 : [http://lama.univ-savoie.fr/~provencal/enseignement/INFO631/TD3.pdf Feuille TD3 (pdf)] |
|||
- CM5 : Chemins de longueur minimum. Algorithmes de Dijkstra et Floyd-Warshall. |
|||
- TD4 : [http://lama.univ-savoie.fr/~provencal/enseignement/INFO631/TD4.pdf Feuille TD4 (pdf)] |
|||
- CM6 : Calcul du flot maximum, algorithme de Ford-Fulkerson. |
|||
- TD5 : [http://lama.univ-savoie.fr/~provencal/enseignement/INFO631/TD5.pdf Feuille TD5 (pdf)] |
|||
- TD6 : [http://lama.univ-savoie.fr/~provencal/enseignement/INFO631/TD6.pdf Feuille TD6 (pdf)] |
|||
== Déroulement (2014-2015) == |
== Déroulement (2014-2015) == |
||
| Ligne 79 : | Ligne 105 : | ||
--> |
--> |
||
<!-- |
|||
=== Quelques ressources additionnelles (vidéos) === |
=== Quelques ressources additionnelles (vidéos) === |
||
| Ligne 100 : | Ligne 127 : | ||
[https://www.youtube.com/watch?v=o7d2wHagfEg Flot maximum en Réseau/ Algorithme Edmonds-Karp] |
[https://www.youtube.com/watch?v=o7d2wHagfEg Flot maximum en Réseau/ Algorithme Edmonds-Karp] |
||
--> |
|||
Dernière version du 21 mars 2016 à 10:15
Cours du semestre 6 de la licence STIC INFO.
- Responsable pour 2015--2016: Xavier Provençal.
- Xavier Provençal (CM/TD/TP).
Documents remis en classe
Algorithmes de parcours (largeur et profondeur)
Quelques algorithmes de minimisation Kruskal, Prim, Dijkstra, Floyd-Warshall.
Ouvrage de référence
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.
Logiciel utilisé lors des TP
TP
Déroulement (2015-2016)
- CM1 : Introduction aux graphes, orienté vs non-orienté, adjacence, degré, chemins, cycles et composantes connexes. - Présentation d'introduction aux graphes
- CM2 : Arbres et forêts, représentations de graphes (matrice VS listes), coût des primitives en fonctions de la représentation, parcours en largeur.
- TD1 : Feuille TD1 (pdf)
- CM3 : Parcours en profondeur, graphe pondérés, arbre couvrant minimum (début).
- TD2 : Feuille TD2 (pdf)
- CM4 : Arbre couvrant minimum (fin), algorithmes de Kruskal et Prim.
- TD3 : Feuille TD3 (pdf)
- CM5 : Chemins de longueur minimum. Algorithmes de Dijkstra et Floyd-Warshall.
- TD4 : Feuille TD4 (pdf)
- CM6 : Calcul du flot maximum, algorithme de Ford-Fulkerson.
- TD5 : Feuille TD5 (pdf)
- TD6 : Feuille TD6 (pdf)
Déroulement (2014-2015)
- (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. Représentation de graphes ( matrice vs listes ).
- (TD 1): Représentation de graphes, propriétés élmentaires de graphes, modélisation par des graphes.
- (Cours 3): Forêt couvrante, parcours de graphes, parcours en largeur, parcours en profondeur.
- (TD 2): Parcours en largeur : connexité, graphes bipartis, détection de cycles.
- (Cours 4): Graphes valués, arbre courvrant de poids minimum et algorithme de Kruskal.
- (TD 3): Parcours en profondeur : tri topologique, implémentation sans récursivité. Algorithme pour le calcul d'un ACM : Prim vs Kruskal.
- (Cours 5): Calcul des chemins de longueur minimale. Algorithme de calcul de chemins de longueur minimale : Dijkstra et Floyd-Warshall.
- (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.
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 ).
- (TD 1): Représentation de graphes, propriétés élmentaires de graphes, modélisation par des graphes.
- (Cours 3): Représentation de graphes (suite et fin). Parcours de graphes, parcours en largeur, parcours en profondeur.
- (TD 2): Parcours en largeur : connexité, graphes bipartis, détection de cycles.
- (Cours 4): Graphes valués, arbre courvrant de poids minimum et algorithme de Prim.
- (TD 3): Parcours en profondeur : tri topologique, implémentation sans récursivité. Algorithme pour le calcul d'un ACM : Prim vs Kruskal.
- (Cours 5): Calcul des chemins de longueur minimale. Algorithme de calcul de chemins de longueur minimale : Dijkstra et Floyd-Warshall.
- (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.