Tous droits réservés

[T.P] Entrons dans la matrice !

Les objets mathématiques se prêtent bien à la sémantique de valeur. Alors, pour ne pas déroger à la tradition, nous allons implémenter un nouveau concept, les matrices. Si vous ne connaissez pas, aucun problème, nous allons aborder rapidement le sujet. Sinon, vous n’avez plus qu’à foncer coder. ;)

Ce chapitre à pour but de nous faire pratiquer toutes les notions vues précédemment.

Qu'est-ce qu'une matrice ?

Un mot pour les mathématiciens

Veuillez nous pardonner si les explications et notations qui suivent ne sont pas parfaitement rigoureuses, le but étant de faire simple.

On peut définir une matrice de manière simple comme étant un tableau de nombres à nn lignes et mm colonnes. Ces nombres sont appelés dimensions de la matrice. Ci-dessous, vous avez un exemple de matrice de dimension 2×32 \times 3.

(123346)\begin{pmatrix} 1 & 2 & 3 \\ 3 & 4 & 6\end{pmatrix}

Si une matrice n’est composée que d’une ligne, on parle de vecteur-ligne. De même, s’il n’y a qu’une colonne, on parle de vecteur-colonne.

Comme pour beaucoup d’objets mathématiques, il est possible d’appliquer un certain nombre d’opérations élémentaires, comme l'addition ou la multiplication. Il existe aussi quelques opérations plus spécifiques aux matrices, comme la transposition.

Addition

L’addition de deux matrices se fait terme à terme. Les deux matrices additionnées doivent être de même dimension.

(123346)+(0494−71)=(16127−37)\begin{pmatrix} 1 & 2 & 3 \\ 3 & 4 & 6\end{pmatrix} + \begin{pmatrix} 0 & 4 & 9 \\ 4 & -7 & 1\end{pmatrix} = \begin{pmatrix} 1 & 6 & 12 \\ 7 & -3 & 7\end{pmatrix}

Le même principe s’applique à la soustraction.

Multiplication par un nombre

Multiplier une matrice par un nombre revient à multiplier chaque terme par ce nombre.

2×(123346)=(2466812)2 \times \begin{pmatrix} 1 & 2 & 3 \\ 3 & 4 & 6\end{pmatrix} = \begin{pmatrix} 2 & 4 & 6 \\ 6 & 8 & 12\end{pmatrix}

Transposition

Transposer une matrice revient à échanger les lignes et les colonnes.

(123346)⇒(132436)\begin{pmatrix} 1 & 2 & 3 \\ 3 & 4 & 6\end{pmatrix} \Rightarrow \begin{pmatrix} 1 & 3 \\ 2 & 4 \\ 3 & 6\end{pmatrix}

Multiplication de deux matrices

Pour définir la multiplication dans le cas général, intéressons-nous d’abord à la multiplication d’un vecteur-colonne par un vecteur-ligne, qu’on appelle produit scalaire. Pour deux matrices de même dimension, calculer leur produit scalaire revient à faire l’opération suivante.

(x1x2...xn)⋅(y1y2...yn)=x1y1+x2y2+...+xnyn=∑i=1nxnyn\begin{pmatrix} x_1 & x2 & ... & x_n \end{pmatrix} \cdot \begin{pmatrix} y_1 \\ y_2 \\ ... \\ y_n\end{pmatrix} = x_1 y_1 + x_2 y_2 + ... + x_n y_n = \sum_{i=1}^{n} x_n y_n

De manière plus générale, la multiplication d’une matrice A(n×m)A(n \times m) par une matrice B(m×p)B(m \times p) donne une matrice C(n×p)C(n \times p) dont chaque élément CijC_{ij} est le produit scalaire de la ligne ii de la matrice AA avec la colonne jj de la matrice BB. L’exemple ci-dessous va vous aider à saisir le principe.

(123346)×(044−791)=(1×0+2×4+3×91×4+2×−7+3×13×0+4×4+6×93×4+4×−7+6×1)=(35−770−10)\begin{pmatrix} 1 & 2 & 3 \\ 3 & 4 & 6\end{pmatrix} \times \begin{pmatrix} 0 & 4 \\ 4 & -7 \\ 9 & 1\end{pmatrix} = \begin{pmatrix} 1 \times 0 + 2 \times 4 + 3 \times 9 & 1 \times 4 + 2 \times -7 + 3 \times 1 \\ 3 \times 0 + 4 \times 4 + 6 \times 9 & 3 \times 4 + 4 \times -7 + 6 \times 1 \end{pmatrix} = \begin{pmatrix} 35 & -7 \\ 70 & -10\end{pmatrix}

D’autres propriétés

Les matrices sont un vaste sujet et il y aurait encore beaucoup à dire. Vous pouvez continuer votre découverte, si le cœur vous en dit, sur de nombreux sites. Vous pouvez par exemple jeter un œil à celui-ci, ou bien encore à la page Wikipédia associée.

Quant à nous, nous nous contenterons de ces notions dans le cadre du T.P. :)

L'énoncé

Comme vous l’avez compris, le but est de pouvoir manipuler des matrices en C++. Mais avant de vous lancer corps et âme dans ce TP, prenons le temps de réfléchir à la conception de notre programme, notamment aux services que l’on souhaite offrir.

Les services

Le premier est bien évidement la création d’une matrice. Sans cette partie, pas de TP. Il serait bien de pouvoir créer une matrice de dimension quelconque, avec éventuellement tous ses éléments ayant une valeur par défaut, mais il faut aussi pouvoir la copier.

