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-011 |
|
|
Language of instruction | Language of assessment | HT(*) | HTPE(*) | HTPS(*) | HR(*) | HD(*) | Term |
---|---|---|---|---|---|---|---|
Français | Français | 36 | 12 | 0 | 0 | 0 | Q1 |
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 of Graph Theory and Combinatorial optimization (theory and exercises) and accounting for 80% of the AA's evaluation. The project deliverables/challenge (part of the AA) accounting for 20 % 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 Learning Resources/Tools
Not applicable
Recommended Reading
Copie de présentation - Partie 3 - Métaheuristiques - M. Mezmaz
,Copie de présentation - Partie 1 - Théorie des graphes - D. Tuyttens
,Copie de présentation - Partie 2 - Optimisation combinatoire - D. Tuyttens
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)