Module IF226 - Syllabus ENSEIRB

Module : IF226
Titre :

Algorithmique probabiliste

Volumes horaires :

Cours Intégré : 20.00 h
Travail Individuel : 18.00 h

Enseignant(s) :

DUCHON Philippe - Responsable

Partagé par le(s) module(s) à choix :

IF229 Un module au choix

Niveau :

module de deuxième année

Résumé :

Ce cours est une introduction à l'algorithmique probabiliste. On s'intéresse à toutes les conséquences de l'utilisation explicite de l'aléatoire en algorithmique: analyse "en moyenne dans le cas le pire", possibilité de répéter utilement le même algorithme sur des données identiques, puissance de la randomisation pour dépasser le problème des "mauvaises instances". Différents archétypes d'algorithmes probabilistes sont étudiés et analysés en détail.

Bibliographie:

R. Motwani, P. Raghavan, "Randomized algorithms" - 1995, Cambridge University Press

M. Mitzenmacher, E. Upfal - "Probability and computing" - 2005, Cambridge University Press

Plan :

Introduction générale, analyse de QuickSort randomisé

Modèles de sources, générateurs pseudo-aléatoires

Algorithmes de type Monte Carlo et Las Vegas, classes RP et ZPP. Exploitation de l'abondance de témoins.

Algorithmes probabilistes en théorie des nombres: le test de Miller-Rabin.

Simulation de lois de probabilités: algorithmes à rejet.

Structures de données probabilistes: notions générales, treaps, skip-lists, tables de hachage.

Prérequis :

IF101, IF102, IF106, IS101

Évaluation :

examen de 2h (notes de cours et polycopié autorisés)

Document(s) :

polycopié "Introduction à l'algorithmique probabiliste"

Mot(s) clé(s) :

Probabilités discrètes, Algorithmique probabiliste, Analyse d'algorithmes