Home
About

Projet exponentiation

Cours/Algorithmie/Problème de l'exponentiation/Projet exponentiation
Prérequis :

On vérifie expérimentalement que nos calculs théoriques sont validés expérimentalement. On codera et testera nos algorithmes, donc vérifiez que vous avez les prérequis.

Mise en place

Structures

  1. créez un dossier nommé exponentiation où vous placerez vos fichiers
  2. créez un projet vscode dans ce dossier
  3. créez dans ce dossier les 3 fichiers de la trinité du code :
    • main.py
    • exponentiation.py
    • test_exponentiation.py

Vérifications

  • on vérifie que python est OK avec le terminal et avec vscode
  • on vérifie que le linter est actif dans vscode
  • on vérifie que les tests fonctionnent (en créant un test bidon dans tests_exponentiation.py et en vérifiant que pytest et vscode le trouvent)

On se force, jusqu'à que cela devienne un automatisme, à écrire du code stylé. C'est à dire sans que le linter ne se fâche.

Le code

Algorithme naif

  • dans le fichier exponentiation.py : implémentez l'algorithme naïf itératif dans une fonction nommée puissance_naif
  • dans le fichier test_exponentiation.py : implémentez les tests de l'algorithme naïf itératif :
    • vérifiez que les cas simples avec nombre et/ou exposant à 1 fonctionnent
    • vérifiez qu'un cas général est correct (comme $2^3$ par exemple)

Vérifier que vos tests se lancent bien dans le terminal.

Pour les tests, on utilisera les règles suivantes :

