Discussion :

[Arnaud F.]

Bonjour,

voilà mon souci, je cherche sur papier depuis tout à l'heure un algorithme de deux matrices qui sont stockées sous forme d'un tableau unidimensionnel depuis tout à l'heure sans rien trouver de convaincant...

En gros, le prototype est le suivant :

fonction pdtMatriciel(e: Matrice m1, Matrice m2 ; s: Matrice res)

Sachant que m1 et m2 sont déclaré de la sorte : Type matrice[UneLongueur].

Un tel algorithme existe il pour des matrices de taille variable?
En avez vous un à me proposer?

[droggo]

Die,

Rien à faire si tu ne passes pas les dimensions de tes matrices à ta fonction, qui ne peut pas les deviner.
Il faut de même pouvoir renvoyer les dimensions de la matrice résultat.

Je pense qu'une structure mieux pensée serait préférable.

[pseudocode]

Rien à faire si tu ne passes pas les dimensions de tes matrices à ta fonction, qui ne peut pas les deviner.

Sauf si les dimensions sont stockées dans les premieres cellules du tableau, facon paquet tcp/ip.

[droggo]

Luo,

Sauf si les dimensions sont stockées dans les premieres cellules du tableau, facon paquet tcp/ip.

Peut-être, mais comme la question est posée, je ne pense pas, sinon le problème serait résolu de lui-même, car ça montrerait qu'il y a eu une réflexion suffisante le concernant.

[Zavonen]

Voici un exemple en python:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Matrice:
    def __init__(self,lignes,colonnes,L=[]):
        self.m=lignes
        self.n=colonnes
        if len(L)!=self.m*self.n:
            self.coeffs=self.m*self.n*[0]
        else:
            self.coeffs=L
    def coeff(self,i,j):
        return self.coeffs[i*self.n+j]
 
    def affiche(self):
        for i in range(0,self.m):
            for j in range(0,self.n):
                print "%6.2f"%self.coeff(i,j),
            print
        print 
 
    def __mul__(self,other):
        if self.n != other.m:
            print "Multiplicaton impossible"
            return
        R=Matrice(self.m,other.n)
        for i  in range (0,R.m):
            for j in range (0,R.n):
                c=0
                for k in range(0,self.n):
                    c+=self.coeff(i,k)*other.coeff(k,j)
                R.coeffs[i*R.n+j]=c
        return R
 
def main():
    M=Matrice(2,2,[1,2,3,4])
    K=M*M
    K.affiche()
 
 
if __name__ == '__main__':
    main()

[Arnaud F.]

Euh oui, j'ai oublié de le préciser et je m'en excuse, Matrice est une classe (C++) dans laquelle j'ai des attributs nbLignes et nbColonnes

En gros, je connais le nombres de lignes et de mes colonnes

Désolé de l'oubli

[Zavonen]

Essaie qqch comme ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#ifndef MATRIX_H
#define MATRIX_H
 
 
class Matrix
{
    public:
        Matrix();
        Matrix(unsigned int,unsigned int);
        virtual ~Matrix();
       Matrix operator*(Matrix&);
 
    private:
    unsigned int nblignes;
    unsigned int nbcolonnes;
    double * coefficients;
 
};
 
 
 
#endif // MATRIX_H

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include "Matrix.h"
 
 
Matrix::Matrix()
{
    //ctor
}
 
Matrix::Matrix(unsigned int m, unsigned int n)
{
    nblignes=m;
    nbcolonnes=n;
    coefficients=new double[m*n];
    //ctor
}
 
Matrix::~Matrix()
{
    //dtor
    delete coefficients;
}
 
Matrix Matrix::operator* (Matrix &Other)
{
    Matrix Result(nblignes,Other.nbcolonnes);
    for (unsigned int i=0; i<Result.nblignes;i++)
        for (unsigned int j=0; j<Result.nbcolonnes;j++)
        {
            int s=0;
            for (unsigned int k=0;k<nbcolonnes;k++)
                s+=this->coefficients[i*nbcolonnes+k]*Other.coefficients[k*Other.nbcolonnes+j];
            Result.coefficients[i*Result.nbcolonnes+j]=s;
        }
    return Result;
 
}

[Arnaud F.]

ça fonctionne parfaitement

@++

[Anna_star]

Je suis en bts ig et je suis pas tres forte en algo...je voudrais savoir comment on écrit un algo pour multiplier deux matrices carré =)
Si quelqu'un pourrait m'aider, ça serait sympa ^^

Merci

[droggo]

Hio,

Je suis en bts ig et je suis pas tres forte en algo...je voudrais savoir comment on écrit un algo pour multiplier deux matrices carré =)
Si quelqu'un pourrait m'aider, ça serait sympa ^^

Merci

L'algo, c'est ce que tu as appris en maths pour multiplier 2 matrices.

