TD 8 C++: allocation dynamique; Matrices.

Rappels


Exercice 1: Matrices

  1. Implémentez dans un fichier 1.1.cc la classe Matrix déclarée ci-dessous (télécharger: 1.1.h, ne le modifiez pas!):
    class Matrix {
     public:
      Matrix(int num_rows, int num_columns);
      ~Matrix();
    
      int NumRows() const;
      int NumColumns() const;
    
      double& Element(int row, int col);
    
     private:
      int num_rows_;
      int num_columns_;
      // We'll use the "flat" representation.
      double* elements_;
    };
    Indices:
    Testez votre code avec:
    rm 1.tar.gz; wget --no-cache http://fabien.viger.free.fr/cpp/td8/1.tar.gz && tar xf 1.tar.gz
    make 1.1
    RENDU: 1.1.cc

  2. Copiez 1.1.h et 1.1.cc dans 1.2.h et 1.2.cc et ajoutez une fonction statique Identity dans la class Matrix pour créer une matrice identité de taille n.
    N'oubliez pas de changer le #include "1.1.h" vers 1.2.h!
    Testez votre code avec: make 1.2

    RENDUS: 1.2.h, 1.2.cc

  3. Copiez 1.2.h et 1.2.cc dans 1.3.h et 1.3.cc et essayez:
    make 1.3.1
    puis:
    make 1.3.2
    Vous devriez avoir des erreurs: ça compile bien, mais ça ne tourne pas!
    Regardez les fichiers tests 1.3.1.test.cc et 1.3.2.test.cc (ré-inclus ci-dessous, mais ils doivent déja être dans votre repertoire de travail):
    #include "main_utils.h"
    #include "1.3.h"
    
    int main() {
      Matrix a = Matrix::Identity(5);
      Matrix b = a;
      Matrix c = b;
      c.Element(2, 1) = 4.5;
      CHECK_EQ(c.Element(2, 1), 4.5);
      CHECK_EQ(b.Element(2, 1), 0.0);
      CHECK_EQ(a.Element(2, 1), 0.0);
      cout << "PASSED" << endl;
    }
    #include "main_utils.h"
    #include "1.3.h"
    
    int main() {
      Matrix a = Matrix::Identity(5);
      Matrix b = a;
      cout << "PASSED" << endl;
    }
    Quel est le problème? (aide au tableau)

    Pour le réparer, ajoutez un constructeur de copie valable. Vérifiez que make 1.3.1 et make 1.3.2 marchent bien desormais.

    NOTE: Normalement on devrait aussi ajouter l'opérateur d'assignment (operator=), ainsi que le constructeur par transfer (move constructor) et l'opérateur d'assignement par transfer (move assignment operators) en C++11.
    Pour comprendre quand l' operator= est utilisé au lieu du constructeur par copie, voir cette page qui l'explique en 2 temps 3 mouvements.

    Vérifiez encore avec make 1.3.3.

    RENDUS: 1.3.h, 1.3.cc

  4. De même, copiez votre code dans 1.4.h et 1.4.cc puis essayez make 1.4.
    Essayez de comprendre ce qui cloche en regardant 1.4.test.cc (également inclus ci-dessous).
    Comment le réparer, sans toucher 1.4.test.cc? (aide au tableau)
    #include "main_utils.h"
    #include "1.4.h"
    
    int main() {
      Matrix a(4, 3);
      a.Element(2, 1) = 42.0;
      a.Element(3, 2) = -3.5;
      const Matrix b = a;
      cout << "b[2][1] = " << b.Element(2, 1) << endl;
      cout << "b[3][2] = " << b.Element(3, 2) << endl;
      cout << "PASSED" << endl;
    }
    RENDUS: 1.4.h, 1.4.cc

  5. On va à présent écrire des petit modules d'opérations sur les matrices.
    Commençons par l'affichage:
    Écrire des fichiers matrix_ops.h et matrix_ops.cc contenant la déclaration et la définition d'une fonction void PrintMatrix(const Matrix& m), qui affiche une matrice comme ça (même les espaces doivent parfaitement respecter l'exemple!):
    [[       1       2     3.4]
     [    -2.1 3.14159      -9]]
    Indices Vérifiez: make 1.5

    RENDUS: matrix_ops.h et matrix_ops.cc.

  6. On va maintenant écrire le produit matriciel.
    Toujours dans les même fichiers matrix_ops.h et matrix_ops.cc, ajoutez une fonction Matrix MatrixProd(const Matrix& a, const Matrix& b) qui calcule a * b et le renvoie dans une nouvelle matrice. Vous pourrez supposer que les dimensions de a et b collent bien.
    Verifiez vous-même, avec votre propre fichier 1.6.test.cc! Vous pouvez par exemple:

    RENDUS: matrix_ops.h et matrix_ops.cc mis à jour, et 1.6.test.cc

  7. Pour finir, on va écrire l'exponentiation rapide pour calculer la puissance n-ième (n entier positif ou nul) d'une matrice.

    Ajoutez à matrix_ops.h et matrix_ops.cc une fonction Matrix MatrixPower(const Matrix& m, int p) qui, pour une matrice carrée m et un exposant entier p, calcule mp.

    Indices importants:
    Vérifiez: make 1.7

    RENDUS: matrix_ops.h et matrix_ops.cc mis à jour.

    BONUS: 1.7.txt qui donne la complexité (en fonction de p et de la taille n de la matrice).