TP 1

TP 1

Normalement, vous devez connaître le langage python, l'environnement pycharm & le développement par les tests. Si ce n'est pas le cas, les tutos suivants sont pour vous :

On cherche à calculer $x^y$

Codez un algorithme itératif et un algorithme récursif naïf permettant de calculer la puissance de deux entiers et leurs tests associés.

Coder l'algorithme d'exponentiation rapide (cf TD 1, Exercice 5) et ses tests.

Pour mesurer ce temps on pourra utiliser la méthode process_time du module time de python (si votre python3 est vieux, utilisez la méthode clock de time).

import time
 
temps_depart = time.process_time()
#ce que l'on veut mesurer
delta_temps = time.process_time() - temps_depart

Vérifiez que :

le temps pris par l'algorithme itératif augmente suivant la valeur de $y$ ,
le temps mis par l'algorithme itératif et rapide ne dépend pas de $x$ ,
le rapport entre le temps mis pour résoudre une exponentiation avec l’algorithme rapide et celui mis avec l'algorithme naïf tend vers 0.

Mesurer précisément le temps mis pour exécuter un algorithme est compliqué. Les oscillations sont normales car le système, l'ide et même python peuvent faire des choses en parallèle. La mesure de temps utilisée n'est donc pas rigoureusement proportionnelle à la complexité de l'algorithme mais en est une bonne approximation.

Utilisez le code ci-dessous pour afficher une courbe avec matplotlib où l'abcisse est $y$ et l'ordonnée le temps mis pour calculer $x^y$ .

import matplotlib.pyplot
from math import log
 
 
coordonnees_abcisses = range(2, 101)
 
x_fois_2 = []
x_carre = []
x_log_x = []
 
for x in coordonnees_abcisses:
    x_fois_2.append(x * 2)
    x_carre.append(x * x)
    x_log_x.append(x * log(x))
 
matplotlib.pyplot.ylabel("axe des ordonnees")
matplotlib.pyplot.xlabel("axe des abcisses")
 
matplotlib.pyplot.plot(coordonnees_abcisses, x_fois_2, color="#ff0000")
matplotlib.pyplot.plot(coordonnees_abcisses, x_carre, color="#00ff00")
matplotlib.pyplot.plot(coordonnees_abcisses, x_log_x, color="#0000ff")
 
matplotlib.pyplot.show()

Supperposez les courbes pour les 3 algorithmes. Conclusions ?

Le rapport entre le temps mis pour effectuer un algorithme et sa complexité théorique doit être une droite. Utilisez numpy et polyfit pour calculer la droite de régression linéaire de ce rapport pour l'algorithme naïf et l'algorithme rapide.

import numpy
 
x = list(range(10))
y = [5 * i + 10 for i in x]  # y = 5x + 10
 
# régression linéaire
a, b = numpy.polyfit(x, y, 1)
print(a, b)  # a = 5, b = 10