Algorithmique #

« L’informatique n’est pas plus la science des ordinateurs que l’astronomie n’est celle des téléscopes »

Michael R. Fellows et Ian Parberry

« Que nul n’entre ici s’il n’est géomètre »

Platon (427 av. J.-C., 348 av. J.-C.)

« Quand c’est qu’on joue à Fortnite ? »

Jean-Killian, 2019

l’Algorithmique, une science très ancienne. #

• Antiquité. Euclide (calcul du pgcd), Archimède (approximation de $\pi$)

• le mot Algorithme vient du mathématicien arabe du 9ème siècle Al Khou Warismi

• L’algorithmique est, avec l’electronique, la base scientifique de l’informique. Elle intervient dans

  • le logiciel (software)
  • le matériel (hardware). Un processeur est un câblage d’algorithmes simples (addition, multiplication, portes logiques etc.)

Algorithme : une définition. #

• Un algorithme prend en entrée des données et fournit, en un nombre fini d’étapes, la réponse à un problème.

• Un algorithme est une série d’opérations à effectuer :

  • Opérations en séquence (algorithme séquentiel)
  • Opérations en parallèle (algorithme parallèle)
  • Opérations exécutées sur un réseau de processeur (algorithme réparti / distribué)

• Mise en oeuvre de l’algorithme

  1. implémentation (plus général que le codage)
  2. écriture de ces opérations dans un langage de programmation (= codage)

  On obtient un programme

Algorithme vs Programme #

• Un programme implémente un algorithme.
• Dans une machine un programme est un fichier (code source, exécutable etc.)
• Un algorithme est la description de ce que fait le programme.

calculabilité #

• (Turing-Church) : les problèmes ayant une solution algorithmique sont ceux résolubles 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é algorithmique)

  • problème de l’arrêt (Turing 1936) - cet algorithme va-t-il s’arrêter ?
  • cet algorithme est-il juste ? (Rice 1951)

Complexité #

Qualité d’un algorithme #

• Deux algorithmes résolvants le même problème ne sont pas équivalents. 2 critères :

  • Temps de calcul : lents vs rapides
  • Mémoire utilisée : peu vs beaucoup

• On parle de complexité en temps (vitesse) ou en espace (mémoire)

Pourquoi faire des algorithmes rapides ? #

• Pourquoi faire des algos efficaces ? Les ordinateurs vont très vite !

• C’est faux, on n’aura jamais assez de puissance de calcul (météo, mécanique des fluides, IA, trafic routier, séquençage du génôme etc.)

Quelques précisions #

Seconde Loi de Moore (Gordon Moore - 1975) : #

• le nombre de transistors des microprocesseurs sur une puce double tous les deux ans.

Elle est restée vraie de ~1960 à ~2000.

Depuis la dissipation thermique limite la taille des puces, on a plutôt tendance à multiplier le nombre de coeurs de processeurs.

La puissance de calcul est la capacité à effectuer un certain nombre de calcul en un temps donné.

Nous discuterons plus en détail des conséquences économiques et environnementales.

Exemple #

• Hypothèse optimiste (Loi de Moore) : la puissance de calcul double tous les deux ans.

• Mon programme en $n^2$ se termine en un temps satisfaisant avec $n=10.000$

  Quand pourrais-je le faire avec $n=1.000.000$ ?

Exemple - quelques précisions #

• Mon programme en $n^2$ :

  cela signifie qu’il réalise $n^2$ opérations pour une donnée de taille $n$.

• se termine en un temps satisfaisant avec $n=10.000$ :

  il a donc réalisé $n^2 = (10.000)^2 = 10^8 = 100.000.000$ opérations en un temps satisfaisant.

Exemple - correction #

• Hypothèse optimiste (Loi de Moore) : la puissance de calcul double tous les deux ans.

• Mon programme en $n^2$ se termine en un temps satisfaisant avec $n=10.000$

  Quand pourrais-je le faire avec $n=100.000$ ?

  • $p = 100.000 \quad q = 10.000 ;;; p = 10 \times q$ donc $p^2 = 100 \times q^2$.

    On a besoin de $100$ fois plus de puissance.

  • $2^6 = 64 \quad 2^7=128$. Elle sera obtenue dans $7\times 2 = 14$ ans !!!

Exemple - correction - suite #

