Algorithmique 2 : Algorithmes et probabilités

Introduction

• Algorithme probabiliste

  • $A$
  • $T_A(d)$ est une var aléatoire

  ⟹ quelque soit la distribution : \(Max_{d∈D_n}(E(T_A(d)))\)

• Algorithme déterministe

  • $d∈D_n$ distribution
  • $A$
  • $X_d$ v.a
  • $T_A(X_i)$

  ⟹ on fait des hypothèses sur la distribution : \(E(T_A(X^n_d)))\)

• Dérandomisation d’algorithmes probabilistes

---

Structure dynamique :

• enregistrements = (clé, valeur)

Rechercher, Ajouter, Supprimer, Modifier, etc…

• Liste : en $𝛳(n)$

• Arbres de recherche :

  • cas moyen + hypothèse sur les données : $𝛳(\log n)$

  • équilibrés :

    • rouge-noir
    • AVL

    pire cas : $𝛳(\log n)$

Skip Lists

En français : listes à trous.