 | Study programme 2020-2021 | 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 2020-2021 assessments (Covid-19) |
|---|
|
| Description of the modifications to the Q3 2020-2021 assessment procedures (Covid-19) |
| The report and the presentation of the projet/challenge (part of the AA) accounting for 20% of the evaluation. The absence at the presentation of the project/challenge (and/or not submitting the report) implies an absence on the whole of the UE. During the session, written examination in person covering both parts of the course: Graph theory : (theory and exercises) 40% Combinatorial optimization : (theory and exercises) 40%. The evaluation procedures are likely to be adjusted according to the assessment context imposed by health measures. |
Organisational arrangements for the end of Q2 2020-2021 assessments (Covid-19) online or face-to-face (according to assessment schedule)
- Written exam (multiple choice, open questions)
Description of the modifications to the Q2 2020-2021 assessment procedures (Covid-19) online or face-to-face (according to assessment schedule)
A written examination during the session 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.
Preferably and if the health crisis allows, the written examination will be done in person.
Otherwise, the written examination will be done remotely via Moodle exams.
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.
The teaching methods are likely to be adjusted according to the educational context
imposed by the health measures.
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
- Ateliers et projets encadrés au sein de l'établissement
Evaluations
The assessment methods of the Learning Activity (AA) are specified in the course description of the corresponding Educational Component (UE)