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

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