« INFO526 : 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
 
(22 versions intermédiaires par le même utilisateur non affichées)
Ligne 1 : Ligne 1 :
Cours du semestre 5 de la licence STIC INFO.
⚫
Ce wiki est un complément de cours pour le cours « info-526 : graphes et algorithmes ». La participation au wiki est fortement encouragée.


* Responsable pour 2012--2013: Xavier Provençal.
⚫
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''...)
* Xavier Provençal (C/TD/TP), Pierre-Étienne Meunier (TP).


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


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


==Administration==




Ligne 17 : Ligne 20 :


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

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

TD5 : [http://lama.univ-savoie.fr/~provencal/INFO526/INFO526-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/INFO526/TP/index.html Énoncé des TP]




Ligne 24 : Ligne 36 :


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



===Références===
===Références===
Ligne 30 : Ligne 45 :




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

<!--


-----------------
-----------------
Ligne 85 : Ligne 117 :


'''Question :''' quelle est la meilleure représentation ?
'''Question :''' quelle est la meilleure représentation ?

-->

Dernière version du 19 juin 2013 à 14:36

Cours du semestre 5 de la licence STIC INFO.

  • Responsable pour 2012--2013: Xavier Provençal.
  • Xavier Provençal (C/TD/TP), Pierre-Étienne Meunier (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


Compléments de cours / TD / TP

Algorithme du parcours en largeur

Algorithme du parcours en profondeur

Quelques algorithmes de minimisation Prim, Dijkstra, Floyd-Warshall.


Références

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


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 )


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