But du cours
Provide engineering students with the essential mathematical foundations required to solve common problems across all optimization domains in computer science.
Acquis d'apprentissage visés
- Ability to model a real-world problem (logistics, networks, machine learning, etc.) as an optimization problem (choice of variables, objective function, constraints) and express this model in appropriate mathematical language.
- Master discrete/combinatorial optimization issues: modeling via linear programming, integer programming, graphs, flows.
- Analyze the algorithmic complexity of optimization problems and distinguish easy vs. hard cases (e.g., NP-complete, pseudo-polynomial).
Prérequis
Set theory and algebra
Programme
- Mathematical modeling of optimization problems.
- Graph Theory.
- Landau notation and complexity theory.
- Linear optimization (linear programming, ILP, gradient descent).
- Dynamic programming.
Modalités d'évaluation
2 Written exams (1h/1h)
Bibliographie
An Introduction to Linear Programming and Game Theory, Third Edition (2008) - Paul R. Thie, G. E. Keough - Wiley
Supports
Course slides + TD handouts + TP handouts available on Moodle