| ⋆⋆⋆ |
Un texte est défini comme une suite (finie) de 0 et 1. Les entiers 0 et 1 sont les chiffres d’une représentation des entiers en base deux, par la suite on les appelle « bits ».
Question 1. Donner un automate fini déterministe (DFA) qui décrit le langage des textes où le bit 1 apparaît un nombre pair de fois.
|
L’automate :
|
En Java nous représentons les bits par les booléens,
à savoir false (pour 0) et true (pour 1).
Les textes sont représentés en machine comme
des tableaux de bits (type boolean []).
Enfin, les canaux de transmission sont représentés en machine par
des objets qui implémentent l’interface suivante Channel.
La méthode read renvoie les bits dans l’ordre du texte transmis,
tandis que la méthode isOver permet de déterminer si la transmission
est terminée ou pas.
À titre d’exemple de la lecture d’un canal, voici une méthode
qui lit le texte transmis sur un canal c
et l’affiche sur la sortie standard.
Question 2.
Nous modélisons l’émetteur du texte comme un objet
d’une classe ArrayChannel qui implémente l’interface Channel.
Le constructeur ArrayChannel (boolean [] t) prend en argument
un tableau de bits t dont les éléments pris dans l’ordre
définissent le texte.
En pratique, on peut partir du squelette suivant :
Remarque Nous prions les élèves de bien vouloir
excuser la rédaction de cette question.
En effet,
il manque une question précise « Écrire la classe ArrayChannel ». Nous espérons que notre présence dans la salle d’examen a permis de minimiser les conséquences de cet oubli. Cela étant dit, voici un code solution. class ArrayChannel implements Channel {
private boolean [] t ;
private int idx ;
ArrayChannel (boolean [] t) {
this.t = t ; idx = 0 ;
}
public boolean isOver() { return idx >= t.length ; }
public boolean read() {
if (isOver()) throw new Error ("No bit available") ;
return t[idx++] ;
}
} |
Nous modélisons
le récepteur comme une méthode
static boolean [] readAll(Channel c) qui prend en argument un
canal c, lit le texte transmis sur ce canal, et renvoie le
texte reçu.
Compte tenu de ce que la taille d’un texte n’est pas connue à l’avance,
les bits du texte seront d’abord stockés dans une liste qui sera finalement
convertie en tableau.
Question 3. Écrire une classe List des cellules de liste de bits.
|
class List {
boolean val ;
List next ;
List (boolean val, List next) {
this.val = val ; this.next = next ;
}
} |
Question 4. Écrire une méthode static boolean [] toArray(List p)
qui transforme une liste de bits en tableau.
|
static boolean [] toArray(List p) {
// D'abord calculer la longueur de la liste
int len = 0 ;
for (List q = p ; q != null ; q = q.next) len++ ;
// Puis allouer/remplir le tableau
boolean [] t = new boolean[len] ;
int k = 0 ;
for (List q = p ; q != null ; q = q.next) {
t[k] = q. val ; k++ ;
}
return t ;
} |
Question 5. Écrire la méthode static boolean [] readAll(Channel c)
de réception du texte lu sur le canal c.
|
Il faut bien faire attention à construire la liste de bits selon
l’ordre de lecture.
private static List readRec(Channel c) {
if (c.isOver()) {
return null ;
} else {
return new List (c.read(), readRec(c)) ;
// ok, car les arguments sont évalués de la gauche vers la droite.
}
}
static boolean [] readAll(Channel c) {
List p = readRec(c) ;
return toArray(p) ;
} |
En réalité, la transmission d’un texte d’une machine à une autre peut se faire incorrectement. Nous adoptons un modèle simple, où la seule sorte d’erreur possible est l’inversion d’un bit (0 est émis et 1 est reçu, ou le contraire), et où au plus un bit est inversé.
Question 6.
Pour modéliser un canal avec erreurs, nous introduisons
la classe UnsafeChannel :
UnsafeChannel implémente l’interface Channel.
UnsafeChannel(Channel c) prend un canal c
en argument.
Un objet de la classe UnsafeChannel
lit et retransmet les bits lus sur c, et ceci bit par bit.
Lors de la retransmission d’un bit, si l’erreur n’est pas encore survenue
et dans un cas sur 256, le bit est retransmis inversé.
Écrire la classe UnsafeChannel.
Pour tirer au hasard un nombre entre 0 (inclus) et n (exclu)
on utilisera la méthode nextInt(int n) d’un
objet de la classe de bibliothèque Random (package java.util).
|
import java.util.* ;
class UnsafeChannel implements Channel {
private Channel c ;
private Random rand ;
private boolean noErrorYet ;
UnsafeChannel (Channel c) {
this.c = c ;
rand = new Random () ;
noErrorYet = true ;
}
public boolean isOver() { return c.isOver() ; }
public boolean read() {
boolean b = c.read() ;
if (noErrorYet && rand.nextInt(256) == 0) {
noErrorYet = false ;
return !b ; // ou if (b) return false else return true ;
} else {
return b ;
}
}
} |
Question 7. Écrire une méthode
static boolean add(boolean b1,boolean b2)
qui renvoie le bit égal à la somme (modulo 2) des deux bits b1
et b2.
|
Si on connaît le ou exclusif, c’est assez rapide.
static boolean add(boolean b1,boolean b2) { return b1 ^ b2 ; } Ou même : static boolean add(boolean b1,boolean b2) { return b1 != b2 ; } Si on a pas vu le truc, ce n’est guère plus difficile. static boolean add(boolean b1,boolean b2) {
if (b1) {
if (b2) { return false ; } else { return true ; }
} else {
if (b2) { return true ; } else { return true ; }
}
} |
La somme de contrôle d’un texte est définie comme la somme de ses bits (toujours modulo 2).
Question 8.
Écrire une méthode static boolean checkSum(boolean [] t) qui
renvoie la somme de contrôle du texte passé en argument.
|
static boolean ckeckSum(boolean [] t) {
boolean r = false ;
for (boolean b : t) r = add(r,b) ;
return r ;
} |
Question 9. Pour cette question seulement, on considère un canal non-sûr quelconque qui peut inverser plus d’un bit du texte transmis, sans en changer la taille. Que peut-on dire de la la transmission du message quand les sommes de contrôle des textes émis et reçu sont distinctes ?
| Un nombre impair de bits sont erronés. En effet, changer un bit dans un texte en inverse la somme (modulo 2). |
Nous supposons toujours qu’au plus une erreur surviendra. Dans ces conditions, il est possible de détecter l’existence de l’erreur, puis sa position.
Une position dans un texte de taille n est un entier
pris entre 0 (compris) et n (exclu) — c’est tout simplement un indice
dans le tableau boolean [].
La liste de contrôle d’ordre k (k entier naturel)
est la liste des positions i telles que
i mod 2k+1 < 2k
(mod est l’opérateur « reste de la
division euclidienne », noté % en Java).
Question 10. Pour n=16, donner les listes de contrôle pour k variant de 0 à 4.
|
Afin de lever toute ambiguïté dans les réponses, nous fixons les notations de l’écriture en base deux des entiers. Soit x entier naturel quelconque, et soit m entier tel que 2m > x. L’écriture binaire (de taille m+1) de x est l’unique suite de bits, notée cette fois à l’envers bmbm−1⋯b1b0, telle que x = ∑k=0k=m bk · 2k. Par exemple, l’écriture binaire de taille 4 de l’entier 5 est 0101.
Question 11. Reformuler la définition de la liste de contrôle d’ordre k en considérant l’écriture binaire des positions pour m suffisamment grand.
| La liste de contrôle d’ordre k est l’ensemble des positions dont le bit d’indice k est nul. En effet, si x est représenté par bmbm−1⋯b1b0, alors x mod 2k+1 est représenté par une suite de 0, suivie de bkbk−1⋯b1b0 et est donc strictement inférieur à 2k si et seulement si le bit bk est nul. |
On représente les listes de contrôle comme des listes de positions
croissantes.
Voici CheckList, une classe des cellules de liste de contrôle.
Question 12.
Écrire une méthode
static CheckList buildList(int k, int n)
qui renvoie la liste de contrôle d’ordre k pour n donné en argument.
|
Avec la première définition.
static CheckList buildList(int k, int n) {
int dk = 1;
for (int i = 0 ; i < k ; i++) dk *= 2 ; // dk = 2k
int dkp = 2*dk ; // dkp = 2k+1
CheckList c = null;
for (int i = n-1 ; i >= 0 ; i--) {
if(i % dkp < dk) c = new CheckList(i,c);
}
return c;
} Selon la définition à l’aide de la représentation binaire. static boolean bitUnset(int i, int k) {
return (i & (1 << k)) == 0 ;
}
static CheckList buildList(int k, int n) {
CheckList c = null;
for (int i = n-1; i >= 0 ; i--) {
if(bitUnset(i,k)) c = new CheckList(i, c);
}
return c;
} |
Pour tout entier n > 0 on considère l’entier noté ⌈log2 n⌉ et défini comme le plus petit entier m tel que n ≤ 2m.
Question 13.
Écrire une méthode static int ceilLog2(int n)
qui renvoie ⌈log2 n⌉.
|
static int ceilLog2(int n) {
int r = 0, d = 1 ; // NB. d = 2r
while (d < n) {
d *= 2 ; r++ ; // NB. d = 2r
}
// NB. r = 1+max{ k ∣ 2k < n } = min{ k ∣ 2k ≥ n }
return r ;
} |
Les listes de contrôle servent à construire le vecteur de contrôle tc qui est fonction d’un texte t de taille n. Le vecteur de contrôle est un texte de taille ⌈log2 n⌉+1. Le bit en position k dans tc est appelé somme de contrôle d’ordre k de t. Ce bit est défini comme la somme (modulo 2) de tous les bits du texte original dont la position appartient à la liste de contrôle d’ordre k. On remarquera que le dernier élément de tc est la somme de contrôle de t, qui est donc aussi la somme de contrôle d’ordre ⌈log2 n⌉ de t.
Question 14.
Écrire une méthode static boolean [] checkVector(boolean [] t) qui
renvoie le vecteur de contrôle du texte t.
|
static boolean [] checkVector(boolean [] t){
int n = t.length ;
int sz = ceilLog2(n)+1 ;
boolean [] tc = new boolean [sz];
for(int k = 0; k < sz ; k++){
tc[k] = false ; // Inutile, mais plus clair.
for (CheckList p = buildList(k, n) ; p != null ; p = p.next) {
tc[k] = add(t[p.pos], tc[k]) ;
}
}
return tc ;
} |
Question 15. Évaluer la complexité de la méthode précédente.
| La taille du vecteur de contrôle de l’ordre de log2 n. Pour chacun de ses éléments, le coût dominant est celui de la construction de la liste de contrôle, qui est de l’ordre de n. Le coût de la méthode est donc de l’ordre de nlog2 n. |
On précise les conditions de transmission du texte. Le texte est transmis par un canal non-sûr. On note ts le texte envoyé, et tr le texte reçu. On se place toujours dans le cas de au plus une erreur, c’est-à-dire de au plus une inversion de bit.
Le vecteur de contrôle du texte original, noté tc, est envoyé par un canal sûr. Le récepteur connaît donc exactement tc. Par ailleurs, le récepteur peut calculer le vecteur de contrôle de tr, noté tc′,
Question 16. On suppose que le texte reçu tr contient exactement une erreur. Soit p la position de cette erreur. Montrer que le bit d’indice k de p vaut zéro, si et seulement si tc[k] et tc′[k] diffèrent.
| Inverser un bit dans un paquet quelconque de bits en inverse la somme modulo 2. Le résultat découle ensuite de la réponse à la question 11, à savoir que la liste de contrôle d’ordre k est exactement l’ensemble des positions dont le bit d’indice k est nul. |
Question 17.
Écrire static boolean [] readAllCorrected(Channel c, Channel cc),
une méthode
qui renvoie le message ts émis sur le canal non-sûr c.
Le canal cc est sûr et sert à la transmission du vecteur de
contrôle tc.
|
static boolean [] reallAllCorrected(Channel c, Channel cc) {
boolean [] tr = readAll(c), tc = readAll(cc) ;
boolean [] tcc = checkVector(tr) ;
int sz = tc.length ;
if (tc[sz-1] == tcc[sz-1]) return tr ;
// Il y a une erreur
int p = 0 ;
for (int k = sz-2 ; k >= 0 ; k--) {
if (tc[k] == tcc[k]) p = p + 1 ; // Ou p |= 1
p *= 2 ; // Ou p <<= 1
}
tr[p] = !tr[p] ; // Corriger le bit.
return tr ;
} On notera que la position p est construite des bits les plus
significatifs vers les moins significatifs.
On peut très bien écrire aussi.
int p = 0, k = 0, d = 1 ; // d est 2k
while (k < sz-1) {
if (tc[k] == tcc[k]) p += d ;
k++ ; d *= 2 ; // d est toujours 2k
} |
Lors du calcul des sommes de contrôle, certaines additions sont effectuées plusieurs fois. Pour limiter le nombre d’additions modulo 2, nous introduisons une structure d’arbre, qui mémorise les additions intermédiaires.
Commençons par le cas simple des textes de taille 2n. L’arbre est un arbre binaire strict, dont chaque sommet porte un bit. À tout texte de taille 2n on associe un arbre de la façon suivante.
La figure 1 donne un un exemple d’arbre et du texte correspondant.
Question 18. Combien l’arbre d’un texte de taille 2n contient-il de sommets ?
De toute évidence 2n+1−1 sommets, comme on le démontre facilement
à partir de la définition, si on y tient.
En effet, on a la récursion :
|
class Tree { boolean sum ; Tree left, right ; // Fils gauche et droit. Tree (boolean b) { // Constructeur des feuilles this.sum = b ; } Tree (Tree left, boolean b, Tree right) { // Constructeur des sommets internes. this.left = left ; this.right = right ; this.sum = b ; } }
Question 19.
Écrire une méthode static Tree buidTree(boolean [] t)
qui renvoie l’arbre associé au texte t
(dont la taille est de la forme 2n).
La classe des sommets d’arbre est donnée par la figure 2.
On prendra soin d’écrire une méthode de complexité linéaire
en la taille du texte.
|
Un code sans copie de tableau :
// Renvoie l'arbre de t[a...b[.
static Tree buildTree(boolean [] t, int a, int b) {
if (a+1 == b) {
return new Tree (t[a]) ;
} else {
int m = (a+b)/2 ;
Tree left = buildTree(t, a, m) ;
Tree right = buildTree(t, m, b) ;
return new Tree (left, Bit.add(left.sum, right.sum), right) ;
}
}
static Tree buildTree(boolean [] t) {
return buildTree(t, 0, t.length) ;
} La complexité linéaire est atteinte,
puisque chaque appel de la méthode buildTree
ne procède en propre qu’à des opérations de coût constant,
et qu’il y a de l’ordre de 2n+1 appels au total
(compter les sommets de l’arbre produit).On notera qu’un code qui calculerait des sous-tableaux serait de complexité de l’ordre de n 2n. En effet, chaque appel pour un tableau de taille m procéderait alors à de l’ordre de m opérations (allouer deux tableaux de taille moitié). Pour une profondeur de récursion k donnée, l’ordre de grandeur est donc 2k fois 2n−k. Soit un coût en 2n pour chaque profondeur de récursion. Il en irait de même d’une solution qui recalculerait les sommes au lieu de les extraire des sous-arbres. |
Question 20. Calculer (à la main) le vecteur de contrôle du texte de la figure 1 à l’aide de l’arbre, en s’efforçant de limiter le nombre d’additions de bits effectuées.
|
Le vecteur de contrôle contient ici 4 sommes. On repère les étages de l’arbre par des entiers croissants : de 0 pour les feuilles, à 3 pour la racine, on note que cette numérotations correspond aux indices du vecteur de contrôle.
|
Question 21. Relier le chemin vers une feuille donnée de l’arbre et la représentation binaire de la position dans le texte du bit contenu dans la feuille. Les chemins sont des suites de zéros et de uns, où zéro signifie « à gauche » et un « à droite ». Par exemple le chemin vers la quatrième feuille de l’arbre de la figure 1 est noté 011.
| Par construction, le chemin est la représentation binaire de la position. |
Question 22. Écrire une méthode
static boolean checkSum(int k, int n, Tree t)
qui renvoie la somme de contrôle d’ordre k du texte représenté par
l’arbre t, en d’efforçant de limiter les additions de bits effectuées.
La taille du texte représenté par t vaut 2n (avec 0 ≤ k ≤ n).
|
La réponse à la question précédente nous permet de
déduire que la somme de contrôle d’ordre k est
la somme des bits d’un sommet sur deux de l’étage k.
Cela vaut également pour la somme de contrôle d’ordre n, en considérant
la représentation binaire de taille n+2.
Dans le cas k < n,
il reste à sélectionner un sommet sur deux à partir de l’étage qui précède k.
static boolean checkSum(int k, int n, Tree t) {
if (k == n) { // Ne peut survenir qu'à la racine.
return t.sum ;
} else if (k == n-1) {
return t.left.sum ;
} else {
return Bit.add(checkSum(k, n-1, t.left),checkSum(k, n-1, t.right)) ;
}
} |
Question 23. Quelle est la complexité du calcul du vecteur de contrôle avec la nouvelle technique, en fonction de la taille du texte, notée 2n.
Il faut tenir compte de la construction de l’arbre
(d’un ordre de grandeur proportionnel à 2n, plus exactement
de terme dominant 2n+1, car l’arbre possède 2n+1−1 sommets)
et du calcul de n+1
sommes de contrôle.
On peut compter les additions ou les appels à checkSum,
puisqu’on peut leur affecter un nombre borné d’opérations.
Pour k = n, un appel.
Pour k < n, il y a un appel initial, puis 2 appels, …
jusqu’à atteindre les 2n−k−1 sommets de l’étage numéroté k+1,
Soit finalement dans ce cas.
Bref, au total, un coût dont l’ordre de grandeur est linéaire, en la taille du texte (qui est 2n). |
On supprime la restriction « le texte est de taille 2n» et on considère le cas général de textes de taille n (avec 0 < n). On souhaite maintenir la relation de la question 21, entre représentation binaire d’une position et chemin de l’arbre. Les nouveaux arbres ne sont plus strictement binaires : ils contiennent des sommets à un seul fils et descendre vers ce fils correspond à zéro dans un chemin vers une feuille.
Question 24. Dessiner l’arbre obtenu pour le texte 000110.
 |
Question 25. Formuler une nouvelle définition des arbres dans le cas général. Il faut considérer un nouvel élément : la taille des chemins de l’arbre ciblé. On se placera dans le cadre d’un texte t de taille n, avec une taille de chemin cible k, avec 0 < n ≤ 2k.
|
This document was translated from LATEX by HEVEA.
