Inversion d'une matrice binaire




Le but de cet exercice est de calculer l'inverse d'une matrice binaire. La matrice sera stockée dans un fichier ayant le format suivant : la première ligne est le nombre de lignes, la seconde le nombre de colonnes, et les lignes suivantes forment la matrice. Dans chaque ligne de la matrice, les caractères seront séparés par des espaces. Le nom du fichier contenant la matrice sera donné en argument du programme exécutable ; on lancera le programme sur le fichier matrice par :
a.out matrice




Comme la plupart des fonctions à écrire nécessite la connaissance du nombre de lignes et du nombre de colonnes de la matrice manipulée, on pourra représenter une matrice par la structure de données suivante : 
struct matrice
{
  unsigned int nb_lignes;
  unsigned int nb_colonnes;
  unsigned short **coeff;
};
Les champs nb_lignes et nb_colonnes de cette structure correspondent respectivement au nombre de lignes et de colonnes de la matrice. Enfin, le champ coeff correspond au tableau formé par ses coefficients.




Il est conseillé de tester progressivement les différentes fonctions du programme. Des matrices inversibles de taille 10 × 10, 100 × 100 et 700 × 700 sont disponibles sur
http://www-rocq.inria.fr/codes/Anne.Canteaut/COURS_C/.



1  Lecture d'une matrice binaire dans un fichier

Écrire une fonction qui prend comme paramètre une chaîne de caractères correspondant au nom du fichier dans lequel la matrice est stockée, et qui retourne un objet de type matrice, dont les différents champs contiennent les informations sur la matrice lue. Cette fonction aura pour prototype :
matrice lecture(char *);


2  Affichage à l'écran d'une matrice binaire

Écrire une fonction qui prend comme paramètre un objet de type matrice et affiche à l'écran les coefficients de la matrice. Cette fonction aura pour prototype :
void affiche(matrice);


3  Inversion d'une matrice binaire

Écrire une fonction qui prend comme paramètre une matrice carrée et qui retourne son inverse, calculé par la méthode du pivot de Gauss. L'algorithme suivant permet d'inverser une matrice M de taille n × n à coefficients dans F2. La notation Xi désigne la ligne i d'une matrice X ; Å désigne la somme dans F2n.

Q ¬ copie de M.
P ¬ matrice identité n × n.
Pour i de 0 à n-1 : Pour justifier le fonctionnement de cet algorithme, il suffit de voir qu'à la fin de chaque itération, on a PM = Q, et que, si M est inversible, Q vaut l'identité à la fin du programme.



4  Vérification de la fonction précédente

Pour vérifier que la fonction précédente calcule bien l'inverse d'une matrice, écrire une fonction de vérification qui prend comme paramètres deux matrices A et B et qui vérifie que leur produit correspond à la matrice identité. Cette fonction retournera la valeur 1 si B est l'inverse de A, et 0 sinon. Son prototype est : 
unsigned short verif_inverse(matrice, matrice);
Pour cela, on écrira une fonction calculant le produit de deux matrices binaires, ayant pour prototype : 
matrice produit(matrice, matrice);

5  Représentation des matrices sous forme compacte

Afin de minimiser à la fois la taille prise en mémoire pour stocker les matrices et le temps de calcul, on stocke une matrice binaire dans un tableau à deux dimensions dont chaque ligne est constituée d'entiers de type unsigned long. De cette façon, on peut diviser la taille de chaque ligne par un facteur proche de 8 * sizeof(unsigned long). Par exemple, le vecteur binaire de longueur 10, 1001000101 peut être stocké sur un unsigned long dont la valeur (en base 10) est 20 + 23 + 27 + 29 = 649. Dans toute la suite, on travaillera donc sur des matrices compactes dont les coefficients sont représentés sous forme d'un tableau à deux dimensions de type unsigned long **. Une matrice binaire sera alors représentée par une structure dont le modèle est le suivant 
struct matrice_compacte 
{
  int nb_lignes;
  int nb_colonnes;
  int nb_col_compacte;
  unsigned long **coeff;
};
Les champs nb_lignes et nb_colonnes de cette structure correspondent respectivement au nombre de lignes et de colonnes de la matrice de départ. Le champ nb_col_compacte donne le nombre de colonnes de la matrice lorsqu'elle est stockée sous forme compacte (c'est-à-dire d'un tableau dont les éléments sont des unsigned long). Enfin, le champ coeff correspond à la forme compacte de la matrice.

Réécrire les fonctions précédentes en utilisant la représentation des matrices. Dans les fonctions inverse et produit, les additions seront effectuées ligne-à-ligne sur le champ coeff de la matrice, en utilisant l'opérateur ^ (ou exclusif bit-à-bit). On n'effectuera donc qu'une seule opération par unsigned long.
This document was translated from LATEX by HEVEA.