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/algo2003-2004/) 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 exit */
#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 -W -Wall matrices.c -o matrices

Puis, pour lancer le programme, tapez ./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 ;

où 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[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. C'est un pointeur vers une zone mémoire réservée pour N objets de type type. La syntaxe type variable[]; existe, est est équivalente à type *variable; et variable est juste un pointeur non alloué.

Pour accéder aux valeurs du tableau, utiliser variable[n] où 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];.

Pour bien comprendre les tableaux il faut les comprende comme des pointeurs.
Par exemple, un tableau à deux coordonnées réserve une zone mémoire 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. Une façon portable de le faire est de poser type *p = &(variable[0][0]); et l'élément variable[i][j] est égal à p[i*M+j].
On voit donc que type variable[][M]; est un pointeur non alloué vers des tableaux à M éléments (de type type ligne[M];) et est donc compatible avec type variable[N][M];. Tandis que type variable[][]; est un pointeur vers un pointeur vers un élément de type type, et n'est donc pas un tableau à deux dimensions.

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.

Exécutez la commande man printf et regardez à quoi ressemble une description exhaustive de la syntaxe d'une fonction C...

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 de taille 3 par 4. 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

La taille d'un tableau devant être connue à la compilation, donc avant l'exécution, et les procédures que nous ferons ne pourront donc pas avoir des tableaux de taille variable. Pour manipuler des matrices de taille variable, on utilisera donc des tableaux a priori suffisamment grands. 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 (puisque cela doit être connu à la compilation). 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.
En réalité, cette limitation est présente dans les vieilles définitions du langage C (K&R ou C89) mais pas dans la dernière version (C99) ni en C++. La norme C99 n'étant pas encore prise en compte par tous les compilateurs, on préfère ici se limiter à C89.

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 fgets 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 mettant dans une matrice le résultat du calcul de la somme de deux autres matrices compatibles et une autre fonction faisant de même pour le 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.

8  Utilisation d'un débuggueur

La commande gdb sert à exécuter un programme pas à pas et à afficher le contenu des variables. Il est nécessaire que la compilation ait été faite avec l'option -g.

Quelques tutoriels en français sont disponibles sur le web : ici ou là.