Ensuite, on aimerait l’accès à un élément de la matrice, tant en lecture qu’en écriture. Cette opération est possible avec std::vector ou std::string par exemple. Cependant, l’opérateur [] n’accepte qu’un seul argument, alors que nous aimerions pouvoir indiquer la ligne et la colonne de l’élément voulu. Heureusement, il existe un opérateur qui peut nous aider.

Opérateur à utiliser

Il s’agit de (). On peut surcharger cet opérateur en fournissant autant d’arguments que l’on veut. Dans notre cas, il s’agit de le surcharger en lui donnant un indice de ligne et un indice de colonne. Il nous permettra d’écrire matrice(0, 0), par exemple.

Tant qu’on parle des opérateurs, il semble évident que l’on va en implémenter plusieurs autres pour gérer l’addition et la multiplication. Vous devez maintenant avoir l’habitude. Néanmoins, n’oubliez pas que l’on veut proposer la multiplication tant par un entier que par une autre matrice.

Enfin, en vrac, proposons de récupérer les dimensions de la matrice, de l'afficher et puis d’extraire une ligne ou une colonne spécifique, pour en faire respectivement un vecteur-ligne et un vecteur colonne.

Détails d’implémentation

Maintenant que nous avons bien fixé nos services, il est temps de se plonger dans des détails d’implémentations. La grande question est de savoir comment stocker les différents nombres qui composent une matrice, en n’oubliant pas que nous ne connaissons pas sa dimension à l’avance.

Je vais vous aider en vous indiquant qu'il suffit d’utiliser un tableau, de taille lignes * colonnes, tout simplement. Une petite astuce vous aidera à accéder directement au bon élément. Essayez de la trouver sans regarder l’indice.

Astuce secrète

Pour comprendre l’astuce, dites vous que nous avons une matrice de taille 2×32 \times 3, soit une matrice de deux lignes par trois colonnes. Cela fait un tableau de 6 éléments. Un moyen de stocker les éléments est de le faire par colonne, donc d’avoir l’élément M0,0M_{0,0} à l’indice 0, l’élément M1,0M_{1,0} à l’indice 1, l’élément M0,1M_{0,1} à l’indice 2, etc.

Supposons que je veuille l’élément M1,1M_{1,1}. Avec ce système, il faut que j’accède à l’élément d’indice 3. Or, si on regarde, ce chiffre s’obtient en multipliant le nombre de lignes, qui vaut 2 par l’indice y voulu, soit 1, puis en rajoutant l’indice x voulu, soit 1 encore.

L’astuce se répète pour n’importe quel indice (x;y)(x ; y). On obtient donc la formule suivante : y×lignes+xy \times lignes + x

Les tests

Bien entendu, nous voulons nous assurer que notre code fonctionne bien. Nous avons vu quelques exemples mathématiques pour illustrer chacune des opérations, donc nous pouvons nous baser sur les valeurs obtenues pour écrire quelques tests. 

void test_addition()
{
    Matrice m1 { 2, 3 };
    m1(0, 0) = 1;
    m1(0, 1) = 2;
    m1(0, 2) = 3;
    m1(1, 0) = 3;
    m1(1, 1) = 4;
    m1(1, 2) = 6;

    Matrice m2 { 2, 3 };
    m2(0, 0) = 0;
    m2(0, 1) = 4;
    m2(0, 2) = 9;
    m2(1, 0) = 4;
    m2(1, 1) = -7;
    m2(1, 2) = 1;

    Matrice resultat { 2, 3 };
    resultat(0, 0) = 1;
    resultat(0, 1) = 6;
    resultat(0, 2) = 12;
    resultat(1, 0) = 7;
    resultat(1, 1) = -3;
    resultat(1, 2) = 7;

    Matrice const addition { m1 + m2 };

    assert(addition.nb_lignes() == resultat.nb_lignes() && "L'addition n'est pas correcte.");
    assert(addition.nb_colonnes() == resultat.nb_colonnes() && "L'addition n'est pas correcte.");
    for (int i { 0 }; i < addition.nb_lignes(); ++i)
    {
        for (int j { 0 }; j < addition.nb_colonnes(); ++j)
        {
            assert(resultat(i, j) == addition(i, j) && "L'addition n'est pas correcte.");
        }
    }
}

void test_multiplication_entier()
{
    Matrice m1 { 2, 3 };
    m1(0, 0) = 1;
    m1(0, 1) = 2;
    m1(0, 2) = 3;
    m1(1, 0) = 3;
    m1(1, 1) = 4;
    m1(1, 2) = 6;

    Matrice resultat { 2, 3 };
    resultat(0, 0) = 2;
    resultat(0, 1) = 4;
    resultat(0, 2) = 6;
    resultat(1, 0) = 6;
    resultat(1, 1) = 8;
    resultat(1, 2) = 12;

    Matrice const multiplication { m1 * 2 };

    assert(resultat.nb_lignes() == multiplication.nb_lignes() && "La multiplication par un entier n'est pas correcte.");
    assert(resultat.nb_colonnes() == multiplication.nb_colonnes() && "La multiplication par un entier n'est pas correcte.");
    for (int i { 0 }; i < multiplication.nb_lignes(); ++i)
    {
        for (int j { 0 }; j < multiplication.nb_colonnes(); ++j)
        {
            assert(resultat(i, j) == multiplication(i, j) && "La multiplication par un entier n'est pas correcte.");
        }
    }
}

