Partie complexe du cours mais totalement fondamentale.
Branchez vos neurones et c'est parti !
Cela signifie que l'on s'appuie sur la puissance de la machine plutôt que sur son intelligence.
Il s'agit de la formule de Leibniz.
Dans le cours précédent, nous avons vu la formule de l'expansion de Laplace.
La formule de Leibniz est simplement une autre manière de calculer un déterminant.
Pour N=3, on a 3! = 6 permutations :
{1, 2, 3} => (-1)^0 * m_{1, 1} * m_{1, 2} * m_{1, 3}
{1, 3, 2} => (-1)^1 * m_{1, 1} * m_{1, 3} * m_{1, 2}
{3, 2, 1} => (-1)^2 * m_{1, 3} * m_{1, 2} * m_{1, 1}
{2, 1, 3} => (-1)^3 * m_{1, 2} * m_{1, 2} * m_{1, 3}
{3, 1, 2} => (-1)^4 * m_{1, 3} * m_{1, 1} * m_{1, 2}
{2, 3, 1} => (-1)^5 * m_{1, 2} * m_{1, 3} * m_{1, 1}
Heureusement, il existe d'autres algorithmes plus efficaces pour calculer un déterminant.
En particulier, l'algorithme de Strassen, en O(N^3) implique une résolution pour N=25 en moins de 25^3 = 15625 multiplications.
Sur le même processeur, il faut moins d'une seconde à cet algorithme pour obtenir le résultat.
Nous n'étudierons pas l'algorithme de Strassen dans ce cours, mais on peut ressentir la différence entre moins d'une seconde et 50 millions d'années pour résoudre le même problème.
On va prendre un exemple.
Dans la boucle imbriquée, on a 2 additions, d'où le 2x^2.
La dernière boucle va de 0 à 98 : 99 instructions.
On y ajoute l'initialisation de y à la première ligne du corps de la fonction f => 100 instructions constantes.
Edmund Georg Hermann LANDAU est un mathématicien berlinois renvoyé en 1934 de l'université par les nazis.
Il décède en 1938.
La notation alternative se dit Grand Oméga de [...].
En mathématiques, on utilise peut-être plus la notation "petit o", et en information, la notation "Grand Oméga".
En pratique, dans l'industrie, cette notation est très rarement utilisée (sauf exception).
De la même manière, la notation asymptotique est peut-être plus utilisée en mathématiques, tandis que la notation Grand Théta est probablement plus utilisée en algorithmique.
Nous allons maintenant détailler chacune de ces classes et donner des exemples.
A chaque itération, on traite un chiffre de N.
Donc le nombre d'instructions est proportionnel au nombre de chiffres dans N.
Le nombre de chiffres dans N est asymptotiquement équivalent à log(N).
Donc on est en O(log N), et en pratique meme en Theta(log N).
En mathématiques, on parle souvent du logarithme népérien tel que ln(e) = 1.
En théorie des nombres et en algorithmique, on utilise le logarithme de base arithmétique : log.
Il s'agit du logarithme en base 10 tel que log(10) = 1.
On peut parfois être tenté d'utiliser le logarithme de base 2 tel que log_2(2) = 1, car nos machines utilisent une représentation binaire.
Mais comme il existe un facteur multiplicatif constant entre les différentes bases logarithmiques, l'ordre de grandeur Grand O est indépendant de la base choisie. Et on choisi donc toujours la base 10.
On utilise plus souvent la récursion pour les problèmes logarithmiques ou exponentiels, mais en réalité, toute classe d'algorithmes (sauf constant) peut être implémenté avec la récursion.
On observe que, comparé à une progression linéaire, la progression logarithmique semble constante.
Cela montre à quel point il est important de rechercher et d'utiliser des algorithmes ayant une meilleure complexité.
Une première observation intéressante est que la progression linéarithmique n'est pas si éloignée de la progression linéaire.
On observe par ailleurs que la progression quadratique écrase la progression linéarithmique, qui est pourtant plus rapide que la progression linéaire.
Cette observation est importante : elle montre que les algorithmes linéarithmiques que nous allons étudier lors du prochain cours sont très largement plus efficaces que des algorithmes quadratiques qui résolvent le même problème.
On observe ici que O(N^3) écrase à nouveau O(N^2). On ferait le même constat entre O(N^4) et O(N^3).
Cela signifie que l'augmentation du rang de la puissance a un impact considérable sur la dégradation des performances.
Si on observe ensuite l'évolution de la complexité exponentielle, on voit qu'elle surpasse très rapidement et très violemment O(N^3). De manière générale, ce serait le cas pour tout k avec O(N^k).
On voit tout de suite, même pour de faibles valeurs de N, la distinction importante entre les complexités polynômiales et exponentielles d'une part, et les autres.
Cette observation est importante en pratique : les algorithmes exponentiels ne sont pas utilisables sans heuristiques, et dans de nombreuses situations, les algorithmes à complexité polynômiale ne sont pas utilisables non plus.
Par exemple, lorsqu'une réponse en temps réel est nécessaire, comme une modification de fréquence accoustique, un algorithme quadratique est inacceptable.
Des algorithmes comme la Transformée de Fourier Rapide (Fast Fourier Transform) ont été développé pour cette raison.
Ici, on zoom simplement pour mieux voir les classes de complexité logarithmique, linéarithmique et linéaire.
C'est une autre manière d'apprécier la différence entre ces classes d'algorithmes.
On a un programme qui prend quelques heures à s'exécuter.
Si on doit exécuter ce programme un nombre de fois proportionnel à l'une des classes de complexité, on regarde le temps que cela va prendre.
Gardons à l'esprit que dans le cas général, l'étude de la complexité des algorithmes donne un très bon indicateur.
En réalité, c'est souvent lorsque l'on compare des algorithmes dans la même classe de complexité que l'on peut éventuellement avoir des surprises.
Un algorithme quadratique restera plus lent en exécution qu'un algorithme linéaire.
En pratique, cet exemple n'est pas très réaliste car il signifierait qu'une personne a écrit 10^100 instructions.
Cela dit, il est possible de générer des programmes. Donc il n'est pas impossible d'écrire un programme qui génère un autre programme pour lequel le nombre d'instructions (sans boucle) est très grand.
En effet, dans la notation O, on s'intéresse au final uniquement au nombre de fois que l'on passe dans la boucle interne de l'algorithme.
Il s'agit ici bien évidemment d'une caricature.
En pratique, tout le monde recherche des modèles mathématiques car ils sont puissants.
De même, tout le monde fait des mesures pour vérifier ses hypothèses.
On parle ici d'un ordinateur "classique", pas d'un super-calculateur ou d'une ferme de calcul.
On ne s'arrête pas ici sur les ALU, FPU et autres unités de calcul dédiés, mais on donne uniquement une vue de très haut niveau.
On s'intéresse donc plus à la concurrence qu'au parallélisme pour améliorer l'efficacité de nos algorithmes.
Attention : lorsque l'on dit que l'on parallélisme un algorithme, on veut dire qu'on va le séparer en tâches qui vont s'exécuter de manière concurrente.
Il y a donc un abus de langage en parallélisation et concurrence.
La classe de complexité reste, de loin, le facteur le plus important.
On parle ici de latence, qui est le temps pour terminer une tâche.
On ne parle pas de "throughput", qui est la quantité d'actions que l'on peut effectuer dans un intervalle de temps.
Que vaut f si p = 1 ?
Qu'est-ce que cela signifie ?
Si p = 1, cela veut dire que l'intégralité du code est parallélisable, ou que 100% du temps est passé dans du code parallélisable.
Dans ce cas, on a f(s, 1) = s, ce qui veut dire que l'accélération théorique maximale est limitée par le nombre de coeurs disponibles.
Cela signifie que même si un code est parallélisable à 95%, on a un facteur d'accélération limité à 20x en pratique, même avec des milliers de coeurs.
Ces supercalculateurs sont eux-aussi contraints par la loi d'Amdahl.
Nos smartphones actuels sont plus puissants que les supercalculateurs des années 1970.
Quelques acteurs du Cloud en 2021 : Heroku, Google, AWS.
Evolutivité verticale : on rajoute du hardware à un PC existant.
Un supercalculateur est basé sur la vertical scalability.
Un cluster de calcul est basé sur la horizontal scalability.
Ce dernier est plus évolutif pour moins cher.
La loi d'Amdahl s'applique également toujours.
Pour le calcul distribué scientifique, on peut mentionner la bibliothèque C++ HPX ou le vénérable MPI.
Pour la gestion de données relationnelles, on peut mentionner les bases de données relationnelles comme PostgreSQL.
Pour la gestion fiable des échanges entre noeuds de calcul, on peut mentionner le pattern Pub/Sub et message queue distribuée comme Kafka.
Pour le Big Data - c'est-à-dire la manipulation d'une grande quantité de données non-relationnelles -, on peut mentionner l'écosystème Hadoop avec Map Reduce, Spark et consorts.
Pour la distribution de milliards de pages web quasi-statiques, on peut mentionner l'architecture REST.
Etc.
Plus précisément, P et NP font référence aux problèmes de recherche.
Cela dit, tout problème (optimisation, décision, etc.) peut se réduire à un problème de recherche.
C'est la raison pour laquelle on a simplifié la définition sur cette diapositive.
L'idée de Non-Déterminisme vient du fait qu'introduire un caractère aléatoire aux machines permet en théorie d'accroître leur puissance de calcul en "devinant" des solutions. La machine "devine" une solution, et prouve ensuite qu'elle est correcte. Plus formellement, cela vient des Machines de Turing Nondéterministes, qui reviennent plus ou moins à des machines quantiques.
On revient sur notre machine de Turing déterministe avant de passer dans le domaine quantique.
Cette image illustre le fait qu'entre 2 observations, la variable observée est dans un état quantique probabiliste.
On appelle le fait d'être potentiellement dans 2 états en même temps la "superposition".
Encore une fois, une observation (la lecture de la valeur de la variable) fixe un état.
Tant qu'il n'y a pas d'observation, on est dans un état superposé.
Les opérations les plus intéressantes ont lieu dans cet état superposé.
Le vecteur (p, q) est dans un espace de probabilité.
Le vecteur (alpha, beta) est dans un espace Euclidien. Il s'agit de l'espace quantique des superpositions.
Ce sont les transformations dans et entre ces espaces qui sont étudiés dans la logique quantique.
On ne rentrera pas plus dans les détails dans ce cours.
Voir les références du cours pour aller plus loin.