« INFO526 : Graphes et algorithmes » : différence entre les versions
Aller à la navigation
Aller à la recherche
Aucun résumé des modifications |
Aucun résumé des modifications |
||
| (14 versions intermédiaires par le même utilisateur non affichées) | |||
| Ligne 1 : | Ligne 1 : | ||
= Module INFO526 Graphes et Algorithmes = |
|||
Cours du semestre 5 de la licence STIC INFO. |
Cours du semestre 5 de la licence STIC INFO. |
||
| Ligne 12 : | Ligne 10 : | ||
#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.--> |
||
| Ligne 18 : | Ligne 17 : | ||
TD1 : [http://lama.univ-savoie.fr/~provencal/INFO526/INFO526-TD1.pdf Première feuille de TD] |
TD1 : [http://lama.univ-savoie.fr/~provencal/INFO526/INFO526-TD1.pdf Première feuille de TD] |
||
| ⚫ | |||
TD2 : [http://lama.univ-savoie.fr/~provencal/INFO526/INFO526-TD2.pdf Deuxième feuille de TD] |
TD2 : [http://lama.univ-savoie.fr/~provencal/INFO526/INFO526-TD2.pdf Deuxième feuille de TD] |
||
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] |
|||
===Compléments de cours / TD / TP=== |
===Compléments de cours / TD / TP=== |
||
| Ligne 31 : | 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.] |
|||
| Ligne 40 : | Ligne 47 : | ||
== Déroulement (2012-2013) == |
== Déroulement (2012-2013) == |
||
* (Cours 1): |
* (Cours 1): 12 septembre. Graphes (vocubulaire et définitions de bases), degré et adjacence, isomorphie de graphes. |
||
* (Cours 2): |
* (Cours 2): 18 septembre. Lemme des poignées de mains, représentations de graphes (listes VS matrice), composantes connexes. |
||
* (TD 1): |
* (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 100 : | 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 )