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|\]