Codage et Représentation de l’information, année 2019

Rappel

Les TD sont à rendre via Moodle avant vendredi soir, minuit. Tout TD non rendu entraîne un 0 immédiatement.

Ces TDs sont à réaliser sous linux. Il faut donc allumer (ou redémarrer) votre machine de TP et la faire redémarrer sous Linux. Les TDs sont à retourner via Moodle sous forme d’une archive tar.gz.

Vous devez faire le maximum du TP dans le terminal, la liste des commandes tapées seront accessibles pour les correcteurs (si tout se passe bien).

Les questions avec des (*) sont facultatives et bien plus difficiles. Le nombre d’étoiles indique la difficulté de la question.

À tout moment vous pouvez consulter le manuel d’une commande en tapant man nom_de_commande.

Préparation du dossier TD8

Créez un dossier TD8 dans votre dossier CRI, ainsi qu’un fichier réponses

Rappel d’utilisation de Python

Dans la suite, tous les scripts sont à écrire avec un éditeur comme atom et à enregistrer dans un fichier avec une extension .py dans le répertoire TD8. Pour lancer votre script enregistré dans un fichier pgm.py exécutez la commande

python3 pgm.py

Remarque Vous n’êtes pas obligés d’utiliser la commande touch pour créer un nouveau fichier pour un script. Si vous le désirez, vous pouvez utiliser atom pour créer de nouveaux fichiers.

Le module random

Dans un ordinateur, il n’y a pas vraiment d’aléa… Les tirages dits aléatoires sont en fait pseudo-aléatoires, et sont obtenus comme des valeurs de suites mathématiques très particulières. Les valeurs sont donc déterminées par une valeur initiale appelée la graine (seed). Pour des raisons de reproductibilité, on a la possibilité de fixer la graine dans les langages de programmation comme Python.

Répondez aux questions suivantes dans un fichier exo1.py. Les fonctions doivent être documentées et doivent contenir au moins deux tests et valider le doctest.

  1. Dans le module random, trouvez comment fixer la graine du générateur à la valeur de la seed. Fixez cette valeur dans exo1.py a 42.
  2. Tirer un nombre entier aléatoire entre 5 et 25 inclus et affichez sa valeur.
  3. Tirez cinquante entiers aléatoires entre -5 et 27 et affichez leur valeur. Note: la fonction print prend en argument optionnel, un paramètre end, qui est une chaîne de caractères qui s’ajoute à la valeur affichée par print. Par défaut c’est un retour à la ligne (\n). Faites en sorte que les 50 valeurs soient séparées par une virgule.
  4. Écrire une fonction moyenne qui prend en argument : deux bornes mini et maxi, un nombre nbr et retourne la moyenne de nbr tirages d’entiers entre mini et maxi. Essayez votre fonction avec 2, 29, 5 puis 2, 29, 50.
  5. Écrire une fonction sup qui prend en argument : deux bornes mini et maxi, un nombre nbr, une valeur seuil et retourne le nombre de valeurs supérieures à seuil parmi nbr tirages d’entiers entre mini et maxi. Essayez votre fonction avec 2, 29, 25, 5 puis 2, 29, 25, 50.
  6. Modifiez votre programme en déplaçant toutes vos définitions de fonction dans un nouveau module appelé alea. Ajoutez/modifiez ce qu’il faut dans votre programme pour utiliser les fonctions définies dans alea.

Un peu de tri

Petit préambule: une fonction peut retourner plusieurs valeurs. Pour cela utilisez return en séparant les valeurs à retourner par des virgules.

Remarque: c’est le genre d’exercice qui demande de sortir un papier et un crayon.

Considérez que vous avez 3 valeurs tirées aléatoirement dans 3 variables a, b, c.

  1. Dans un module tri, écrivez une fonction tri3 qui prend 3 valeurs et les retourne dans l’ordre croissant.
  2. Combien de tests de comparaison votre programme fait-il dans le pire des cas ? La bonne réponse sera celle qui fera le moins de tests de comparaison. (Voyez ici)
  3. Faites un programme testtri.py qui tire 3 entiers entre 1 et 10 aléatoirement et utilise tri3 pour les afficher dans l’ordre croissant. (Rappel : on ne veut pas de print dans la fonction tri3).
  4. Modifiez votre programme pour que ce que la question précédente soit répétée 10 fois.
  5. Recommencez ces 4 questions maintenant avec 4 valeurs et une fonction tri4. (la fonction doit être placée dans le module tri)
  6. Le programme le plus rapide est-il celui qui s’écrit avec le moins de lignes de code ?
  7. Remarquez que savoir combien de comparaisons sont nécessaires pour trier des valeurs est encore d’actualité, même pour un faible nombre de valeurs…