void test_multiplication_matrice()
{
    Matrice m1 { 2, 3 };
    m1(0, 0) = 1;
    m1(0, 1) = 2;
    m1(0, 2) = 3;
    m1(1, 0) = 3;
    m1(1, 1) = 4;
    m1(1, 2) = 6;

    Matrice m2 { 3, 2 };
    m2(0, 0) = 0;
    m2(0, 1) = 4;
    m2(1, 0) = 4;
    m2(1, 1) = -7;
    m2(2, 0) = 9;
    m2(2, 1) = 1;

    Matrice resultat { 2, 2 };
    resultat(0, 0) = 35;
    resultat(0, 1) = -7;
    resultat(1, 0) = 70;
    resultat(1, 1) = -10;

    Matrice const multiplication { m1 * m2 };

    assert(resultat.nb_lignes() == multiplication.nb_lignes() && "La multiplication par une matrice n'est pas correcte.");
    assert(resultat.nb_colonnes() == multiplication.nb_colonnes() && "La multiplication par une matrice n'est pas correcte.");
    for (int i { 0 }; i < multiplication.nb_lignes(); ++i)
    {
        for (int j { 0 }; j < multiplication.nb_colonnes(); ++j)
        {
            assert(resultat(i, j) == multiplication(i, j) && "La multiplication par une matrice n'est pas correcte.");
        }
    }
}

void test_transposition()
{
    Matrice m1 { 2, 3 };
    m1(0, 0) = 1;
    m1(0, 1) = 2;
    m1(0, 2) = 3;
    m1(1, 0) = 3;
    m1(1, 1) = 4;
    m1(1, 2) = 6;

    Matrice resultat { 3, 2 };
    resultat(0, 0) = 1;
    resultat(0, 1) = 3;
    resultat(1, 0) = 2;
    resultat(1, 1) = 4;
    resultat(2, 0) = 3;
    resultat(2, 1) = 6;

    Matrice const transposee { m1.transpose() };

    assert(resultat.nb_lignes() == transposee.nb_lignes() && "La transposition n'est pas correcte.");
    assert(resultat.nb_colonnes() == transposee.nb_colonnes() && "La transposition n'est pas correcte.");
    for (int i { 0 }; i < transposee.nb_lignes(); ++i)
    {
        for (int j { 0 }; j < transposee.nb_colonnes(); ++j)
        {
            assert(resultat(i, j) == transposee(i, j) && "La transposition n'est pas correcte.");
        }
    }
}

void test_affichage()
{
    Matrice m1 { 2, 2 };
    m1(0, 0) = 1;
    m1(0, 1) = 2;
    m1(1, 0) = 3;
    m1(1, 1) = 3;

    Matrice m2 { 2, 2 };
    m2(0, 0) = 0;
    m2(0, 1) = 4;
    m2(1, 0) = 4;
    m2(1, 1) = -7;

    std::cout << m1 << "\n";
    std::cout << m1 + m2 << "\n";
    std::cout << m1 + m2 + m2 << "\n";
}

int main()
{
    test_addition();
    test_multiplication_entier();
    test_multiplication_matrice();
    test_transposition();
    test_affichage();

    return 0;
}

Vous avez maintenant tout ce qu’il vous faut pour faire ce T.P. Bon courage. :)

Correction détaillée

Comment le TP s’est-il passé ? Si vous avez tout fini, ou même pris de l’avance, félicitations. Si vous avez bloqué ou n’avez pas pu tout faire, pas d’inquiétude. La correction est justement là pour vous aider à voir une façon de faire. Elle se trouve ci-dessous au complet.

#ifndef MATRICE_HPP
#define MATRICE_HPP

#include <iosfwd>
#include <vector>

/**
 * @brief Manipulation de matrices.
 */
class Matrice
{
public:
    /**
     * @brief Créé une nouvelle instance de Matrice.
     * @param[in] lignes Le nombre de lignes de la matrice à créer.
     * @param[in] colonne Le nombre de colonnes de la matrice à créer.
     * @pre Le nombre de lignes et de colonnes doit être supérieur à 0.
     * @param[in] valeur_initiale La valeur à donner à chaque élément de la matrice. Vaut 0 par défaut.
     */
    Matrice(std::size_t lignes, std::size_t colonne, int valeur_initiale = 0);

    /**
     * @brief Constructeur de copie par défaut.
     * @param[in] matrice La matrice à copier.
     */
    Matrice(Matrice const & matrice) = default;

    /**
     * @brief Opérateur d'affectation par copie par défaut.
     * @param[in] matrice La matrice à copier.
     * @return La matrice actuelle après copie.
     */
    Matrice& operator=(Matrice const & matrice) = default;

    /**
     * @brief Opérateur d'accès à un élément de la matrice, version constante.
     * @param[in] x L'indice de la ligne voulue.
     * @param[in] y L'indice de la colonne voulue.
     * @pre Les indices de ligne et de colonne doivent être inférieurs aux dimensions de la matrice.
     * @return Une référence constante sur l'indice trouvé.
     */
    int const & operator()(std::size_t x, std::size_t y) const;

    /**
     * @brief Opérateur d'accès à un élément de la matrice.
     * @param[in] x L'indice de la ligne voulue.
     * @param[in] y L'indice de la colonne voulue.
     * @pre Les indices de ligne et de colonne doivent être inférieurs aux dimensions de la matrice.
     * @return Une référence sur l'indice trouvé.
     */
    int& operator()(std::size_t x, std::size_t y);

