Study programme 2019-2020 | Français | ||
Graph Theory and Combinatorial Optimization | |||
Learning Activity |
Code | Lecturer(s) | Associate Lecturer(s) | Subsitute Lecturer(s) et other(s) | Establishment |
---|---|---|---|---|
I-MARO-153 |
|
|
Language of instruction | Language of assessment | HT(*) | HTPE(*) | HTPS(*) | HR(*) | HD(*) | Term |
---|---|---|---|---|---|---|---|
Français | Français | 36 | 4 | 0 | 0 | 0 | Q2 |
Organisational online arrangements for the end of Q3 2019-2020 assessments (Covid-19) |
---|
|
Description of the modifications to the Q3 2019-2020 online assessment procedures (Covid-19) |
A written examination (remotely via Moodle examens) covering both parts (Graph Theory and Combinatorial optimization) and accounting for 70% of the AA's evaluation. The project deliverables/challenge (part of the AA) accounting for 30 % of the AA's evaluation. |
Content of Learning Activity
Basic notions of graph theory and data structure; study of classical graph theory problems : trees, shortest paths, connexity, flows;introduction to complexity theory : P and NP classes; study of classical combinatorial optimization problems : knapsack, set covering, travelling salesman; introduction to metaheuristics.
Required Reading
Copie de présentation - Partie 2 - Optimisation combinatoire - D. Tuyttens
,Copie de présentation - Partie 1 - Théorie des graphes - D. Tuyttens
,Copie de présentation - Partie 3 - Métaheuristiques - 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
Type of Teaching Activity/Activities
Evaluations
The assessment methods of the Learning Activity (AA) are specified in the course description of the corresponding Educational Component (UE)