Structures de données Tables de hachage et graphes Flashcards
quelle est l’utilité et les contraintes de la table de hachage (HashTable)
utilité • Permet d’insérer, supprimer et chercher des éléments en O(1) Contraintes: • Ordre des éléments n’est pas important • Performance dépend de la fonction de hachage
Ce qu’il faut décider lors de la
conception de la table de hachage (HashTable)
• Déterminer la fonction de hachage • Déterminer la taille de la table • Déterminer stratégie de résolution des collisions
différente opération pour la table de hachage (HashTable) et le temps moyen de la comception de celle-ci
Insertion
suppression
recherche
Une bonne conception permet un temps moyen de
O(1) pour l’insertion et la recherche.
qu’est ce que les dimension de la table? et de quoi elle dépend
La dimension de la table est le nombre d’emplacements (« buckets ») disponibles
La dimension dépend de la fonction de hachage et de la stratégie de résolution des conflits
comment déterminer facilement la table de hachage
Une bonne règle du pouce pourrait être:
• Pour une bonne performance, il ne faut pas que le nombre d’éléments
dépasse 75% de la capacité totale de la table
• Donc, la taille du tableau devrait être d’environ 1.3 fois le nombre
maximum de clés qu’elle devra contenir
• Dimension du tableau devrait être un nombre premier
Que se passe-t-il si l’estimation est mauvaise?
• Table trop petite, il faudra éventuellement en créer une plus grande et
« rehasher » tous les éléments
• Table trop grande, on gaspille potentiellement de l’espace
quelle est la fonction de l’hachage et comment choisir la fonction
La fonction de hachage fait l’association
entre la clé et un index dans la table
• Doit-être facile et rapide à calculer • Devrait distribuer les clés de façon la plus uniforme possible • Réduis les risques de collision • Ne dois pas être aléatoire
quelle serait la fonction simple Si les clés sont des entiers?
• h(clé) = clé mod |T|
• Cette fonction distribue uniformément les clés
lorsque les celles-ci sont insérer aléatoirement.
Qu’est-ce qui se passe si la table est de dimension
100 et que toutes les clés sont des multiples de 10?
• En pratique, il est préférable que la taille de la
table soit un nombre premier.
voir exemple chaine de caractèere pour table de hachage
dia 9 a 12
quelles sont les Techniques pour la gestion des collisions
- Par listes chaînées
- Adressage ouvert
- Double hachage
- Etc.
qu’est ce que la Résolution par liste chaînée
Chaque élément du tableau est la tête d’une liste
chaînée
• Lors d’une collision, les éléments sont ajoutés à
la liste
voir ex dia 15 16
quels sont les avantage et inconvénient de la Résolution par liste chaînée
Avantages
traitement simple des collisions
traitement simple des suppressions
• Il suffit d’éliminer l’élément de la liste
Le nombre de données peut dépasser la grandeur de
la table.
Inconvénients:
La liste peut devenir très longue
• De trop longues listes réduisent l’efficacité de la table de hachage
Plus de mémoire à cause des pointeurs
• Particulièrement important lorsque la taille des données est petite
Le pire cas absolu:
•Tous les éléments dans une seule liste
• Causé par une mauvaise fonction de hachage
quel est le principe de la Résolution par adressage ouvert
Principe:
• Tous les éléments sont stockés directement dans la
table
• Lorsqu’il y a une collision, il faut chercher une autre
case disponible
quels sont les avantage et inconvénient de la Résolution par adressage ouvert
Avantages:
• Pas besoin de structures supplémentaires
• Pas besoin d’allouer/libérer de la mémoire lors des
insertions/suppressions
Inconvénients:
• Insertions plus lentes, ça peut être long avant de
trouver un nouvel emplacement
• Table doit être plus grande pour obtenir le même
genre de performance
• La suppression est difficile à gérer
quel est le principe de la Résolution par Sondage linéaire
• Lorsque l’emplacement à l’index h(k) est occupé, la case suivante est explorée• F(i) est une fonction linéaire de i
voir ex dia 21 et 22
quel est le principe de la Résolution par Sondage quadratique
F(i) est une fonction quadratique de i
quel est le principe de la Résolution par doublage de hachage
Lors d’une collision, une deuxième fonction de
hachage est utilisée pour déterminer le saut
explique le Sondage aléatoire
• Utilise un générateur de nombre aléatoire pour obtenir
l’incrément
• Le générateur devrait toujours générer le même nombre
aléatoire si la semence de départ est la même
• Cette méthode évite le regroupement avec succès
• Généralement moins rapide que les autres
il existe une autre méthode laquelle
Mettre au point une fonction incrémentielle qui
dépend de la clef.
défini un graphe
Un graphe est défini par G = (V,E) où:
• V est un ensemble de nœuds
• E est un ensemble de transitions entre les noeuds
énumère et décrit les deux type de graphes
Type de graphes
• Orienté : une transition (u,v) permet une
transition de u à v seulement.
• Non-orienté: une transition (u,v) permet une
transition de u à v et de v à u.
qu’est qu’un Graphe pondéré
Graphe où un coût (poids) est associé à chacune
des transitions.
Chemin (path)
un chemin p , aussi noté v1~v4 , est une
séquence de transitions consécutives reliant v1 à v4
Noeuds adjacents (voisins):
Noeuds successeurs :
Noeuds adjacents (voisins): un noeud v2 est adjacent
à v1 s’il existe une transition (v1,v2).
Noeuds successeurs : un noeud v2 est un successeur
de v1 s’il existe un chemin v1~v2
que représente les matrices
Les transitions sont représentées par un tableau à deux
dimensions.
Liste d’adjacences
Chaque nœud possède une liste de ses nœuds adjacents
compare les matrice d’adjacences et les Liste d’adjacences
Liste d’adjacences
– Bonne performance pour tous les graphes
– Un peu plus compliqué à implémenter
• Mais plus de flexibilité
Matrice d’adjacences
– Meilleur choix lorsque le graphe est dense
• |E| est O(|V|2), ça fait de longues listes
– Difficile de faire des modifications
• Préférable lorsqu’il y peu d’insertion et de suppression de
nœuds.
est ce qu’on peut parcourir un graph dans deux sens largeur ou profondeur d’abord?
oui
Largeur d’abord: à partir d’un nœud v, on visite
d’abord tous les voisins de v avant d’aller plus
en profondeur dans le graphe.
Profondeur d’abord: recherche tous les
successeurs possibles d’un nœud avant de
parcourir les autres voisins de ce nœud.
ex 37 a 40
à quoi la Le tri topologique peut être appliqué
au graphe
acyclique (sans cycle) seulement.
qu’est que Le tri topologique d’un graphe G = (V,E)
Le tri topologique d’un graphe G = (V,E) est une liste
linéaire des noeuds telle que s’il existe une transition
(u,v), u précède v dans la liste.
Comment peuvent être vu Le tri topologique
comme un alignement
de ses sommets le long d’une ligne horizontale de
manière que tous les arcs soient orientés de gauche à
droite.
ex dia 42 a 44
quelle est la définition d’un Composantes fortement connectées
Définition: Une composante (graphe ou sous-graphe) est fortement connectée s’il existe un chemin entre tous les nœuds de ladite composante.
qu’Est ce que le Théorème de Euler
Un chemin parcourant toutes les transitions une seule
fois est possible si et seulement si:
• tous les nœuds ont un degré pair
• si seulement deux nœuds ont un degré impair.
nomme moi les étapes de Algorithme de Fleury
- Vérifier que le graphe est entièrement connecté et que tous les nœuds ont un degré pair et pas plus de 2 nœuds avec un degré impair
- Démarrer à un nœud avec un degré impair si non démarrer avec n’importe quel nœud
- Choisir une transition dont la suppression ne déconnecte pas un sous graphe non visité
- Marquer la transition comme étant effacée
- Retourner à l’étape 3 tant qu’il reste des transitions accessibles.
décrit le Chemin Hamiltonien et son algorithme
Un chemin Hamiltonien est un chemin qui passe
par chacun des nœuds d’un graphe seulement une
fois.
Algorithme:
Il n’y a pas d’algorithme connue qui
résout ce problème efficacement.
Automate à états finis est formellement représenté par
un 5-tuple
voir dia 56 pour symboles
ex 57 a 60
qu’est ce qu’une Construction d’une expression régulière
Une expression régulière est une notation qui permet de spécifier un ensemble de chaînes de symboles.
en quoi consiste Algorithme du retour en arrière :
Consiste à choisir un chemin si ça ne fonctionne pas, il faut retourner en arrière pour recommencer un autre chemin
ex 63 a 69
