TD 8 C++: allocation dynamique; Matrices.

Rappels

• Page du Cours
• Procédure de rendu
• Pour vérifier le rendu de ce TD: test.sh

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:
   • On utilise la représentation plate
   • Element(i, j) est l'élement à la rangée i et la colonne j. On indexe a partir de zéro.
   • Il faudra bien initialiser les éléments à zéro. Regardez l'excellente réponse sur la question (sur stackoverflow.com)
   • N'oubliez pas de libérer la mémoire...
   
   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, changez le #include "1.2.h" vers 1.3.h, 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, changez le #include "1.3.h" vers 1.4.h, et 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
   • On pourra utiliser printf("% 8g", ...) pour afficher un double aligné à droite, en prenant au moins 8 caractères.
     Voir la documentation. Il faut inclure <cstdio>.
   • Pensez à inclure 1.4.h
     Vous aurez sans doute un souci de double inclusion de "1.4.h". C'est un grand classique des projets C++ avec plusieurs fichiers!
     La parade est d'insérer le code suivant autour du contenu de 1.4.h:

     #ifndef _1_4_H
     #define _1_4_H
     ...
     ...
     #endif  // _1_4_H

   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:
   • Vous inspirer de 1.2.test.cc pour l'ossature (notamment le #include "main_utils.h" qui vous donne CHECK_EQ(..)), et de 1.5.test.cc pour l'entrée manuelle d'une matrice.
   • Remplir une petite matrice avec des nombres au hasard, et vérifier que son produit avec l'identité, à droite ou à gauche, est égal à la matrice de départ
   • Essayer une petite multiplication, comme celle donnée en exemple sur la page wikipédia.
   Faites en sorte que 1.6.test.cc puisse tourner avec:

   g++ -std=c++11 1.4.cc matrix_ops.cc 1.6.test.cc && ./a.out

   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 m^p.
   
   Indices importants:
   • Il est dangereux de manipuler des classes dont un des trois (destructeur, constructeur par copie, operateur d'assignement =) a été "personalisé" sans que les 3 soient personalisés.
     C'est pourtant ce qu'on a fait jusqu'ici! Car on a pas encore personalisé l'opérateur d'assignement operator=.
     Par exemple, le code suivant est problématique, au niveau de la 2^ème ligne:

     Matrix x = quelquechose;
     x = MatrixProd(x, x);

     Pour réparer cette erreur, vous pouvez personaliser l'operator= vous-même, par exemple. Vous pouvez aussi choisir de complètement éviter l'opérateur =, en s'appuyant par exemple sur une fonction void CopyTo(const Matrix& from, Matrix* to) qui copie from dans to, en supposant qu'elles ont déja les mêmes dimensions; fonction que vous ajouteriez vous-même a matrix_ops.h.
   • Attention aussi à l'overflow avec le dernier bit de la puissance entière!
   
   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).