Structures de données Tables de hachage et graphes

Question 1

quelle est l’utilité et les contraintes de la table de hachage (HashTable)

Answer 1

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

Question 2

Ce qu’il faut décider lors de la

conception de la table de hachage (HashTable)

Answer 2

• Déterminer la fonction de
hachage
• Déterminer la taille de la table
• Déterminer stratégie de
résolution des collisions

Question 3

différente opération pour la table de hachage (HashTable) et le temps moyen de la comception de celle-ci

Answer 3

Insertion
suppression
recherche

Une bonne conception permet un temps moyen de
O(1) pour l’insertion et la recherche.

Question 4

qu’est ce que les dimension de la table? et de quoi elle dépend

Answer 4

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

Question 5

comment déterminer facilement la table de hachage

Answer 5

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

Question 6

Que se passe-t-il si l’estimation est mauvaise?

Answer 6

• 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

Question 7

quelle est la fonction de l’hachage et comment choisir la fonction

Answer 7

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

Question 8

quelle serait la fonction simple Si les clés sont des entiers?

Answer 8

• h(clé) = clé mod |T|
• Cette fonction distribue uniformément les clés
lorsque les celles-ci sont insérer aléatoirement.

Question 9

Qu’est-ce qui se passe si la table est de dimension

100 et que toutes les clés sont des multiples de 10?

Answer 9

• En pratique, il est préférable que la taille de la

table soit un nombre premier.

Question 10

voir exemple chaine de caractèere pour table de hachage

Answer 10

dia 9 a 12

Question 11

quelles sont les Techniques pour la gestion des collisions

Answer 11

• Par listes chaînées
• Adressage ouvert
• Double hachage
• Etc.

Question 12

qu’est ce que la Résolution par liste chaînée

Answer 12

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

Question 13

quels sont les avantage et inconvénient de la Résolution par liste chaînée

Answer 13

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

Question 14

quel est le principe de la Résolution par adressage ouvert

Answer 14

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

Question 15

quels sont les avantage et inconvénient de la Résolution par adressage ouvert

Answer 15

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

Question 16

quel est le principe de la Résolution par Sondage linéaire

Answer 16

• 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

Question 17

quel est le principe de la Résolution par Sondage quadratique

Answer 17

F(i) est une fonction quadratique de i

Question 18

quel est le principe de la Résolution par doublage de hachage

Answer 18

Lors d’une collision, une deuxième fonction de

hachage est utilisée pour déterminer le saut

Question 19

explique le Sondage aléatoire

Answer 19

• 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

Question 20

il existe une autre méthode laquelle

Answer 20

Mettre au point une fonction incrémentielle qui

dépend de la clef.

Question 21

défini un graphe

Answer 21

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

Question 22

énumère et décrit les deux type de graphes

Answer 22

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.

Question 23

qu’est qu’un Graphe pondéré

Answer 23

Graphe où un coût (poids) est associé à chacune

des transitions.

Question 24

Chemin (path)

Answer 24

un chemin p , aussi noté v1~v4 , est une

séquence de transitions consécutives reliant v1 à v4

Question 25

Noeuds adjacents (voisins):

Noeuds successeurs :

Answer 25

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

Question 26

que représente les matrices

Answer 26

Les transitions sont représentées par un tableau à deux

dimensions.

Question 27

Liste d’adjacences

Answer 27

Chaque nœud possède une liste de ses nœuds adjacents

Question 28

compare les matrice d’adjacences et les Liste d’adjacences

Answer 28

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.

Question 29

est ce qu’on peut parcourir un graph dans deux sens largeur ou profondeur d’abord?

Answer 29

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

Question 30

à quoi la Le tri topologique peut être appliqué

Answer 30

au graphe

acyclique (sans cycle) seulement.

Question 31

qu’est que Le tri topologique d’un graphe G = (V,E)

Answer 31

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.

Question 32

Comment peuvent être vu Le tri topologique

Answer 32

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

Question 33

quelle est la définition d’un Composantes fortement connectées

Answer 33

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.

Question 34

qu’Est ce que le Théorème de Euler

Answer 34

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.

Question 35

nomme moi les étapes de Algorithme de Fleury

Answer 35

1. 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
2. Démarrer à un nœud avec un degré impair si non démarrer avec n’importe quel nœud
3. Choisir une transition dont la suppression ne déconnecte pas un sous graphe non visité
4. Marquer la transition comme étant effacée
5. Retourner à l’étape 3 tant qu’il reste des transitions accessibles.

Question 36

décrit le Chemin Hamiltonien et son algorithme

Answer 36

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.

Question 37

Automate à états finis est formellement représenté par

Answer 37

un 5-tuple
voir dia 56 pour symboles

ex 57 a 60

Question 38

qu’est ce qu’une Construction d’une expression régulière

Answer 38

Une expression régulière est une notation qui permet de spécifier un ensemble de chaînes de symboles.

Question 39

en quoi consiste Algorithme du retour en arrière :

Answer 39

Consiste à choisir un chemin si ça ne fonctionne pas, il faut retourner en arrière pour recommencer un autre chemin
ex 63 a 69