Algorithmique 2 : Algorithmes et probabili té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.

Leave a comment