LdB TPL1

De Ensiwiki
Aller à : navigation, rechercher
AttentionCette page est maintenue uniquement par les enseignants. Afin de ne pas perturber le déroulement des cours, elle n'a pas vocation à être modifiée par les élèves. Mais si vous avez des modifications à proposer, merci d'en discuter ou d'envoyer un e-mail aux auteurs de la page (cf. historique)

Laptop.png  Première Année  CDROM.png  Informatique 

Introduction

Le but de ce TP en temps libre est d’apprendre la syntaxe du langage C. On attend de vous que vous écriviez du code en C avec la même rigueur que vous écrivez de l’Ada en Algo. Notamment, vous prendrez soin de respecter les directives suivantes :

  • votre code doit être commenté : un bon commentaire ne paraphrase pas le code, mais éclairci une partie complexe ou un cas particulier ;
  • vous spécifierez rigoureusement chaque fonction que vous écrivez ;
  • vous prendrez soin d’indenter correctement vos programmes ;
  • vous choisirez des noms de variables parlant.

La clarté de votre code sera prise en compte dans la notation.

Comme en Algo, vous devez tester vos programmes pour vous assurer de leur correction. Votre jeu de tests devra évidemment comprendre des tests aux limites. Un programme échouant avec une erreur de segmentation ou partant en boucle infinie sera sévèrement sanctionné.

Pour vous aider dans la mise au point de votre programme, en plus de gdb que vous avez appris à utiliser en séance encadrée, vous pouvez utiliser le logiciel valgrind installé sur telesun. Ce logiciel est capable de détecter un certain nombre d’erreurs classiques liées à l’utilisation de la mémoire en C (fuites mémoire, utilisation de zones non-initialisées, etc.). Voir la page ensiwiki de valgrind ou sa page man pour plus de détail sur son utilisation. On recommande notamment l'utilisation de l'option --leak-check=full de valgrind pour détecter les fuites mémoires.

On vous recommande de tester vos fonctions au fur et à mesure que vous les écrivez. Vous pouvez compiler votre programme avec la commande

gcc -Wall -Wextra -m32 -g -std=c99 -o tp1 tp1.c

pour bénéficier du maximum de vérifications de la part du compilateur.

Types de données

Dans ce TP, on va manipuler des matrices creuses, semblables à celles manipulées au premier semestre en Algorithmique. On rappelle que le principe de cette structure de données est de ne pas stocker les coefficients égaux à 0 de la matrice pleine équivalente, pour gagner de l'espace mémoire et accélérer certaines opérations. Ici les matrices manipulées ne seront pas forcément carrées et contiendront des entiers relatifs.

On va représenter les lignes et colonnes de la matrice par des listes chaînées contenant les coefficients non-nuls de la matrice pleine équivalente. Les pointeurs de tête de ces listes seront stockés dans deux tableaux de pointeurs (un pour les lignes et l'autre pour les colonnes).

Par exemple, la matrice pleine : 
\begin{pmatrix}
1 & 0 & -3 & 0\\
0 & 4 & 0 & 2\\
0 & -2 & -7 & 0
\end{pmatrix}

sera représentée par une structure de ce type :

LdB matrice creuse.png

Représentations en C

On fourni un squelette de code qui contient notamment des définitions de types et des fonctions de manipulation de matrices pleines, qui seront représentées simplement par des tableaux à deux dimensions d'entiers relatifs.

On défini le type matrice creuse par la structure C suivante :

struct creuse_t {
    unsigned nbr_lig;
    struct cell_t **lignes;
    unsigned nbr_col;
    struct cell_t **colonnes;
};

lignes est le tableau contenant les pointeurs vers les têtes des listes chaînées représentant les lignes de la matrice creuse. Idem pour le tableau colonnes qui contient les têtes de listes des colonnes de la matrice. nbr_lig et nbr_col représentent respectivement le nombre de lignes et de colonnes de la matrice.

Le type cellule des listes chaînées représentant les lignes et colonnes de la matrice creuse est défini par :

struct cell_t {
    int val;
    unsigned lig, col;
    struct cell_t *suiv_lig, *suiv_col;
};

val est le coefficient de la case représentée par la cellule, lig et col représentent la position de la case dans la matrice, et suiv_lig (resp. suiv_vol) est un pointeur vers la cellule suivante sur la même ligne (resp. colonne).

Travail demandé

On vous demande de compléter le squelette de code fourni avec les fonctions spécifiées ci-dessous.

Construction d'une matrice creuse

La première fonction à écrire est struct creuse_t *pleine_vers_creuse(int pleine[H][L]) qui prend en paramètre une matrice pleine et renvoie un pointeur vers la matrice creuse correspondante. Vous devez évidemment allouer dynamiquement toute la mémoire nécessaire pour stocker la matrice creuse (et systématiquement vérifier que l'allocation s'est bien passée à l'aide d'assertions).

Copie dans une matrice pleine

Ensuite, on demande d'écrire une fonction void creuse_vers_pleine(struct creuse_t *creuse, int pleine[H][L]) qui prend en entrée une matrice creuse et remplit en sortie la matrice pleine passée en paramètre.

Multiplication d'une matrice creuse

La troisième fonction à écrire est void multiplie_creuse(struct creuse_t *creuse, int val) qui multiple chaque coefficient de la matrice creuse passée en argument par une valeur entière donnée. Attention, il y a un cas particulier pour une valeur à traiter différemment des autres.

Destruction d'une matrice creuse

Enfin, il faut écrire une fonction void detruit_creuse(struct creuse_t *creuse) qui désalloue complètement toutes les zones mémoires correspondant à la matrice creuse passée en paramètre.

Règles du jeu

On ne vous demande pas de rendre de rapport rédigé, seulement le fichier tp1.c commenté. La fonction main contiendra les différents tests que vous avez effectués.

Vous pouvez travailler en binôme ou en monôme : le fait d’être seul n’entraînera pas de bonus dans la notation.

Enfin, on rappelle que la fraude est sanctionnée sévèrement pour tous les TP et projets, comme précisé dans la charte d’utilisation du matériel informatique.

Les enseignants se réservent le droit d’utiliser des logiciels de détection automatique pour localiser les ressemblances suspectes entre les fichiers rendus. Toute fraude avérée sera sanctionnée par un 0/20 au TP, sans possibilité de rattrapage. La récidive entraînera l’application des sanctions administratives prévues dans le règlement des études.