Combinatorial optimisation and related algorithms - Master 1 Informatique

Head: Sophie Pinchinat
Team: Rumen Andonov, Sophie Pinchinat
Prerequisite knowledge: Algorithmique impérative (API), Outils formels de l'informatique (OFI), Algorithmique des graphes (AGR1), Méthodes algorithmiques (ALG)

Why efficient algorithms?

Read this piece from "Algorithms" by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani

NP-complete problems

Content

Lectures by Rumen Andonov
Lectures by Sophie Pinchinat
- Look at this video as soon as you can.
- Intelligent exhaustive search (Backtracking and Branch-and-Bound)
- Approximation algorithms

Material

All the material will be available on Teams.

Bibliography

"NETWORKS" de M.E.J.Newman
"Algorithms" by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani
"Conception d'algorithmes Principes et 150 exercices non corriges" by Bosc, P., Guyomard, M., and Miclet, L.
"Algorithm Design" by Jon Kleinberg and Eva Tardos
"Approximation Algorithms" by Vijay V. Vazirani
"Introduction to Algorithms" by Thomas H. Cormen, Clifford Stein, Charles E. Leiserson, Robert L. Rivest

Annales d'examens

April 2018
June 2018 (oral examination)

Schedule

Look at your ENT .