cours 511 - partie 2

Ghost

Informations

• Publié par: Miching
• Nombre de lectures: 18
• Langue: Français

Extrait

Définition
Algorithmes complexes
Une table est une structure de
Partie 2
Clé Infos
données telle que l’accès à un
élément est déterminé à partir de
0
sa clé.
Une clé permet d’identifier un
élément de manière unique : la clé 1
est dite discriminante.
L’allocation d’un table est
2 Dupond …
Les tables
généralement contiguë.
La partie infos contient les
3
informations spécifiques à
l’application.
N-1
Algorithmes complexes : Les 1 Algorithmes complexes : Les 2
Tables
Tables
Index Rappel sur les clés
Sorte Clé
Si une structure données (Infos) contient plusieurs éléments
Utilise Booléen
discriminants, il est possible alors de créer une table servant d’index et
utilisant comme clé l’élément discriminant choisi.
Opérations :
Un index permet d’accélérer les traitements de recherche.
≤ : Clé ⊗ Clé Booléen ;
Exemple :
= : Clé ⊗ Clé Booléen ;
Index sur Nom Tableau de données
Avec :
Nom Pos Pos Nom Prénom Adresse Numéro
x , y , z : Clé
Henri 0
Henri Arthur Rue là 0478923210
0
Axiomes :
Dupond 25
…
x ≤ y= vrai
Dupond Michel Rue Ici 0630302456
( x ≤ y ) ∧ ( y ≤ x ) ⇒ x = y
25
( x ≤ y ) ∧ ( y ≤ z ) ⇒ x ≤ z
Index sur Numéro
On appelle clé l’application, qui à chaque éléments associe sa clé :
Numéro Pos
Clé: Elément Clé
0630302456 0
0630302456 25
Algorithmes complexes : Les 3 Algorithmes complexes : Les 4
Tables Tables
1Spécification du type Spécification du type
Sorte Table
Axiomes
Utilise Elément, Clé, Entier, Booléen
Taille(Créer-Table(i)) = 0
TailleMax(Créer-Table(i)) = i
Opérations:
Créer-Table : Entier Table
I < 0 ⇒ E ∈ Insérer(Créer-Table(i), E)
Insérer : Table ⊗ Element Table
Rechercher : Table ⊗ Clé Element
I < 0 ⇒ Rechercher(Insérer(Créer-Table(i), E), Cle(E)) = E
∈ : Element ⊗ Table Booléen
Supprimer : Table ⊗ Clé Table
E ∈ T ⇒ Taille(Insérer(T, E)) = Taille(T)
TailleMax : Table Entier
Taille : Table Entier
E ∈ T ⇒ E ∈ Insérer(T, E)
Nième : Table ⊗ Entier Element
E ∉ T ∧ Taille(T) < TailleMax(T) ⇒ Taille(Insérer(T, E)) = Taille(T) + 1
Avec
I : entier;
E ∉ T ∧ Taille(T) < TailleMax(T) ⇒ E ∈ Insérer(T, E)
T : Table;
E ∉ T ∧ Taille(T) < TailleMax(T) ⇒ Rechercher(Insérer(T, E), Cle(E)) =
E : Element;
E
TailleMax(T) = TailleMax(Inserer(T, E))
Pré-condition :
Rechercher ( T , Cle(E) ) est défini si et seulement si E ∈ T
Algorithmes complexes : Les 5 Algorithmes complexes : Les 6
Tables Tables
Spécification du type Recherche dichotomique
La recherche dichotomique n’est possible que sur un ensemble trié
E ∈ T ⇒ Taille(Supprimer(T, Cle(E))) = Taille(T)-1
Principe de base : au lieu de parcourir séquentiellement la structure, on la
E ∈ T ⇒ E ∉ (Supprimer(T, Cle(E)))
parcourt en prenant le milieu de l’espace de recherche:
E ∉ T ⇒ Taille((Supprimer(T, Cle(E))) = Taille(T)
Si on a trouvé l’élément recherche, l’algorithme s’arrête en renvoyant
E ∉ T ⇒ Supprimer(T, Cle(E)) = T
l’index.
E ∉ T ⇒ E ∉ (Supprimer(T, Cle(E)) Sinon on prend le milieu de l’espace restant, en choissant la moitié gauche
ou la moitié droite, suivant si l’élément recherché est inférieur ou supérieur
E, E2 ∈ T ∧ E ≠ E2 ⇒ Rechercher(Supprimer(T, Cle(E)), Cle(E2)) =
à l’élément courant observé.
E2
TailleMax(T) = TailleMax(Supprimer(T, E))
j >= 0 ∧ j < i ⇒ Nieme(Insérer(Créer-Table(i), E), j) = E
Algorithmes complexes : Les 7 Algorithmes complexes : Les 8
Tables Tables
2)
=
;
/


v
S
a
R
(
O

L
O
A
e



t
;
T
)

i
e

e
,
I
T

(

e
:
m
n
i
l
N
)

v
e
u
n
Q
r
u
u
)
o
r
t
A
e
=
r
+

