Algorithmique : Recherche d’un mot.

Dictionnaire :
  • un ens. d’enregistrements
  • accédé par des clés dans un espace ordonné
  • Chercher (clé)
  • Insérer (clé)
  • Supprimer (clé)
  • Concaténer 2 dico :
    • max(Dict1) < min(Dict2)
  • Scinder Dict, clé :
    • Dict1 $≤$ clé
    • Dict2 $>$ clé

Arbres balisés

Complexité $= 𝛩(b\log_a(n))$

Question : scission en $\log(n)$ sur les AVL ?

File de priorité

Cas le plus important : simulateur : événements classés par date d’échéance.

Création d’un tas : complexité : mieux que $n\log n$ : en $𝛳(n)$

8.1 + 4.2 + 2.3 + 1.4

8 4 2 1 = 15 <= 16
  4 2 1 = 7 <= 8
    2 1 = 3 <= 4
      1 = 1 <= 2
_________________
            <= 32

Tas binomial

Longueur de la liste : en $\log(n)$.

Si on a l’union, il faut utiliser tas binomial.

Si on a $n$ sommets en tout dans notre tas : en écrivant $n$ en base $2$, on a un $1$ à l’indice $i$ ssi il y a l’arbre $B_i$ dans notre tas.

Union ≡ addition en binaire, opération fondamentale.

Faire de même que l’addition en binaire : $B_i ≡ i$-ème bit vaut $1$.

Ce qu’on gagne avec les tas binomiaux : le min en $O(1)$, toutes les autres opérations en $O(log(n))$.

Tas de Fibonacci

Inventés par Tarjan :

$O(1)$ amorti

$O(k)$

$k$ opérations.

Heuristique : on profite de l’opération chère pour rééquilibrer les arbres tournois.

Attention : liste du tas plus en $\log(n)$, comme il n’y a pas de rééquilibrage lors de l’insertion !

Opération clé à faire de manière intelligente : extraction du minimum.

Sur le transparent :

  • gris = marqué
  • petits 1, 2, … en superscript = arbre de degré 1, 2, …

NB: quand on extrait le minimum, on ne change pas les marquages.

La seule opération qui change les marquages : diminuer la valeur. Mais attention : on ne marque pas la racine, pq? :

  • Analyse de complexité

Une racine ne peut être marquée que si elle était fils d’une racine qui a été extraite.


Elimination du min d’un arbre donné : en $O(degré de la racine)$

Tas binomial : diminution de valeurs en $O(1)$, alors que pour les 2 autres structures : c’était en $O(1)$.

Diminution de valeur, complexité amortie :

  • $a(T)$ a augmenté d’au plus $m$
  • $m(T)$ a diminué d’au plus $m-2$.

$𝛥Pot = O(m+1) -2C(m-2) = O(1)$

Matroïdes :

  • familles libres
  • sous-graphes acycliques d’un graphe connexe

Pseudo-matroïde : différence

  • avec matroïde : quand on on élimine un élément, on ne le regarde plus après
  • pseudo-matroïde : on peut le revoir
Arbre à $n$ sommets :

Graphe connexe acyclique.

Algo de Prim

Grâce aux tas de Fibonacci : Complexité passe de $O(\vert A\vert \log(\vert S) \vert)$ (pour tas binomial) à $O(\vert S\vert \log(\vert S) \vert + \vert A \vert)$ (pour tas de Fibonacci) : gain énorme, car le graphe est connexe, d’où :

|S| << |A|

Leave a comment