TP sur les tableaux

Page Home (contact) Retour TPs

Support de cours

Codes correcteurs, tableaux d'octets

Cet exercice fait manipuler des tableaux. Il introduit la notion de code correcteur.

Un code correcteur code des données de telle sorte que des erreurs dans la transmission des données (transmission de bits 0 ou 1) pourront être automatiquement détectées, et éventuellement corrigées, par le receveur. Un code correcteur est nécessairement redondant : il ajoute des informations aux données intiales pour pouvoir détecter et corriger les erreurs de transmission.

Un code correcteur envoie des blocs de données (composé des k bits initiaux + les bits ajoutés par le code correcteur pour détecter les erreurs de transmissions). Si n est la longueur du bloc transmis , le rendement d'un code est k / n.

Pour juger de la qualité d'un code correcteur, 3 nombres sont importants ; le rendement et les 2 nombres suivants :

• le nombre d'erreurs n1 maximum pour que le code puisse détecter qu'il y a eu des erreurs dans un bloc de transmission. n1 est le nombre tel que si le nombre de bits erronés (par exemple un bit égal à 1 au départ de la transmission et reçu comme un 0) dépasse n1, on n'est pas assuré que le code détectera qu'il y a eu une erreur de transmission.
• le nombre d'erreurs n2 maximum que le code peut corriger dans un bloc de transmission. n2 est le nombre tel que si le nombre d'erreurs dépasse n2, on n'est pas assuré que les erreurs seront corrigées par le code.

Le code correcteur que vous allez utiliser dans cet exercice travaille sur des blocs de données de longueur n = 24 bits (3 octets ; un octet est représenté en Java par le type primitif byte).

Exemple de code correcteur

La théorie des codes correcteurs nécessite des connaissances mathématiques solides. Vous allez utiliser dans cet exercice un code correcteur simpliste qui ne demande aucune connaissance particulière mais qui permet tout de même de comprendre la notion. Pour les curieux, un cours en français (la version PDF) sur les codes correcteurs (la version HTML) et une référence Wikipédia.

Le code correcteur est le suivant : un bloc de données est composé d'un octet initial (k = 8 bits) qu'on veut transmettre et de 2 copies de ce bloc ; chaque octet est donc envoyé en triple exemplaire. Celui qui reçoit les données compare les 3 exemplaires. Si les 3 octets sont identiques il suppose qu'il n'y a pas eu d'erreur de transmission. Sinon, si au moins 2 exemplaires sont identiques il suppose que la valeur envoyée est donnée par ces 2 exemplaires. Sinon, il ne peut rien dire et il choisit un des 3 octets (le 1er) comme valeur supposée.

1. Ce lien donne le rendement et les 2 nombres n1 et n2 décrits ci-dessus pour ce code. La réponse tient compte de la pire situation ; par exemple, si le nombre d'erreurs est supérieur à n1, on n'est pas certain à 100 % de pouvoir détecter une erreur.
   Dans beaucoup de cas, cependant, on ne tombera pas sur la pire situation et ce code permettra de détecter et de corriger davantage d'erreurs que ne le laisseraient penser les nombres n1 et n2. Un exemple est donné dans le lien.
