Transcrit par les étudiants. Avec seulement des corrections superficielles par l'enseignant.
Il manque des choses sur les algorithmes probabilistes
(min-cut par contraction d'arête, programmation linéaire avec arrondi randomisé),
les graphes aléatoires (loi 0-1), les chaînes de Markov (convergence vers la distribution stationnaire, algorithme pour 2-SAT). Ces points sauf la loi 0-1 sont dans les notes de cours de 2000-2001.
Pascal Koiran