Advertising Console

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

    Reposter
    Nicolas Schabanel

    par Nicolas Schabanel

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

    Cours n°1: Mar. Oct 30, 2012 - 16:30-19:30
    1) Introduction aux algorithmes randomisés
    2) Un algorithme randomisé pour Min-Cut

    Séance d'exercices n°1: Solutions aléatoires et dérandomisation
    1) Analyse d'une partition aléatoire pour Max-Cut
    2) Dérandomisation par la méthode de l'espérance conditionnelle
    3) Dérandomisation par la construction d'un espace probabilisé de bits uniformes 2-à-2 indépendants
    4) Généralisation à des bits uniformes k-à-k indépendants