Changes between Version 29 and Version 30 of CaoCourseTme2
- Timestamp:
- Feb 17, 2007, 5:15:56 PM (18 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
CaoCourseTme2
v29 v30 34 34 Le programme fourni compte le nombre de mots d'un fichier texte et indique le nombre total 35 35 de mots dans le fichier et le nombre de mots différents. Vous devrez modifier ce programme de façon 36 à ce qu'il indique, pour chaque mot: 37 * le nombre d'occurences 38 * les numéros de toutes les lignes où il est présent 36 à ce qu'il indique, pour chaque mot, les numéros de toutes les lignes où le mot est présent 39 37 40 Vous donnerez également des statistiques sur l'usage des tables de hachage: 41 * taux de remplissage. 42 * moyenne du nombre de comparaisons nécessaire lors de la recherche d'un mot 38 Vous donnerez également des statistiques sur l'usage des tables de hachage, telles que le nombre moyen de comparaisons nécessaire lors de la recherche d'un mot 43 39 44 40 = Description des sources et principe des tables de hachage = … … 52 48 53 49 Une table de hachage est une structure de données permettant de stocker des 54 ensembles d'éléments, où chaque élément est un couple de la forme (clé, valeur).55 Le plus souvent la clé est une chaîne de caractères. La valeur peut être un nombre56 ou une structure de données quelconque.57 Le principal objectif d e cette structure est d'accélérer la recherche d'un élément50 ensembles contenant un nombre quelconque d'éléments, où chaque élément est un couple 51 de la forme (clé, valeur). Le plus souvent la clé est une chaîne de caractères. 52 La valeur peut être un nombre ou une structure de données plus ou moins complexe. 53 Le principal objectif d'une table de hachage est d'accélérer la recherche d'un élément 58 54 par sa clé. 59 55 60 56 Pour représenter un ensemble de couple (clé, valeur) la méthode la plus simple 61 consiste à les réunir dans une liste chainée.57 consiste à les stocker dans une liste chainée. 62 58 La recherche d'un élément se fait alors par un parcours de la liste, donc de 63 l'ensemble des éléments. 64 Cette solution n'est évidemment pas satisfaisante si le nombre d'élément est 65 grand. 59 l'ensemble des éléments, ce qui n'est pas très efficace si le nombre d'élément est grand. 66 60 67 61 Pour accélérer la recherche, on créé un tableau de listes chainées. Le nombre de … … 69 63 que l'on souhaite gérer. Si on veut gérer 1000 éléments, il faut un tableau 70 64 d'environ 1000 cases. 71 On définit ensuite une fonction, que l'on nomme fonction de hachage, donnant72 un index de caseà partir de la clé d'un élément.73 Un élément doit être rangé dans la liste chainée associée à la case d éfinie par la fonction de hachage74 appliquée sur la clé de cet élément.65 On définit ensuite une fonction, que l'on nomme '''fonction de hachage''', 66 qui calcule un index à partir de la clé d'un élément. 67 Un élément doit être rangé dans la liste chainée associée à la case du tableau 68 définie par l'index calculé par la fonction de hachage. 75 69 76 70 Pour que cette méthode soit efficace, il faut que les éléments se répartissent … … 78 72 Il existe plusieurs méthodes de calcul de l'index, nous vous 79 73 donnons celle proposé par Donald Knuth. 80 Dans la pratique, il n'est pas possible d'éviter les collisions. 81 Cela signifie que deux éléments de clés différentes peuvent avoir 82 le même index de hachage. 74 Dans la pratique, il n'est pas possible d'éviter les collisions, et deux éléments 75 ayant des clés différentes peuvent avoir le même index de hachage. 83 76 84 77 En résumé, pour ranger 1000 éléments, on fabrique un tableau de 1000 listes chainées avec l'espoir … … 86 79 qu'un tout petit nombre de listes contenant plus d'un élément. 87 80 88 La propriété principale d'une table de hachage est que si la taille de la table89 est du même ordre de grandeur que le nombre d'éléments présents, le temps de81 La propriété principale d'une table de hachage est que (si la taille de la table 82 est du même ordre de grandeur que le nombre d'éléments), le temps de 90 83 recherche est en O(1), c'est à dire indépendant du nombre d'éléments, (même pour 91 84 un million d'éléments).
