Python L1, TD/TP 11.02


Exercices

Exercice 1.

Approximation numérique de la fonction sinus.
On a travaillé sur l'approximation de Newton de la racine carrée, revisez cet exercice si vous l'avez oublié. Cette fois, une autre méthode, qui utilise la récursivité.
Plusieurs fonctions élémentaires ou non, satisfont des simples relations récurrentielles, ce qui fournit des intéressants algorithmes d'approximation. Par exemple, la fonction sinus satisfait la formule :

\(\sin(3 x) = 3 \sin(x) - 4 \sin(x)^3\,.\)

(Ou, si vous voulez : \(\sin(x) = 3 \sin(x/3) - 4 \sin(x/3)^3\)). On sait que pour des arguments très petits, \(\sin(x) \approx x\) (si l'argument est en radians). Grâce à la formule ci-dessus, on peut réduire le calcul de \(\sin(x)\) au \(\sin(\frac{x}{3})\), ensuite \(\sin(\frac{x}{9})\), etc., et ainsi, en réduisant l'argument, on peut arriver à une valeur si petite – par ex. 0.0000001 –, que le remplacement du sinus par son argument soit suffisamment précis.

Codez la fonction monsin(x) qui réalise ce calcul. Le codage le plus simple et clair est récursif :

def monsin(x):
   ...
   if abs(x) < 0.0000001   # disons...
   ...
   # sinon ...
       utiliser ... monsin(x/3)
   ...

L'algorithme est rapide et précis. (Il a été utilisé dans la pratique, dans les calculatrices, mais en optimisant la récursivité, ce qui est un peu compliqué, et sera peut-être discuté plus tard). Voici le résultat de l'approximation, la différence entre la fonction que vous allez coder, et le sinus standard. Le seuil est de 0.000001 ; la précision est beaucoup meilleure que le seuil, est de l'ordre de \(10^{-13}\); (L'axe horizontal est celui des \(x\), entre 0 et \(2\pi\)).


Commentaire. Bien sûr, il faut d'abord réduire l'argument de la fonction modulo 2 π ! (Donc, l'argument initial ne sera jamais trop grand. Cependant, pendant la construction de l'algorithme et les premiers tests, ne prenez pas en compte ce détail, afin de ne pas vous disperser. On y reviendra peut-être plus tard)

Si vous voulez voir comment se comportent les approximations successives, récursives ou itératives, voici un graphique. Si \(x\) est très petit, la solution est \(y=x\). L'approximation suivante : \(y=x - 4 (x/3)^3\) garde cette propriété, mais est meilleure pour \(x\) un peu plus grands. La suivante, \(y = x - 120 (x/9)^3 + 432 (x/9)^5 - \ldots\), est encore meilleure, et ainsi de suite.

Le graphique montre les approximations : seconde (jaune), troisième (bleue), quatrième (noire) et sinus (rouge). On voit que même pour \(2\pi\) le résultat n'est pas mauvais pour la courbe bleue.

Il est presqu'impossible de discerner entre les courbes rouge et noire, donc quelques itérations (sans doute moins de 10) suffisent pour une excellente précision.


Exercice 2.

Votre premier tri.
En général, les algorithmes de tri, c'est un sujet "bien-aimé" dans l'enseignement d'informatique. Plusieurs algorithmes, et plusieurs styles d'implémentation, qui dépendent des langages utilisés. Analyse de la complexité algorithmique (temps du calcul en fonction de la taille des données), etc. D'autres exercices nous attendent...

Implémenter en Python l'algorithme de tri par insertion. Étant donnée une liste numérique, disons l=[5, 0, 7, 6, 9, 3, 1, 8, 2, 4], construire une liste avec les mêmes éléments dans l'ordre croissant, ici r=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (appelons-la : le tampon). Voici la description de l'algorithme.

Il faut structurer les boucles de manière disciplinée, afin d'éviter le débordement. Voici quelques pas du procédé pour nos données exemplaires.

 x      r          res. d'insertion
--------------------------------------
 5      []           [5]
 0      [5]          [0] + [5] = [0,5]
 7      [0,5]        [0,5] + [7] = [0,5,7]
 6      [0,5,7]      [0,5] + [6] + [7] = [0,5,6,7]
 9      [0,5,6,7]    [0,5,6,7] + [9] = [0,5,6,7,9]
 ...

etc. À chaque pas le tampon reste bien ordonné.

C'est une méthode de tri bien connue, et facile à implémenter. Elle est utilisée pour des tableaux courts, car sa complexité pour des tableaux volumineux (taille : milliers) est trop importante, d'autres méthodes, plus efficaces, sont de rigueur. Son avantage est son incrémentalité, pas besoin d'avoir d'emblée la liste source complète, on lit les éléments, et on les insère tout de suite. Si la lecture est lente, on gaspille moins de temps.