Organisation des tests :

  • un fichier de test par fichier de code. Chaque fichier de test sea nommé : test_[nom du fichier de code].py où [nom du fichier de code] sera le nom du fichier (ne mettez pas les [])
  • chaque test sera nommé en 3 parties : test_[nom de la fonction_testée]_[ce que l'on teste] où [nom de la fonction_testée] est le nom de la fonction testée (ne mettez pas les []) et [ce que l'on teste] une description succincte (en 1 ou 2 mots max) de ce que l'on teste.
  • un test doit tester une unique chose. On peut se permettre d'avoir plusieurs assert par fonction de test du moment que ce qu'on test peut être qualifié par un nom précis (la partie [ce que l'on teste] du nom de la fonction de test)

Algorithme rapide

  • dans le fichier exponentiation.py : implémentez l'algorithme rapide dans une fonction nommée puissance_rapide
  • dans le fichier test_exponentiation.py : implémentez les tests de l'algorithme rapide en faisant les mêmes tests que pour l'algorithme naïf. :

Vérifier que vos tests se lancent bien dans le terminal.

Ne supprimez pas les tests de l'algorithme naïf en créant ceux pour l'algorithme rapide ! Vos deux fonctions DOIVENT être testées.

Si l'on modifie notre algorithme naif plus tard il faudra toujours qu'il soit testé.

Complexité temporelle

La seule façon de mesurer expérimentalement la complexité d'un algorithme est de mesurer la complexité en temps de celui-ci pour une entrée réalisant la complexité maximale.

Ce n'est cependant pas si simple de mesurer ce temps précisément parce que :

Mais pour ce qui nous importe, on va dire que c'est pas grave parce que ces temps parasites :

Le protocole de calcul sera alors le suivant :

À retenir

Pour mesurer le temps d'exécution d'un algorithme :

  1. on note le nombre de secondes $t_1$ utilisées par le programme python juste avant d'exécuter l'algorithme
  2. on exécute l'algorithme
  3. on note le temps $t_2$ utilisé par le programme juste après exécution l'algorithme

La complexité temporelle sera alors : $\Delta = t_2 - t_1$.

Comment faire

On va utiliser les fonctions simple du module time. Faisons une petite fonction de test pour voir comment on peut utiliser la mesure du temps dans notre programme.

Créez un fichier temps_mesure.py et mettez y le code suivant :

import time

print("Avant l'attente")
x = 1000
t1 = time.perf_counter()
x ** x ** 2
t2 = time.perf_counter()
print("Après l'attente")

delta = t2 - t1

print("Temps d'attente :", delta)

On utilise à dessein un calcul long $x^{x^2}$ pour que vous voyiez le temps passé à le calculer.

Le code précédent utilise une fonction du module time : perf_counter qui mesure le temps utilisé par le programme python en secondes, indépendamment des autres programmes tournant sur votre ordinateur (Youtube, Instagram, etc). On utilise une fonction longue à calculer (ici $1000^{1000^2}$, vous pouvez essayer $2000^{2000^2}$ ou $500^{500^2}$ pour voir les différences de temps)

  1. Exécutez plusieurs fois le code précédent pour voir que l'on passe bien environ 1 seconde à calculer $1000^{1000^2}$.
  2. Faites pour dix essais :
    • le temps maximum de calcul
    • le minimum maximum de calcul
    • le temps moyen de calcul

Voua devriez voir que le temps d'exécution de chaque fonction est similaire mais non identique.

Lorsque l'on calcule des complexités temporelles, on réalise plusieurs mesures pour en rendre la moyenne et ainsi atténuer les fluctuations.

Expérimentations

Un temps d'exécution

Créer un programme principal (dans le fichier main.py) qui demande à l'utilisateur un exposant $n$. Ce programme donne ensuite le temps mis pour exécuter $3^n$ avec l'algorithme naïf et avec l'algorithme rapide.

Temps max

Créer dans un fichier nommé main_temps.py un programme permettant de trouver $K$ et $N$ tels que $N = 2^K$ soit la première puissance de 2 pour laquelle le temps mis pour exécuter l’exponentiation naïve de $3^N$ dure plus de 1 seconde.

On trouve que $K$ vaut de l'ordre de 20.

solution

 
temps = 1

delta = 0 # valeur par défaut pour rentrer dans la boucle while
K = 0
N = 1

while delta < temps:
    t1 = time.perf_counter()
    puissance_naif(3, N)
    t2 = time.perf_counter()

    delta = t2 - t1
    K += 1
    N *= 2

Liste de temps

On va mesurer le temps pris pour chaque algorithme à des pas de temps discrets correspondants aux calculs de $3^{n}$ pour $n$ allant de $n=1$ à $n=N$ (avec le $N$ calculé dans la partie précédente). Ceci nous permettra d'avoir quelques points de contrôles espacés dans le temps et nécessitant chacun peu de temps de calcul (moins d'une seconde pour chaque mesure).

Commençons par créer les points de contrôles sous la forme d'un tableau d'exposants à calculer :

Créez (et testez) une fonction donne_pas(nombre_pas: int, min_valeur: int, max_valeur: int) -> [int] qui rend une liste d'entiers allant de min_valeur à au plus max_valeur par pas de (max_valeur - min_valeur) // nombre_pas

donne_pas(4, 2, 23) rendra la liste [2, 7, 12, 17, 22]. Elle est très facile à créer avec la fonction range

Puis mesurons le temps pris pour calculer $3^n$, pour 20 points de contrôles entre $1$ et $N$ :

Ajoutez au programme du fichier temps_exponentiation.py trois nouvelles listes :

  • la liste exposant qui est le retour de la fonction donne_pas(20, 1, N) (avec le $N$ calculé la partie précédente)
  • la liste mesures_temps_naif telle que mesures_temps_naif[i] corresponde au temps mis pour exécuter la fonction calculer puissance_naif(3, exposant[i])
  • la liste mesures_temps_rapidecorresponde au temps mis pour exécuter la fonction calculer puissance_rapide(3, exposant[i])

La complexité de l'algorithme naif doit être linéaire et celui de l'algorithme rapide logarithmique, donc :

Vérifiez que le rapport mesures_temps_naif[i] / mesures_temps_rapide[i] augmente lorsque $i$ augmente (il doit tendre vers l'infini).

Vérifiez que le rapport :

  • mesures_temps_naif[i] / exposant[i] reste à peut prêt constant
  • mesures_temps_rapide[i] / log(exposant[i]) reste à peut prêt constant (log est une fonction du module math de python)

Graphiques

Nous allons dans cette partie représenter graphiquement nos mesures. Nous utiliserons pour cela la bibliothèque Matplotlib.

Bibliothèque Matplotlib

Commencez par l'installer :

Dans un terminal, tapez la commande suivante pour installer Matplotlib :

python -m pip install matplotlib

Utiliser cette bibliothèque ne s'improvise pas. Commencez par lire le tutoriel suivant pour en comprendre les bases :

Suivez le tutoriel Matplotlib. Il est fait pour être utilisé avec un notebook, mais vous devriez pouvoir facilement convertir les exemples pour pouvoir les utiliser dans un fichier python normal.

Temps naïf

Ajoutez le code suivant au code du fichier temps_exponentiation.py pour afficher le temps mis pour afficher le temps mis pour calculer puissance_naif(3, exposant[i]) en fonction de exposant[i].

Est-ce conforme à ce qui était attendu ?

import matplotlib.pyplot as plt

fig, ax = plt.subplots(figsize=(20, 5))

ax.set_title("complexités temporelles")
ax.set_xlabel("valeur de l'exposant")
ax.set_ylabel("temps de calcul")

ax.plot(exposant, mesures_temps_naif, 'o-')

plt.show()

Temps exponentiel

Adaptez le code précédent pour afficher les mesures de temps pour l'exponentiation rapide.

Est-ce conforme à ce qui était attendu ?

Combinaison des deux

Superposez en un seul graphique les deux courbes (on pourra faire deux plot l'un à la suite des autres).

Le temps mis par l'exponentiation rapide est très inférieur à celui effectué par l'algorithme d'exponentiation naif, on ne le voit pratiquement p[as.

Deux axes des ordonnées

Utilisez le code de ce lien pour utiliser ax.twinx qui permet de partager l'axe des abscisse en ayant deux axes des ordonnées et permettre de voir les 2 courbes,chacune ayant son axe des ordonnées.

Vous pourrez également changer la couleur d'un des dessins en remplaçant le paramètre 'o-' d'un des 2 plot par 'ro-' pour dessiner en rouge (red).