    /**
     * @brief Additionne une matrice à la matrice courante.
     * @param matrice La matrice à additionner à la matrice courante.
     * @pre La matrice passée en paramètre doit être de même dimension que la matrice courante.
     * @return Matrice& L'objet modifié après addition.
     */
    Matrice& operator+=(Matrice const & matrice);

    /**
     * @brief Opérateur libre d'addition de deux matrices.
     * @param[in] lhs La matrice de gauche. 
     * @param[in] rhs La matrice de droite.
     * @pre Les deux matrices doivent être de même dimension.
     * @return Le résultat de l'addition des deux matrices.
     */
    friend Matrice operator+(Matrice lhs, Matrice const & rhs);

    /**
     * @brief Multiplie la matrice courante par un entier.
     * @param[in] multiplicateur Un entier, par lequel la matrice est multipliée.
     * @return L'objet modifié après multiplication.
     */
    Matrice& operator*=(int multiplicateur);

    /**
     * @brief Opérateur libre de multiplication d'une matrice par un entier.
     * @param[in] m La matrice à multiplier.
     * @param[in] multiplicateur L'entier multiplicateur.
     * @return Le résultat de la multiplication d'une matrice par un entier.
     */
    friend Matrice operator*(Matrice m, int multiplicateur);

    /**
     * @brief Opérateur libre de multiplication d'une matrice par un entier.
     * @param[in] multiplicateur L'entier multiplicateur.
     * @param[in] m La matrice à multiplier.
     * @return Le résultat de la multiplication d'une matrice par un entier.
     */
    friend Matrice operator*(int multiplicateur, Matrice m);

    /**
     * @brief Multiplie la matrice courante par une autre matrice.
     * @param[in] matrice La matrice par laquelle la matrice courante sera multipliée.
     * @return L'objet modifié après multiplication.
     */
    Matrice& operator*=(Matrice const & matrice);

    /**
     * @brief Opérateur libre de multiplications de matrices.
     * @param[in] lhs La matrice de gauche.
     * @param[in] rhs La matrice de droite.
     * @return Le résultat de la multiplication d'une matrice par une autre.
     */
    friend Matrice operator*(Matrice const & lhs, Matrice const & rhs);

    /**
     * @brief Affiche une matrice sur un flux de sortie.
     * @param[in,out] stream Le flux sur lequel sera affichée la matrice.
     * @param[in] matrice La matrice à afficher.
     * @return Le flux de sortie utilisé.
     */
    friend std::ostream& operator<<(std::ostream & stream, Matrice const & matrice);
    
    /**
     * @brief Retourne un vecteur ligne, selon l'indice demandé.
     * @param[in] index_ligne L'index de la ligne désirée.
     * @pre L'index de la ligne désirée doit être strictement inférieur au nombre de lignes de la matrice.
     * @return Un vecteur ligne de type Matrice, correspondant à la ligne demandée.
     */
    Matrice ligne(std::size_t index_ligne) const;

    /**
     * @brief Retourne un vecteur colonne, selon l'indice demandé.
     * @param[in] index_colonne L'index de la colonne désirée.
     * @pre L'index de la colonne désirée doit être strictement inférieur au nombre de colonnes de la matrice.
     * @return Un vecteur colonne de type Matrice, correspondant à la colonne demandée.
     */
    Matrice colonne(std::size_t index_colonne) const;

    /**
     * @brief Transpose la matrice courante.
     * @return La matrice courante une fois transposée.
     */
    Matrice transpose() const;

    /**
     * @brief Donne le nombre de lignes de la matrice actuelle.
     * @return Le nombre de lignes de la matrice actuelle.
     */
    std::size_t nb_lignes() const noexcept;

    /**
     * @brief Donne le nombre de colonnes de la matrice actuelle.
     * @return Le nombre de colonnes de la matrice actuelle.
     */
    std::size_t nb_colonnes() const noexcept;

private:
    /**
     * Permet de calculer la position dans le tableau de l'élement qui se trouve à la ligne et à la colonne demandées.
     * @param[in] ligne La ligne demandée.
     * @param[in] colonne La colonne demandée.
     * @pre La ligne et la colonne doivent être inférieures aux dimensions de la matrice.
     * @returns L'index dans le tableau auquel se trouve l'élément.
     */ 
    std::size_t offset(std::size_t ligne, std::size_t colonne) const noexcept;

    std::size_t m_nb_lignes;
    std::size_t m_nb_colonnes;
    std::vector<int> m_matrice;
};

#endif
Matrice.hpp
#include <algorithm>
#include <cassert>
#include <ostream>
#include <numeric>
#include "Matrice.hpp"

Matrice::Matrice(std::size_t lignes, std::size_t colonnes, int valeur_initiale)
  : m_nb_lignes(lignes), m_nb_colonnes(colonnes), m_matrice(lignes * colonnes, valeur_initiale)
{
    assert(m_nb_lignes > 0 && m_nb_colonnes > 0 && "On ne peut pas avoir une matrice de dimension 0.");
}

std::size_t Matrice::offset(std::size_t ligne, std::size_t colonne) const noexcept
{
    assert(ligne < m_nb_lignes && "Ligne demandée invalide.");
    assert(colonne < m_nb_colonnes && "Colonne demandée invalide.");
    return colonne * m_nb_lignes + ligne;
}

