TP 6

Dans le cadre du stockage de données dans une matrice, on s'intéresse au cas particulier des matrices sparses. Il s'agit d'une matrice qui contient essentiellement des valeurs nulles. Cela est très fréquent dans des domaines telles que l'IA, la reconnaissance de formes, le traitement statistiques, etc...

Une matrice sparse contient donc un nombre limité de valeurs. Plutôt que d'allouer l'espace d'une très grande matrice pour stocker ces quelques valeurs, on préfère stocker une collection de ces valeurs en gardant également en mémoire la ligne et la colonne à laquelle elles sont censé se trouver.

1. Définissez une structure capable de stocker une valeur entière, c'est à dire son numéro de ligne, son numéro de colonne, et la valeur elle même.
2. On représente une matrice sparse comme un tableau d'élément du type défini précédemment. Proposez une fonction permettant de déclarer une matrice sparse de taille 1000x1000 et d'y stocker 100 valeurs aléatoires dans des cases choisies aléatoirement.
3. Quelle est la taille en mémoire de la matrice précédente ? Quelle autait été sa taille avec une représentation "classique"?
4. Soit une matrice de taille n par m, contenant k éléments. Donnez une condition sur k pour que l'utilisation d'une matrice sparse soit plus intéressante qu'une matrice classique en terme d'occupation mémoire.
5. Donnez une fonction permettant à l'utilisateur de déclarer et d'initialiser une matrice sparse. L'utilisateur donnera d'abord le nombre d'élément qu'il souhaite y stocker, puis entrera les triplets ligne-colonne-valeur correspondant. Quels sont les paramètres nécessaires de cette fonction ? Et les tests à utiliser ?
6. On suppose maintenant que l'utilisateur ne va pas saisir à l'avance le nombre d'éléments. Il entre les triplets ligne-colonne-valeur les uns après les autres, et termine par -1 quand il a terminé. Proposez une variation de la fonction précédente permettant de répondre à ce problème.
7. Définissez une fonction prenant en paramètre une matrice, une ligne et une colonne et renvoyant la valeur qui se trouve dans cette case.
8. Donnez une fonction permettant à l'utilisateur de modifier une valeur dans une matrice sparse. Si la valeur n'existe pas déjà dans la matrice, il faut l'ajouter.

Correction jusqu'ici : tp6.c.

9. Les éléments présents réellement dans le represéntation d'une matrice sparse peuvent venir à être nuls lors de l'utilisation. Donnez une fonction qui enlève tous les éléments nuls d'une matrice sparse et réduit sa taille en mémoire autant que nécessaire.
10. Prenons une matrice sparse 10000x10000 contenant 100 valeurs non nulles. Quelle est la place qu'elle occupe en mémoire ? Comparez à une matrice classique. En considérant une matrice carrée, quelle est la taille de matrice à partir de laquelle il devient plus intéressant d'utiliser une matrice sparse plutôt qu'une matrice classique pour stocker N valeurs non nulles ?