 | 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-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 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 Q1 2020-2021 assessments (Covid-19) online or face-to-face (according to assessment schedule)
- Production of individual or group work, essay, report, dissertation...
Description of the modifications to the Q1 2020-2021 online assessment procedures (Covid-19) online or face-to-face (according to assessment schedule)
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
(remotely via Moodle examens).
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
- Travaux pratiques
Evaluations
The assessment methods of the Learning Activity (AA) are specified in the course description of the corresponding Educational Component (UE)