Algorithmes de multiplications d'entiers et de matrices

Introduction

Depuis l'apparition des ordinateurs modernes, une quantité faramineuse de calcul a dû être effectué. Les progressions technologiques nous poussent à envisager la puissance de calcul comme une ressource qu'il faut optimiser dans les moindres détails. C'est ainsi que l'optimisation des algorithmes de calcul est devenue cruciale, surtout lorsqu'il nous faut effectuer des opérations sur des très grands entiers par exemple.

Objectif

L'objectif majeur de ce projet est de comprendre de manière plus approfondie ce qu'est la complexité algorithmique. Pour atteindre cet objectif, nous implémenterons plusieurs algorithmes de multiplication qui auront pour but de calculer le produit de grands entiers ou de matrices.

Quelques rappels

(expliquer la notion de complexité, la notation, les courbes éventuellement) ...

Problématique

Le calcul du produit de deux entiers de manière naïve a une complexité de On^2, et celui de deux matrices une complexité de On^3. Afin de mieux comprendre ce qu'est la complexité algorithmique, nous devrons implémenter des algorithmes ayant le même objectif, mais étant plus efficace. Ces algorithmes s'avèreront plus complexes mais devrait aboutir à un calcul plus rapide du produit demandé.

complexité : La multiplication naïve d'entiers

...

complexité : La multiplication naïve de matrices

...