TP n°1 : manipulation de matrices

Ce premier TP ne suppose aucune connaissance en C. Toutes les instructions dont vous aurez besoin seront décrites. Afin de simplifier la présentation déjà assez lourde, ces descriptions ne seront pas toujours complètes. Vous pourrez trouver un résumé plus complet ou plein de tutorials sur le web. Pour tout savoir sur une instruction, vous pouvez aussi utiliser man.

1  Compiler

1.1  Mise en place

Pour bien travailler, vous aurez besoin de trois fenêtres : une fenêtre pour lire le sujet du TP (à l'adresse http://www.di.ens.fr/~granboul/enseignement/mmfai/algo2002-2003/) et deux autres pour programmer. Vous pouvez utiliser un écran virtuel pour lire le TP et un autre pour les deux fenêtres de programmation. Ces deux fenêtres sont d'une part un éditeur de texte et d'autre part un shell (une fenêtre dans laquelle vous pouvez taper des instructions).

L'éditeur de texte sert à écrire votre programme. Le texte de votre programme sera donc enregistré dans un fichier. Commencez par créer un répertoire (à l'aide de la commande mkdir) dans lequel vous rangerez tout ce qui concerne ce TP. Dans ce répertoire, donc, lancez votre éditeur : joe matrices.c ou gvim matrices.c ou xemacs matrices.c. Vous pouvez donner un autre nom que matrices.c à votre fichier, mais il est recommandé de terminer le nom du fichier par .c.

1.2  Le cycle de compilation

Le fichier contenant le texte de votre programme ne peut pas être exécuté directement. Pour cela il faut d'abord compiler votre programme (avec cc ou gcc de préférence). Cette opération produit un autre fichier contenant du code qui lui est exécutable. Vous n'avez ensuite plus qu'à lancer ce fichier (en tapant simplement son nom) pour voir votre programme s'exécuter.

1.3  Un exemple

Tapez le programme suivant (vous pouvez vous dispenser des commentaires) :

/* Manipulations de matrices */
#include <stdlib.h> /* bibliothèque contenant les fonctions de base comme malloc */
#include <stdio.h> /* bibliothèque contenant les fonctions d'entrée/sortie comme printf */

int main() /* La procédure principale, point de départ du programme */
{
printf("Manipulations de matrices\n"); /* \n signifie passage à la ligne */
exit(0); /* on sort du programme. La valeur 0 indique par convention que le programme se termine normalement */
}

Avant de compiler, n'oubliez pas de sauvegarder le fichier contenant le programme. Pour compiler, dans la fenêtre shell tapez :

gcc -g -Wall matrices.c -o matrices

Puis, pour lancer le programme, tapez ./matrices ou bien matrices.

2  Structure de données pour les matrices

2.1  Variables de type simple

En C, toutes les variables doivent être déclarées. Cela permet de définir leur type et de leur allouer de la mémoire. L'instruction permettant de déclarer une variable est :

TYPE variable; ou TYPE variable = valeur ;

TYPE est le type de la variable. Pour l'instant, le type d'une variable peut être int pour un entier, ou float pour un flottant (nombre à virgule flottante). valeur est la valeur initiale de la variable.

2.2  Tableaux

Pour déclarer une variable destinée à contenir un tableau, on écrit :

TYPE variable[]; ou TYPE variable[N]; ou
TYPE variable[N] = { val, ... ,val };

N est un nombre entier positif (et pas une expression ou une variable entière) spécifiant la taille du tableau. Si N n'est pas précisé, variable est juste un pointeur. Sinon, c'est un pointeur vers une zone mémoire réservée pour N objets de type TYPE.

Pour accéder aux valeurs du tableau, utiliser variable[n] n est n'importe quelle expression (nombre, variable,...) ayant une valeur entre 0 et N-1.

Pour les tableaux à deux dimensions, on rajoute juste une paire de crochets de plus : TYPE variable[N][M];. Attention toutefois, la valeur de M est obligatoire.

Pour ceux qui veulent manipuler les tableaux comme des pointeurs, attention !
Il y a alors une zone mémoire réservée pour N*M objets de type TYPE, qui seront stockés ligne par ligne, mais le tableau pluridimensionnel ne peut être directement utilisé comme pointeur. La seule façon portable est de poser TYPE *p = &(variable[0][0]); et l'élément variable[i][j] est égal à p[i*sizeof(TYPE[M])+j].

2.3  Application

Modifiez le programme précédent pour y déclarer un tableau de taille 3 par 4, contenant des flottants, initialisé avec les valeurs de votre choix.

Dans la suite, nous utiliserons de tels tableaux pour représenter les matrices.

3  Impression d'une matrice

Nous allons écrire une procédure permettant d'imprimer les matrices que nous manipulerons.

3.1  Procédures

