« INFO631 : Graphes et algorithmes » : différence entre les versions

De Wiki du LAMA (UMR 5127)
Aller à la navigation Aller à la recherche
(Page créée avec « 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--20... »)
 
 
(34 versions intermédiaires par le même utilisateur 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 2015--2016: Xavier Provençal.
* 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).
* Xavier Provençal (CM/TD/TP).




=== Documents remis en classe ===
<!-- Ce wiki est un complément de cours pour le cours « info-526 : graphes et algorithmes ». La participation au wiki est fortement encouragée.

#Pour pouvoir modifier les pages, inscrivez-vous (lien en haut à droite) pour obtenir un login et mot de passe. (Choisissez un login du style ''PrenomNom''...)

#Je vous conseille d'aller lire [http://meta.wikimedia.org/wiki/Aide:Contenu ce guide] pour vous familiariser avec les wikis.-->


===TD et TP===

TD1 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD1.pdf Première feuille de TD]

TD2 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD2.pdf Deuxième feuille de TD]

TD3 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD3.pdf Troisième feuille de TD]

TD4 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD4.pdf Quatrième feuille de TD]


TD5 : [http://lama.univ-savoie.fr/~provencal/INFO632/TD5.pdf Cinquième feuille de TD]
[http://lama.univ-savoie.fr/~provencal/enseignement/INFO631/parcours.pdf Algorithmes de parcours (largeur et profondeur)]

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]


[http://lama.univ-savoie.fr/~provencal/enseignement/INFO631/algoMinimisation.pdf Quelques algorithmes de minimisation Kruskal, Prim, Dijkstra, Floyd-Warshall.]


<!--
<!--

===Compléments de cours / TD / TP===

[http://lama.univ-savoie.fr/~provencal/INFO526/parcoursLargeur.pdf Algorithme du parcours en largeur]

[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/INFO526/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.]
-->
-->


===Algorithmes===
===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.
[https://www.youtube.com/watch?v=vYv8MhxCO00 Parcourt en Profondeur (DFS) 1/2]


[https://www.youtube.com/watch?v=zEKRCDSxYXg Parcourt en Profondeur (DFS) 2/2]


===Logiciel utilisé lors des TP===
[http://sagemath.org http://sagemath.org]


===TP===
[http://lama.univ-savoie.fr/~provencal/enseignement/INFO631/TP/ Lien vers la page de TP]


[https://www.youtube.com/watch?v=JucGeygpzFw Parcourt en Largeur (BFS) 1/2]


== Déroulement (2015-2016) ==
[https://www.youtube.com/watch?v=0rH7OgcM6eA Parcourt en Largeur (BFS) 2/2]


- 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]


- 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.
[https://www.youtube.com/watch?v=-3YIKISpTsQ Arbres Couvrants Minimum (Prim)]


- 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).
[https://www.youtube.com/watch?v=ocYYUiCTqI8 Algorithme Ford-Fulkerson (avec capacités aux noeuds)]


- TD2 : [http://lama.univ-savoie.fr/~provencal/enseignement/INFO631/TD2.pdf Feuille TD2 (pdf)]


- CM4 : Arbre couvrant minimum (fin), algorithmes de Kruskal et Prim.
[https://www.youtube.com/watch?v=Z5B_Ruz1woI A* (un algorithme pour super mario); excerpt]


- 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.
[https://www.youtube.com/watch?v=WOTOjbHBEXY Graphes et Algorithmes/ Ford-Fulkerson (Graphe Résiduel) 1/2 ]


- TD4 : [http://lama.univ-savoie.fr/~provencal/enseignement/INFO631/TD4.pdf Feuille TD4 (pdf)]
[https://www.youtube.com/watch?v=c57gOxo4hWo Graphes et Algorithmes/ Ford-Fulkerson (Graphe Résiduel) 2/2 ]


- CM6 : Calcul du flot maximum, algorithme de Ford-Fulkerson.


- TD5 : [http://lama.univ-savoie.fr/~provencal/enseignement/INFO631/TD5.pdf Feuille TD5 (pdf)]
[https://www.youtube.com/watch?v=o7d2wHagfEg Flot maximum en Réseau/ Algorithme Edmonds-Karp]


- TD6 : [http://lama.univ-savoie.fr/~provencal/enseignement/INFO631/TD6.pdf Feuille TD6 (pdf)]
===Ouvrage de référence===


== Déroulement (2014-2015) ==
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...


* (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.


=== 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) ==
== Déroulement (2013-2014) ==
Ligne 97 : Ligne 85 :
* (TD 5): Réseaux de tarnsport et flot maximal.
* (TD 5): Réseaux de tarnsport et flot maximal.


<!--




Ligne 114 : Ligne 103 :
* (TD 5): Réseaux de tarnsport et flot maximal.
* (TD 5): Réseaux de tarnsport et flot maximal.
* (TD 6): Misc. ( Recherche guidée, chemin eulériens et clôture transitive )
* (TD 6): Misc. ( Recherche guidée, chemin eulériens et clôture transitive )
-->

<!--
=== Quelques ressources additionnelles (vidéos) ===

[https://www.youtube.com/watch?v=vYv8MhxCO00 Parcourt en Profondeur (DFS) 1/2]

[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]
-->



<!--
<!--

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

http://sagemath.org

TP

Lien vers la page de 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.



Récupérée de « http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=INFO631_:_Graphes_et_algorithmes&oldid=8880 »