« INFO632 : algorithmes de graphes » : différence entre les versions
Aller à la navigation
Aller à la recherche
(Page créée avec « Cours du semestre 6 de la licence STIC INFO. * Responsable pour 2012--2013: Xavier Provençal. * Responsable pour 2013--2014: Xavier Provençal. * Xavier Provençal (C/TD/TP… ») |
|||
| (28 versions intermédiaires par 2 utilisateurs non affichées) | |||
| Ligne 1 : | Ligne 1 : | ||
Cours du semestre 6 de la licence STIC INFO. |
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 2012--2013: Xavier Provençal. |
||
* Responsable pour 2013--2014: Xavier Provençal. |
* Responsable pour 2013--2014: Xavier Provençal. |
||
* Xavier Provençal ( |
* Xavier Provençal (CM/TD/TP). |
||
| Ligne 11 : | Ligne 13 : | ||
#Je vous conseille d'aller lire [http://meta.wikimedia.org/wiki/Aide:Contenu ce guide] pour vous familiariser avec les wikis.--> |
#Je vous conseille d'aller lire [http://meta.wikimedia.org/wiki/Aide:Contenu ce guide] pour vous familiariser avec les wikis.--> |
||
===TD et TP=== |
===TD et TP=== |
||
TD1 : [http://lama.univ-savoie.fr/~provencal/ |
TD1 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD1.pdf Première feuille de TD] |
||
TD2 : [http://lama.univ-savoie.fr/~provencal/ |
TD2 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD2.pdf Deuxième feuille de TD] |
||
TD3 : [http://lama.univ-savoie.fr/~provencal/ |
TD3 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD3.pdf Troisième feuille de TD] |
||
TD4 : [http://lama.univ-savoie.fr/~provencal/ |
TD4 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD4.pdf Quatrième feuille de TD] |
||
TD5 : [http://lama.univ-savoie.fr/~provencal/ |
TD5 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD5.pdf Cinquième feuille de TD] |
||
TD6 : [http://lama.univ-savoie.fr/~provencal/INFO526/INFO526-TD6.pdf Sixième feuille de TD] |
TD6 : [http://lama.univ-savoie.fr/~provencal/INFO526/INFO526-TD6.pdf Sixième feuille de TD] |
||
| ⚫ | |||
| ⚫ | |||
<!-- |
|||
===Compléments de cours / TD / TP=== |
===Compléments de cours / TD / TP=== |
||
| Ligne 39 : | Ligne 41 : | ||
[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.] |
||
--> |
|||
===Algorithmes=== |
|||
[https://www.youtube.com/watch?v=vYv8MhxCO00 Parcourt en Profondeur (DFS) 1/2] |
|||
===Références=== |
|||
[https://www.youtube.com/watch?v=zEKRCDSxYXg Parcourt en Profondeur (DFS) 2/2] |
|||
[https://www.youtube.com/watch?v=JucGeygpzFw Parcourt en Largeur (BFS) 1/2] |
|||
[https://www.youtube.com/watch?v=0rH7OgcM6eA Parcourt en Largeur (BFS) 2/2] |
|||
[https://www.youtube.com/watch?v=-3YIKISpTsQ Arbres Couvrants Minimum (Prim)] |
|||
[https://www.youtube.com/watch?v=ocYYUiCTqI8 Algorithme Ford-Fulkerson (avec capacités aux noeuds)] |
|||
[https://www.youtube.com/watch?v=Z5B_Ruz1woI A* (un algorithme pour super mario); excerpt] |
|||
[https://www.youtube.com/watch?v=WOTOjbHBEXY Graphes et Algorithmes/ Ford-Fulkerson (Graphe Résiduel) 1/2 ] |
|||
[https://www.youtube.com/watch?v=c57gOxo4hWo Graphes et Algorithmes/ Ford-Fulkerson (Graphe Résiduel) 2/2 ] |
|||
[https://www.youtube.com/watch?v=o7d2wHagfEg Flot maximum en Réseau/ Algorithme Edmonds-Karp] |
|||
===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... |
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/INFO632/parcours.pdf Parcours de graphes, en largeur et en profondeur.] |
|||
[http://lama.univ-savoie.fr/~provencal/INFO632/algos_minimisation.pdf Algorithmes de minimisation ( Prim, Dijkstra, Floyd-Warshall ).] |
|||
== 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. |
|||
Dernière version du 13 mai 2014 à 13:43
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 (CM/TD/TP).
TD et TP
TD1 : Première feuille de TD
TD2 : Deuxième feuille de TD
TD3 : Troisième feuille de TD
TD4 : Quatrième feuille de TD
TD5 : Cinquième feuille de TD
TD6 : Sixième feuille de TD
TP : Énoncé des TP
Algorithmes
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
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...
Documents remis en classe
Parcours de graphes, en largeur et en profondeur.
Algorithmes de minimisation ( Prim, Dijkstra, Floyd-Warshall ).
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.
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 )