Les procédures permettent d'améliorer la lisibilité des programmes en réunissant en un endroit séparé les instructions correspondant à une fonction particulière. Cela permet aussi de n'écrire qu'une seule fois ces instructions qui peuvent être utilisées plusieurs fois.

L'écriture d'une procédure se fait de la facon suivante :
TYPE_RESULTAT proc(TYPE1 arg1,...,TYPEn argn)
{
...
return
expr;
}

Dans notre cas, la procédure prendra trois arguments : la matrice, son nombre de lignes et son nombre de colonnes. Elle ne rendra aucun résultat, TYPE_RESULTAT sera donc void. L'instruction de fin de procédure sera simplement return;.

3.2  printf

Pour imprimer des résultats, on utilise la fonction printf. Cette fonction prend en premier argument une chaîne (des lettres ou nombres entre ") qui définit ce qui sera imprimé. Dans cette chaîne, tous les %d ou %f seront remplacés dans l'ordre par les arguments suivants de printf. %d indique que cette valeur sera un entier, et %f un flottant.

Example : printf("Nous sommes le %d/%d/%d",23,2*4,annee); imprimera Nous sommes le 23/8/1996 si la valeur de annee est 1996.

3.3  Les boucles

Pour effectuer une instruction N fois, on peut utiliser l'instruction for. Il faut définir une variable entière, i par exemple, et écrire

for(i=0; i<N; i++)
{
...
}

La valeur de i est incrémentée de 1 à chaque passage dans la boucle.

3.4  Application

Écrire la procédure imprimant une matrice. La tester en l'appelant dans la procédure main avec la matrice que vous avez définie plus haut.

4  Saisir une matrice au clavier

Afin de manipuler n'importe quelle matrice, nous allons maintenant écrire une procédure permettant de saisir une matrice au clavier une fois le programme lancé.

4.1  Dimensions maximales des matrices

Tout au long du programme, on aura besoin de savoir la taille des tableaux dans lesquels seront stockées les matrices. Pour simplifier, nous prendrons des tableaux de même taille, supérieure à la plus grande taille de matrice que nous aurons à manipuler. Pour être sûr d'utiliser partout la même valeur et pouvoir changer facilement cette valeur si d'aventure elle devenait trop petite pour nos matrices, il faut la définir au départ dans une sorte de variable. Le problème, c'est que la déclaration de taille de tableaux n'admet pas l'utilisation de variables. Nous utilisons donc une macro, définie par #define N 10, par exemple, et qui aura pour effet de remplacer partout dans le texte du programme N par 10 avant d'appeler le compilateur.

Modifiez votre programme pour n'utiliser que des valeurs définies par macro dans les déclarations de tableaux (y compris dans la procédure).

4.2  scanf

La fonction scanf fonctionne de manière analogue à printf : le premier argument est un format et les autres arguments les adresses de variables destinées à contenir les valeurs lues au clavier.

Exemple : scanf("%d %f",&i,&f); lit au clavier un entier, un ou plusieurs blancs ou retours à la ligne, puis un flottant. L'entier est rangé dans la variable i, et le flottant dans la variable f.

4.3  Lire une matrice

La procédure de lecture de matrice prend en argument une matrice déjà allouée et ses nombres de colonnes et de lignes attendus. Elle modifie cette matrice en fonction de ce qui est rentré au clavier et ne retourne rien.

Écrire la procédure de lecture et la tester. Avant d'appeler la procédure de lecture, demander dans la procédure principale le nombre de colonnes et de lignes à l'utilisateur.

Pour les utilisateurs plus confirmés, faire la lecture ligne à ligne, sans demander le nombre de lignes et de colonnes à l'utilisateur (hint : utiliser gets et sscanf).

5  Addition et multiplication

L'affectation se fait avec =, la multiplication avec * et l'addition avec +. Par exemple m[i][j]=t[k][j]*2+m[i][j] affecte à m[i][j] deux fois la valeur de t[k][j] plus l'ancienne valeur de m[i][j].

Écrire une procédure calculant la somme de deux matrices compatibles et une autre calculant leur produit.

6  Polynôme caractéristique

On se propose d'utiliser la méthode de Le Verrier pour calculer le polynôme caractéristique d'une matrice carrée. Cette méthode utilise les relations de Newton :

ak = -1/k (Tk+a1Tk-1 + ... + ak-1T1)

a0 est le coefficient de plus haut degré du polynôme, an le plus petit. Ti est la trace de la matrice à la puissance i.

7  Utilisation de la mémoire

La fonction malloc(n), dans la stdlib, alloue un espace mémoire de taille n. La fonction sizeof(TYPE) donne la taille du type TYPE sur la machine sur laquelle on compile.

Réécrire les fonctions précédentes pour qu'elles n'utilisent que la place mémoire nécéssaire pour les matrices (et non N*N*sizeof(float) quelle que soit la taille réelle de la matrice). On pourra écrire deux procédures pour lire la valeur de la matrice en [i][j] ou changer cette valeur.