Responsable / In charge of : Nisse Nicolas (Nicolas.NISSE@inria.fr)

Résumé / Abstract :
The lectures will present the basic notions of Discrete Mathematics and Combinatorial Optimization. We will focus on two important problems, namely Network Flows and their applications to connectivity, and Graph Coloring. Through these two problems, we will give the basic notions of Algorithmic, Computational Complexity and Graph Theory. During the second part of the lecture, we will present an introduction to Linear Programming and duality, revisiting Flows and Coloring Problems.

Prérequis / Prerequisite :
• Basic knowledge of graph theory (shortest paths algorithms, search algorithms (BFS...))

Objectifs / Objectives :
Learn to write formal proofs of algorithms

Contenu / Contents :

• Introduction to graphs
• Shortest path and spanning tree problems
• Maximum flow
• applications in bipartite graphs and notions of complexity
• Model a combinatorial problem using linear programming.
• Proving optimality of a solution or finding approximate solutions.
• Using software solvers to solve linear programs in practice.

Références / References :
Lectures notes at http://www-sop.inria.fr/members/Frederic.Havet/Cours/ubinet.html and references inside.

Acquis / Knowledge :

Evaluation / Assessment :
Two written exams. - midterm: 30% of the mark - final: 70% of the mark