 | Study programme 2025-2026 | Français | |
| Graph Theory and Combinatorial Optimization | |||
Learning Activity |
| Code | Lecturer(s) | Associate Lecturer(s) | Subsitute Lecturer(s) et other(s) | Establishment |
|---|---|---|---|---|
| I-MARO-011 |
|
|
| Language of instruction | Language of assessment | HT(*) | HTPE(*) | HTPS(*) | HR(*) | HD(*) | Term |
|---|---|---|---|---|---|---|---|
| Français | Français | 42 | 18 | 0 | 0 | 0 | Q1 |
Content of Learning Activity
Basic notions of graph theory and data structure; study of classical graph theory problems : trees, shortest paths, connexity, flows; Comparison of graphs using global connexity indicators, global connectivity indicators and local position indicators. Introduction to complexity theory : P and NP classes; study of classical combinatorial optimization problems : knapsack, set covering, travelling salesman; introduction to metaheuristics.
A project/challenge is orgnized and it is part of the content of the AA.
The teaching methods are likely to be adjusted according to the educational context
imposed by the health measures.
Required Reading
Copie de présentation - Partie 2 - Optimisation combinatoire - D. Tuyttens
,Copie de présentation - Partie 1 - Théorie des graphes - D. Tuyttens
Required Learning Resources/Tools
Not applicable
Recommended Learning Resources/Tools
Not applicable
Other Recommended Reading
P. Lacomme, C. Prins & M. Sevaux Algorithmes de graphes, Editions Eyrolles, 2003. J. Dréo, A. Pétrowski, P. Siarry & E. taillard Métaheuristiques pour l'optimisation difficile, Editions Eyrolles, 2003.
Mode of delivery
- Face-to-face
Type of Teaching Activity/Activities
- Cours magistraux
- Travaux pratiques
Evaluations
The assessment methods of the Learning Activity (AA) are specified in the course description of the corresponding Educational Component (UE)
Location of learning activity
- Université de Mons - Mons
Location of assessment
- Université de Mons - Mons