Syllabus 2014/2015
 
Extrait PDF Anglais
Français
index
Module : IF226
Titre :
Algorithmique probabiliste
Volumes horaires :
Cours Intégré : 30.00 h
Travail Individuel : 15.00 h
Crédits ECTS :
2.50
Évaluation :
S1: ET(2h,E,da:notes de cours manuscrites) x1   Détail de la nomenclature employée pour la création du code d'évaluation
Enseignant(s) :
DUCHON Philippe - Responsable
Partagé par le(s) module(s) à 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
    Document(s) :
    polycopié "Introduction à l'algorithmique probabiliste"
    Mot(s) clé(s) :
    Probabilités discrètes, Algorithmique probabiliste, Analyse d'algorithmes