====== 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 :
  * https://informatique.centrale-marseille.fr/tutos/post/python-bases.html
  * https://informatique.centrale-marseille.fr/tutos/post/utilisation-pycharm-bases.html
  * https://informatique.centrale-marseille.fr/tutos/post/python-tests.html


===== Calcul de Puissance =====

On cherche à calculer $x^y$

==== Itératif et récursif naïf ====

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.

==== Exponentiation rapide ====

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

==== Calcul de complexité ====

Pour mesurer ce temps on pourra utiliser la méthode [[https://docs.python.org/3/library/time.html#time.process_time|process_time]] du module time de python (si votre python3 est vieux, utilisez la méthode clock de time).

<code python>
import time

temps_depart = time.process_time()
#ce que l'on veut mesurer
delta_temps = time.process_time() - temps_depart
</code>


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.



<note>
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.
</note>

===== Affichage de courbes =====

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$.

<code python>
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()
</code>


Supperposez les courbes pour les 3 algorithmes. Conclusions ?

===== Corrélation aux complexités théoriques =====

Le rapport entre le temps mis pour effectuer un algorithme et sa complexité théorique doit être une droite.
Utilisez [[http://www.numpy.org|numpy]] et [[http://docs.scipy.org/doc/numpy/reference/generated/numpy.polyfit.html|polyfit]] pour calculer la droite de régression linéaire de ce rapport pour l'algorithme naïf et l'algorithme rapide.

<code python>
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

</code>

En déduire le coefficient de corrélation linéaire (on pourra utiliser la méthode [[http://docs.scipy.org/doc/numpy/reference/generated/numpy.corrcoef.html|corrcoef]] de numpy). Conclusion ?


__Up__ : [[accueil:]]