Ensuite, différents implémentations peuvent être plus ou moins efficaces pour un même algorithme, mais c'est une autre histoire.

[millie]

Si c'est toi qui développe la classe Matrice.

Je conseille fortement de créer deux méthodes :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
double getValue(unsigned int x, unsigned int y) const;
void setValue(unsigned int x, unsigned int y, double value);
 
//ou version avec l'operator ()
double & operator()(unsigned int x, unsigned int y);
double operator()(unsigned int x, unsigned int y) const;

Qui positionne ou lit la valeur en (x,y).

[Arnaud F.]

Si c'est toi qui développe la classe Matrice.

Je conseille fortement de créer deux méthodes :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
double getValue(unsigned int x, unsigned int y) const;
void setValue(unsigned int x, unsigned int y, double value);
 
//ou version avec l'operator ()
double & operator()(unsigned int x, unsigned int y);
double operator()(unsigned int x, unsigned int y) const;

Qui positionne ou lit la valeur en (x,y).

Oui c'est moi qui la développe cette classe

Je vais les implémenter

[edit] Pour l'opérateur, ça marche comment les () ? J'aurai juste à faire :

MaMatrice(2,3) ?

[edit2] ça serait que pour les GET les opérateurs (), ou bien?

[millie]

Tu utiliseras comme ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
Matrice m(taillex, tailley);
double d = m(0,0); //utilisation de l'opérateur () avec signature constante
m(4,5) = 45; //utilisation de l'opérateur () avec signature non constante et renvoit d'une référence

[Arnaud F.]

[Zavonen]

Fortement conseillé à implémenter par surcharge d'opérateurs:
somme, différence, produit (c'est fait)
produit par un scalaire
transposée
et plus spécialement pour les carrées:
déterminant
inverse
Le pb est que les opérateurs unaires sont en petit nombre et que C++, du moins je crois, ne permet la surcharge que des opérateurs existants.

[Anna_star]

Hio,

L'algo, c'est ce que tu as appris en maths pour multiplier 2 matrices.

Ensuite, différents implémentations peuvent être plus ou moins efficaces pour un même algorithme, mais c'est une autre histoire.

Oui je sais comment calculer 2 matrices mais je ne sais pas comment l'écrire en algo... donc si vous pourriez m'aider ?

[Jedai]

C'est très instructif tout ça, mais pour éviter d'induire en erreur de futurs visiteurs du sujet, il serait bon de préciser que l'algorithme naïf de multiplication de matrices utilisé ici n'est pas optimal pour de grandes matrices. Le mieux qu'on ait actuellement en théorie est une méthode en O(n^2.38), et en pratique l'algorithme de Strassen en O(n^2.81) est utilisable pour les grandes matrices bien qu'il ait des problèmes de stabilité numérique. De plus on utilise généralement des algorithmes spécialisés pour des types de matrices particuliers.

Autrement dit, si vous avez besoin de faire du calcul matriciel vraiment optimisé, utilisez les librairies spécialisées dans le domaine, n'essayez pas de réinventer la roue (sauf si vous faites de la recherche dans le domaine, mais vous n'avez sûrement pas lu ce sujet dans ce cas...).

--
Jedaï

[Zavonen]

Autrement dit, si vous avez besoin de faire du calcul matriciel vraiment optimisé, utilisez les librairies spécialisées dans le domaine, n'essayez pas de réinventer la roue (sauf si vous faites de la recherche dans le domaine, mais vous n'avez sûrement pas lu ce sujet dans ce cas...).

Très heureux de lire çà.
Un jour j'ai suggéré d'utiliser des librairies spécialisées pour écrire une interface, pour ne pas réinventer la roue. Quelqu'un m'a répondu qu'on était sur un forum d'algo, etc... etc... un puriste sans doute.

[Jedai]

Très heureux de lire çà.
Un jour j'ai suggéré d'utiliser des librairies spécialisées pour écrire une interface, pour ne pas réinventer la roue. Quelqu'un m'a répondu qu'on était sur un forum d'algo, etc... etc... un puriste sans doute.

Et bien il est logique que sur un forum d'algo, on ne cherche pas forcément les meilleures solution du point de vue pratique, mais plutôt à comprendre comment résoudre le problème par soi-même, néanmoins je soulignais plutôt qu'il y avait des domaines ou vraiment, sauf à être un spécialiste, il vaut mieux utiliser ce qui a déjà été fait sauf dans une optique purement pédagogique (et les interfaces en sont un autres exemple, comme tu le dis).

--
Jedaü

[Zavonen]

Le mieux qu'on ait actuellement en théorie est une méthode en O(n^2.38), et en pratique l'algorithme de Strassen en O(n^2.81)

Que représente le paramètre n ici ?
J'ai cru comprendre qu'on s'intéressait au produit de deux matrices rectangulaires.