Introduction à l'algorithmique probabiliste
Date de publication : 16/10/2007 , Date de mise à jour : 16/10/2007
Par
Philippe Duchon
Ce cours est une introduction à l'algorithmique probabiliste. Les modèles d'algorithmes probabilistes
seront initialement illustrés grâce aux algorithmes RandQuickSort et RandMinCut.
Une série de problèmes et d'algorithmes probabilistes seront ensuite étudiés : sélection probabiliste (RandLazySelect), racine
carrés modulaires, test de primalité de Miller-Rabin.
Des structures de données probabilistes seront enfin vues (principe, listes à sauts aléatoires, treaps, tables de hachage).
Enfin, une annexe rappellera les notions de bases en probabilités.
I. Téléchargement
II. Sommaire
- Introduction
- Modèles d'algorithmes probabilistes
- Sélection probabiliste
- Algorithmes issus de la théorie des nombres
- Structures de données probabilistes
- Rappels de probabilités
Les sources présentées sur cette page sont libres de droits,
et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation
constitue une oeuvre intellectuelle protégée par les droits d'auteurs. Copyright ©
2007 Philippe Duchon. Aucune reproduction,
même partielle, ne peut être faite de ce site et de l'ensemble de son contenu :
textes, documents, images, etc sans l'autorisation expresse de l'auteur.
Sinon vous encourez selon la loi jusqu'à 3 ans de prison et jusqu'à 300 000 E
de dommages et intérêts.
Cette page est déposée à la
SACD.
