L'implémentation de votre classe Tableau doit offrir l'interface publique suivante. Tous les constructeurs, fonctions et opérateurs suivants doivent être implémentés.
template <class T>
class Tableau {
public:
// Constructeurs
Tableau(int capacite_initiale=4);
Tableau(const Tableau<T>&);
~Tableau();
// Fonctions de modifications
void ajouter(const T& element); // à la fin
void vider();
void inserer(const T& element, int index = 0);
void enlever(int index = 0);
void enlever_dernier();
// Opérateurs d'accès []
T& operator[] (int index);
const T& operator[] (int index) const;
// Fonctions utilitaires
bool vide() const;
int taille() const;
int chercher(const T& element) const; // retourne indice première occurrence
bool contient(const T& element) const;
// Opérateurs
Tableau<T>& operator = (const Tableau<T>& autre);
bool operator == (const Tableau<T>& autre) const;
private:
// ...
};
La classe Matrice doit quant-à-elle offrir l'interface publique suivante en faisant usage d'un tableau unidimensionnel pour représenter une matrice.
template <class T>
class Matrice {
public:
// Constructeur
Matrice(int lignes = 1, int colonnes = 1);
Matrice t() const; // Transposition de la matrice
void ajouterLigne(int position, const T& element = T());
// Opérateurs d'accès ()
T& operator() (int i, int j);
const T& operator() (int i, int j) const;
// Opérateurs
bool operator == (const Matrice<T>& autre) const;
bool operator != (const Matrice<T>& autre) const;
Matrice<T> operator + (const Matrice<T>& autre) const;
Matrice<T> operator * (const Matrice<T>& autre) const;
friend std::istream& operator >> (std::istream& is, Matrice<T>& matrice);
private:
// ...
};
Vous pouvez ajouter d'autres fonctionnalités, mais pas en retirer. Si vous ajoutez d'autres fonctionnalités, ces dernières ne devraient pas nuire au fonctionnement et à la performance de celles demandées. Vous pouvez modifier la représentation autant que vous le souhaitez.
Vous devez implémenter l'opérateur de produit matriciel (operator*) en utilisant l'algorithme classique de manière efficace. Il est possible de prouver mathématiquement que l'ordre des trois boucles imbriquées permettant le calcul du produit n'influence pas le résultat obtenu. De plus, la complexité temporelle asymptotique reste la même en permutant les boucles. On aimerait cependant avoir une analyse empirique qui permettrait de déterminer si ces résultats théoriques s'observent en pratique. Il vous est donc demandé:
Taille IJK IKJ JIK JKI KIJ KJI 100 ? ? ? ? ? ? 200 ? ? ? ? ? ? 300 ? ? ? ? ? ? 400 ? ? ? ? ? ? 500 ? ? ? ? ? ? 600 ? ? ? ? ? ? 700 ? ? ? ? ? ? 800 ? ? ? ? ? ? 900 ? ? ? ? ? ? 1000 ? ? ? ? ? ? 1100 ? ? ? ? ? ? 1200 ? ? ? ? ? ?où les nombres sur une même ligne sont délimités par une tabulation et les '?' sont les temps d'exécution en milli-secondes que vous obtiendrai pour les différentes méthodes de multiplication de matrices. Les temps d'exécution doivent être arrondis à la milliseconde près.
Votre implémentation doit viser la perfection ! Lorsque vous avez différents choix possibles, au niveau de la représentation ou des algorithmes, vous devez autant que possible prendre les meilleurs choix possibles. Ces choix peuvent avoir des impacts différents sur l'efficacité (temps et mémoire) et la lisibilité du code.
Par exemple, examinons le constructeur par copie suivant.
template <class T>
Tableau<T>::Tableau(const Tableau& autre)
: nbElements(0), capacite(0), elements(nullptr) {
for(int i = 0; i < autre.taille(); i++)
ajouter(autre[i]);
}
L'implémentation ci-haut fonctionne correctement (bon résultat).
Sa simplicité fait en sorte qu'elle est facile à le comprendre et à le vérifier.
Toutefois, cette implémentation est imparfaite sur le plan de l'efficacité.
Il faut être vigilant au fait que la fonction publique ajouter vérifie systématiquement la capacité du tableau et que dans le cas ci-haut, elle provoquera plusieurs agrandissements, donc plusieurs allocations de mémoire.
Lorsque la taille ultime du tableau est inconnue à l'avance, nous avons vu que cela est même inévitable.
Cependant, dans le présent contexte, les réallocations du tableau natif sont évitables.
En effet, la taille du tableau autre étant connue,
il est possible de construire le nouveau tableau natif directement avec la bonne capacité.
C'est ainsi que nous avons obtenu la solution proposée dans les notes de cours, reproduite ci-dessous.
template <class T>
Tableau<T>::Tableau(const Tableau& autre)
: capacite(autre.nbElements), // ou autre.capacite
nbElements(autre.nbElements),
elements(new T[capacite]) {
for(int i = 0; i < nbElements; i++)
elements[i] = autre.elements[i];
}
Atteindre la perfection dans toutes dimensions (temps, mémoire, simplicité, etc.) simultanément n'est pas toujours possible.
Lorsque certaines dimensions sont en opposition, des compromis sont requis.
Par exemple, nous avons vu que de doubler la capacité du tableau natif était une politique appropriée.
En effet, c'est un compromis entre le temps d'exécution et la mémoire utilisée.
Cela permet à la fonction ajouter d'avoir un coût amorti en O(1).
Toutefois, le prix à payer est d'accepter une certaine perte de mémoire.
En effet, on peut se retrouver avec des situations où un tableau est à moitié plein.
Généralement, il s'agit d'une perte raisonnable étant donné l'avantage d'obtenir un ajout en temps constant.
Dans le cadre du TP1, lorsqu'il n'est pas possible d'atteindre la perfection dans toutes les dimensions, vous devez prioriser l'ordre suivant:
Vous devez implémenter et utiliser votre propre classe générique Tableau selon le squelette dans tableau.h du laboratoire 3. Vous devez implémenter votre propre classe générique Matrice dans un fichier matrice.h. Pour l'instant, l'utilisation des conteneurs de la bibliothèque standard de C++ (ex.: std::vector ou std::list) n'est pas permise. Ce sera permis plus tard dans le cours.
Relisez les Politiques et les directives sur les outils informatiques dans le cours INF3105. Votre TP1 doit pouvoir être compilé avec g++ version 11 (version installée sur le serveur java.labunix.uqam.ca).
Vous pouvez faire ce travail en équipe de 1 ou 2. Toutefois, tous les membres de l'équipe doivent contribuer à l'ensemble du travail et non à seulement quelques parties. Le travail d'équipe vise à favoriser les discussions et l'entraide. Le travail d'équipe ne vise pas à réduire la tâche. Ainsi, se diviser la tâche en deux n'est pas une méthode de travail d'équipe appropriée dans ce cours. La participation inadéquate des membres de l'équipe peut être considérée comme du plagiat. Le professeur et le correcteur pourront sélectionner quelques équipes au hasard afin de vérifier que tous les membres sont capables d'expliquer l'ensemble du travail.
Des tests sont inclus avec le squelette de départ dans tp1.zip. Les exécutables test_tableau et test_matrice permettent de tester les classes Tableau et Matrice respectivement. Les tests ne sont cependant pas exhaustifs. Il est suggéré d'effectuer des tests supplémentaires pour valider votre code.
Les matrices à utiliser pour effectuer l'évaluation empirique de vos produits matriciels sont disponibles dans tests.tar.xz. Vous devez extraire les tests à la racine de votre projet. La commande pour extraire est
tar xaf tests.tar.xz
Vous devez soumettre votre TP au plus tard le 2 juin 2024 à 23h59m59s EST (heure de Montréal).
Tous les membres de l'équipe doivent:
Vous pouvez soumettre votre TP et les réponses au questionnaire autant de fois que vous voulez. Seule la dernière soumission sera considérée.
Ce travail pratique compte pour 5% de la note finale.
| Critère | Description | Points | ||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| A. | Respect des directives pour la remise
|
10 | ||||||||||||||||||||||||
| B. | Appréciation générale
|
10 | ||||||||||||||||||||||||
| C. | Gestion de la mémoire
|
10 | ||||||||||||||||||||||||
| D. | Fonctionnement correct 15 points: les tests du Tableau (fournis et ajoutés) fonctionnent tous. 25 points: les tests de la Matrice (fournis et ajoutés) fonctionnent tous. |
40 | ||||||||||||||||||||||||
| E. | Exactitude de l'auto-évaluation déclarée dans le formulaire de remise
Attention : les tests fournis ne sont pas nécessairement ceux qui seront utilisés pour la correction. De nouveaux tests pourront être utilisés. |
10 | ||||||||||||||||||||||||
| F. | Analyse et complexité Réponses correctes au questionnaire portant sur le TP1. |
20 | ||||||||||||||||||||||||
| Total | 100 | |||||||||||||||||||||||||