Résumé:
L'aléatoire permet-il d'aller réellement plus vite (c'est-à-dire de gagner un
facteur plus que polynomial) ? La tendance actuelle est de penser que peut-être
pas: une chaîne aléatoire est certes incalculable donc puissante mais n'est après
tout que du bruit... En fait toute une branche de l'informatique théorique
s'acharne actuellement à réduire au maximum les "besoins" en aléatoire des
algorithmes randomisés (taille de la chaine aléatoire nécessaire) via différentes
techniques.
Je présenterai dans cet exposé quelques unes de ces techniques, les plus élémentaires: 1) la "gloutonisation" ou comment transformer un algorithme randomisé en un algorithme glouton (par la méthode dite des probabilités conditionnelles) ; 2) la méthode des probabilités 2-à-2-indépendantes (qui se généralise à d-à-d-indépendantes) --- et peut-être un rapide survol des méthodes "de pointe" à base d'extracteurs, concentrateurs et autres graphes innomables... Nous les mettrons en oeuvre ensemble et en détail sur des exemples simples et précis, Max-Cut sera une cible de choix ;-).
Retour au sommaire / Back to schedule