| ⋆⋆⋆ |
Question 1.
Les entiers et les tableaux.
Chacune des sous-questions donne une définition de méthode,
que l'on suppose survenir dans une classe Test.
Pour chacune des définitions de méthode, il faut :
a)
| Correct, termine et renvoie toujours 0. |
b)
| Correct, renvoie 2y si y ≥ 0, et 1 si y < 0. Très lente. |
c) Calcule la factorielle.
Incorrect, la fonction déclare renvoyer
un int, mais n'exécute pas toujours return.
Il faut remplacer la dernière ligne par return y*fact(y-1).
Notons que fact ne termine pas pour n < 0.
|
d) Renvoie un tableau de taille n dont les cases sont initialisées aux valeurs 0, 1,…, n−1.
Incorrect, la syntaxe correcte de la création
de tableau est new int [n].
La fonction échoue pour n < 0.
|
e)
Appelée avec un tableau d'entiers t et un
entier n, renvoie un indice k tel que t[k] == n ou −1 si n n'est
pas dans le tableau.
|
Acceptée par le compilateur. L'itération est incorrecte et conduit à
l'échec systématique si n n'est pas dans t. Il faut écrire :
static int find(int [] t, int n) {
for (int k = 0 ; k < t.length ; k++) {
if (t[k] == n) return k ;
}
return -1 ;
} |
f)
La fonction find2 réalise la même recherche que
celle de sous-question précédente, sous une condition portant sur le
tableau t qu'il faut identifier.
Il est inutile de discuter la correction, la fonction find2
est correctement programmée.
| La fonction compile et réalise une recherche dite dichotomique de coût log(T) où T est la taille de t, à condition que t soit trié en ordre croissant. |
Question 2.
Même exercice que la question précédente mais sur les arbres.
Les méthodes sont cette fois définies dans la classe Tree.
a)
Renvoie la valeur (champ val) contenue dans la cellule d'arbre.
Ne compile pas, car la méthode est statique et donc n'a pas accès à
this.val. Il faut écrire une méthode dynamique.
int getVal() { return val ; } |
b) Renvoie la hauteur de l'arbre passé en argument.
Ne compile pas, car la méthode statique hauteur est
appelée récursivement comme une méthode dynamique.
Il faut remplacer la dernière ligne par.
return 1+Math.max(hauteur(t.left), hauteur(t.right)) ; |
c) Teste si un arbre est une feuille.
|
Ne compile pas, il manque le type des valeurs renvoyées dans la déclaration.
Une fois cette correction effectuée, la fonction échoue sur l'arbre vide.
Il faut écrire par exemple.
static boolean isLeaf(Tree t) {
if (t == null) {
return false ;
} else {
return t.left == null && t.right == null ;
}
} |
d) Affiche le contenu de toutes les feuilles de l'arbre t.
|
Compile, échoue sur l'arbre vide, on peut écrire.
static void printLeaves(Tree t) {
if (t == null) return ;
…
} |
e)
| Affiche huit fois 1. |
f)
| Affiche une infinité de 1. |
Les algorithmes de compression sont indispensables lorsqu'il s'agit de stocker ou de déplacer des quantités importantes d'information.
Dans tout le problème nous considérons des textes qui sont des suites
de bits valant donc 0 ou 1.Nous définissons la classe Text :
On notera donc que les textes sont tout simplement des listes de zéros et de
uns, et que le texte vide est représenté par null.
Question 3.
Écrire une méthode statique
static String toString(Text c) qui renvoie la chaîne de zéros et
de uns qui exprime le texte c passé en argument.
On suppose que les textes sont petits et on ne demande pas de porter
une attention exagérée à l'efficacité.
Portons une attention exagérée et écrivons un toString linéaire
en la taille du texte.
static String toString(Text c) {
StringBuffer b = new StringBuffer () ;
for ( ; c != null ; c = c.next)
b.append(c.bit) ;
return b.toString() ;
} Sans attention exagérée,
toString quadratique acceptable dans les conditions de l'énoncé.
static String toString(Text c) {
String r = "" ;
for ( ; c != null ; c = c.next)
r = r + c.bit ;
return r ;
} |
Question 4.
Écrire une méthode static boolean equals(Text c1, Text c2)
qui renvoie true si les deux textes sont identiques en terme de
contenu, ou renvoie false autrement.
|
static boolean equals(Text c1, Text c2) {
if (c1 == null) {
return c2 == null ;
} else if (c2 == null) {
return false ;
} else {
return c1.bit == c2.bit && equals(c1.next, c2.next) ;
}
} |
Question 5.
Écrire une méthode static Text addBit(Text c, int b)
qui renvoie le texte obtenu en ajoutant le bit b à la fin du texte c.
|
static Text addBit(Text c, int b) {
if(c==null){
return new Text(b,null) ;
} else {
return new Text(c.bit,addBit(c.next,b));
}
} |
Question 6.
On dit qu'un texte c1 est préfixe d'un texte c2, si il existe
un texte s tel que la concaténation de c1 et de s est égale
à c2, c'est-à-dire c2=c1 · s. Le texte s est alors un
suffixe du texte c2. Écrire une méthode
static boolean isPrefix(Text c1, Text c2) qui teste si
le texte c1 est préfixe du texte c2.
|
static boolean isPrefix(Text c1, Text c2) {
if (c1 == null) {
return true ;
} else if (c2 == null) {
return false ;
} else {
return c1.bit == c2.bit && isPrefix(c1.next, c2.next) ;
}
} |
Question 7.
En supposant que le texte c1 est un préfixe du texte
c2, écrire une méthode
static Text getSuffix(Text c1, Text c2)
qui renvoie le suffixe s du texte c2 qui suit c1 dans
c2, c'est-à-dire tel que c2=c1 · s.
|
static Text getSuffix(Text c1, Text c2) {
if (c1 == null) {
return c2 ;
} else {
return getSuffix(c1.next, c2.next) ;
}
} |
Dans cette partie on traite d'un ensemble de textes appelé « base de préfixes » La base de préfixes satisfait la propriété de préfixe croissant : pour chaque texte non vide contenu dans la base, il existe dans la base, un texte préfixe de longueur exactement inférieure d'une unité. Ce préfixe est appelé le parent du texte en question. Par ailleurs, un texte donné est toujours présent au plus une fois dans la base de préfixes.
Chaque texte c de la base de préfixes est associé à un
numéro d'ordre, au numéro d'ordre de son texte parent, et au
bit complémentaire qu'il faut rajouter à la fin du parent pour obtenir
le texte c. Par exemple, si le texte est 010011 son texte
parent est 01001 et le bit complémentaire
est 1. L'ensemble de ces informations est donné par un objet
de la classe Info suivante :
Par la suite, on supposera que le texte null est
présent dans la base de préfixes,
associé au numéro d'ordre zéro, que le numéro d'ordre de son parent est
par convention égal à −1, et que son bit complémentaire vaut
aussi −1.
Dans un premier temps on implémente la base de préfixes par une liste :
Les deux méthodes suivantes
sont des méthodes statiques de cette classe List.
Question 8.
Écrire une méthode static int find(Text c, List db)
qui renvoie le numéro d'ordre du texte c dans
la base de préfixes db, ou −1 si le texte c n'est pas présent dans la
base.
|
static int find(Text c, List db){
for ( ; db != null ; db = db.next) {
if (Text.equals(c,db.info.text)) {
return db.info.order ;
}
}
return -1 ;
} |
Question 9.
Écrire une méthode
static Info findLargestPrefix(Text c, List db)
qui renvoie les informations associées au plus long préfixe du
texte c présent dans la base de préfixes db.
On observera que findLargestPrefix est correctement définie,
puisque la base contient au moins le préfixe
vide null (associé à 0, −1 et −1).
|
static Info findLargestPrefix(Text c, List db) {
Info r = new Info (null, 0, -1, -1) ;
for ( ; db != null ; db = db.next) {
if (Text.isPrefix(db.info.text, c) &&
Text.isPrefix(r.text, db.info.text)) {
r = db.info ;
}
}
return r ;
} En fait, les préfixes étant introduits par ordre croissant dans la
base (cf. la méthode add de la question suivante),
on peut se contenter de renvoyer le premier préfixe trouvé.
static Info findLargestPrefix(Text c, List db) {
for ( ; db != null ; db = db.next) {
if (Text.isPrefix(db.info.text, c)) {
return db.info ;
}
}
// Not reached
throw new Error ("La base de préfixes est incorrecte") ;
} |
Afin de permettre plusieurs implémentations de la base de préfixes, celle-ci sera représentée par un objet qui implémente l'interface suivante :
Où
add(Info i) ajoute l'information i à la base de préfixes
(on supposera que i.text n'est pas dans la base),
et findLargestPrefix(Text c) renvoie les informations associées
par la base au plus long préfixe du texte c.
Question 10.
Compléter la classe suivante DataList qui implémente
l'interface Database à l'aide des listes.
|
class DataList implements Database {
private List p ;
DataList() { p = new List () ; }
public void add(Info i) { p = new List (i, p) ; }
public Info findLargestPrefix(Text c) {
return List.findLargestPrefix(c, p) ;
}
} |
L'algorithme Ziv-Lempel (le fameux utilitaire zip) compresse un texte
en le coupant en tranches successives. Le découpage
se fait à partir du texte original et de la base de préfixes initialement
constituée du texte vide null. À chaque étape de compression, on
dispose d'un numéro d'étape n, d'une base de préfixes courante et d'un
suffixe courant s du texte original. Le découpage d'une
tranche de s consiste, tant que s n'est pas
null, à chercher le plus court préfixe s1 du texte s qui n'est
pas dans la base de préfixes. Il y a alors deux cas,
En outre, dans les deux cas ci-dessus, le texte compressé est émis au passage : chaque fois qu'un préfixe q est retiré de s (q est s1 dans le premier cas et s dans le second cas), on affichera la paire composée du numéro d'ordre du parent p de q et du bit complémentaire b tel que q = p · b.
étape tranche paire émise ajouté à la base 1 0 0 0 0 → (1, 0, 0) 2 1 0 1 1 → (2, 0, 1) 3 00 1 0 00 → (3, 1, 0) 4 11 2 1 11 → (4, 2, 1) 5 01 1 1 01 → (5, 1, 1) 6 111 4 1 111 → (6, 4, 1) 7 00 1 0
Considérons par exemple la compression du texte 0100110111100, ce texte est découpé en 0, 1, 00, 11, 01, 111, 00, et compressé comme indiqué à la figure 1.
Question 11. Donner l'ordre de grandeur de la taille du code compressé —c'est-à-dire du nombre de paires émises— dans le cas particulier où le texte d'origine est une suite de n zéros.
| Tant qu'on n'a pas atteint l'état final la longueur du k préfixe inséré dans la base de préfixes est k et la longueur du suffixe restant est n−∑i=1k i=n−(k+1)k/2. Le nombre d'étape est donc environ √2 n ce qui est l'ordre de grandeur de la taille du code compressé. |
Pour décrire un état de la compression on
introduit la classe Zip. Un objet de la classe Zip
contient le numéro d'étape et le suffixe courant. La base de préfixes est
inchangée durant la compression (mais pas son contenu, évidemment),
elle est encodée comme une variable statique de la
classe Zip.
Question 12. Écrire une
méthode Zip step() qui donne le nouvel état de la compression
après l'application de l'étape de compression sur le suffixe courant
suffix. On supposera que suffix est distinct
de null. La méthode step devra par ailleurs modifier la
base de préfixes et afficher la paire d'entiers représentant le préfixe
compressé. Cette question et la suivante sont liées, consultez la
question suivante maintenant.
|
Zip step() {
Info prefix = db.findLargestPrefix(suffix) ;
Text rem = Text.getSuffix(prefix.text, suffix) ;
if (rem == null) {
System.out.println(prefix.parent + " " + prefix.nextBit) ;
return new Zip(stepNumber, null) ;
} else {
Text t = prefix.text ;
int bit = rem.bit ;
t = Text.addBit(t, bit) ;
System.out.println(prefix.order + " " + bit) ;
db.add(new Info (t, stepNumber, prefix.order, bit)) ;
return new Zip (stepNumber+1, rem.next) ;
}
} |
Question 13. Ecrire une méthode
static void compress(Text c) qui
affiche toutes les paires résultant de la compression du
texte c. La méthode compress est responsable de
l'initialisation de la base de préfixes.
|
static void compress(Text c) {
Zip.db = new DataList () ;
Zip state = new Zip(c) ;
while (state.suffix != null) {
state = state.step() ;
}
} |
L'usage d'une liste pour réaliser la base de préfixes introduit une inefficacité importante. Nous allons corriger ce point en implémentant la base par un arbre. Nos arbres sont des arbres binaires utilisés pour associer les numéros d'ordre aux préfixes.
On observe que les sommets des arbres ne comportent plus qu'une unique information : le numéro d'ordre. Les préfixes sont encodés implicitement par un chemin dans l'arbre, et les autres informations (numéro d'ordre du parent et bit complémentaire) peuvent se retrouver grâce à la structure d'arbre. La figure 2 représente l'arbre qui résulte de la compression du texte 0100110111100 (cf. figure 1).
On interprète un chemin dans l'arbre comme un texte, 0 signifiant « à gauche » et 1 signifiant « à droite ». Ainsi, l'arbre de la figure 2 associe le numéro d'ordre 5 au text 01, et le numéro d'ordre 6 aux texte 111. On remarque que la propriété de préfixe croissant entraîne que tous les numéros des sommets de l'arbre sont pertinents.
Question 14. Dessiner l'arbre qui résulte de la compression du texte 01001101111000.
 |
