Introduction à l'algorithmique probabiliste

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.

Article lu   fois.

L'auteur

Liens sociaux

Viadeo Twitter Facebook Share on Google+   

I. Téléchargement

Vous pouvez accéder au cours au format PDF (site d'origine) ou sur le serveur de developpez.com.

II. Sommaire

  1. Introduction
  2. Modèles d'algorithmes probabilistes
  3. Sélection probabiliste
  4. Algorithmes issus de la théorie des nombres
  5. Structures de données probabilistes
  6. Rappels de probabilités

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

  

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 œuvre intellectuelle protégée par les droits d'auteur. 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'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.