Remerciez-le!

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

Tp1 1433553 Rapport de laboratoire INF Analyse et conception d ? algorithmes Fait par Simon Parent - À Polytechnique de Montréal Le vendredi octobre C Table des matières Introduction Description du jeu de données Résultats expérimentaux Analyse et discuss

Rapport de laboratoire INF Analyse et conception d ? algorithmes Fait par Simon Parent - À Polytechnique de Montréal Le vendredi octobre C Table des matières Introduction Description du jeu de données Résultats expérimentaux Analyse et discussion Algorithme Conventionnel et de Strassen seuil calculé Test de puissance Test du rapport Analyse asymptotique Conclusion Bibliographie Annexe Temps d ? exécution de chaque algorithme et chaque matrice C Introduction Lors de ce laboratoire il nous faudra multiplier des matrices de taille di ?érente gr? ce à un algorithme conventionnel na? f ainsi que la méthode de Strassen diviser-pour-régner Chacun de ces algorithmes est e ?cace mais il est annoncé que cette e ?cacité dépend de la taille des matrices considérées En e ?et il nous faudra trouver le seuil de taille qui détermine quel algorithme est plus e ?cace que l ? autre Lorsque le seuil aura été déterminé plusieurs autres seuils seront testés pour mettre en perspective l ? e ?cacité 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éci ?er un dossier personnalisé Les données sont dans des documents texte nommés exn chi ?re chi ?re de à ex exn 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 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 seed les valeurs varient entre et 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 di ?érents seuils C Temps d'execution selon les seuils Seuil Seuil Double Seuil Moitie Seuil Seuil Seuil Seuil Seuil Conventionnel temps ms m atrices 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 di ?cile l ? identi ?cation du moment o? l ? algorithme conventionnel devient moins e ?cace que strassen L ? image ci-dessous montre plus clairement ce seuil C Si vous regardez le tableau 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 à Cela signi ?e que l ? algorithme conventionnel