 | Study programme 2023-2024 | Français | |
 | Graphs and Combinatorial Optimisation | ||
Programme component of Bachelor's in Computer Science (MONS) (day schedule) à la Faculty of Science |
| Code | Type | Head of UE | Department’s contact details | Teacher(s) |
|---|---|---|---|---|
| US-B3-SCINFO-003-M | 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 | 12 | 0 | 0 | 0 | 5 | 5.00 | 1st term |
| AA Code | Teaching Activity (AA) | HT(*) | HTPE(*) | HTPS(*) | HR(*) | HD(*) | Term | Weighting |
|---|---|---|---|---|---|---|---|---|
| I-MARO-011 | Graph Theory and Combinatorial Optimization | 36 | 12 | 0 | 0 | 0 | Q1 | 100.00% |
| Programme component | ||
|---|---|---|
 | US-B2-SCINFO-008-M Optimisation | |
| | US-B2-SCINFO-011-M Data Structures I | |
Objectives of Programme's Learning Outcomes
- Understand the fundamentals of computer science
- Show an understanding and deep knowledge of the concepts of computer science and mathematical formalisms used in the field of computer science
- Use the vocabulary and the correct mathematical reasoning to formulate and solve problems in the field of computer science
- Understand computer technologies
- Understand the IT involved in the different stages of the life of a computer application
- Self-train in ICT
- Demonstrate basic knowledge and know-how in related fields
- Demonstrate knowledge and basic skills in science and technology.
- Understand the fundamentals related to scientific methods
- Develop skills of abstraction and modelling through a conceptual and scientific approach
- Conduct rigorous reasoning based on scientific arguments
- Understand the fundamentals of communication
- Communicate information (both orally and in writing) relating to the field of computer science in an intelligible, clear and structured way
- Communicate a consistent and rigorous scientific argument, either orally or in writing
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,...
UE Content: description and pedagogical relevance
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.
A project/challenge is orgnized and it is part of the content of the AA.
The teaching methods are likely to be adjusted according to the educational context
imposed by the health measures.
Prior Experience
Linear programming; duality; notion of algorithm.
Type of Teaching Activity/Activities
| AA | Type of Teaching Activity/Activities |
|---|---|
| I-MARO-011 |
|
Mode of delivery
| AA | Mode of delivery |
|---|---|
| I-MARO-011 |
|
Required Learning Resources/Tools
| AA | Required Learning Resources/Tools |
|---|---|
| I-MARO-011 | Not applicable |
Recommended Reading
| AA | Recommended Reading |
|---|---|
| I-MARO-011 | 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
| AA | Recommended Learning Resources/Tools |
|---|---|
| I-MARO-011 | Not applicable |
Other Recommended Reading
| AA | Other Recommended Reading |
|---|---|
| I-MARO-011 | 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-011 | Authorized |
Term 1 Assessment - type
| AA | Type(s) and mode(s) of Q1 assessment |
|---|---|
| I-MARO-011 |
|
Term 1 Assessment - comments
| AA | Term 1 Assessment - comments |
|---|---|
| I-MARO-011 | 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. 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 educational/assessment context imposed by health measures. |
Resit Assessment - Term 1 (B1BA1) - type
| AA | Type(s) and mode(s) of Q1 resit assessment (BAB1) |
|---|---|
| I-MARO-011 |
|
Term 3 Assessment - type
| AA | Type(s) and mode(s) of Q3 assessment |
|---|---|
| I-MARO-011 |
|
Term 3 Assessment - comments
| AA | Term 3 Assessment - comments |
|---|---|
| I-MARO-011 | 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. 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 educational/assessment context imposed by health measures. |