Différences
Ci-dessous, les différences entre deux révisions de la page.
restricted:tc-a:tp1:travaux_pratiques_premiere_seance_2017 [2017/09/28 16:18] – créée pprea | restricted:tc-a:tp1:travaux_pratiques_premiere_seance_2017 [2017/10/26 14:12] (Version actuelle) – pprea | ||
---|---|---|---|
Ligne 1: | Ligne 1: | ||
+ | ====== TP 1 ====== | ||
+ | |||
+ | Normalement, | ||
+ | * https:// | ||
+ | * https:// | ||
+ | * https:// | ||
+ | |||
+ | |||
+ | ===== 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' | ||
+ | |||
+ | ==== Calcul de complexité ==== | ||
+ | |||
+ | Pour mesurer ce temps on pourra utiliser la méthode [[https:// | ||
+ | |||
+ | <code python> | ||
+ | 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' | ||
+ | * le temps mis par l' | ||
+ | * le rapport entre le temps mis pour résoudre une exponentiation avec l’algorithme rapide et celui mis avec l' | ||
+ | |||
+ | |||
+ | |||
+ | < | ||
+ | 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' | ||
+ | </ | ||
+ | |||
+ | ===== Affichage de courbes ===== | ||
+ | |||
+ | Utilisez le code ci-dessous pour afficher une courbe avec matplotlib où l' | ||
+ | |||
+ | <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(" | ||
+ | matplotlib.pyplot.xlabel(" | ||
+ | |||
+ | matplotlib.pyplot.plot(coordonnees_abcisses, | ||
+ | matplotlib.pyplot.plot(coordonnees_abcisses, | ||
+ | matplotlib.pyplot.plot(coordonnees_abcisses, | ||
+ | |||
+ | matplotlib.pyplot.show() | ||
+ | </ | ||
+ | |||
+ | |||
+ | 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:// | ||
+ | |||
+ | <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, | ||
+ | print(a, b) # a = 5, b = 10 | ||
+ | |||
+ | </ | ||
+ | |||
+ | En déduire le coefficient de corrélation linéaire (on pourra utiliser la méthode [[http:// | ||
+ | |||
+ | |||
+ | __Up__ : [[accueil: |