Théorie et Algorithmique des Graphes
[make
]
[gcc
]
[gdb
]
[graphviz
]
[flex
]
[bison
]
[tag
]
[galerie
]
Il s'agit de présenter quelques notions fondamentales
concernant les graphes des points de vues théorique et pratique
dans le cadre d'une mise en oeuvre en Langage C.
Programme
- Introduction
- Pile et graphe eulerien
- Complexité du parcours eulerien
- Cycle Hamiltonien
- Complexité du problème du cycle hamiltonien
- Quelques problèmes sur les graphes
- Réduction algorithmique
- Ensembles disjoints et connexité
- Arbre couvrant minimal
- Voyageur de commerce
- Complexité de TSP
- Approximation
- Tri topologique
- Fonction de Grundy
- Connexité forte
- Une élégante réduction du problème 2-SAT
Travaux-Pratiques
Les sujets de travaux-pratiques sont présentés, et
détaillés en cours. Au cours des séances vous développerez
une bibliothèque en Langage C.
- Entrées/Sorties pour les graphes.
- Parcours en profondeur, calcul des composantes connexes.
- Implantation des piles, parcours eulérien
- Ensemble disjoints, expérience numérique sur la connexité, composante géante.
- Arbre couvrant, 2-approximation du problème du voyageur de commerce
- Tri toplogique, fonction de Grundy.
- Backtracking : Reines sur l'échiquier.
- Ensemble stable.
- Cycle Hamiltonien.
- Coloriage des sommets.
Examens
- 2018-19 :
écrit 1,
écrit 2,
pratique.
- 2019-20 :
écrit 1,
corrigé 1,
écrit 2,
pratique.
- 2020-21 :
écrit 1,
corrigé 1,
écrit 2,
corrigé 2,
pratique.
- 2021-22 :
écrit 1,
corrigé 1,
écrit 2,
corrigé 2,
pratique.
- 2022-23 :
écrit 1,
corrigé 1,
écrit 2,
corrigé 2,
pratique.
archive.
- 2022-23 :
écrit 1,
corrigé 1,
pratique.
Liens
[home
]
[ abcduC
]
[ palgo
]
[compilation
]