L2SI / I31 - Examen de TP d'algorithmique

Vendredi 17 novembre 2017: 13:15(-0:15) → 15:15(+0:15)

CONSIGNES.

TOUS DOCUMENTS INTERDITS. Vous avez 1/4 d'heure au début de l'examen pour lire en détail les consignes ci-dessous avant de commencer les exercices, et un deuxième 1/4 d'heure en fin d'examen pour le finaliser.

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.

L'expérience prouve que certains étudiants ne savent pas lire un énoncé et/ou recopier une simple commande. Vous devriez donc les copier avec la souris afin d'éviter, entre autres, de confondre la quote ' et l'antiquote `.

NB. Pour les étudiants de la filière SI : si vous n'avez pas suivi ces consignes et que je dois intervenir pour faire ce travail à votre place (10% des étudiants de la promotion 2016-2017), je retirerai 5 points à votre note.


SUJET.

Le barème indiqué sur les exercices est approximatif. Les réponses aux questions posées doivent être incorporées aux fichiers sources Python sous forme de commentaires en début de programme.

IMPORTANT : Expliquez en français sous forme de commentaires les algorithmes que vous utilisez pour écrire vos fonctions !

[+4] On désigne par A et B deux listes d'entiers naturels triées. Écrivez une fonction Fusionner(A,B) qui renvoie la liste triée contenant tous les termes des deux listes. Vous ne devez pas utiliser d'algorithme de tri pour trier la concaténation des deux listes A+B mais balayer les termes des deux listes pour construire la liste résultat.

Exemple : si A=[1,1,3,5] et B=[2,4,7], la liste renvoyée est la liste [1,1,2,3,4,5,7].

Quelle est la complexité de votre algorithme en fonction des longueurs n et m des deux listes ?

[+6] On désigne par a et b chaînes de caractères. Écrivez une fonction Trouver(a,b) qui renvoie la liste des positions de la chaîne a dans la chaîne b si a est une sous-chaîne de b et la liste vide sinon. Vous ne devez pas utiliser les opérateurs Python match, find ou in.

Par exemple si a="GA" et b="GARGANTUA", la liste renvoyée est la liste [0,3].

Quelle est/sont la/les complexité(s) de votre algorithme en fonction des longueurs n et m des deux chaînes ?

[+6] Écrivez une fonction S2B(N,t) qui renvoie la représentation binaire sur t bits de l'entier N sous forme de chaîne de caractères (bit de poids fort à gauche). Ainsi S2B(5,8) renvoie la chaîne "00000101".

On désigne par L une liste d'entiers. Écrivez une fonction Python Blocs(L,t) qui renvoie une liste d'entiers contenant alternativement les longueurs des séquences de 0 et de 1 qui constituent la concaténation des écritures binaires sur t bits des entiers de la liste L.

Par exemple, si L=[3,0,8,2], la concaténation des écritures binaires des entiers sur 8 bits de cette liste est "00000011"+"00000000"+"00001000"+"00000010" et la fonction Blocs doit renvoyer la liste [6,2,12,1,9,1,1].

Quelle est la liste renvoyée par l'appel Blocs(Blocs(Blocs(0,8),8),8) ?

[+4] En incluant la librairie random (rajouter from random import * dans votre script), l'appel de la fonction random() (sans paramètre) renvoie un nombre flottant de l'intervalle [0,1[.

Écrivez une fonction DansUnite(x,y) qui renvoie True si le point de coordonnées (x, y) du plan réel est dans la boule unité, autrement dit si sa distance au point de coordonnées (0,0) est strictement inférieure à 1, et False sinon.

Écrivez une fonction Flechette() (sans paramètre) qui renvoie un couple de points (x, y) dans le carré unité, i.e. tel que x < 1 et y < 1.

Écrivez une fonction Cribler(n) qui génère n couples (x, y) au hasard dans le carré unité et qui renvoie le nombre de ces couples qui appartiennent au cercle unité.

Écrivez un script qui demande de saisir la valeur entière n et qui renvoie la valeur (4 * Cribler(n)) / n. Que calcule ce script ?