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

De Wiki du LAMA (UMR 5127)
Aller à la navigation Aller à la recherche
Aucun résumé des modifications
Aucun résumé des modifications
Ligne 3 : Ligne 3 :
* Responsable pour 2015--2016: Xavier Provençal.
* Responsable pour 2015--2016: Xavier Provençal.
* Xavier Provençal (CM/TD/TP).
* Xavier Provençal (CM/TD/TP).


<!-- 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.-->

Présentation d'introduction présentée au premier cours : [http://lama.univ-savoie.fr/~provencal/INFO631/PresIntro.pdf Présentation]

===TD===

À venir.

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

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

TD3 : [http://lama.univ-savoie.fr/~provencal/INFO631/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/INFO631/TD5.pdf Cinquième feuille de TD]

TD6 : [http://lama.univ-savoie.fr/~provencal/INFO631/TD6.pdf Sixième feuille de TD]
-->

===TP===

À venir.

<!--
[http://lama.univ-savoie.fr/~provencal/INFO631/TP/index.html Lien vers la page des TP]
-->




=== Documents remis en classe ===
=== Documents remis en classe ===


[http://lama.univ-savoie.fr/~provencal/enseignements/INFO631/parcours.pdf Algorithmes du parcours, largeur et profondeur]
[http://lama.univ-savoie.fr/~provencal/enseignement/INFO631/parcours.pdf Algorithmes du parcours, largeur et profondeur]


<!--
<!--
Ligne 62 : Ligne 27 :


- 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/enseignements/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]
- TD1 :

== Déroulement (2014-2015) ==
== Déroulement (2014-2015) ==



Version du 18 janvier 2016 à 09:51

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

http://sagemath.org


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


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

Parcourt en Largeur (BFS) 1/2

Parcourt en Largeur (BFS) 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