Study programme | Français | ||
Graph Theory and Combinatorial Optimization | |||
Programme component of Master's Degree in Computer Engineering and Management (Charleroi (Hor. décalé)) à la Faculty of Engineering |
Code | Type | Head of UE | Department’s contact details | Teacher(s) |
---|---|---|---|---|
UI-M1-IRIGIG-808-C | Compulsory UE | TUYTTENS Daniel | F151 - Mathématique et Recherche opérationnelle |
|
Language of instruction | Language of assessment | HT(*) | HTPE(*) | HTPS(*) | HR(*) | HD(*) | Credits | Weighting | Term |
---|---|---|---|---|---|---|---|---|---|
| Français | 36 | 4 | 0 | 0 | 0 | 4.00 | 4.00 |
AA Code | Teaching Activity (AA) | HT(*) | HTPE(*) | HTPS(*) | HR(*) | HD(*) | Term | Weighting |
---|---|---|---|---|---|---|---|---|
I-MARO-153 | Graph Theory and Combinatorial Optimization | 36 | 4 | 0 | 0 | 0 | Q2 | 100.00% |
Unité d'enseignement |
---|
Objectives of Programme's Learning Outcomes
Learning Outcomes of UE
Understand the fundamental notions and problems appearing in graph theory;study the corresponding algorithms;go deeply into algorithmic notions from the algorithm efficiency point of view;understand the fundamental problems and techniques of combinatorial optimization;illustrate some methods on some particular problems;show the utility of algorithms for solving practical problems in scheduling management, logistics,...
Content of UE
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.
Prior Experience
Linear programming, notion of algorithm.
Q1 UE Assessment Comments
Not applicable
Type of Assessment for UE in Q2
Q2 UE Assessment Comments
Reports of practical works : 20%. Written examination covering both parts of the course: Graph theory : (theory and exercises) 40% Combinatorial optimization : (theory and exercises) 40%
Type of Assessment for UE in Q3
Q3 UE Assessment Comments
Reports of practical works : 20%. Written examination covering both parts of the course: Graph theory : (theory and exercises) 40% Combinatorial optimization : (theory and exercises) 40%
Q1 UE Resit Assessment Comments (BAB1)
Not applicable
Type of Teaching Activity/Activities
AA | Type of Teaching Activity/Activities |
---|---|
I-MARO-153 |
|
Mode of delivery
AA | Mode of delivery |
---|---|
I-MARO-153 |
|
Required Reading
AA | Required Reading |
---|---|
I-MARO-153 | Copie de présentation - Partie 1 - Théorie des graphes - D. Tuyttens Copie de présentation - Partie 2 - Optimisation combinatoire - D. Tuyttens Copie de présentation - Partie 3 - Métaheuristiques - D. Tuyttens |
Required Learning Resources/Tools
AA | Required Learning Resources/Tools |
---|---|
I-MARO-153 | Not applicable |
Recommended Reading
AA | Recommended Reading |
---|---|
I-MARO-153 |
Recommended Learning Resources/Tools
AA | Recommended Learning Resources/Tools |
---|---|
I-MARO-153 | Not applicable. |
Other Recommended Reading
AA | Other Recommended Reading |
---|---|
I-MARO-153 | 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. |
Grade Deferrals of AAs from one year to the next
AA | Grade Deferrals of AAs from one year to the next |
---|---|
I-MARO-153 | Autorisé |