« INFO631 : Graphes et algorithmes » : différence entre les versions
Aller à la navigation
Aller à la recherche
Aucun résumé des modifications |
Aucun résumé des modifications |
||
| Ligne 1 : | Ligne 1 : | ||
Cours du semestre 6 de la licence STIC INFO. |
Cours du semestre 6 de la licence STIC INFO. |
||
* Responsable pour |
* Responsable pour 2015--2016: Xavier Provençal. |
||
* Xavier Provençal (CM/TD/TP). |
* Xavier Provençal (CM/TD/TP). |
||
| Ligne 15 : | Ligne 15 : | ||
===TD=== |
===TD=== |
||
À venir. |
|||
<!-- |
|||
TD1 : [http://lama.univ-savoie.fr/~provencal/INFO631/TD/TD1.pdf Première feuille de TD] |
TD1 : [http://lama.univ-savoie.fr/~provencal/INFO631/TD/TD1.pdf Première feuille de TD] |
||
| Ligne 26 : | Ligne 29 : | ||
TD6 : [http://lama.univ-savoie.fr/~provencal/INFO631/TD6.pdf Sixième feuille de TD] |
TD6 : [http://lama.univ-savoie.fr/~provencal/INFO631/TD6.pdf Sixième feuille de TD] |
||
--> |
|||
===TP=== |
===TP=== |
||
À venir. |
|||
| ⚫ | |||
<!-- |
<!-- |
||
| ⚫ | |||
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] |
|||
TP : [http://www.lama.univ-savoie.fr/~provencal/INFO632/TP/index.html Énoncé des TP] |
|||
--> |
--> |
||
===Compléments de cours / TD / TP=== |
|||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
<!-- |
|||
[http://lama.univ-savoie.fr/~provencal/INFO526/parcoursProfondeur.pdf Algorithme du parcours en profondeur] |
[http://lama.univ-savoie.fr/~provencal/INFO526/parcoursProfondeur.pdf Algorithme du parcours en profondeur] |
||
[http://lama.univ-savoie.fr/~provencal/INFO631/algoMinimisation.pdf Quelques algorithmes de minimisation Prim, Dijkstra, Floyd-Warshall.] |
[http://lama.univ-savoie.fr/~provencal/INFO631/algoMinimisation.pdf Quelques algorithmes de minimisation Prim, Dijkstra, Floyd-Warshall.] |
||
--> |
|||
===Ouvrage de référence=== |
===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. |
||
| Ligne 57 : | Ligne 59 : | ||
== Déroulement (2015-2016) == |
|||
| ⚫ | |||
[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 ).] |
|||
- CM1 : Introduction aux graphes, orienté vs non-orienté, adjacence, degré, chemins, cycles et composantes connexes. |
|||
- [http://lama.univ-savoie.fr/~provencal/enseignements/INFO631/presentationCM1.pdf Présentation d'introduction aux graphes] |
|||
- TD1 : |
|||
== Déroulement (2014-2015) == |
== Déroulement (2014-2015) == |
||
Version du 18 janvier 2016 à 09:49
Cours du semestre 6 de la licence STIC INFO.
- Responsable pour 2015--2016: Xavier Provençal.
- Xavier Provençal (CM/TD/TP).
Présentation d'introduction présentée au premier cours : Présentation
TD
À venir.
TP
À venir.
Documents remis en classe
Algorithmes du parcours, largeur et profondeur
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
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 - TD1 :
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.
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