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.

Point important

Définition

La complexité d'un algorithme, c'est la quantité des ressources qu'il utilise en fonction de la taille des entrée qu'on lui demande de traiter. On peut par exemple se concentrer sur le temps qu'un algorithme prend pour renvoyer un résultat ou sur la mémoire dont il a besoin. Dans cadre de notre projet, nous nous attarderons plus particulièrement sur la quantité de calcul effectuée en fonction de la taille des entrées, ce qui est par ailleurs très fortement corrélée à la notion de temps. De manière générale, plus un algorithme doit faire de calcul, plus il est lent. (Attention, toutes les opérations arithmétiques de base ne se valent pas)

De manière plus familière, on dira que la complexité d'un algorithme pourrait s'apparenter à son comportement lorsqu'il doit traiter des données plus ou moins grandes. Chaque algorithme a une complexité, et on l'exprime par une fonction qui adopte un comportement similaire au nombre de calcul nécessaire en fonction de la taille des entrées.

Notation

La complexité d'un algorithme se note ${\mathcal {O}}(f(x))$, avec $f(x)$ la fonction qui adopte un comportement similaire à l'algorithme. Pour être plus précis, la notation ${\mathcal {O}}(f(x))$ retranscrit mathématiquement que : (expression mathématique de la complexité)

$\exists$C > 0, $\exists$$n_{0}$, $\forall$ n^0 > n, $f(n)$ ≤ C x n^0

Problématique

Le calcul du produit de deux entiers de manière naïve a une complexité de Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{O}(n^2)} , et celui de deux matrices une complexité de Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{O}(n^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é.