Travaux Pratiques du L1 année 2001-2002
Recouvrements dans un espace de Hamming
Objectifs : Il existe toujours au moins deux méthodes pour déterminer les solutions d'un problème délicat : la recherche exhaustive et la recherche aléatoire. Dans les deux cas, les chances de succès dépendent du nombre de solutions. Le plus souvent la recherche exhausitive donne lieu à un algorithme de backtracking. L'objectif de cette séance est d'utiliser ces approches pour déterminer des recouvrements optimaux des espaces de Hamming.
Temps : 1 séance de 3 heures.
Rayon de recouvrement. L'ensemble des n-uplets binaires est muni de la métrique qui compte le nombre de discordances entre les mots. Il s'agit de la distance de Hamming, et dans ce contexte, on parle d'espaces de Hamming. Si x et y désignent deux mots de l'espace de Hamming alors la distance de Hamming entre x et y est
Ham(x,y) := nombre de
position i telle que x[i]
!= y[i]
La distance entre un mot x et une partie Z est notée dist(x, Z). Elle est égale à la distance qui sépare x et un des points de Z parmi les plus proches.
dist( x, Z ) := minimum Ham(x,z)
quand
z
parcourt Z.
La distance maximale entre la partie Z et un point arbitraire de l'espace de Hamming s'appelle le rayon de recouvrement de Z, c'est donc :
R(Z) := maximum dist(
x, Z) quand x parcourt
l'espace de Hamming.
Dans les problèmes recouvrements, on recherche la taille minimale d'une partie de rayon donné, un nombre usuellement noté K(n,r). Déterminer la valeur exacte de K(n,r) est un problème théoriquement difficile et pratiquement impossible à résoudre quand n devient grand.
Quelques valeurs de K(n,r) pour n et r petits sont résumées dans la table ci-dessous, on constate que n=9 est le premier cas ouvert avec 57 <= K(9,1) <= 62. Pour en savoir plus, vous êtes invités à consulter la mise à jour de Simon Litsyn un des spécialistes de ces questions.
| n | R=1 | R=2 | R=3 |
| 1 | 1 | ||
| 2 | 2 | 1 | |
| 3 | 2 | 2 | 1 |
| 4 | c 4 L | 2 | 2 |
| 5 | c 7 S | 2 | 2 |
| 6 | f 12 S | c 4 L | 2 |
| 7 | a 16 L | c 7 Q | 2 |
| 8 | d 32 L | p 12 Q | c 4 L |
| 9 | t 57-62 W | q 16 L | c 7 Q |
L'objectif de ces travaux pratiques est de construire des codes de recouvrement optimaux de longueurs raisonnables. Nous traiterons uniquement des codes de longueurs n <= 13. Les plus joueurs pourront alors appliquer leurs résultats au football pool problem du LotoFoot !
[ 0 ] Dans la suite, on décide de représenter une partie de l'espace de Hamming de dimension n par un tableau de taille 2^n, le tableau Y représente la partie formée des indices y tels que Y[y] = 0. Justifier et commenter cette représentation.
[ 1 ] Le poids d'un mot est égal au nombre de ses composantes non nulles. Donner une relation entre distance de Hamming et poids. Ecrire les fonctions Hamming(x,y) et poids(x).[ 2 ] Ecrire les procédures recouvrir( z, Y. r) qui incrémente Y[y] pour chaque mot y du disque de centre z et de rayon r. Ecrire la procédure decouvrir(z, Y, r) qui fait le travail inverse.
[ 3 ] Implanter l'algorithme de recherche aléatoire ci-dessous :Aleatoire( r, n, nbi )
parmsr, n, nbi : entier;
var score : entier;
Y : tableau;debut
score := infini;
tantque ( nbi > 0 )
Y := vecteur nul
tmp := 0;
tantque ( non vide (Y) ) et ( tmp < score )
Choisir y au hasard tel que Y[y] = 0;
recouvrir( y, Y, r)
Inc(tmp);
ftq
score := min ( tmp, score);
dec ( nbi )
ftq
retourner ( score );
fin
[ 4 ] Quelles estimations de K(n,1) et K(n,2) trouvez vous ?[ 5 ] Implanter l'algorithme de backtracking ci-dessous. Comment doit-etre initialisée la variable globale score ? Comment lancer la recherche ?
[ 3 ] Quelles valeurs de K(n,1) et K(n,2) trouvez vous ?
Recherche( Y , r, cpt)
Y : tableau;
r : entier;
cpt : entier;
debut
si ( score <= cpt)
retourner
fsi;
si vide(Y)
score = cpt;
retourner;
fsi
inc ( cpt );
Pour chaque y tel que Y[y] = 0
recouvrir( y, Y, r);
Recherche( Y, r, cpt);
decouvrir( y, Y, r);
fip
fin
[ 4 ] Mettez de l'ordre dans votre programme pour supprimer les appels redondants.[ 5 ] Modifiez votre algorithme pour obtenir un code optimal.
[ 6 ] La solution de K(5, 1)=7 est aux abonnés absents... L'algorithme contient une erreur de conception, corrigez la !
[ 7 ] K(7, 1) = 16 est résalisé par un code parfait. Modifiez votre code pour retrouver ce résultat.
[ 8 ] Ecrire un algorithme hybride des deux approches.
Challenge.
Modifiez votre code pour résoudre le problème analogue en remplacant l'espace de Hamming par une boule de rayon donné. En d'autres termes, pour r < R< n donnés, il s'agit de déterminer une partie X de taille minimale telle que tout mot de la boule de rayon R dans l'espace de Hamming de dimension n soit à distance au plus r de X.