int const & Matrice::operator()(std::size_t x, std::size_t y) const
{
    return m_matrice[offset(x, y)];
}

int& Matrice::operator()(std::size_t x, std::size_t y)
{
    return m_matrice[offset(x, y)];
}

Matrice& Matrice::operator+=(Matrice const & matrice)
{
    assert(nb_lignes() == matrice.nb_lignes() && nb_colonnes() == matrice.nb_colonnes() && "Impossible d'additionner deux matrices de dimensions différentes.");
    for (std::size_t i { 0 }; i < nb_lignes(); ++i)
    {
        for (std::size_t j { 0 }; j < nb_colonnes(); ++j)
        {
            (*this)(i, j) += matrice(i, j);
        }
    }
    return *this;
}

Matrice operator+(Matrice lhs, Matrice const & rhs)
{
    lhs += rhs;
    return lhs;
}

Matrice& Matrice::operator*=(int multiplicateur)
{
    for (std::size_t i { 0 }; i < nb_lignes(); ++i)
    {
        for (std::size_t j { 0 }; j < nb_colonnes(); ++j)
        {
            (*this)(i, j) *= multiplicateur;
        }
    }
    return *this;
}

Matrice operator*(Matrice matrice, int multiplicateur)
{
    matrice *= multiplicateur;
    return matrice;
}

Matrice operator*(int multiplicateur, Matrice matrice)
{
    return matrice * multiplicateur;
}

Matrice& Matrice::operator*=(Matrice const & matrice)
{
    Matrice copie { *this * matrice };
    std::swap(*this, copie);
    return *this; 
}

Matrice operator*(Matrice const & lhs, Matrice const & rhs)
{
    assert(lhs.nb_colonnes() == rhs.nb_lignes() && "Le nombre de colonnes de la matrice multipliée doit être égal au nombre de lignes de la matrice multipliante.");

    Matrice copie { lhs.nb_lignes(), rhs.nb_colonnes() };
    for (std::size_t i { 0 }; i < copie.nb_lignes(); ++i)
    {
        auto const ligne_courante { lhs.ligne(i).m_matrice };
        for (std::size_t j { 0 }; j < copie.nb_colonnes(); ++j)
        {
            auto const colonne_courante { rhs.colonne(j).m_matrice };
            const int valeur { std::inner_product(std::begin(ligne_courante), std::end(ligne_courante), std::begin(colonne_courante), 0) };
            copie(i, j) = valeur;
        }
    }

    return copie;
}

std::ostream& operator<<(std::ostream & stream, Matrice const & matrice)
{
    for (std::size_t i { 0 }; i < matrice.nb_lignes(); ++i)
    {
        for (std::size_t j { 0 }; j < matrice.nb_colonnes(); ++j)
        {
            stream << matrice(i, j) << " ";
        }
        stream << "\n";
    }
    return stream;
}

Matrice Matrice::ligne(std::size_t index_ligne) const
{
    assert(index_ligne < nb_lignes() && "L'index demandé pour la ligne est plus grand que la dimension de la matrice.");

    Matrice matrice_ligne { 1, nb_colonnes() };
    for (std::size_t j { 0 }; j < nb_colonnes(); ++j)
    {
        matrice_ligne(0, j) = (*this)(index_ligne, j);
    }
    return matrice_ligne;
}

Matrice Matrice::colonne(std::size_t index_colonne) const
{
    assert(index_colonne < nb_colonnes() && "L'index demandé pour la colonne est plus grand que la dimension de la matrice.");

    Matrice matrice_colonne { nb_lignes(), 1 };
    for (std::size_t i { 0 }; i < nb_lignes(); ++i)
    {
        matrice_colonne(i, 0) = (*this)(i, index_colonne);
    }
    return matrice_colonne;
}

Matrice Matrice::transpose() const
{
    Matrice transposee { nb_colonnes(), nb_lignes() };
    for (std::size_t i { 0 }; i < nb_lignes(); ++i)
    {
        for (std::size_t j { 0 }; j < nb_colonnes(); ++j)
        {
            transposee(j, i) = (*this)(i, j);
        }
    }

    return transposee;
}

std::size_t Matrice::nb_lignes() const noexcept
{
    return m_nb_lignes;
}

std::size_t Matrice::nb_colonnes() const noexcept
{
    return m_nb_colonnes;
}
Matrice.cpp

Les services

Constructeurs

Commençons par réfléchir à la façon dont nous voulons créer des matrices. Il parait évident de renseigner le nombre de lignes et de colonnes quand on crée une matrice. On peut vouloir aussi initialiser toute la matrice à une valeur précise.

De plus, comme nous sommes en plein dans la sémantique de valeur, on aimerait pouvoir copier une matrice, ce qui signifie que nous avons besoin d’un constructeur par copie et un opérateur d’affectation par recopie. On en déduit donc le code suivant.

Matrice(std::size_t lignes, std::size_t colonne, int valeur_initiale = 0);
// Constructeur par copie.
Matrice(Matrice const & matrice) = default;
// Opérateur d'affectation par recopie
Matrice& operator=(Matrice const & matrice) = default;

Accès aux éléments d’une matrice

De manière similaire à std::vector ou encore std::string, il faut qu’on puisse accéder à un élément de la matrice, tant en lecture qu’en écriture. On doit donc penser à gérer une matrice constante. Puisqu’on sait qu’on doit utiliser l’opérateur (), on obtient les services suivants.