2. Écrivez une classe Bloc qui représente un bloc composé de 3 octets (le bloc qui sera transmis) ; les 3 octets sont conservés dans un tableau. Cette classe comprendra
• un constructeur qui construit un bloc à partir d'un octet (les 3 octets du bloc sont identiques),
• une méthode getValeurDecodee() qui renvoit l'octet décodé à partir du bloc (par exemple si le bloc contient les valeurs 1, 1, 2 à cause d'une erreur de transmission sur le 3ème octet, la méthode getValeurDecodee() renvoit 1),
• des méthodes utilitaires pour coder et décoder un tableau d'octets,
• une méthode toString(),
• une méthode simulationErreurTransmission(int i, byte valeur) pour simuler une erreur de tramission sur l'octet numéro i du bloc (le 1er octet a le numéro 0) : la valeur passée en paramètre remplace la valeur conservée dans un des 3 octets du bloc.
3. Testez la classe Bloc avec cette classe TestBloc. L'exécution devra ressembler à ceci :
   

   Valeurs à transmettre :
   [1, 2, 3, 4, 5, 6]
   Blocs avant la transmission :
   Bloc [data=[1, 1, 1]]
   Bloc [data=[2, 2, 2]]
   Bloc [data=[3, 3, 3]]
   Bloc [data=[4, 4, 4]]
   Bloc [data=[5, 5, 5]]
   Bloc [data=[6, 6, 6]]
   Blocs après la transmission :
   Bloc [data=[1, 1, 1]]
   Bloc [data=[25, 2, 2]]
   Bloc [data=[3, 3, 3]]
   Bloc [data=[44, 55, 66]]
   Bloc [data=[5, 45, 45]]
   Bloc [data=[58, 58, 58]]
   Valeurs décodées
   [1, 2, 3, 44, 45, 58]
   

4. Améliorez les informations données par le décodage avec une classe BlocAvecRapportErreurs. Cette classe ressemble à la classe Bloc mais contient en plus une variable d'instance dans laquelle on peut ranger ce qui s'est passé au moment du décodage. Le type de la variable sera une énumération pour les différents cas qui peuvent arriver lors du décodage :
• 3 octets identiques (CORRECT) ;
• 2 octets identiques (CORRECTION) ;
• 3 octets différents (ERREUR).
Ajoutez un accesseur pour cette variable afin de savoir si le décodage a corrigé des erreurs de transmission.
Testez votre code avec cette classe TestBlocAvecRapportErreurs. L'affichage d'une telle méthode main pourrait ressembler à ceci :


Valeurs à transmettre :
[1, 2, 3, 4, 5, 6]
Blocs avant la transmission :
Bloc [data=[1, 1, 1]]
Bloc [data=[2, 2, 2]]
Bloc [data=[3, 3, 3]]
Bloc [data=[4, 4, 4]]
Bloc [data=[5, 5, 5]]
Bloc [data=[6, 6, 6]]
Blocs après la transmission :
Bloc [data=[1, 1, 1]]
Bloc [data=[25, 2, 2]]
Bloc [data=[3, 3, 3]]
Bloc [data=[44, 55, 66]]
Bloc [data=[5, 45, 45]]
Bloc [data=[58, 58, 58]]
Valeurs décodées
[1, 2, 3, 44, 45, 58]
Bloc 0 : CORRECT
Bloc 1 : CORRECTION
Bloc 2 : CORRECT
Bloc 3 : ERREUR
Bloc 4 : CORRECTION
Bloc 5 : CORRECT

Correction :

Etagères de livres, tableaux d'objets