2
E

U
I
Q
a
T
=
N
v
C
u


=
f

:

a
)
e
I
(

1
,
o
T

(
f
e
;
m
N
r
E
i
e
N
<
(
i
o
E
l
!
C
u


I
R
A

T
(
N
u
I
i
F
u


I
S
S
N
N
N
I
S
F
i

r
I

S
S
N
e
I
d
F
b

t
1
=
+
0
i


i
=

:
=
t
T
u
i
b
l
e
M
d
x

T
N
-
O
;
N
r
I
u
S
e

:
1

-
a
i
x


=
A
:
T

U
n

i
d
f
b

t
S
=
R
f
O
n
L

A
T

(
)
t
C
o

v
>
)

F
)
I
I
E

i
,
:
T

(
d
e
b
m
t
i
f
N
n
(

l

C
;
(
t

:
Recherche dichotomique ALGORITHME DE HACHAGE
Fonction Rechercher( T : Table ; C : Clé) : Element Structures ordonnées : la place d’un élément dépend de la valeur de sa clé
debut, fin, i : Entier;
comparée à celle des autres éléments.
trouve : Booléen;
Différence avec les tables : la clé n’est plus discriminante
Début
Technique de hachage : la place d’un élément n’est calculée qu’à partir de sa clé.
Calcul de la place réalisé à l’aide de la fonction de hachage.
Calcul à partir de la clé d’une adresse mémoire ou d’un indice de tableau.
Opérations de recherche, d’adjonction et de suppression en temps moyen
constant.
Le temps d’accès ne dépend plus du nombre d’élément dans la structure.
é è
é è
è
Fin
Algorithmes complexes : Les 9 Algorithmes complexes : Les 10
Tables Tables
Exemple Exemple (Suite)
D’où les résultats suivant :
Soit E un ensemble de prénoms = { serge, odile, luc, anne, annie, jean, julie,
h ( serge ) = ( 54 + 5 ) mod 13 =
basile, marcel, élise}
7 Pos clé Élément
On associe à chaque élément e de E un nombre h ( e ) compris entre 0 et h ( odile ) = ( 45 + 5) mod 13 =
0 0 Luc
11
12
h ( luc ) = ( 36 + 3 ) mod 13 = 0
1 1
1. Attribuer aux lettres a, b, c, …, z les valeurs 1, 2, …, 26.
…
2 2 Basile
h ( élise ) = 3
2. Ajouter les valeurs de lettres de e.
3 3 Élise
3. Ajouter au nombre obtenu, le nombre de lettre de e.
h est injective : on peut ranger chaque
4 4 Paula
4. Calculer ce nombre modulo 13 pour obtenir le nombre h ( e ) recherché élément e à l’indice que l’on vient de
calculer
5 5
6 6 Marcel
h non injective : x ≠ x et h ( x ) = h (
1 2 1
x ) : collision primaire.
2 7 7 Serge
Il n’est pas possible dans le cas
8 8 jean
général d’éviter des collisions.
La fonction de hachage ne donne 9 9 Annie
pas accès à un élément mais à un
10 10 Julie
petit ensemble d’éléments en
petits morceaux. 11 11 Odile
12 12 Anne
Algorithmes complexes : Les 11 Algorithmes complexes : Les 12
Tables Tables
3Principes généraux du hachage Propriétés de la fonction de hachage
Gestion d’une collection C d’éléments, les clé appartiennent à univers U très Calcul de la fonction de hachage aussi rapide que possible.
grand.
La fonction doit être uniforme afin de limiter les collisions :
Taille de C relativement petite par rapport au nombre d’éléments de U
∀ x ∈ U et ∀ i ∈ [ 1..m ], probabilité ( h ( x ) = 1 ) = ( 1 / m )
Exemple :
C est un ensemble de 1000 mots de 10 lettres
Il faut gérer les inévitables collisions ; deux grands types de techniques :
U est l’ensemble de tous les mots possibles de 10 lettres
13
card ( U ) = 10 Les méthodes de résolution des collisions par chaînage.
Les méthodes de résolution des collisions par calcul.
On ne peut réserver une place mémoire pour chacun des éléments de U
On utilise une fonction de hachage h :
h : U [ 1..m ]
où l’entier m est choisi en fonction de la taille de C
La fonction de hachage h n’est pas injective.
x, clé,