L2 - I31. Examen de travaux pratiques d'algorithmique.


Mardi 17 novembre 2015 - 16:00 → 18:15 (durée 2H15)  DOCUMENTS INTERDITS

Vous avez 1/4 d'heure pour vous installer et lire en détail le contenu de ce paragraphe avant de commencer les exercices ! Lisez attentivement les énoncés et suivez scrupuleusement les instructions en respectant à la lettre les commandes, les noms des fichiers proposés, majuscules/minuscules comprises. Suggestion : copiez les à la souris afin d'éviter, entre autres, de confondre la quote ' et l'antiquote `... Les réponses aux questions posées doivent être incorporées aux fichiers sources Python sous forme de commentaires en début de programme.

Le barème est approximativement de 5 points par exercice.

NB. Pour les étudiants de la filière SI : si vous n'avez pas réussi à suivre les instructions ci-dessus et que je dois intervenir pour faire ce travail à votre place (20% des étudiants de la promotion 2014-2015), je retirerai 4 points à votre note.
Écrivez une fonction TriInsertion(L) qui effectue le tri in situ (sur place, on ne crée par d'autre liste) de la liste L à l'aide de l'algorithme du tri par insertion étudié en cours.
On rappelle qu'un dictionnaire en python est une structure énumérée (comme les listes, tuples, chaînes) dont les clés sont quelconques (dans les autres cas les clefs sont entières). Comme pour une liste, on accède à la valeur associée à une clef c par H[c]. On crée un dictionnaire vide avec H = {}. L'appartenance d'un objet x à une structure énumérée S s'obtient avec x in S (dans le cas d'un dictionnaire c'est l'appartenance de la clef qui est testée).

Écrivez une fonction Python Histogramme(L) qui renvoie un dictionnaire dont les clefs sont les valeurs de la liste L (par hypothèse la liste ne contient que des valeurs entières) et la valeur associée à une clef c est le nombre d'occurences de cette clef dans la liste L. Par exemple, si L=[3,2,1,2,1,1,2,1], alors le dictionnaire renvoyé est {1:4,2:3,3:1}. Écrivez une fonction Moyenne(H) qui calcule la moyenne des clefs pondérée par les valeurs du dictionnaire H en entrée.

Écrivez une fonction Python Fusion(A,B) qui renvoie la fusion de deux listes A, B d'entiers supposées triées. Par exemple si A=[1,2,5,6,9] et B=[2,4,5,5,7,8], la liste renvoyée est la liste [1,2,2,4,5,5,5,6,7,8,9]. Attention ! votre programme doit avoir une complexité linéaire. Vous ne devez pas trier la liste A+B par exemple.
Écrivez une fonction Python DansCible(x,y) qui renvoie True si le point M = (x,y) du plan euclidien est dans la boule unité, i.e. d(M,O) ≤ 1 où O = (0,0) et False sinon.

Écrivez une procédure Flechette() qui renvoie les coordonnées (x,y) d'un point du plan euclidien choisi au hasard dans le carré unité, i.e. tel que -1≤ x ≤ 1 et -1≤ y ≤ 1. Indication : importez la fonction uniform avec from random import uniform en tête de fichier, l'appel uniform(a,b) renvoie un flottant compris entre a et b.

Écrivez une fonction Python Compter(n) qui prend en entrée un entier naturel n, et qui lance n fléchettes et renvoie le nombre de fléchettes qui ont atteint la cible (la boule unité). Calculez la valeur 4*Compter(n)/n pour les valeurs n = 10k pour k = 1,2,3,...,7. En déduire ce que calcule le programme.