Université de la Polynésie

Française

Partiel Algo et programmation C

Deug MIAS 2

Année 2001-02

Mardi 4 Décembre 2001

Modalités

1.Vous disposez de une heure et quarante cinq minutes,

2.vos documents personnels sont autorisés,

3.vos algorithmes seront commentés,

4.le barème est donné à titre indicatif et est susceptible d'être modifié,

Algèbre linéaire

1.1. Ecrire un algorithme de suppression d’une ligne donnée dans une matrice (env. 1 pt)

1.2. Ecrire un algorithme de suppression d’une colonne donnée dans une matrice (env.1 pt)

1.3. Ecrire un algorithme RECURSIF de calcul de la trace d’une matrice carrée (env. 2 pts)

1.4. Programmez cet algorithme en C (env. 2 pts)

Remarque : Vous supposerez disposer des procédures et fonctions suivantes

void delcol(matrix M, matrix *M1, int j) suppression d’une colonne

void delrow(matrix M, matrix *M1, int i) suppression d’une ligne

Faire tourner la procédure C suivante à la main

void mystere(matrix m, int p, matrix *toto)

{ int i,j;

if (p==0)

{ toto->coldim = m.coldim;

toto->rowdim = m.rowdim;

for( i=0; i < toto->coldim; i ++)

for( j=0; j < toto->coldim; j ++)

if (i==j)

toto->elts[i][j] = 1;

else

toto->elts[i][j] = 0;

}

else

{ scalarmul(1, m, toto);

for( i=0; i < p-1; i ++)

mult(*toto, m, toto);

}

Remarque : La procédure scalarmul effectue une multiplication par un scalaire alors que mult multiplie deux matrices entre elles.

1.5. Que vaut toto si p=2 et m vaut la matrice ci-dessous (env. 3 pts)

(2 4 5)

m = (7 7 9)

(4 3 1)

1.6. Donner la définition C du type matrix (env. 1 pts)

Inversion d’une matrice

La méthode la plus connue pour inverser une matrice de taille raisonnable est la méthode des sous matrices dite méthode de Kramer. Cette méthode fait appel aux déterminants des sous matrices de la matrice transposée (on remplace l’élément i,j de trans(M) par (-1)^i+j * le déterminant de trans(M) sans la ligne i et la colonne j).

Rappel à l’ordre 2 :

[M11 M12] [ M22 - M12]

M = [ ] M^-1 = 1/det(M) [ ]

[M21 M22] [- M21 M11 ]

Rappel à l’ordre 3 :

[M22 M33 - M23 M32 - M12 M33 + M13 M32 M12 M23 - M13 M22]

1/det(M) [-M21 M33 + M23 M31 M11 M33 - M13 M31 -M11 M23 + M13 M21]

[M21 M32 - M22 M31 -M11 M32 + M12 M31 M11 M22 - M12 M21]

1.7. Ecrire un algorithme d’inversion par la méthode de Kramer (env. 3 pts)

1.8. Ecrire une procédure ou fonction de calcul de l’inverse d’une matrice carrée par la méthode de Kramer (env.5 pts)

Remarque : Vous supposerez disposer des procédures et fonctions suivantes

int int_power(int a, int b) un entier à une puissance entière

transpose(matrix m1, matrix *m2) transposition de matrice

double det(matrix m) calcul du déterminant

void scalarmul(double x, matrix m1, matrix *m2) multiplication par un scalaire

void delcol(matrix m, matrix *m1, int j) suppression d’une colonne

void delrow(matrix m, matrix *m1, int i) suppression d’une ligne