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
