TP sur les tableaux

Page Home (contact) Retour TPs

Support de cours


Codes correcteurs, tableaux d'entiers

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 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 code correcteur que vous allez utiliser dans cet exercice travaille sur des blocs de données initiales de longueur k = 8 bits (un octet, 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 : chaque octet est envoyé en triple exemplaire. Celui qui reçoit les données compare les 3 exemplaires. 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.

  1. Donnez le rendement et les 2 nombres n1 et n2 décrits ci-dessus pour ce code. Votre réponse doit tenir 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.
  2. 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. Donnez au moins un exemple.
  3. Écrivez une classe Code3 qui implémente ce type de code pour transmettre des données. Les données transmises seront représentées par un tableau d'octets (type primitif byte).
    La classe Code3 contiendra une méthode coder qui sera utilisée par celui qui envoie les données. Cette méthode coder prendra en paramètre un tableau d'octets à 1 dimension qui représentera les données à transmettre. Elle retournera le tableau à 2 dimensions qui contient les 3 exemplaires du tableau à transmettre. Par exemple, le tableau 1 2 8 25 36 15 sera transformé en le tableau à 2 dimensions dont les 3 "lignes" sont identiques au tableau à transmettre (la 1ère colonne, par exemple, contiendra le 1er octet à envoyer, suivi de ses 2 copies).
    ligne 0 : 1 2 8 25 36 15
    ligne 1 : 1 2 8 25 36 15
    ligne 2 : 1 2 8 25 36 15
    Ce tableau sera envoyé sur la ligne de télécommunication sous la forme 1 1 1 2 2 2 8 8 8 25 25 25 36 36 36 15 15 15 (le tableau sera envoyé colonne par colonne) et sera reçu sous la forme d'un tableau de byte à 2 dimensions. Vous ne vous occupez pas de la transmission et de la réception des données. Les données reçues seront rangées dans un tableau à 2 dimensions ayant la même structure que le tableau envoyé. Par exemple, si les données reçues sont 1 1 1 2 3 2 8 8 8 28 25 28 36 36 36 15 15 15 (il y a eu des erreurs durant la transmission pour les nombres en gras et colorés en bleu), elles sont rangées dans le tableau
    ligne 0 : 1 2 8 28 36 15
    ligne 1 : 1 3 8 25 36 16
    ligne 2 : 1 2 8 28 36 17
    La classe Code3 contiendra une méthode decoder qui prend ce tableau en paramètre et retourne un tableau de dimension 1 qui est supposé être le résultat de la réception de données (après correction des erreurs). Pour l'exemple ci-dessus, la méthode decoder renverra le tableau qui contient
    1 2 8 28 36 15 (une erreur n'a pu être corrigée ; en cas de 3 nombres différents on garde un des nombres, ici celui de la ligne 0).
    Voici un exemple d'utilisation.
  4. Améliorez les informations données par le décodage : l'utilisateur a la possibilité de savoir si le décodage a corrigé des erreurs de transmission. Testez à nouveau. Voici un exemple de méthode main qui teste différents cas. L'affichage d'une telle méthode main pourrait être celui-ci. Vous remarquez une différence importante pour l'utilisation de la classe Code3 dans la méthode main par rapport à la question précédente : les méthodes coder et decoder sont des méthodes d'instance et plus des méthodes de classe. Il sera ainsi plus facile de lancer plusieurs codages/décodages en même temps, qui n'interfèreront pas.
    La classe utilisera une énumération pour les différents cas qui peuvent arriver lors du décodage :

Correction :

Questions 1 et 2
Classe Code3 sans rapport sur les erreurs
Classe Code3 avec rapport sur les erreurs et utilisation d'une énumération


Etagères de livres, tableaux d'objets

Créez une classe Etagere pour représenter une étagère qui peut contenir un certain nombre de livres (fixe pour chaque étagère). Vous utiliserez un tableau pour ranger les livres. Dans la méthode main(), vous créerez des livres, 2 étagères et ajouterez les livres dans les étagères. Vous chercherez un des livres dans une étagère ; s'il y est, vous ferez afficher son nombre de pages. Vous rechercherez tous les livres d'un auteur et les ferez afficher. Vous supprimerez un des livres d'une étagère. Vous ferez afficher à chaque fois que nécessaire les étagères modifiées (en utilisant la méthode toString()). Vous pouvez vous appuyer sur cette méthode main().

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 :

Etagere.java

Paquetage bibliotheque

  1. Mettez toutes les classes liées aux livres dans un paquetage "fr.unice.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.
Une petite indication.

Correction :

Livre.java
Etagere.java
Librairie.java

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. Voici aussi un exemple de programme commenté. 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 !). On devra pouvoir atteindre votre page personnelle en allant à l'adresse http://www-mips.unice.fr/~toto (remplacez toto par votre nom de login). 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

Dans la méthode main() de la classe TestLivre, créez un livre dont l'auteur et le titre sont donnés en paramètre de la ligne de commande. Pour vérifier, faites afficher l'auteur et le titre de ce livre.

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).


Les tableaux et la traduction d'une chaîne de caractères en entier

En utilisant un tableau, complétez/corrigez la classe TestMois (et éventuellement complétez la classe Mois, mais sans modifier le code déjà écrit) pour qu'elle affiche le nombre de jours dans un mois donné (vous ne tiendrez pas compte des années bissextiles), par exemple (attention, 11 correspond au mois de novembre) :
    prompt: java TestMois 11
    Le mois de novembre a 30 jours
    prompt:

Voici une partie du fichier qui contient  la classe TestMois :
public class TestMois {
  public static void main(String args[]) {
    int monMois = Integer.parseInt(args[0]);
    //
    // code à fournir
    //
    System.out.print("Le mois de "
                     + moisJours[monMois].getNom() + " a ");
    System.out.println(moisJours[monMois].getNbJours()
                       + " jours");
  }
}

Et la classe Mois :

public class Mois {
  private String nom;
  private int nbJours;

  Mois(String nom, int nbJours) {
    this.nom = nom;
    this.nbJours = nbJours;
  }
}

Correction :

TestMois
Mois.java


Retour TPs