Mon autre algorithme est en $n :\log n$

• $\log n$ (logarithme de $n$) est une fonction croissante vers l’$\infty$, comme $n$ mais “très lente”

Entre $q= 10.000$ et $p = 100.000$

On passe de $100.000$ opérations à $1.000.000$ d’opérations.

Il ne faudra que $4$ ans ($2^3 = 8 \quad 2^4=16$).

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 résoudre un problème

• Cela va permettre de comparer des algorithmes.

• La complexité est exprimée en fonction du nombre de données et de leur taille.

• C’est très difficile…

  • On considère que toutes les opérations sont équivalentes
  • Seul l’ordre de grandeur nous intéresse.
  • On considère uniquement le pire des cas (souvent ~ cas moyen)

Pourquoi faire des algos rapides ? #

• Dans la vie réelle, ça n’augmente pas toujours !

• OUI et NON :

  • 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 mieux définie.

• Dès que l’on résout un problème on le complexifie !

Algorithme : vitesse #

Rapide

: un algorithme qui met un temps polynomial en $n$ (nombre de données) pour être exécuté : $n^2 ,; n^8$

Lent

: un algorithme qui met un temps exponentiel : $2^n$

Pour certains problèmes (voyageur de commerce, remplissage de sac à dos de façon optimale) on ne sait même pas s’il existe un algorithme rapide.

On connaît des algorithme exponentiels en temps $2^n$.

• $100^2 = 10.000 \qquad 100^3 = 1.000.000$
• $2^{100} = 1267650600228229401496703205376$

Algorithme : vitesse #

1 million de $ si vous résolvez la question ! #

$4^{eme}$ problème du millénaire : $P = NP~?$

Exemples en Python : #

Tri à bulle vs tri implémenté dans Python3 #

Tri à bulle #

On veut trier ( = ranger par ordre croissant) [3, 2, 1]

  On prend 3. On parcourt à partir de 3.
  À chaque étape, on échange si 3 est plus grand que l'élément :
    1.  3 > 2 on échange. [2, 3, 1]
    2.  3 > 1 on échange. [2, 1, 3]
  On recommence avec le 2ème élément :
    1. 1 < 3 on ne fait rien.
On recommence depuis le départ
jusqu'à ce qu'on n'ait plus aucun échange.

## Tri à bulle (suite)

[2, 1, 3]
    1. 2 > 1 on échange. [1, 2, 3]
    2. 2 < 3 on ne fait rien.
    On recommence avec le 2ème élément :
    1. 2 < 3 on ne fait rien.
On recommence depuis le départ
  1. 1 < 2 on ne fait rien.
  2. 2 < 3 on ne fait rien.
C'est terminé.

4 comparaisons #

4 comparaisons effectuées après avoir terminé le tri.

Pour une liste de 3 éléments.

Dans Python #

  def bubble_sort(l):
      while True:
          echange = False
          for i in range(len(l) - 1):
              if l[i] > l[i+1]:
                  l[i], l[i+1] = l[i+1], l[i]
                  echange = True
          if not echange:
              return l

Python Tutor

Comparaison de vitesse #

from time import time
from random import sample

n = 1000  # on mélange 2 listes de 1 à 1000
l1, l2 = sample(range(n),n), sample(range(n),n)

start = time() # on note l'heure de départ
bubble_sort(l1)
print(time() - start) # 0.3104 secondes

start = time()
sorted(l2) # tri interne
print(time() - start)
# 0.0003 sec : 1000 fois plus rapide.

Conclusion #

• Le tri à bulle est bien gentil. On en verra de meilleurs.

• Il est important d’utiliser de bons algorithmes pour réaliser des tâches coûteuses.

Preuve #

Algorithme : preuve #

• On peut prouver les algorithmes !

• Un algorithme est dit totalement correct si, pour tout jeu de données, il termine et rend le résultat attendu.

• C’est difficile (très) mais c’est important.

  • Encodage, décodage des données (compression, cryptographie etc.)

  • Centrale nucléaire

  • Airbus

• Attention : un algorithme juste peut être mal implémenté.

Algorithme : résumé #

• C’est ancien
• C’est fondamental en informatique
• Ça se prouve
• On estime le temps de réponse et la mémoire occupée
• Algorithme $\neq$ Programme