Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Ann´ ee Universitaire 2013/2014 DS 2 Parcours : Licence LIMI201 & LIMI211 Code

Ann´ ee Universitaire 2013/2014 DS 2 Parcours : Licence LIMI201 & LIMI211 Code UE : J1MI2013 ´ Epreuve : Algorithmes et Programmes Date : Vendredi 18 avril 2014 Heure : 8 heures 30 Dur´ ee : 1 heure 30 Documents : non autoris´ es Coll` ege Sciences et Technologies SUJET + CORRIGE Avertissement – La plupart des questions sont ind´ ependantes. – ` A chaque question, vous pouvez au choix r´ epondre par un algorithme ou bien par un programme python. – Les indentations des fonctions ´ ecrites en Python doivent ˆ etre respect´ ees. – L’espace laiss´ e pour les r´ eponses est suﬃsant (sauf si vous utilisez ces feuilles comme brouillon, ce qui est fortement d´ econseill´ e). Question Points Score ´ Evaluation d’expressions 3 Homog´ en´ eit´ e 3 Calculs d’une suite 6 Tableaux 8 Total: 20 Exercice 1 : ´ Evaluation d’expressions (3 points) On d´ eﬁnit les variables suivantes (en Python) : t = [4, 8, 15, 16, 23, 42] i = 3 x = t[1] Donner le r´ esultat de l’´ evaluation des expressions suivantes, en pr´ ecisant le r´ esultat de l’´ evaluation des sous-expressions qui sont utilis´ ees. (a) (1 point) t[i + 1] - t[i - 1] == t[i - 2] Solution: ‘True’ : ‘t[4] - t[2] == t[1]’ donne ‘23 - 15 == 8’ donne ‘8 == 8’ (b) (1 point) x < len(t) and t[x] != 0 Solution: ‘False’ : ‘8 < 6 and ... ’ donne ‘False and ... ’, ´ evalu´ e paresseusement (c) (1 point) not t[i] < x or t[x] > 20 UE J1MI2013 : Algorithmes et Programmes DS 2, Ann´ ee 2013/2014 Solution: ‘True’ : ‘not t[3] < 8 or ... ’ donne ‘not False or ... ’ donne ‘True or ... ’, ´ evalu´ e idem Exercice 2 : Homog´ en´ eit´ e (3 points) (a) (2 points) ´ Ecrire une fonction homogene (t) prenant en param` etre un tableau t et qui retourne True si le tableau est homog` ene, c’est-` a-dire si tous ses ´ el´ ements sont identiques, et False sinon. Exemples : >>> homogene([]) True >>> homogene([2, 2, 2]) True >>> homogene([2, 2, 1]) False Solution: def homogene (t): for i in range(1, len(t)): if t[i] != t[0]: return False return True (b) (1 / 2 point) Donner la complexit´ e dans le meilleur des cas ? Solution: Ω(1). Le meilleur des cas se produit lorsque t[0] diﬀ` ere de t[1]. (c) (1 / 2 point) Donner la complexit´ e dans le pire des cas ? Solution: O(len(t)). Le pire de cas se produit lorsque le tableau est homog` ene. Exercice 3 : Calculs d’une suite (6 points) On consid` ere la fonction : def suiteIter (n): u = 1 while n > 0: u = 2 * u + 1 n -= 1 return u (a) (1 point) Calculer suiteIter(3). Solution: suiteIter(3) retourne 15. (b) (2 points) ´ Ecrire une version r´ ecursive suiteRec (n) pour la fonction pr´ ec´ edente. Solution: def suiteRec (n): if n == 0: return 1 return 2 * suiteRec(n - 1) + 1 (c) (2 points) Pour tout entier naturel k, soit Sk la valeur retourn´ ee par suiteIter(k). Sans utiliser les fonctions suiteIter (n) et suiteRec (n), ´ ecrire une fonction tableauSuite (n) qui cr´ ee et retourne un tableau contenant les n premiers termes de la suite S. Page 2 sur 4 UE J1MI2013 : Algorithmes et Programmes DS 2, Ann´ ee 2013/2014 Solution: def tableauSuite (n): t = creerTableau(n,1) for i in range(1, n): t[i] = 2 * t[i - 1] + 1 return t (d) (1 point) Donner une version r´ ecursive terminale de la fonction suiteRec (n). Solution: def suiteRecTerm (n, acc): if n == 0: return acc return suiteRecTerm(n - 1, 2 * acc + 1) Exercice 4 : Tableaux (8 points) Pour cet exercice, vous pouvez faire appel aux primitives de la biblioth` eque bibTableau.py utilis´ ee en cours. (a) (2 points) ´ Ecrire une fonction compterChangements (t) qui prend en param` etre un tableau t et qui retourne le nombre d’apparitions d’une valeur diﬀ´ erente de la pr´ ec´ edente (en comptant la premi` ere valeur). Exemples : >>> compterChangements([]) 0 >>> compterChangements([2]) 1 >>> compterChangements([2, 1, 1, 1, 2, 3, 2]) 5 Solution: def compterChangements (t): # Theta(len(t)) l = len(t) if l == 0: return 0 c = 1 for i in range(1, l): if t[i] != t[i-1]: c = c + 1 return c (b) (1 point) Quelle est la complexit´ e de cette fonction ? Solution: Θ(len(t)) Pour repr´ esenter une suite de n valeurs v identiques de mani` ere compress´ ee, on utilise une paire (k, v). En Python, on repr´ esentera une paire (k, v) par un tableau ` a deux cases [k, v]. Par exemple, la suite 2, 2, 2, 2 est repr´ esent´ ee par la paire (4, 2) et en Python par le tableau [4, 2]. (c) (1 point) ´ Ecrire une fonction Python creerPaire (k, v) qui retourne le tableau repr´ esentant la paire (k, v). Solution: def creerPaire (k, v): Page 3 sur 4 UE J1MI2013 : Algorithmes et Programmes DS 2, Ann´ ee 2013/2014 paire = creerTableau(2) paire[0] = k paire[1] = v return paire (d) (1 / 2 point) Quelle est la complexit´ e de la fonction creerPaire ? Solution: Θ(1) Soit la fonction mystere (t) donn´ ee Figure 1 qui prend en param` etre un tableau t non vide. def mystere (t): s = creerTableau(compterChangements(t)) v = t[0] k = 1 j = 0 for i in range(1, len(t)): if t[i] != v: s[j] = creerPaire(c, v) k = 1 j = j + 1 v = t[i] else: k = k + 1 s[j] = creerPaire(k, v) return s Figure 1 – Fonction mystere (e) Que retournent les appels suivants ? i. (1 / 2 point) mystere([1]) Solution: [[1, 1]] ii. (1 / 2 point) mystere([1, 1, 1]) Solution: [[3, 1]] iii. (1 / 2 point) mystere([1, 1, 1, 4, 4, 1]) Solution: [[3, 1], [2, 4], [1, 1]] (f) (1 point) Quelle est la complexit´ e de la fonction mystere ? Solution: Θ(len(t)) (g) (1 point) Expliquer en une ou deux phrases ce que retourne la fonction mystere en fonction de t. Solution: La fonction retourne un tableau s de paires qui repr´ esente une forme compress´ ee du tableau t. Si on concat` ene les s´ equences obtenues par d´ ecompression de chaque paire, on retrouve la suite des ´ el´ ements de t. Page 4 sur 4 uploads/s3/ ds1-2014-corrige 1 .pdf