Pourquoi faire des algorithmes rapides ?

Algorithme 

… Un algorithme prend en entrée des données et fournit un résultat permettant de donner la réponse à un problème
…Un algorithme = une série d’opérations à effectuer : †Opérations exécutées en séquence ⇒algorithme séquentiel. †Opérations exécutées en parallèle ⇒algorithme parallèle. †Opérations exécutées sur un réseau de processeurs ⇒algorithme réparti ou distribué. p
…Mise en œuvre de l’algorithme †= implémentation (plus général que le codage) †= écriture de ces opérations dans un langage de programmation. Donne un programme.
…Un programme implémente un algorithme
…Thèse de Turing-Church : les problèmes ayant une solution algorithmique sont ceux résolvables par une machine de algorithmique sont ceux résolvables par une machine de Turing (théorie de la calculabilité)
…On ne peut pas résoudre tous les problèmes avec des algorithmes (indécidabilité) †Problème de la halte †Savoir de façon indépendante si un algorithme est juste
…Tous les algorithmes ne sont pas équivalents. On les différencie selon 2 critères †Temps de calcul : lents vs rapides †Mémoire utilisée : peu vs beaucoup pp …On parle de complexité en temps (vitesse) ou en espace (mémoire utilisée) (mémoire utilisée)

Pourquoi faire des algorithmes rapides?

…Pourquoi faire des algo efficaces ?  Les ordinateurs vont super vite ! …Je peux faire un algorithme en n2avec n=10000 …Je voudrais faire avec n=100000 Tous les 2 ans la …Je voudrais faire avec n=100000. Tous les 2 ans la puissance des ordinateurs est multipliée par 2 (optimiste) Quand estce que je pourrais faire avec (optimiste). Quand est-ce que je pourrais faire avec n=100000 ?… Pourquoi faire des algorithmes efficaces ? Les ordinateurs vont super vite ! …Je peux faire un algorithme en n2avec n=10000 …Je voudrais faire avec n=100000. Tous les 2 ans, la puissance des ,p ordinateurs est multipliée par 2 (optimiste). Quand est-ce que je pourrais faire avec n=100000 ?
…Réponse: †p=100000 q=10000; p=10*q; donc p2 =100*q2. Donc besoin de 100 fois plus de puissance plus de puissance †26 =64, 27 =128 donc obtenue dans 7*2 ans=14 ans !!! …Je trouve un algoen n log(n) pour p, je ferai 17*100000= 1 700 000 00/fopérations donc 1 00/1.7 fois moins de temps !!!

Complexité des algorithmes

 … But: †avoir une idée de la difficulté des problèmes †donner une idée du temps de calcul ou de l’espace nécessaire pour †donner une idée du temps de calcul ou de lespace nécessaire pour résoudre un problème …Cela va permettre de comparer les algorithmes Eié fi d b d dé d l ill … Exprimée en fonction du nombre de données et de leur taille. …A défaut de pouvoir faire mieux : †On considère que les opérations sont toutes équivalentes †On considère que les opérations sont toutes équivalentes †Seul l’ordre de grandeur nous intéresse. †On considère uniquement le pire des cas …Pour n données on aura : O(n) linéaire, O(n2) quadratique O(n log(n)),…

…Dans la vie réelle, ça n’augmente pas toujours !
…OUI et NON: †Certains problèmes sont résolus †Certains problèmes sont résolus †Pour d’autres, on simplifie moins et donc la taille des données à traiter augmente ! Réalité virtuelle de mieux en données à traiter augmente ! Réalité virtuelle : de mieux en mieux définie Dè l’ ét l h lifi