Study programme 2018-2019Français
Graphs and Combinatorial Optimisation
Programme component of Master's Degree in Mathematics à la Faculty of Science
CodeTypeHead of UE Department’s
contact details
Teacher(s)
US-M1-SCMATH-024-MOptional 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çais361200044.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

  • Have integrated and elaborate mathematical knowledge.
    • Mobilise the Bachelor's course in mathematics to address complex issues and have profound mathematical expertise to complement the knowledge developed in the Bachelor's course.
    • Research mathematical literature in an efficient and relevant way.
  • Apply innovative methods to solve an unprecedented problem in mathematics or within its applications.
    • Mobilise knowledge, and research and analyse various information sources to propose innovative solutions targeted unprecedented issues.
    • Appropriately make use of computer tools, as required by developing a small programme.
  • Communicate clearly.
    • Communicate the results of mathematical or related fields, both orally and in writing, by adapting to the public.

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; duality; notion of algorithm.

Type of Assessment for UE in Q1

  • Presentation and/or works
  • Written examination

Q1 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

  • Presentation and/or works
  • Written examination

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%

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

AARequired Reading
I-MARO-011Copie 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 - M. Mezmaz

Required Learning Resources/Tools

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

Recommended Reading

AARecommended Reading
I-MARO-011

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 : 02/05/2019
20, place du Parc, B7000 Mons - Belgique
Tél: +32 (0)65 373111
Courriel: info.mons@umons.ac.be