Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

1 Rapport de laboratoire 1 INF4705 Analyse et conception d’algorithmes Fait par

1 Rapport de laboratoire 1 INF4705 Analyse et conception d’algorithmes Fait par : Simon Parent - 1433553 À Polytechnique de Montréal Le vendredi 4 octobre 2013 2 Table des matières Introduction...............................................................................................................................................3 Description du jeu de données.............................................................................................................3 Résultats expérimentaux.......................................................................................................................3 Analyse et discussion.............................................................................................................................5 Algorithme Conventionnel et de Strassen seuil calculé................................................................5  Test de puissance :...................................................................................................................5  Test du rapport..........................................................................................................................6  Analyse asymptotique..............................................................................................................7 Conclusion................................................................................................................................................8 Bibliographie..............................................................................................................................................9 Annexe :...................................................................................................................................................10 Temps d’exécution de chaque algorithme et chaque matrice :............................................................10 3 Introduction Lors de ce laboratoire, il nous faudra multiplier des matrices de taille différente, grâce à un algorithme conventionnel (naïf), ainsi que la méthode de Strassen (diviser-pour-régner). Chacun de ces algorithmes est efficace, mais il est annoncé que cette efficacité dépend de la taille des matrices considérées. En effet, il nous faudra trouver le seuil de taille qui détermine quel algorithme est plus efficace que l’autre. Lorsque le seuil aura été déterminé, plusieurs autres seuils seront testés pour mettre en perspective l’efficacité du changement d’algorithme lorsqu’on dépasse le seuil. Le code de l’implémentation est compilé en Java. Description du jeu de données Les données sont contenues dans le dossier « donnees », mais il est possible à l’utilisateur de spécifier un dossier personnalisé. Les données sont dans des documents texte, nommés ex_n(chiffre).(chiffre de 1 à 5) (ex : ex_n5.2), parcourues dans le programme et mises dans des tableaux en mémoire. Le format des données est :  Seed : la base de la matrice. La taille de la matrice est 2 seed . Dans les documents de données, il s’agit d’un nombre sur la première ligne du document.  Données : les valeurs de la matrice. Matrices carrées de taille 2 seed , les valeurs varient entre 0 et 3 Résultats expérimentaux Le tableau suivant résume les temps d’exécution pour chacun des algorithmes considérés, ainsi que pour les différents seuils 4 0 10000 20000 30000 40000 50000 60000 Temps d'execution selon les seuils Seuil = 5 Seuil Double Seuil Moitie Seuil 1 Seuil = 6 Seuil = 7 Seuil = 8 Seuil = 9 Conventionnel matrices temps (ms) On peut tout de suite voir que certains algorithmes, spécialement la méthode de multiplication de matrices de Strassen au seuil, ont un temps d’exécution bien plus important au fur et à mesure que la taille de la matrice augmente. Pour déterminer le seuil, dans l’algorithme de strassen Calculé, qui est à la base des autres, plusieurs valeurs de seuil ont étés testées, comme il est explicité dans le tableau plus haut. Cependant, la perspective éloignée rends difficile l’identification du moment où l’algorithme conventionnel devient moins efficace que strassen. L’image ci-dessous montre plus clairement ce seuil : 5 Si vous regardez le tableau 1, qui contient toutes les méthodes testées, vous constaterez que la ligne bleu pâle correspond à l’algorithme conventionnel. On voit plus haut que cette méthode a soudainement un temps d’exécution plus élevé en passant d’un seuil de 7 à 8. Cela signifie que l’algorithme conventionnel est plus efficace pour un seuil de 7 et moins. Ce fut cette preuve qui permit de déterminer le seuil pour la méthode strassenSeuilCalcule. Les données résultantes directement de tous les algorithmes lancés en bloc sont affichées en annexe, où les temps sont en (ms). Le temps le plus long observé est bien avec le seuil de 1, quel que soit la taille de la matrice. Analyse et discussion 6 Algorithme Conventionnel et de Strassen seuil calculé  Test de puissance : moyenne 5.* moyenne 6.* moyenne 7.* moyenne 8.* moyenne 9.* moyenne 10.* 0 2 4 6 8 10 12 14 f(x) = 1.69x - 0.61 f(x) = 2.06x - 1.26 T emps d'execution selon les seuils : Échelle Logarithmique Strassen_seuil_calculé_7 Linear (Strassen_seuil_calculé_7) Conventionnel Linear (Conventionnel) matrices temps (ms) On constate que strassen avec un seuil de 7 a une puissance d’environ 1.69, alors que l’algorithme conventionnel a une puissance d’environ 2.06. C’est une surprise, puisque l’algorithme conventionnel est de l’ordre de 3, et l’algorithme de strassen est de l’ordre de 2.795, selon les notes du cours. Pour obtenir ce graphique, les valeurs de temps moyennes ont étés prises, puis mises en base 2. Un simple graphique en échelle logarithmique nous donne ensuite cette figure. 7  Test du rapport moyenne 5.* moyenne 6.* moyenne 7.* moyenne 8.* moyenne 9.* moyenne 10.* 0 0 0 0 0 0 0 0 0 T emps exposant 2 Conventionnel 7 taille T emps (ms) moyenne 5.* moyenne 6.* moyenne 7.* moyenne 8.* moyenne 9.* moyenne 10.* 0 0 0 0 0 0 0 0 T emps exposant 3 Conventionnel 7 taille T emps (ms) On obtiens ces valeurs avec la formule : b=temps(ms)/taille exposant , où la valeur de b est la convergence on constate qu’on converge pour un exposant entre 2 et 3 (certainement plus près de 3). Cela est plus proche 8  Analyse asymptotique 0 20000000 40000000 60000000 80000000 100000000 120000000 140000000 160000000 7 Ordre de n^2.795 Y 0 200000000 400000000 600000000 800000000 1000000000 1200000000 Conventionnel Ordre de n^3 Y Aucune droite ne peut être tracée sur ces courbes exponentielles, ne permettant pas de trouver une constante multiplicative ou un coût fixe. Ces graphiques on étés pris en mettant le temps d’exécution en (ns) en Y, sur l’axe des y, et la fonction connue f(x) en X. 9 Conclusion En revenant sur mon expérience de laboratoire, je peux affirmer que j’ai eu de la difficulté à terminer le travail demandé. J’ai décidé d’être seul, pour bien comprendre les concepts. Cependant, ma charge de travail s’en est trouvée augmentée, et en combinant le tout avec mes autres cours, j’ai ultimement passé de nombreuses heures, et 2 nuits blanches complètes pour faire ce laboratoire. À l’avenir, je grugerai plus rapidement le laboratoire, m’assurant de ne pas avoir à passer des nuits blanches pour un cours que j’aurais dû passer la première fois. J’avais également commencé initialement par la construction d’un programme qui stoquait chaque matrice dans un vecteur en 3D, mais la logistique était trop lourde, et après avoir utilisé plus de 20 heures de programmation sur cette option, je me suis inspiré d’un code trouvé sur internet (site dans la bibliographie et en commentaire dans le code), simplifiant grandement mon exécution, et me permettant de tout refaire en une nuit. Suite à ce laboratoire, j’en retire une compréhension extensive sur les multiplications de matrices, ainsi que l’importance du choix de l’algorithme choisi pour y parvenir. 10 Bibliographie  Notes en ligne du cours INF4705 .  http://martin-thoma.com/strassen-algorithm-in-python-java-cpp/  http://architects.dzone.com/articles/algorithm-week-strassens 11 12 Annexe : T emps d’exécution de chaque algorithme et chaque matrice : uploads/Management/ tp1-1433553.pdf