3.3 Probabilité d'erreur
51
Question : Pourquoi utilise-t-on le XOR pour calculer la valeur de hachage ?
Réponse : Utiliser le XOR pour coder une position a plusieurs avantages :
- Le XOR est une opération très rapide sur les bits.
- Pour ôter un élément de la position et défaire un XOR, il suffit de refaire le XOR
avec la même valeur. En effet (a XOR b) XOR b =a.
- Le XOR de valeurs aléatoires bien réparties donne une valeur aléatoire bien répartie. Ce qui est important pour diminuer la probabilité d'erreur et de collision.
- La valeur de hachage d'une position peut être calculée incrémentalement. Pour cela
il suffit de faire des XOR entre la valeur de hachage de la position précédente et les
nombres aléatoires correspondant aux éléments enlevés et aj outés à la position.
Exercice : É crire une fonction qui joue un coup au Tic-Tac-Toe et une fonction qui
déjoue un coup, en mettant à jour incrémentalement la valeur de hachage.
3.3 Prob ab ilité d'e rreur
"L' ordinateur vous permet de faire plus d'erreurs plus vite que n'importe quelle autre
invention de l'histoire de l'humanité, à l'exception possible des armes à feu et de la tequila."
Mitch Ratcliffe.
Il y a deux types d'erreurs :
- Une erreur de type 1 intervient quand deux positions différentes ont des valeurs de
hachage égales. Un moyen de détecter ces erreurs est de tester si le meilleur coup
mémorisé dans cette position est légal. La probabilité d'une erreur de type 1 est
diminuée quand on augmente le nombre de bits dans la valeur de hachage.
- Une erreur de type 2 intervient lorsque deux positions différentes ont le même indice dans la table de transposition mais pas la même valeur de hachage. Cette erreur est définie comme une collision [50). Lorsqu'on a une collision, on doit choisir
entre les deux positions celle qui doit être gardée dans la table de transposition. La
probabilité d'avoir une collision est diminuée quand on augmente la taille de la
table de transposition.
Exercice : Soit N le nombre de valeurs possibles et M le nombre de positions différentes qui vont être stockées dans la table de transposition. Donner une approximation
de la probabilité P que les M positions aient des valeurs de hachage différentes si M
est petit par rapport à N. Quelle est la probabilité d'avoir au moins une erreur de type 1
quand on utilise IO millions de fois la table de transposition avec des valeurs de hachage
sur 32 bits ? Même question avec des valeurs de hachage sur 64 bits ?
51
Question : Pourquoi utilise-t-on le XOR pour calculer la valeur de hachage ?
Réponse : Utiliser le XOR pour coder une position a plusieurs avantages :
- Le XOR est une opération très rapide sur les bits.
- Pour ôter un élément de la position et défaire un XOR, il suffit de refaire le XOR
avec la même valeur. En effet (a XOR b) XOR b =a.
- Le XOR de valeurs aléatoires bien réparties donne une valeur aléatoire bien répartie. Ce qui est important pour diminuer la probabilité d'erreur et de collision.
- La valeur de hachage d'une position peut être calculée incrémentalement. Pour cela
il suffit de faire des XOR entre la valeur de hachage de la position précédente et les
nombres aléatoires correspondant aux éléments enlevés et aj outés à la position.
Exercice : É crire une fonction qui joue un coup au Tic-Tac-Toe et une fonction qui
déjoue un coup, en mettant à jour incrémentalement la valeur de hachage.
3.3 Prob ab ilité d'e rreur
"L' ordinateur vous permet de faire plus d'erreurs plus vite que n'importe quelle autre
invention de l'histoire de l'humanité, à l'exception possible des armes à feu et de la tequila."
Mitch Ratcliffe.
Il y a deux types d'erreurs :
- Une erreur de type 1 intervient quand deux positions différentes ont des valeurs de
hachage égales. Un moyen de détecter ces erreurs est de tester si le meilleur coup
mémorisé dans cette position est légal. La probabilité d'une erreur de type 1 est
diminuée quand on augmente le nombre de bits dans la valeur de hachage.
- Une erreur de type 2 intervient lorsque deux positions différentes ont le même indice dans la table de transposition mais pas la même valeur de hachage. Cette erreur est définie comme une collision [50). Lorsqu'on a une collision, on doit choisir
entre les deux positions celle qui doit être gardée dans la table de transposition. La
probabilité d'avoir une collision est diminuée quand on augmente la taille de la
table de transposition.
Exercice : Soit N le nombre de valeurs possibles et M le nombre de positions différentes qui vont être stockées dans la table de transposition. Donner une approximation
de la probabilité P que les M positions aient des valeurs de hachage différentes si M
est petit par rapport à N. Quelle est la probabilité d'avoir au moins une erreur de type 1
quand on utilise IO millions de fois la table de transposition avec des valeurs de hachage
sur 32 bits ? Même question avec des valeurs de hachage sur 64 bits ?