Ce cours commence par quelques révisions sur quelques structures mathématiques discrètes (relations, ordres, treillis, matroïdes) utiles en optimisation combinatoire. Dans une seconde partie, il s'intéresse à l'approximation de problème NP-difficile avec garantie de performance. Enfin, dans une dernière partie, il s'intéresse à l'apport de l'aléa en algorithmique.
- Enseignant responsable de l'UE: Bertrand Meyer