// Version d'accès en lecture, marche avec une matrice const.
int const & operator()(std::size_t x, std::size_t y) const;
// Version d'accès en écriture.
int& operator()(std::size_t x, std::size_t y);

Remarquez l’usage d’assertions, car nous avons des préconditions à respecter sur les index fournis.

Surcharges des opérateurs d’addition et de multiplication

On a vu dans l’énoncé qu’on peux additionner deux matrices de même dimension, multiplier une matrice par un entier ou par une autre matrice. On en déduit donc plusieurs surcharges d’opérateurs, en n’oubliant bien sûr pas leurs versions libres.

// Additionne une matrice à l'objet courant.
Matrice& operator+=(Matrice const & matrice);
// Opérateur libre d'addition.
friend Matrice operator+(Matrice lhs, Matrice const & rhs);

// Multiplie la matrice courante par un entier.
Matrice& operator*=(int multiplicateur);
// Opérateur libre de multiplication par un entier.
friend Matrice operator*(Matrice matrice, int multiplicateur);

// Multiplie l'objet courant par une autre matrice.
Matrice& operator*=(Matrice const & matrice);
// Opérateur libre de multiplication de deux matrices.
friend Matrice operator*(Matrice lhs, Matrice const & rhs);

Autres fonctions utiles

Terminons la définition de notre classe Matrice en parlant de quelques services supplémentaires qu’elle peut être ammenée à fournir. On a déjà la fonction permettant de faire une transposition, qui apparait dans l’énoncé. J’ai personnellement choisi de faire une fonction membre retournant une copie de l’objet courant, après transposition, mais d’autres pourraient considérer que transposition s’applique à l’objet courant. C’est une question de choix.

Matrice transposition() const;

On peut aussi se dire qu’il serait bien d’accéder à une colonne ou une ligne précise de la matrice, les fameux vecteurs lignes et vecteurs colonnes. Cela ajoute deux nouvelles fonctions membres à la liste de nos services.

// Pour obtenir un vecteur ligne.
Matrice ligne(std::size_t index_ligne) const;
// Pour obtenir un vecteur colonne.
Matrice colonne(std::size_t index_colonne) const;

Enfin, il parait important de connaître les dimensions de notre matrice, ce qui nous ammène aux deux dernières fonctions membres à définir. Celles-ci sont très courtes et donc sont définies directement dans le fichier d’en-tête.

// Connaître le nombre de lignes de la matrice courante.
std::size_t nb_lignes() const noexcept { return _lignes; }
// Connaître le nombre de colonnes de la matrice courante.
std::size_t nb_colonnes() const noexcept { return _colonnes; }

Notez qu’on voit ici des détails d’implémentation, ce qui fait une excellente transition avec la partie suivante.

Les détails d’implémentation

Fichiers d’en-tête standards

Notre fichier d’en-tête Matrice.hpp utilise deux composants de la bibliothèque standard, à savoir std::vector et std::ostream. Il faut donc inclure les fichiers d’en-tête correspondants, pour que le nôtre soit valide. On s’assure ainsi qu’il est auto-suffisant, qu’il n’y a pas besoin d’ajouts externes ou de manipulations supplémentaires pour pouvoir l’utiliser.

Le fichier <vector> ne devrait pas vous surprendre. Par contre, l’autre <iosfwd> est nouveau. On l’utilise à la place de <iostream> quand on a simplement besoin de déclarer des types I/O, comme std::ostream, std::istream, std::stringstream, etc. Ce fichier d’en-tête est très léger car il ne contient que ça. À l’opposé, <iostream> contient toutes les implémentations et est donc très lourd.

Constructeurs

En plus des lignes et des colonnes, il faut un tableau dans lequel stocker les nombres de la matrice. Comme nous ne savons pas à l’avance sa taille, un std::vector est tout désigné pour ça. Et comme un de ses constructeurs permet d’initialiser tous les éléments à une certaine valeur, on peut déjà écrire le nôtre.

Matrice::Matrice(std::size_t lignes, std::size_t colonnes, int valeur_initiale)
  : _lignes(lignes), _colonnes(colonnes), _matrice(lignes * colonnes, valeur_initiale)
{
    assert(_lignes > 0 && _colonnes > 0 && "On ne peut pas avoir une matrice de dimension 0.");
}

Notez qu’on utilise ici une assertion pour s’assurer qu’on fournit bien des dimensions correctes. Une matrice de dimension 0 ou moins n’ayant pas de sens, ce serait une erreur de programmation que de l’accepter.

Le constructeur par recopie et l’opérateur d’affectation par recopie seront très bien gérés par le compilateur, donc on se contente de les définir avec default.

Accès aux éléments d’une matrice

L’accès à un élément d’une matrice n’est pas très compliqué à écrire. Il faut simplement penser à une petite astuce pour savoir comment récupérer le bon élément dans le tableau. Si quelque chose vous perturbe, n’hésitez pas à relire les explications que j’ai données dans la partie énoncé.

Notez qu’encore une fois, nous utilisons la programmation par contrat pour nous assurer qu’on ne demande pas à accéder à un élément inexistant de la matrice. Et, afin de ne pas répéter dans deux endroits cette vérification, j’utilise une fonction membre privée qui s’occupe de ça, qui est ensuite appelée dans les deux opérateurs.

std::size_t Matrice::offset(std::size_t ligne, std::size_t colonne) const noexcept
{
    assert(ligne < m_nb_lignes && "Ligne demandée invalide.");
    assert(colonne < m_nb_colonnes && "Colonne demandée invalide.");
    return colonne * m_nb_lignes + ligne;
}