• Le constructeur prendra en paramètre le nombre de livres que pourra contenir l'étagère.
• Vous ajouterez des méthodes pour (lisez l'énoncé jusqu'au bout avant de commencer à coder)
• Donner le nombre de livres que peut contenir l'étagère, et le nombre de livres qu'elle contient.
• Ajouter des livres ("void ajouter(Livre)"). Vous ajouterez les livres à la suite des livres déjà ajoutés dans l'étagère ; le premier livre est ajouté au début de l'étagère (au début du tableau). Il devra être impossible d'ajouter des livres dans une étagère pleine.
• Récupérer un livre dont on donne la position sur l'étagère (le livre reste sur l'étagère, on récupère simplement une référence sur le livre). La méthode renverra une instance de Livre. La position du premier livre d'une étagère devra être 1 (et pas 0, bien que le livre soit rangé dans la première position du tableau, qui est d'indice 0). La signature de la méthode sera "Livre getLivre(int)".
• Chercher sur l'étagère un livre repéré par son titre et son auteur. La méthode renverra la position du livre dans l'étagère (ou 0 si le livre n'y est pas). Le profil de la méthode sera "int chercher(String, String)". S'il y a plusieurs livres avec le même titre et le même auteur, la méthode renvoie celui qui a le plus petit indice.
• Avoir une fonctionnalité semblable à la précédente, mais la méthode renvoie un tableau de positions s'il y a plusieurs livres qui ont ce titre et cet auteur. On aimerait appeler cette méthode "chercher" ; est-ce possible ? Le tableau aura pour taille le nombre de livres trouvés (0 si aucun livre n'a été trouvé). Si vous avez besoin de faire une copie de tableau, utilisez la méthode arraycopy pour voir... Ecrivez aussi 2 méthodes pour rechercher tous les livres d'un auteur, ou tous les livres qui ont un certain titre. Cette fois-ci, les méthodes renvoient un tableau de livres.
• Enlever des livres. Vous "tasserez" les livres vers le début quand vous enleverez des livres. Vous écrirez 2 méthodes de même nom pour enlever un livre (on appelle ça une surcharge) :
• une méthode qui repèrera le livre par sa position (1 pour le premier livre) dans l'étagère (de profil "Livre enleverLivre(int)"),
• une méthode qui repèrera le livre par son auteur et son titre, et qui utilisera la méthode chercherLivre (de profil "Livre enleverLivre(String, String)").
Les 2 méthodes renverront le livre supprimé (ou null si le livre n'a pas été trouvé).
• S'il y a beaucoup de livres, cet algorithme ("tasser" les livres, et donc faire un grand nombre de décalages) n'est pas bon pour enlever un livre. Réécrivez les méthodes enleverLivre pour placer le dernier livre à la place du livre enlevé ; vous nommerez les nouvelles versions "enlever".
• Renvoyer une description d'une étagère (la fameuse, et bien utile, méthode toString()). Utilisez-la dès le début, par exemple pour tester la méthode ajouter.
• Et tout ce qu'il vous semblera utile d'ajouter....

Si vous n'avez pas votre propre classe Livre, vous pouvez utiliser la classe Livre minimale dont le source est ici.

Un conseil : commencez par écrire le constructeur, la méthode pour ajouter un livre et la méthode toString et testez. N'écrivez les autres méthodes que lorsque l'ajout de livre fonctionne correctement.

Correction :

Paquetage bibliotheque

1. Mettez toutes les classes liées aux livres dans un paquetage "eg.ufe.toto.bibliotheque" (vous remplacerez toto par votre nom).
2. Compilez, testez avec une classe qui n'appartient pas à ce paquetage. Par exemple, créez en dehors de ce paquetage une classe Librairie avec une méthode main qui créera quelques étagères et y rangera des livres.

Correction :

Javadoc (à présenter à l'enseignant au cours du prochain TP)

Générez la documentation du paquetage bibliotheque avec l'outil javadoc. Vous pouvez vous aider de ce guide ou d'un article de Doug Lea qui donne des conventions de présentation d'un code Java et quelques recommandations. Ce cours, en français, peut aussi vous être utile.
Ajoutez une page pour votre travail dans votre page Web personnelle (il est temps de vous en créer une si ça n'est pas déjà fait !). Dans cette page, un lien devra conduire à la documentation javadoc. Une présentation simple est suffisante ; n'en faites pas trop.

Essayez d'utiliser le plus grand nombre de possibilités de javadoc (sans que ce soit trop artificiel) ; en particulier, glissez quelques mises en forme HTML. La documentation devra faire le lien avec la documentation des API standard (par exemple, pointer vers la documentation de la classe String) ; voir option -link de la commande javadoc. Important : documentez aussi le paquetage (cherchez comment faire dans les cours indiqués ci-dessus).

Vous ne devez pas utiliser un IDE pour générer votre javadoc ; utilisez directement la commande javadoc.

Pour ceux qui ont déjà fini...

Paramètres de la ligne de commande

Variante : si l'utilisateur a donné 2 paramètres, ces 2 paramètres indiquent l'auteur et le titre du premier livre créé,  sinon, le livre est créé avec un titre et un auteur par défaut (ceux de votre livre préféré par exemple).

Retour TPs