Question 15. Écrire une
méthode static int find(Text c, Tree t) qui renvoie le numéro
d'ordre associé au texte c, ou −1 si aucun chemin de t ne
représente le texte c.
|
static int find(Text c, Tree t) {
if (t == null) {
return -1 ;
} else if (c == null) {
return t.val ;
} else if (c.bit == 0) {
return find(c.next, t.left) ;
} else { // c.bit == 1
return find(c.next, t.right) ;
}
} |
Question 16.
Écrire une méthode static Tree insert(Text c, int n, Tree t)
qui renvoie l'arbre obtenu par insertion
du texte c dans l'arbre t. Dans le nouvel arbre,
le numéro du sommet correspondant au chemin c est n.
On se place dans les conditions de la compression, c'est-à-dire que
tous les préfixes de c sont présents dans l'arbre, sauf c lui même.
|
static Tree insert(Text c, int n, Tree t) {
if (c == null) {
return new Tree (null, n, null) ;
} else if (c.bit == 0) {
return new Tree (insert(c.next, n, t.left), t.val, t.right) ;
} else { // c.bit == 1
return new Tree (t.left, t.val, insert(c.next, n, t.right)) ;
}
} |
Question 17.
Ecrire une méthode static Info findLargestPrefix(Text c, Tree t)
qui renvoie les informations associées au plus long préfixe
du texte c présent dans l'arbre. On se place ici encore dans les
conditions de la compression c'est-à-dire que l'arbre t contient
au moins la racine portant le numéro d'ordre 0.
|
Voici un code qui procède en une recherche dans l'arbre.
// p is parent number, b is parent next bit, Tree t != null
private static Info findLargestPrefix(Text c, int p, int b, Tree t) {
if (c == null) { // text present in data base
return new Info (null, t.val, p, b) ;
} else if (c.bit == 0) {
if (t.left == null) {
return new Info (null, t.val, p, b) ;
} else {
Info i = findLargestPrefix(c.next, t.val, 0, t.left) ;
return
new Info (new Text(0, i.text), i.order, i.parent, i.nextBit) ;
}
} else { // c.bit == 1
if (t.right == null) {
return new Info (null, t.val, p, b) ;
} else {
Info i = findLargestPrefix(c.next, t.val, 1, t.right) ;
return
new Info (new Text(1, i.text), i.order, i.parent, i.nextBit) ;
}
}
}
static Info findLargestPrefix(Text c, Tree t) {
return findLargestPrefix(c, -1, -1, t) ;
} Pour une fois un code itératif est peut-être plus simple à produire. // Dans les conditions de la compression, on a t != null
static Info findLargestPrefix(Text c, Tree t) {
Text prefix = null ; // chemin dans l'arbre : de la racine -> t
int prevVal = -1 ; // Numéro du parent
int prevBit = -1 ; // Bit 'parent'
for ( ; c != null ; c = c.next) {
// avancer dans t d'abord, on a tjs ici t != null
Tree next = c.bit == 0 ? t.left : t.right ;
if (next == null) { // sorti de l'arbre, chemin -> t plus long prefixe
return new Info (prefix, t.val, prevVal, prevBit) ;
}
// Ajuster toutes les variables
prevVal = t.val ; t = next ;
prefix = Text.addBit(prefix, c.bit) ;
prevBit = c.bit ;
}
// On ne peut parvenir ici que pour c (intial) chemin valide dans l'arbre
return new Info (prefix, t.val, prevVal, prevBit) ;
} Le code ci-dessus est quadratique dans la longueur du préfixe renvoyé
(à cause de la construction de Enfin, un code nettement plus simple procède en plusieurs étapes. private static Text findPrefix(Text c, Tree t) {
if (c == null) {
return null ;
} else if (c.bit == 0) {
return new Text (0, findPrefix(c.next, t.left)) ;
} else {
return new Text (1, findPrefix(c.next, t.right)) ;
}
}
private static int last(Text c) {
for ( ; c.next != null ; c = c.next) ;
return c.bit ;
}
private static Text exceptLast(Text c) {
if (c.next == null) {
return null ;
} else {
return new Text (c.bit, exceptLast(c.next)) ;
}
}
static Info findLargestPrefix(Text c, Tree t) {
Text p = findPrefix(c, t) ;
int order = find(p, t) ;
if (p == null) {
return new Info (p, order, -1, -1) ;
} else {
return new Info (p, order, find(exceptLast(p)), last(p)) ;
}
} On note que les trois codes proposés sont linéaires en la taille du préfixe renvoyé (compte tenu de la modification décrite du code itératif). |
Question 18.
Compléter la classe suivante DataTree, qui réalise la base de préfixes à
l'aide d'un arbre.
En outre, expliquer comment modifier la méthode compress de la
classe Zip, afin d'employer les arbres à la place des listes.
|
class DataTree implements Database {
private Tree t ;
DataTree() {
t = new Tree(null, 0, null) ;
}
public void add(Info i) {
t = Tree.insert(i.text, i.order, t) ;
}
public Info findLargestPrefix(Text c) {
return Tree.findLargestPrefix(c, t) ;
}
} Il faut en outre, dans la méthode compress, remplacer l'initialisation
Zip.db = new DataList() par Zip.db = new DataTree().
|
Question 19. Quel est l'ordre de grandeur du coût en temps de la compression d'un texte composé de n bits.
| La compression divise le texte en sous-mots dont la somme des tailles vaut n. Pour un sous-mot donné de taille k on procède à un nombre d'opérations élémentaires proportionnel à k, la compression est donc en O(n). |
Le texte compressé est représenté en machine par deux tableaux de n entiers chacun. Le premier tableau regroupe les numéros d'ordre, et le second les bits (de la paire de codage de rang k). Par exemple, le texte compressé à la figure 1 est représenté par deux tableaux de 7 entiers.
Question 20.
Écrire une méthode
static Text decompress(int [] order, int [] bit)
qui renvoie le texte d'origine à partir de son code
compressé order et bit. Indication : commencer par la fin.
Toute l'astuce consiste à remarquer que la paire (p, b) de numéro
d'ordre k est au rang k−1 dans les tableaux order
et bit. On profite de ce que le texte décodé est naturellement
construit à l'envers (c'est une liste), ce qui permet d'interpréter
les numéros de séquence en remontant vers le début du texte codé.
static Text decompress(int [] order, int [] bit) {
int n=c.length;
Text t=null;
for (int i = n ; i > 0 ; i--) {
int k = i ;
do {
t = new Text (bit[k-1], t);
k = order[k-1] ;
} while (k > 0) ;
}
return t;
} Le code est assez astucieux et la question teste la bonne compréhension de
la technique de compression. L'astuce est malheureusement
sans grande portée pratique, car lire le texte
compressé à l'envers n'est pas naturel.
|
This document was translated from LATEX by HEVEA.