int const & Matrice::operator()(std::size_t x, std::size_t y) const
{
    return m_matrice[offset(x, y)];
}

int& Matrice::operator()(std::size_t x, std::size_t y)
{
    return m_matrice[offset(x, y)];
}

Surcharges des opérateurs d’addition et de multiplication

Parlons maintenant d’un plus gros morceau. Commençons simplement et parlons de l’addition. On rappelle que celle-ci ne peut se faire que si les deux matrices ont la même dimension, d’où le assert pour s’en assurer. Dans une logique de réutilisation, on fait appel à operator() en l’appliquant sur l’objet courant (d’où le *this), ce qui nous permet de ne pas dupliquer la logique d’accès à un élément.

Matrice& Matrice::operator+=(Matrice const & matrice)
{
    assert(nb_lignes() == matrice.nb_lignes() && nb_colonnes() == matrice.nb_colonnes() && "Impossible d'additionner deux matrices de dimensions différentes.");
    for (std::size_t i { 0 }; i < nb_lignes(); ++i)
    {
        for (std::size_t j { 0 }; j < nb_colonnes(); ++j)
        {
            (*this)(i, j) += matrice(i, j);
        }
    }
    return *this;
}

La version libre de l’addition est elle aussi très simple, puisqu’elle réutilise operator+=.

Matrice operator+(Matrice lhs, Matrice const & rhs)
{
    return lhs += rhs;
}

Passons maintenant à la multiplication par un entier. Là encore, l’algorithme est simple puisqu’on doit simplement multiplier chaque élément de la matrice par l’entier en question. Il n’y a pas de précaution ni de vérification particulière à faire, donc pas de assert cette fois-ci.

Matrice& Matrice::operator*=(int multiplicateur)
{
    for (std::size_t i { 0 }; i < nb_lignes(); ++i)
    {
        for (std::size_t j { 0 }; j < nb_colonnes(); ++j)
        {
            (*this)(i, j) *= multiplicateur;
        }
    }
    return *this;
}

La version libre, pareil, très simple.

Matrice operator*(Matrice matrice, int multiplicateur)
{
    matrice *= multiplicateur;
    return matrice;
}

Maintenant, nous abordons le plus gros morceau, la multiplication de deux matrices. On doit commencer par vérifier que la précondition sur les dimensions des matrices multipliées est respectée. Ensuite, on applique l’algorithme, à savoir multiplier chaque ligne de la matrice actuelle par chaque colonne de la matrice passée en paramètre.

Sauf que voilà, si on modifie la matrice courante, cela va fausser les résultats puisque des éléments auront été modifiés en cours de route puis réutilisés dans les calculs suivants. On doit donc utiliser une copie. C’est justement ce que fait l’opérateur libre de multiplication. Cela veut dire que, de manière exceptionnelle, nous allons écrire l’opérateur intégré *= en fonction du libre *.

Sur cette copie, on va pouvoir faire la multiplication de chaque vecteur-ligne par chaque vecteur-colonne, qu’on peut obtenir avec les fonctions membres lignes et colonnes, que l’on définira juste après.

Cette multiplication revient à faire une somme de produits. Un algorithme comme celui-ci est assez commun. Alors commençons par regarder dans la bibliothèque standard. Ça tombe bien, la fonction std::inner_product sert justement à ça. C’est ainsi qu’on peut obtenir l’entier résultat de la multiplication d’un vecteur-ligne par un vecteur-colonne.

const int valeur { std::inner_product(std::begin(ligne_courante), std::end(ligne_courante), std::begin(colonne_courante), 0) };
copie(i, j) = valeur;

On obtient au final le code suivant pour l’opérateur libre.

Matrice operator*(Matrice const & lhs, Matrice const & rhs)
{
    assert(lhs.nb_colonnes() == rhs.nb_lignes() && "Le nombre de colonnes de la matrice multipliée doit être égal au nombre de lignes de la matrice multipliante.");

    Matrice copie { lhs.nb_lignes(), rhs.nb_colonnes() };
    for (std::size_t i { 0 }; i < copie.nb_lignes(); ++i)
    {
        auto const ligne_courante { lhs.ligne(i).m_matrice };
        for (std::size_t j { 0 }; j < copie.nb_colonnes(); ++j)
        {
            auto const colonne_courante { rhs.colonne(j).m_matrice };
            const int valeur { std::inner_product(std::begin(ligne_courante), std::end(ligne_courante), std::begin(colonne_courante), 0) };
            copie(i, j) = valeur;
        }
    }

    return copie;
}

Reste à écrire l’opérateur intégré. Comment mettre à jour notre objet avec le nouveau résultat ? En l'échangeant. Encore une fois, la bibliothèque standard contient ce qu’il faut, avec std::swap. 

Matrice& Matrice::operator*=(Matrice const & matrice)
{
    Matrice copie { *this * matrice };
    // On échange l'objet courant avec la copie.
    std::swap(*this, copie);
    // L'objet courant est à jour et contient bien le résultat attendu, on peut donc le renvoyer.
    return *this;
}

Autres fonctions utiles

Pour que la surcharge de l’opérateur *= puisse fonctionner, nous devons définir les fonctions membres lignes et colonnes. Celles-ci sont simples et ne consistent qu’en un simple tour de boucle.