Programmer par des tests

Il est possible d’utiliser la chaîne de documentation des fonctions pour écrire des expressions qui testent si le code de la fonction réalise le calcul attendu.

def somme(a, b):
    """ Calcule la somme entre deux entiers

    >>> somme(5, 4)
    9
    >>> somme(0, 0)
    0
    >>> somme(-20, 4)
    -16


    """
    return a + b
  1. Reproduisez le code de la fonction ci-dessous dans un fichier mafunc.py et lancez python3 -m doctest mafunc.py.
  2. Modifiez le calcul pour provoquer une erreur (exemple faites le calcul de la différence) et relancez python3 -m doctest mafunc.py. Concluez dans le fichier réponse sur l’intérêt des doctest.
  3. Modifiez le module alea pour ajouter au moins cinq tests dans chaque fonctions**

Approximation des racines carrées par dichotomie

Nous allons écrire une fonction qui approxime la racine carrée d’un nombre. L’idée est de simplement utiliser la croissance de la fonction \(x\mapsto \sqrt x\). Pour ce faire, on va isoler l’intervalle où se trouve la racine en réalisant une dichotomie:

Si on suppose que la racine d’un nombre \(x\) est comprise entre \(A\) et \(B\) alors il est possible d’améliorer cet intervalle en prenant le point médian \(C= \frac{A+B}{2}\) et en comparant sa position par rapport à \(\sqrt x\). Si \(C^2>x\) alors on sait que \(\sqrt x\) appartient à l’intervalle entre \(A\) et \(C\), si \(C^2<x\) alors on sait qu’il appartient à l’intervalle entre \(C\) et \(B\).

  1. Écrire dans un fichier racine.py une fonction racine qui prend en argument un nombre x dont on calcule la racine et un nombre entier etape et qui retourne deux entiers représentant l’intervalle. L’intervalle de départ est \([1,x]\).

  2. Comparer le résultat de cette fonction en estimant la valeur de \(\sqrt 2\) après 5, 10, 50, 100 et 1000 étapes. Comparer également avec le résultat de la fonction sqrt du module math.

  3. Estimer la taille de l’intervalle après \(n\) étapes de calculs.

(*) Monte-Carlo

La méthode de Monte-Carlo permet d’approcher une valeur numérique donnée via des tirages aléatoires successifs. Nous allons calculer des approximations du nombre \(\pi\) par cette méthode.

Le module math contient une approximation de \(\pi\) qui va nous servir de référence. Toutes les réponses sont a écrire dans monte_carlo.py.

  1. Afficher la valeur de l’approximation du nombre \(\pi\) contenu dans le module math.
  2. Créer une fonction sample_cercle sans arguments, qui tire aléatoirement uniformémement deux nombres entre -1 et 1 et retourne 1 si le point représenté par ces deux nombres appartient au disque centré en 0 et de rayon 1 et retourne 0 sinon.
  3. La probabilité que la fonction sample_cercle retourne \(1\) est égale à \(\frac{\pi}{4}\) car il s’agit de la surface du disque unité divisée par la surface du carré de longueur 2. Écrire une fonction qui prend en argument un nombre d’itérations nb_iter et calcule l’estimation de \(\pi\) par cette méthode après nb_terations. Évaluer cette fonction en réalisant 100, 1000, 10000 et 1000000 itérations. Comparer avec la valeur de \(\pi\).
  4. Il est possible d’avoir une approximation déterministe du nombre \(\pi\) en utilisant par exemple la formule de Leibnitz. Proposez une méthode pour comparer l’efficacité de la formule de Leibnitz avec celle de la méthode de Monte-Carlo.



Compiled the: mer. 04 sept. 2024 12:49:38 CEST