DST de SDA Complexe!! Matrice creuse
Samira
-
Samira -
Samira -
bonjour à tous
Je vous ecris ce message car j'ai un petit problème. Je suis en premiere année de DUT info et j'ai passé mon DST de SDA il ya quelque jours.
Le sujet portait sur les matrices creuses. Helas, en cours nous n'en avions jamais parlé auparavant si ce n'est en mathématique, mais jamais en programmation.
Serait-il possible que quelqu'un puisse me donner les grandes lignes du code, les differents prototypes, pour voir si je suis sur la bonne voie pour valider mon semestre.
Voici le sujet:
On choisit pour donnée concrete des matrices creuses la structure de donnée (MatriseCreuse) regroupant i) les dimensions( nombre de lignes et de colones) de la matrice et ii)le
tableau nommé ligne qui stocke à l'indice i (0<= i< nbLig) la liste des élèments non nuls de la ieme ligne. Les élèments non nuls de la lignes sont stocké dans la lisye dans l'ordre
de leur numero de colonne.
La structure de données (ElemNNul) associée à un élèment non nul est composée de deux champs : i) la valeur numériquede l'élèment et ii) l'indice j de la colonne de l'élèment dans la matrice.
Le composant Liste utilisé dans la MatriceCreuse stoke en liste des éléemnts de type Items. Le type Item est spécialisé avec le type ElemNNul dans Item.h
Les consignes étaients:
Pour la matrice creuse A(7,10)
0 | 0 | 7.0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 |4.0|0 |0 |5.0| 0 | 0 | 0 |3.0|0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 |0 |0 |0 |0 |0 |0
0 |0 |0 |0 |0 |0 |0 |0 |0 |0
0 |0 |0 |0 |6.0|0 |0 |2.0| 0 |0
0 |0 |1.0 |0 | 0 | 0 |0 |0 |0 |0
1)donner le contenu du champ ligne de la structure de donnée MatriceCreuse. Cette représeantation se fera indepedanment de la stucture de donnée concrete du type abstrait Liste.
2) Prototypez documentez et codez la fonction (creerMatC) de création d'une variable de type MatriceCreuse. Le role fonctionnel de creerMatC ets i) l'allocation en mémoire dynamique du champ ligne et son initialisation des champs correspondant aux dimensions de la matrice d'origine.
3) Codez la fonction (dessaloMatC) de ma désallocation de la mémoire dynamique d'une matruce creuse allouée dans la fonction creerMatC.
4)Codez la fonction (LireMatCTxt) qui initialise à partir d'un fichier texte une variable de type MatriceCreuse. DAns le fichier texte, une 1ere ligne indique le nombre de ligne et de colonnes de la matrice.
Pour une matrice A(m,n) chacune des lignes suivantes contient les n éléments de la matrice par ligne ( de la ligne 0 à la ligne m-1)
NOTATION: Pour la suite, on utilisera i) le terme d'indices abstraits pour désigneri et j (0<= i< m et 0<=j<n) les indices d'un élement quelconque a(i,j) de la matrice A(m,n) et ii) le terme d'indices concrets pourdesigner, dans la representation de A en matrice creuse, l'indice i(0<=i<m) de ligne et le rang r d'un élément non nul dans la liste correspondant à la ligne i.
5) Soit a(1,4) l'élèment non nul de A(7,10) d'indices abstraits iA=1 et jA=4, donner les indices concrets iC et rC lui correspondant dans la structure de donnée MatriceCreuse
Soit les indices concrets iC=1 et rC=2 de l'élèment non nul dans la structure de donnée de type MatriceCreuse correspondant a A(7,10), donnez les indices abstrait (iA et jA) coresspondants.
6) Codez la fonction lire qui renvoie pour tout couple d'indices abstraits iA et jA (0<=iA <m et 0<=jA<n) la valeur de lélément a(iA jA) de la matrice a(m,n) à partir de la représentation de A en matrice creuse.
Donnez le nombre de comparaison d'indices abstrait de colonnes pour la lecture de tous les éléments de la ligne 5.
7) On peut remarquer que pour des accès succesifs comme dans le cas de la lecture d'une ligne, l'accàs à l'élèments par la fonction lire revient à balayer la liste des éléments non nuls de la ligne. Ainsi, pour optimiser les acces aux elements successifs, on ajoute à la structure de donnée MAtriceCreuse les indices concrets (iC et rC) correspondant au dernier accès en lectureou en écriture d'un élément non nul.
7) Modifier la fonction lire afin d'optimiser la lecture d'une ligne de la matrice originelle.
REmarque: Il est necessaire de change le prototype de la fonction lire. La liste ne peut plus etre en mode de lecture seule car elle doit etre modifiée
Donnez le nombre de comparaisons d'indices abstraits de colonne pour la lecture de tous les élements de la ligne5.
8) Codez la fonction ecrire qui ecrit la valeur réelle val correspondant à un élément d'indices absatrits iA et jA de la matrice A(m,n) dans la matrice creuse correspondante.
Indication : un élément non nul pourra etre modifié, supprimé ou crée
9) Prototypez , commentez et codez la fonction (somme) de calcul de la somme de deux matrices A(m,n) et B(m,n) dont le résultat est la matrice R(m,n)
Indication: Vérifiez les pré conditions dans le code. L'accés aux élements de la matrice étant optimisé,vous pourrez utiliser les fonctions lire et écrire dans un algo qui balaie les matrices A, B et R par des indices abstraits.
Rappel de la formule de calcul matriciel R(m,n)=A(m,n)+B(m,n):
r(i,j)=a(i,j)+b(i,j) avec i=(0,...,m-1) et j =(0,..., n-1)
Merci d'avance pour vos réponses
Je vous ecris ce message car j'ai un petit problème. Je suis en premiere année de DUT info et j'ai passé mon DST de SDA il ya quelque jours.
Le sujet portait sur les matrices creuses. Helas, en cours nous n'en avions jamais parlé auparavant si ce n'est en mathématique, mais jamais en programmation.
Serait-il possible que quelqu'un puisse me donner les grandes lignes du code, les differents prototypes, pour voir si je suis sur la bonne voie pour valider mon semestre.
Voici le sujet:
On choisit pour donnée concrete des matrices creuses la structure de donnée (MatriseCreuse) regroupant i) les dimensions( nombre de lignes et de colones) de la matrice et ii)le
tableau nommé ligne qui stocke à l'indice i (0<= i< nbLig) la liste des élèments non nuls de la ieme ligne. Les élèments non nuls de la lignes sont stocké dans la lisye dans l'ordre
de leur numero de colonne.
//** @file Extrait du fichier DonneeConcrete.h*/
struct MatriceCreuse {
int nbLig; // nb de ligne
int nbCol//nb de colonnes
Liste *ligne // tableau de dimension nbLig ligne[i] stoke la liste
};
La structure de données (ElemNNul) associée à un élèment non nul est composée de deux champs : i) la valeur numériquede l'élèment et ii) l'indice j de la colonne de l'élèment dans la matrice.
// ** @file Extrait du fichier ElemNNul.h*/
strcut ElemNNul {
double coef ; // valeur numerique de l'élement non nul
int j; // indice de colonne de l'élément non nul dans la matrice
};
Le composant Liste utilisé dans la MatriceCreuse stoke en liste des éléemnts de type Items. Le type Item est spécialisé avec le type ElemNNul dans Item.h
**/ @file Extrait du fichier Item.h*/ #include"ElemNNul.h" typedf ElemNNul Item;
Les consignes étaients:
Pour la matrice creuse A(7,10)
0 | 0 | 7.0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 |4.0|0 |0 |5.0| 0 | 0 | 0 |3.0|0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 |0 |0 |0 |0 |0 |0
0 |0 |0 |0 |0 |0 |0 |0 |0 |0
0 |0 |0 |0 |6.0|0 |0 |2.0| 0 |0
0 |0 |1.0 |0 | 0 | 0 |0 |0 |0 |0
1)donner le contenu du champ ligne de la structure de donnée MatriceCreuse. Cette représeantation se fera indepedanment de la stucture de donnée concrete du type abstrait Liste.
2) Prototypez documentez et codez la fonction (creerMatC) de création d'une variable de type MatriceCreuse. Le role fonctionnel de creerMatC ets i) l'allocation en mémoire dynamique du champ ligne et son initialisation des champs correspondant aux dimensions de la matrice d'origine.
3) Codez la fonction (dessaloMatC) de ma désallocation de la mémoire dynamique d'une matruce creuse allouée dans la fonction creerMatC.
4)Codez la fonction (LireMatCTxt) qui initialise à partir d'un fichier texte une variable de type MatriceCreuse. DAns le fichier texte, une 1ere ligne indique le nombre de ligne et de colonnes de la matrice.
Pour une matrice A(m,n) chacune des lignes suivantes contient les n éléments de la matrice par ligne ( de la ligne 0 à la ligne m-1)
NOTATION: Pour la suite, on utilisera i) le terme d'indices abstraits pour désigneri et j (0<= i< m et 0<=j<n) les indices d'un élement quelconque a(i,j) de la matrice A(m,n) et ii) le terme d'indices concrets pourdesigner, dans la representation de A en matrice creuse, l'indice i(0<=i<m) de ligne et le rang r d'un élément non nul dans la liste correspondant à la ligne i.
5) Soit a(1,4) l'élèment non nul de A(7,10) d'indices abstraits iA=1 et jA=4, donner les indices concrets iC et rC lui correspondant dans la structure de donnée MatriceCreuse
Soit les indices concrets iC=1 et rC=2 de l'élèment non nul dans la structure de donnée de type MatriceCreuse correspondant a A(7,10), donnez les indices abstrait (iA et jA) coresspondants.
6) Codez la fonction lire qui renvoie pour tout couple d'indices abstraits iA et jA (0<=iA <m et 0<=jA<n) la valeur de lélément a(iA jA) de la matrice a(m,n) à partir de la représentation de A en matrice creuse.
Donnez le nombre de comparaison d'indices abstrait de colonnes pour la lecture de tous les éléments de la ligne 5.
7) On peut remarquer que pour des accès succesifs comme dans le cas de la lecture d'une ligne, l'accàs à l'élèments par la fonction lire revient à balayer la liste des éléments non nuls de la ligne. Ainsi, pour optimiser les acces aux elements successifs, on ajoute à la structure de donnée MAtriceCreuse les indices concrets (iC et rC) correspondant au dernier accès en lectureou en écriture d'un élément non nul.
/** @brief Type de matrices creuses */ struct MatriceCreuse int nbLig; int nbCol; Liste* ligne; int iC, rC // indices concrects de lelement (non nul) courant correspondant au dernier accès (en lecture ou en ecriture) };
7) Modifier la fonction lire afin d'optimiser la lecture d'une ligne de la matrice originelle.
REmarque: Il est necessaire de change le prototype de la fonction lire. La liste ne peut plus etre en mode de lecture seule car elle doit etre modifiée
Donnez le nombre de comparaisons d'indices abstraits de colonne pour la lecture de tous les élements de la ligne5.
8) Codez la fonction ecrire qui ecrit la valeur réelle val correspondant à un élément d'indices absatrits iA et jA de la matrice A(m,n) dans la matrice creuse correspondante.
Indication : un élément non nul pourra etre modifié, supprimé ou crée
9) Prototypez , commentez et codez la fonction (somme) de calcul de la somme de deux matrices A(m,n) et B(m,n) dont le résultat est la matrice R(m,n)
Indication: Vérifiez les pré conditions dans le code. L'accés aux élements de la matrice étant optimisé,vous pourrez utiliser les fonctions lire et écrire dans un algo qui balaie les matrices A, B et R par des indices abstraits.
Rappel de la formule de calcul matriciel R(m,n)=A(m,n)+B(m,n):
r(i,j)=a(i,j)+b(i,j) avec i=(0,...,m-1) et j =(0,..., n-1)
Merci d'avance pour vos réponses
A voir également:
- DST de SDA Complexe!! Matrice creuse
- Creuse - Guide
- Heure creuse - Guide
- Racine complexe pci express ✓ - Forum Pilotes (drivers)
- Tableau complexe word - Guide
- Vous ne pouvez pas modifier une partie de matrice - Forum Excel
1 réponse
Voici la fin du sujet, en fait lexo 2
Il s'agit du meme exerciece cependant , il n'a q'un seul indice concret et il est demandé de faire un produit de matrice et non pas une somme.
Voici le sujet:
On choisit pour donnée concréte des matrices creuses la structure de données
(MatriceCreuse) regroupant i) les dimensions (nombres de lignes et de colonnes)
de la matrice et la liste des items de type ElemNNul donné ci-dessous .
La structure de données (ElemNNul) est composée de cinq champs relatifs à
l' élément nul representé ; i) sa valeur numérique (coef), ii) ses indices de ligne et
de colonne (i, j) dans la matrice et iii) relativement à l'élément représenté , le rang
nextL (resp. nextC) dans la liste (lst) du prochain élément non nul sur la
meme ligne (resp. sur la meme colonne). Lorsque l'élément non nul représenté
n'admet pas de prochain élément non nul sur sa ligne (resp . colonne) , la valeur
de nextL (resp. nextC) vaut -1.
Le composant Liste utilisé dans MatriceCreuse stocke en liste des éléments de
type Item. Le type Item est spécialisé avec le type ElemNNul dans Item.h.
1) On prend comme convention la liste non nuls est triée d'abord par l'indice de ligne puis par l'indice de colonne. Pour la matrice de la structure de données MatriceCreuse. Cette réprésentation se fera indépendamment de la structure de donnée concrète du type abstrait Liste.
2) Prototypez et codez la fonction (creerMatC) de création d'une variable de type MatriceCreuse. Le role fonctionnel de creerMatC est i) initialisation du champs lst à une liste vode ,ii) initialisation des champs correspondant aux dimensions de la matrice.
3) Codez la fonction (dessallocMatC) de désallocation de la mécmoire dynamique d'une matrice creuse allouée dans la fonction creerMatC
4) Codez la fonction LireMatcBin) qui initialise à partir d'un fichier binaire une variable de type MatriseCreuse. Le fichier binaire est composé des dimensions de la matrice et de la suite des mxn valeurs reelles des elements (triés par ligne puis par colonne) de la matrice A(m,n).
Notation: Pour la suite, on utilisera i) le terme d'indices abstraits pour désigner i et j (0<= i< m et 0<=j<n) les elements d'indices quelconque a(i,j) de la matrice A(m,n) et ii) le terme d'indice concret pour désigner, dans la représentationde A en matrice creuse, le rang r d'un élément non nul dans la liste lst.
5) Soit a'1,4) l'element non nul de A(7,10) d'indices abstraits iA=1 et jA=4, donner l'indice concret rC lui correspondant dans la structure de données MatriceCreuse.
Soit l'indice concrect rC=2 de l'élément non nul dans la structure de donnée de type MatriceCreuse correspondant a A(7,10), donnez les indices abstraits (iA et jA) correspondants
6) Codez la fonction lire qui renvoie pour tout couple d'indices abstraits iA et jA (0<= iA< m et 0<=jA<n) la valeur de l'élement a (iA,jA) de la matrice A(m,n) à partir de la représentation de A en matrice creuse.
Donnez le nombre de comparaisons d'indices abstraits de ligne et de colonne pour la lecture de tous les elements de la ligne 5.
7) On peut remarquer que pour des accès succesifs comme dans le cas de la lecture d'une ligne, l'accàs à l'élèments par la fonction lire revient à balayer la liste des éléments non nuls de la ligne. Ainsi, pour optimiser les acces aux elements successifs, on ajoute à la structure de donnée MAtriceCreuse l' indice concret ( rC) correspondant au dernier accès en lecture ou en écriture d'un élément non nul.
Donnez le nombre de comparaisons d'indices abstraits de colonne pour la lecture de tous les élements de la ligne5.
7) Codez la fonction ecrire qui ecrit la valeur réelle val correspondant à un élément d'indices absatrits iA et jA de la matrice A(m,n) dans la matrice creuse correspondante.
8) Modifier la fonction lire afin d'optimiser la lecture d'une ligne de la matrice originelle.
REmarque: Il est necessaire de change le prototype de la fonction lire. La liste ne peut plus etre en mode de lecture seule car elle doit etre modifiée
Donnez le nombre de comparaisons d'indices abstraits de colonne pour la lecture de tous les élements de la ligne5.
9) Prototypez , commentez et codez la fonction (produit) de calcul de le produit de deux matrices A(m,n) et B(m,n) dont le résultat est la matrice R(m,n)
Indication: Vérifiez les pré conditions dans le code. L'accés aux élements de la matrice étant optimisé,vous pourrez utiliser les fonctions lire et écrire dans un algo qui balaie les matrices A, B et R par des indices abstraits.
JE vous remercie d'avance pour vos reponses, je vous en serai extremement reconnaissante.
Il s'agit du meme exerciece cependant , il n'a q'un seul indice concret et il est demandé de faire un produit de matrice et non pas une somme.
Voici le sujet:
On choisit pour donnée concréte des matrices creuses la structure de données
(MatriceCreuse) regroupant i) les dimensions (nombres de lignes et de colonnes)
de la matrice et la liste des items de type ElemNNul donné ci-dessous .
struct MatriceCreuse {
int nbLig; // nonbre de lignes
int nbCol; // nombre de colonnes
liste lst; // liste des éléments non nuls (de type ElemNNul)
};
La structure de données (ElemNNul) est composée de cinq champs relatifs à
l' élément nul representé ; i) sa valeur numérique (coef), ii) ses indices de ligne et
de colonne (i, j) dans la matrice et iii) relativement à l'élément représenté , le rang
nextL (resp. nextC) dans la liste (lst) du prochain élément non nul sur la
meme ligne (resp. sur la meme colonne). Lorsque l'élément non nul représenté
n'admet pas de prochain élément non nul sur sa ligne (resp . colonne) , la valeur
de nextL (resp. nextC) vaut -1.
struct ElemNNul {
double coef; // valeur numérique de lélément non nul
int i; // indice de ligne de l'élément dans la matrice
int j; // indice de colonne de l'élément dans la matrice
int nextL; // rang dans la liste (lst) du prochain élem. (!=0) sur la lig.
int nextC; // rang dans la liste (lst) du prochain élém. (!=0) sur la col.
};
Le composant Liste utilisé dans MatriceCreuse stocke en liste des éléments de
type Item. Le type Item est spécialisé avec le type ElemNNul dans Item.h.
#include "ElemNNul.h" typedef ElemNNul.h Item; // Spécialisation du type Idem
1) On prend comme convention la liste non nuls est triée d'abord par l'indice de ligne puis par l'indice de colonne. Pour la matrice de la structure de données MatriceCreuse. Cette réprésentation se fera indépendamment de la structure de donnée concrète du type abstrait Liste.
2) Prototypez et codez la fonction (creerMatC) de création d'une variable de type MatriceCreuse. Le role fonctionnel de creerMatC est i) initialisation du champs lst à une liste vode ,ii) initialisation des champs correspondant aux dimensions de la matrice.
3) Codez la fonction (dessallocMatC) de désallocation de la mécmoire dynamique d'une matrice creuse allouée dans la fonction creerMatC
4) Codez la fonction LireMatcBin) qui initialise à partir d'un fichier binaire une variable de type MatriseCreuse. Le fichier binaire est composé des dimensions de la matrice et de la suite des mxn valeurs reelles des elements (triés par ligne puis par colonne) de la matrice A(m,n).
Notation: Pour la suite, on utilisera i) le terme d'indices abstraits pour désigner i et j (0<= i< m et 0<=j<n) les elements d'indices quelconque a(i,j) de la matrice A(m,n) et ii) le terme d'indice concret pour désigner, dans la représentationde A en matrice creuse, le rang r d'un élément non nul dans la liste lst.
5) Soit a'1,4) l'element non nul de A(7,10) d'indices abstraits iA=1 et jA=4, donner l'indice concret rC lui correspondant dans la structure de données MatriceCreuse.
Soit l'indice concrect rC=2 de l'élément non nul dans la structure de donnée de type MatriceCreuse correspondant a A(7,10), donnez les indices abstraits (iA et jA) correspondants
6) Codez la fonction lire qui renvoie pour tout couple d'indices abstraits iA et jA (0<= iA< m et 0<=jA<n) la valeur de l'élement a (iA,jA) de la matrice A(m,n) à partir de la représentation de A en matrice creuse.
Donnez le nombre de comparaisons d'indices abstraits de ligne et de colonne pour la lecture de tous les elements de la ligne 5.
7) On peut remarquer que pour des accès succesifs comme dans le cas de la lecture d'une ligne, l'accàs à l'élèments par la fonction lire revient à balayer la liste des éléments non nuls de la ligne. Ainsi, pour optimiser les acces aux elements successifs, on ajoute à la structure de donnée MAtriceCreuse l' indice concret ( rC) correspondant au dernier accès en lecture ou en écriture d'un élément non nul.
/** @brief Type de matrices creuses */ struct MatriceCreuse int nbLig; int nbCol; Liste* ligne; int rC // indice concrect de lelement (non nul) courant correspondant au dernier accès (en lecture ou en ecriture) } ;
Donnez le nombre de comparaisons d'indices abstraits de colonne pour la lecture de tous les élements de la ligne5.
7) Codez la fonction ecrire qui ecrit la valeur réelle val correspondant à un élément d'indices absatrits iA et jA de la matrice A(m,n) dans la matrice creuse correspondante.
8) Modifier la fonction lire afin d'optimiser la lecture d'une ligne de la matrice originelle.
REmarque: Il est necessaire de change le prototype de la fonction lire. La liste ne peut plus etre en mode de lecture seule car elle doit etre modifiée
Donnez le nombre de comparaisons d'indices abstraits de colonne pour la lecture de tous les élements de la ligne5.
9) Prototypez , commentez et codez la fonction (produit) de calcul de le produit de deux matrices A(m,n) et B(m,n) dont le résultat est la matrice R(m,n)
Indication: Vérifiez les pré conditions dans le code. L'accés aux élements de la matrice étant optimisé,vous pourrez utiliser les fonctions lire et écrire dans un algo qui balaie les matrices A, B et R par des indices abstraits.
JE vous remercie d'avance pour vos reponses, je vous en serai extremement reconnaissante.
