Study programme 2021-2022Français
Graphs and Combinatorial Optimisation
Programme component of Master's in Computer Science à la Faculty of Science

CodeTypeHead of UE Department’s
contact details
Teacher(s)
US-MC-SCINFO-044-MCompulsory UETUYTTENS DanielF151 - Mathématique et Recherche opérationnelle
  • TUYTTENS Daniel

Language
of instruction
Language
of assessment
HT(*) HTPE(*) HTPS(*) HR(*) HD(*) CreditsWeighting Term
  • Français
Français361200055.001st term

AA CodeTeaching Activity (AA) HT(*) HTPE(*) HTPS(*) HR(*) HD(*) Term Weighting
I-MARO-011Graph Theory and Combinatorial Optimization3612000Q1100.00%
Programme component

Objectives of Programme's Learning Outcomes

  • Manage large-scale software development projects.
    • Apply, mobilise, articulate and promote the knowledge and skills acquired in order to help lead and complete a project.
  • Manage research, development and innovation.
    • Understand unprecedented problems in computer science and its applications.
    • Methodically research valid scientific information, lead a critical analysis, propose and argue potentially innovative solutions to targeted problems.
  • Master communication techniques.
    • Communicate, both orally and in writing, their findings, original proposals, knowledge and underlying principles, in a clear, structured and justified manner.
  • Develop and integrate a high degree of autonomy.
    • Aquire new knowledge independently.

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.

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 Assessment for UE in Q1

  • Presentation and/or works
  • Written examination

Method of calculating the overall mark for the Q1 UE assessment

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.

Q1 UE Assessment Comments

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.

Type of Assessment for UE in Q3

  • Presentation and/or works
  • Written examination

Method of calculating the overall mark for the Q3 UE assessment

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.

Q3 UE Assessment Comments

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.

Type of Resit Assessment for UE in Q1 (BAB1)

  • N/A

Q1 UE Resit Assessment Comments (BAB1)

Not applicable

Type of Teaching Activity/Activities

AAType of Teaching Activity/Activities
I-MARO-011
  • Cours magistraux
  • Travaux pratiques

Mode of delivery

AAMode of delivery
I-MARO-011
  • Face to face

Required Reading

AA
I-MARO-011

Required Learning Resources/Tools

AARequired Learning Resources/Tools
I-MARO-011Not applicable

Recommended Reading

AARecommended Reading
I-MARO-011Copie de présentation - Partie 3 - Métaheuristiques - M. Mezmaz
,Copie de présentation - Partie 2 - Optimisation combinatoire - D. Tuyttens

Recommended Learning Resources/Tools

AARecommended Learning Resources/Tools
I-MARO-011Not applicable

Other Recommended Reading

AAOther Recommended Reading
I-MARO-011P. 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

AAGrade Deferrals of AAs from one year to the next
I-MARO-011Authorized
(*) HT : Hours of theory - HTPE : Hours of in-class exercices - HTPS : hours of practical work - HD : HMiscellaneous time - HR : Hours of remedial classes. - Per. (Period), Y=Year, Q1=1st term et Q2=2nd term
Date de génération : 17/09/2021
20, place du Parc, B7000 Mons - Belgique
Tél: +32 (0)65 373111
Courriel: info.mons@umons.ac.be