Bien sûr, vu l'importance du classement des objets dans des collections (tableaux, listes ...) tous les langages de programmation disposent des librairies avec les procédures de tri, et Python dispose également de procédures prédéfinies, efficaces. En Python il suffit de lancer r=sorted(l) pour obtenir une nouvelle liste, triée. Par contre, l.sort() ne retourne rien, mais modifie sur place la liste l, elle sera triée. On peut paramétrer cette opération, avoir le tri décroissant, etc., mais ce sera pour plus tard.


Exercice 3.

Le module turtle, et un peu de graphisme.


Comme vous avez vu (probablement ; c'était prévu pour cette semaine) en cours, Python est distribué avec un module graphique turtle, qui complémente Tkinter par des constructions de plus haut niveau, et permet de faire des dessins, des exercices en graphisme algorithmique. Ce module est la réalisation en Python de la technique de programmation graphique conçue dans le cadre du langage Logo, qui n'est plus utilisé. On dispose d'un petit objet, la "tortue", qui a une position dans l'espace (dans la fenêtre), et une direction (et quelques propriétés stylistiques qui ne nous intéressent pas).

Attention, le module Turtle par défaut fonctionne dans les "coordonnées pixel", il n'y a aucun ajustement de la géométrie du dessin quand on modifie la fenêtre. De plus, soit vous lancez les commandes, qui sont exécutées, mais la fenêtre de la tortue n'est pas capable d'intéragir avec vous, soit vous demandez l'interaction en exécutant mainloop() de Tkinter. Alors la fenêtre ne recevra plus de commandes de la console. Ce module n'est pas trop facile à manipuler... C'est le prix à payer pour l'avoir basé sur Tkinter.

Cependant ON PEUT déclarer les coordonnées "virtuelles", un système Cartésien personnalisé, comme avec Matplotlib. Il faut déclarer, par exemple

setworldcoordinates(-1, -1, 1, 1) # xmin, ymin, xmax, ymax
et ainsi vous aurez une fenêtre avec les coordonnées centrées au centre. Si les dimensions sont les mêmes, il serait judicieux d'avoir la fenêtre carrée, sinon les angles seront distordues (vous avez pu le voir en manipulant votre horloge Matplotlib). Voici un test :
from turtle import *

setup (width=600, height=600, startx=10, starty=10) # fenêtre
setworldcoordinates(-1, -1, 1, 1)
mode('world')
width(4) #largeur de la plume
ht()     # cacher l'avatar de la tortue
speed(2) # 0 est maximale

color("red")
circle(0.4,None,50)
mainloop()
(si mainloop() devient peu commode, mais vous voulez au moins pouvoir fermer la fenêtre par un click, exécutez : exitonclick()).

La tortue accepte des "commandes", par ex. tourner à gauche, ou bouger vers l'avant ou arrière. Lisez la documentation, afin de connaître les commandes de base : forward(...), right(...), setheading(...), etc. Je ne peux répéter ici ce que vous pouvez trouver par un clic... Les exemples sur le Web son très abondants, et vous trouverez facilement aussi les réponses à plusieurs exercices. Mais faites les exercices vous mêmes, si vous voulez apprendre quelque chose. Posez des questions. Apprenez à déplacer la tortue avec/sans trace, grâce à up() et down() : plume levée, plume "sur papier".


Exercice 4.

La tortue encore

Construire – avec les mouvements relatifs classiques : fd(...), left(...), right(...) la figure à gauche.

L'algorithme doit être paramétrable : l'angle des lignes, le nombre de sub-divisions, la longueur, - tout peut varier.

La figure n'est pas composée de petits carrés, même si c'est parfaitement faisable, et même plus facile que la méthode que je propose : ici la tortue d'abord trace les lignes "horizontales" (presque, bien sûr), une après l'autre, revient, et ensuite trace les verticales (de longueur totale) de la même manière.

[Peut-être nous pourrons répéter cet exercice avec Matplotlib, de manière très différente, en construisant les lignes en dehors de la procédure de traçage, et dessinant tout comme un graphique complexe].

Ici l'essentiel est la possibilité de retourner à un point précédent, et récupérer la direction précédente. Ici les procédures suivantes peuvent vous aider, vous pouvez les améliorer. La première sauvegarde la position et la direction actuelles de la tortue, et retourne une liste avec ces données.

La seconde prend cette liste, et restaure la configuration.

def save():
    xy=pos()
    hd=heading()
    return [xy,hd]

def rstr(l):
    up()  # On revient la la pos. ancienne sans tracer la ligne
    setpos(l[0]); seth(l[1])
    down()


Semaine dernière
Semaine suivante
Retour à l'index