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.