« INFO631 : Graphes et algorithmes » : différence entre les versions
Aucun résumé des modifications |
Aucun résumé des modifications |
||
| Ligne 34 : | Ligne 34 : | ||
À venir |
À venir |
||
| ⚫ | |||
[http://lama.univ-savoie.fr/~provencal/INFO526/parcoursLargeur.pdf Algorithme du parcours en largeur] |
[http://lama.univ-savoie.fr/~provencal/INFO526/parcoursLargeur.pdf Algorithme du parcours en largeur] |
||
| Ligne 40 : | Ligne 39 : | ||
[http://lama.univ-savoie.fr/~provencal/INFO526/algoMinimisation.pdf Quelques algorithmes de minimisation Prim, Dijkstra, Floyd-Warshall.] |
[http://lama.univ-savoie.fr/~provencal/INFO526/algoMinimisation.pdf Quelques algorithmes de minimisation Prim, Dijkstra, Floyd-Warshall.] |
||
--> |
|||
===Ouvrage de référence=== |
===Ouvrage de référence=== |
||
| Ligne 65 : | Ligne 63 : | ||
* (Cours 3): Forêt couvrante, parcours de graphes, parcours en largeur, parcours en profondeur. |
* (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. |
* (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. |
* (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. |
* (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. |
* (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. |
* (TD 4): Chemins de longueur minimales. |
||
Version du 3 mars 2015 à 17:20
Cours du semestre 6 de la licence STIC INFO.
- Responsable pour 2014--2015: Xavier Provençal.
- Xavier Provençal (CM/TD/TP).
Présentation d'introduction présentée au premier cours : Présentation
TD et TP
TD1 : Première feuille de TD
Compléments de cours / TD / TP
À venir Algorithme du parcours en largeur
Algorithme du parcours en profondeur
Quelques algorithmes de minimisation 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
Documents remis en classe
Parcours de graphes, en largeur et en profondeur.
Algorithmes de minimisation ( Prim, Dijkstra, Floyd-Warshall ).
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 Prim.
- (TD 3): Parcours en profondeur : tri topologique, implémentation sans récursivité. Algorithme pour le calcul d'un ACM : Prim vs Kruskal.
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.
Quelques ressources additionnelles (vidéos)
Parcourt en Profondeur (DFS) 1/2
Parcourt en Profondeur (DFS) 2/2
Arbres Couvrants Minimum (Prim)
Algorithme Ford-Fulkerson (avec capacités aux noeuds)
A* (un algorithme pour super mario); excerpt
Graphes et Algorithmes/ Ford-Fulkerson (Graphe Résiduel) 1/2
Graphes et Algorithmes/ Ford-Fulkerson (Graphe Résiduel) 2/2
Flot maximum en Réseau/ Algorithme Edmonds-Karp