Matrice Matrice::ligne(std::size_t index_ligne) const
{
    assert(index_ligne < nb_lignes() && "L'index demandé pour la ligne est plus grand que la dimension de la matrice.");

    Matrice matrice_ligne { 1, nb_colonnes() };
    for (std::size_t j { 0 }; j < nb_colonnes(); ++j)
    {
        matrice_ligne(0, j) = (*this)(index_ligne, j);
    }
    return matrice_ligne;
}

Matrice Matrice::colonne(std::size_t index_colonne) const
{
    assert(index_colonne < nb_colonnes() && "L'index demandé pour la colonne est plus grand que la dimension de la matrice.");

    Matrice matrice_colonne { nb_lignes(), 1 };
    for (std::size_t i { 0 }; i < nb_lignes(); ++i)
    {
        matrice_colonne(i, 0) = (*this)(i, index_colonne);
    }
    return matrice_colonne;
}

Ensuite, la transposition ne devrait pas vous causer trop de problème, puisqu’il s’agit simplement d’inverser les indices de lignes et de colonnes.

Matrice Matrice::transposition() const
{
    Matrice transposee { nb_colonnes(), nb_lignes() };
    for (std::size_t i { 0 }; i < nb_lignes(); ++i)
    {
        for (std::size_t j { 0 }; j < nb_colonnes(); ++j)
        {
            transposee(j, i) = (*this)(i, j);
        }
    }

    return transposee;
}

Enfin, il ne reste que l’affichage, qui nous permettra de visualiser les résultats. Dans une classe plus complète, destinée à être utilisée par d’autres, nous ne l’écririons pas, car le formattage et l’affichage des données dépend beaucoup du contexte et des besoins de l’utilisateur, donc nous ne voudrions pas le forcer à afficher ses matrices d’une certaine façon. Pour le T.P, on se le permet. :)

std::ostream& operator<<(std::ostream & stream, Matrice const & matrice)
{
    for (std::size_t i { 0 }; i < matrice.nb_lignes(); ++i)
    {
        for (std::size_t j { 0 }; j < matrice.nb_colonnes(); ++j)
        {
            stream << matrice(i, j) << " ";
        }
        stream <<  "\n";
    }
    return stream;
}

Aller plus loin

Travailler sur les matrices vous a mis l’eau à la bouche ? Vous voulez d’autres idées pour pratiquer la sémantique de valeur ? Les exercices suivants vont vous plaire.

Le plus grand nombre

Comme vous le savez, les types comme int ou double ont une taille maximale, que vous pouvez retrouver dans l’en-tête <limits>. Et si jamais on veut manipuler des entiers encore plus grands ? Il faut coder.

Le but de cet exercice est de pouvoir manipuler des entiers très, très grands. Pour cela, on peut utiliser des chaînes de caractères. Mais plutôt que de les manipuler nous-mêmes, nous allons encapsuler tout ça dans une belle classe, qui nous fournira des services simples à utiliser, comme l’addition, la soustraction, ou encore la valeur absolue.

Vous pouvez vous servir du code suivant comme base, pour vous donner une idée de comment la classe est utilisée.

int main()
{
    BigInt a { 420 };
    BigInt b { "48879554321858363547485554545557454555445" };

    // Doit afficher 48879554321858363547485554545557454555865.
    std::cout << a + b << std::endl;

    // Doit afficher 48879554321858363547485554545557454555025.
    std::cout << a - b << std::endl;

    // Doit afficher 20529412815180512689943932909134130913286900.
    std::cout << a * b << std::endl;

    // Doit afficher 116379891242519913208298939394184415608.
    std::cout << a / b << std::endl;

    return 0;
}

Des polynômes

Continuons dans notre voyage mathématique en parlant maintenant des polynômes, ces outils d’algèbre qu’on commence à découvrir au lycée et qui ont la forme suivante.

P(x)=∑i=0naixi=a0+a1x+a2x2+⋯+anxn,n≥0P(x) = \sum_{i=0}^n a_ix^i = a_0 + a_1x+ a_2x^2 + \dotsb + a_nx^n , \quad n \ge 0

De même que pour des réels ou des entiers, il est possible de leur appliquer plusieurs opérations, dont les quatre élémentaires. Le but de l’exercice est donc de créer une classe encapsulant ces différents services.

Si les maths et vous, ça fait 4…

Si vous ne connaissez pas les polynômes ou n’êtes pas très à l’aise en mathématiques, ne vous en faîtes pas. Vous pouvez vous contenter d’implémenter l’addition et la soustraction, qui sont les opérations les plus simples.

Voici un exemple d’utilisation, pour vous inspirer.

int main()
{
    Polynome p1 { "3x^2+x+7" };
    Polynome p2 { "4x^3-3x^2+x+1" };

    // Doit afficher 4x^3+2x+8.
    std::cout << p1 + p2 << std::endl;
    // Doit afficher -4x^3+6x^2+6.
    std::cout << p1 - p2 << std::endl;
    // Doit afficher 12x^5-5x^4+28x^3-17x^2+8x+7.
    std::cout << p1 * p2 << std::endl;

    return 0;
}

En résumé

  • Nous avons pu pratiquer toutes les notions vues précédemment.
  • Nous avons revu l’importance de chercher au préalable si une fonction ou un algorithme n’existe pas déjà dans la bibliothèque standard.
  • Nous avons pu voir l’importance de d’abord réfléchir aux services que propose une classe et seulement après de penser aux détails d’implémentation.