Programmation impérative : TP 6

Matrices carrées

But : réaliser un programme de manipulation de matrices carrées d'entiers.

On considèrera des matrices au sens « vraie 2d », c'est-à-dire que pour accéder à la case de coordonnées i,j, on doit pouvoir écrire t[i][j]. Dans la plupart des fonctions et procédures demandées, on sera amené à donner également en paramètre la taille de la matrice.

  1. Définir le type matrix.
  2. (Vu en TD.) Réaliser et tester une fonction qui effectue l'allocation dynamique et renvoie une matrix de taille m fournie.
  3. Réaliser et tester une procédure d'affichage d'une matrix.
  4. Réaliser et tester une procédure d'affichage des adresses des cases d'une matrix. (Cf. format %p pour printf.)
  5. Dans la fonction main, permettre la saisie de la taille m au clavier, et tester.
  6. Réaliser et tester une fonction qui effectue le remplissage d'une matrix donnée par tirage aléatoire (cf. infra) de chaque élément entre 0 et un entier n fourni.
  7. Réaliser et tester une fonction d'addition de deux matrix (le résultat sera retourné, attention aux tailles).
  8. (Vu en TD.) Réaliser et tester une procédure qui libère la mémoire allouée dynamiquement lors de la création d'une matrix.
  9. (Vu en TD.) Réaliser et tester une fonction de multiplication de deux matrix (le résultat sera retourné, attention aux tailles).
  10. Réaliser et tester une fonction qui retourne la trace d'une matrix (somme des éléments diagonaux).
  11. Réaliser et tester une fonction qui calcule la transposée d'une matrix (le résultat sera retourné).
  12. Réaliser et tester une procédure qui effectue le remplissage d'une matrix donnée par les éléments du triangle de Pascal (0 ailleurs).

Fichiers PNM

On considèrera maintenant des tableaux de pixels représentés en 1D, c'est-à-dire que pour accéder à la case de coordonnées i,j, on devra écrire t[i * w + j] où w est la largeur de l'image.

Pour simplifier, on ne considérera ici que des images en niveau de gris.

On se reportera au cours pour la description du format PGM.

On pourra tester avec le fichier Lenna.pgm.

  1. Définir le type pixel.
  2. Définir un type picture pour stocker une image. Ce sera un enregistrement contenant la largeur et la hauteur de l'image, ainsi qu'un tableau contenant la grille de pixels.
  3. Écrire une fonction capable de lire un fichier au format PGM dont le nom est passé en argument, et de retourner la picture correspondante.
  4. Écrire une procédure qui prend en argument une picture et un nom de fichier, et qui écrit dans le fichier l'image au format PGM.
  5. Tester vos fonctions en écrivant un programme qui prend en arguments deux noms de fichier in.pgm et out.pgm et qui copie l'image contenue dans in.pgm dans out.pgm.
  6. Implémenter divers algorithme de traitement d'image et les tester:

Annexe : Génération de nombres pseudo-aléatoires

La bibliothèque standard de C définit un générateur de nombre pseudo-aléatoire. La fonction 

  int rand();
permet d'obtenir un entier pseudo-aléatoire compris en 0 et RAND_MAX. (RAND_MAX est une constante définie par le compilateur.) La séquence des nombres obtenus est déterministe, donc plusieurs exécutions du même programme donneront les mêmes valeurs.

Il est possible de changer ces valeurs en modifiant la « graine » initiale à partir de laquelle les valeurs pseudo-aléatoires successives sont obtenues. Pour cela, on utilise la fonction 

  void srand(unsigned int seed);
qui utilise donc seed comme valeur initiale. Il ne faut faire appel à cette fonction qu'une seule fois par exécution (en général, au début de la fonction main), et non pas à chaque appel à rand, sinon la graine est réinitialisée et on retombe sur les même valeurs.

Pour avoir une valeur de graine différente à chaque exécution, on peut utiliser l'heure courante. La fonction 

time_t time(time_t *tloc);
retourne le nombre de secondes depuis le premier janvier 1970.

On pourra donc faire : 

#include <stdlib.h>
#include <time.h>

    ... fonctions qui utilisent rand() ...

int main() {
  srand(time(NULL));  
    ...
}

Pour obtenir une valeur pseudo-aléatoire comprise entre 0 et un certain entier n on pourrait faire rand() % (n + 1) mais si on fait cela certaines valeurs seront plus fréquentes que d'autres. Une bonne façon de procéder est d'utiliser la fonction auxiliaire suivante : 

/*@ requires max <= RAND_MAX
  assigns nothing
  ensures returns a pseudo-random value between 0 and max included
  if rand() is assumed to be uniform, so is this function */
int rand_up_to(int max) {
  int r;
  do
    r = rand();
  while (r >= RAND_MAX - (RAND_MAX % (max + 1)));
  return r % (max + 1);
}