Différences
Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente | ||
restricted:alg-1:tp1 [2015/09/29 10:26] – fbrucker | restricted:alg-1:tp1 [2016/11/29 12:45] (Version actuelle) – fbrucker | ||
---|---|---|---|
Ligne 1: | Ligne 1: | ||
+ | ====== TP1 ====== | ||
+ | Elements de complexité et programmation par tests (niveau 1). | ||
+ | |||
+ | ===== Les tests ===== | ||
+ | |||
+ | Nous devons être certains que toutes les méthodes, fonctions ou modules que nous créons soient corrects. On écrira donc des tests pour être moralement sûrs que nos programmes fonctionnent (la plupart du temps une preuve de code est illusoire). | ||
+ | |||
+ | Pour éviter de retaper tous ces tests à chaque modification du code (ce qui arrive souvent lorsque un algorithme ou une application est utilisée longtemps) ou à chaque découverte de bug, ils sont conservés dans un fichier à part. Ceci nous permettra d' | ||
+ | |||
+ | ==== Environnement de tests avec pyCharm ==== | ||
+ | |||
+ | De nombreux [[https:// | ||
+ | |||
+ | ==== Premier exemple ==== | ||
+ | |||
+ | Créez un nouveau projet avec pycharm que l'on pourra appeler '' | ||
+ | <code python> | ||
+ | def double(entier): | ||
+ | return 2 * entier | ||
+ | </ | ||
+ | |||
+ | Pour tester ce code, j' | ||
+ | * double(0) vaut 0, | ||
+ | * double (21) vaut 42 | ||
+ | |||
+ | Ma méthode sera exacte. | ||
+ | |||
+ | On utilise le mot clé [[http:// | ||
+ | <note warning> | ||
+ | Les fonctions de tests doivent toutes commencer par '' | ||
+ | </ | ||
+ | |||
+ | Ajouter la méthode ci-après à votre fichier : | ||
+ | <code python> | ||
+ | def test_double(): | ||
+ | assert double(0) == 0 | ||
+ | assert double(21) == 42 | ||
+ | </ | ||
+ | |||
+ | et executez là : | ||
+ | <code python> | ||
+ | test_double() | ||
+ | </ | ||
+ | |||
+ | Si tout s'est passé comme prévu, il ne s'est rien passé. Normal, l''' | ||
+ | <code python> | ||
+ | Traceback (most recent call last): | ||
+ | File "/ | ||
+ | test_double() | ||
+ | File "/ | ||
+ | assert double(0) == 7 | ||
+ | AssertionError | ||
+ | </ | ||
+ | |||
+ | Ainsi, si tout se passe bien, nos tests sont passés, si le programme s' | ||
+ | |||
+ | ==== Séparer code et tests ==== | ||
+ | |||
+ | Placez la fonction de test (et son exécution) dans un fichier que vous nommerez '' | ||
+ | |||
+ | Faites en sorte qu'il s' | ||
+ | |||
+ | <note warning> | ||
+ | On séparera toujours les tests du code. Tout fichier de test commence par '' | ||
+ | </ | ||
+ | |||
+ | |||
+ | ==== Utilisation de l' | ||
+ | |||
+ | Nous allons demander à l' | ||
+ | |||
+ | Commencez par supprimer l' | ||
+ | <note warning> | ||
+ | Un fichier de test ne doit contenir que des fonctions. | ||
+ | </ | ||
+ | |||
+ | Puis nous allons demander à pycharm d' | ||
+ | * le champ '' | ||
+ | * le champ '' | ||
+ | |||
+ | Une fois ceci configuré, cliquez sur le bouton OK. | ||
+ | |||
+ | Un nouvel environnement de test est créé dans l' | ||
+ | |||
+ | Pour finir cette partie : | ||
+ | * séparez votre fonction de tests en 2 fonctions (chaque fonction de test ne doit contenir qu'une chose à tester, donc a priori qu'un seul '' | ||
+ | * exécutez votre nouvel environnement | ||
+ | * ajoutez une fonction de test qui plante. Exécutez votre environnement de test. Voyez la barre rouge. Supprimez ce test non valide. | ||
+ | |||
+ | ==== Les tests en ligne de commande ==== | ||
+ | |||
+ | La bibliothèque [[http:// | ||
+ | |||
+ | ===== 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 ? |