Advertising Console

    [MPRI 2012] Algorithmes randomisés (2A)

    Reposter
    Nicolas Schabanel

    par Nicolas Schabanel

    26
    188 vues
    MPRI 1.24 - Algorithmes Randomisés (Nicolas Schabanel, CNRS - Université Paris Diderot)
    [ Cours n°2 Partie A/C ]

    Cours n°2: Mar. Nov. 6, 2012 - 16:00-19:00
    1) Fonctions booléennes, CNF et DNF
    2) L'algorithme Walk-SAT

    Séance d'exercices n°2: Le principe de Yao & Un algorithme plus rapide pour Min-Cut
    1) Mise en veille d'un disque dur
    1.a) Approche déterministe
    1.b) Le principe de Yao
    1.c) Un algorithme randomisé optimal
    2) L'algorithme de Karger-Stein (1993) pour Min-Cut