Remerciez-le!

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

Numéro d’anonymat (à remplir par un surveillant) Examen 2016 – 2017 Éléments de

Numéro d’anonymat (à remplir par un surveillant) Examen 2016 – 2017 Éléments de Programmation I – 1I001 Durée : 2h Documents autorisés: Aucun document ni machine électronique n’est autorisé à l’exception de la carte de référence de Python. Le sujet comporte 23 pages. Ne pas désagrafer les feuilles. Répondre directement sur le sujet, dans les boîtes appropriées. La taille des boîtes suggère le nombre de lignes de la réponse attendue. Le quadrillage permet d’aligner les indentations. Le barème indiqué pour chaque question n’est donné qu’à titre indicatif. Le barème total est lui aussi donné à titre indicatif : 66 points auxquels peuvent s’ajouter des points bonus explicités dans l’énoncé des questions. La clarté des réponses et la présentation des programmes seront appréciées. Les exercices peuvent être résolus dans un ordre quelconque. Pour répondre à une question, il possible et souvent utile, d’utiliser les fonctions qui sont l’objet des questions précédentes, même si vous n’avez répondu à ces questions précédentes. Remarque: si nécessaire, on considère que la bibliothèque de fonctions mathématiques a été importée avant les fonctions à écrire. Sauf mention contraire explicite, seules les primitives Python présentes sur la carte de référence peuvent être utilisées. Important: bien lire ce qui est demandé dans l’intitulé de la question. Sauf exception (ex.: fonction mystère), pour les fonctions demandées, il est nécessaire de donner une déﬁnition avec signature et hypothèse(s) éventuelle(s), mais pas nécessaire de donner la description ou un jeu de test. Notation des spéciﬁcations: Une spéciﬁcation (signature et hypothèses) seule ne rapporte pas de point. Une fonction correcte dont la spéciﬁcation est fausse ou manquante est pénalisée. L’examen est composé de quatre exercices indépendants : — Exercice 1 : Organisation du festival Elem-o-Prog – (p. 2) — Exercice 2 : Réseaux Sociaux – (p. 6) — Exercice 3 : Ensemble de Mandelbrot – (p. 11) — Exercice 4 : Analyse de Code – (p. 15) c ⃝UPMC - Informatique - 1I001 - page 1 - Exercice 1 : Organisation du festival Elem-o-Prog Chaque année, le Festival Elem-o-Prog a lieu le 1er janvier, entre 0h et 24h. Les groupes de musique envoient une demande de concert, sous la forme d’une chaîne de caractères avec un format bien précis : ’XX-nom-YY’. Les 2 caractères XX correspondent à l’heure de début (un nombre entier à 2 chiﬀres compris entre 00 et 23) et les caractères YY correspondent à l’heure de ﬁn (un nombre entier à 2 chiﬀres compris entre 01 et 24) tels que XX < YY. Enﬁn ’nom’ est le nom de leur groupe. Ainsi la chaîne ’06-LesPtitsDej-10’ correspond au groupe ’LesPtitsDej’ qui souhaite jouer de 6h à 10h. L’exercice consiste à sélectionner des concerts dont les horaires sont compatibles. Question 1.1 : [2/66] Donner une déﬁnition avec signature et hypothèse(s) éventuelle(s) de la fonction extraction_concert qui, étant donné une demande (sous la forme ’XX-nom-YY’), renvoie le triplet concert du style sous la forme (’nom’, XX, YY) dont les éléments sont respectivement de type str, int et int. Par exemple : >>> extraction_concert(’02-LeveTot-05’) (’LeveTot’, 2, 5) >>> extraction_concert(’06-LesPtitsDej-10’) (’LesPtitsDej’, 6, 10) Rappel : la fonction int(s) transforme la chaîne de caractères représentant un entier en un entier. >>> int( ’12’ ) 12 >>> int( ’05’ ) 5 Réponse def extraction_concert(demande): """ str -> (str, int, int) H: demande est bien formattee""" return (demande[3:-3], int(demande[:2]), int(demande[-2:])) Les demandes d’inscription sont enregistrées dans la liste de demandes suivante : # Demandes : list[str] Demandes = [ ’07-Les7:9-09’, ’22-LesNoctambules-23’, ’06-LesPtitsDej-10’, ’06-Aube-07’, ’02-LeveTot-05’] Question 1.2 : [3/66] Donner une déﬁnition avec signature et hypothèse(s) éventuelle(s) de la fonction liste_concerts qui, étant donné une liste de demandes (contenant des éléments sous la forme ’XX-nom-YY’), renvoie la liste des triplets de concerts du style (’nom’, XX, YY). Ainsi, c ⃝UPMC - Informatique - 1I001 - page 2 - >>> liste_concerts(Demandes) [(’Les7:9’, 7, 9), (’LesNoctambules’, 22, 23), (’LesPtitsDej’, 6, 10), (’Aube’, 6, 7), (’LeveTot’, 2, 5)] Réponse def liste_concerts(L): """ list[str] -> list[ (str, int, int) ] """ # R : list[(str, int, int)] R = [] # d : str for d in L: R.append(extraction_concert(d)) return R La liste des triplets de concerts est triée suivant l’heure de début de chaque concert. Voilà le résultat obtenu : # Concerts : list[(str, int, int)] Concerts = [ (’LeveTot’,2, 5), (’LesPtitsDej’, 6, 10), (’Aube’,6, 7), (’Les7:9’, 7, 9), (’LesNoctambules’, 22, 23) ] On reçoit une nouvelle demande d (de type str). On veut insérer le triplet concert associé à d, dans la liste de triplets déjà triée suivant l’heure de début (la liste est éventuellement vide). On veut le placer à la première position possible qui respecte l’ordre croissant de début de concert. Question 1.3 : [4/66] Donner une déﬁnition avec signature et hypothèse(s) éventuelle(s) de la fonction indice qui, étant donné une demande d, et une liste de triplets concerts triée Concerts, renvoie l’indice où l’insertion doit se faire. Par exemple : >>> indice(’20-LeVingtHeure-21’, Concerts) 4 >>> indice(’22-LesDer-24’, Concerts) 4 >>> indice(’23-GongFinal-24’, Concerts) 5 >>> indice(’20-LeVingtHeure-21’, []) 0 Attention : la fonction indice peut ne pas être correcte si en entrée, la liste n’est pas triée suivant le début de concert. c ⃝UPMC - Informatique - 1I001 - page 3 - Réponse def indice(d, L): """ str * list[(str, int, int)]-> int Hypothese : L est triee suivant le dàbut des concerts """ # nom:str, deb:int fin:int nom, deb, fin = extraction_concert(d) # i : int indice courant i = 0 while i<len(L): # nomL:str, debL:int, finL:int nomL, debL, finL = L[i] if deb > debL: i = i+1 else: return i return i Question 1.4 : [2/66] Donner une déﬁnition avec signature et hypothèse(s) éventuelle(s) de la fonction insertion qui, étant donnée la nouvelle demande d, et une liste de triplets concerts triée L, renvoie une nouvelle liste dans laquelle le concert associé à d a été inséré. Par exemple : >>> insertion(’20-LeVingtHeure-21’, Concerts) [(’LeveTot’, 2, 5), (’LesPtitsDej’, 6, 10), (’Aube’, 6, 7), (’Les7:9’, 7, 9), (’LeVingtHeure’, 20, 21), (’LesNoctambules’, 22, 23)] >>> insertion(’22-LesDer-24’, Concerts) [(’LeveTot’, 2, 5), (’LesPtitsDej’, 6, 10), (’Aube’, 6, 7), (’Les7:9’, 7, 9), (’LesDer’, 22, 24), (’LesNoctambules’, 22, 23)] >>> insertion(’23-GongFinal-24’, Concerts) [(’LeveTot’, 2, 5), (’LesPtitsDej’, 6, 10), (’Aube’, 6, 7), (’Les7:9’, 7, 9), (’LesNoctambules’, 22, 23), (’GongFinal’, 23, 24)] >>> insertion(’20-LeVingtHeure-21’, []) [(’LeVingtHeure’, 20, 21)] Réponse def insertion(d, L): """ str * list[(str, int, int)]-> list[(str, int, int)] Hypothese : L est triee suivant le debut des concerts """ #i : int i = indice(d, L) return L[:i] + [extraction_concert(d)] + L[i:] On déﬁnit Concerts2, le résultat des deux insertions suivantes : # Concerts2 : list[ (str, int, int) ] >>> Concerts2 = insertion(’20-LeVingtHeure-21’, insertion(’22-LesDer-24’, Concerts)) c ⃝UPMC - Informatique - 1I001 - page 4 - >>> Concerts2 [(’LeveTot’, 2, 5), (’LesPtitsDej’, 6, 10), (’Aube’, 6, 7), (’Les7:9’, 7, 9), (’LeVingtHeure’, 20, 21), (’LesDer’, 22, 24), (’LesNoctambules’, 22, 23)] Question 1.5 : [1/66] Donner une déﬁnition avec signature et hypothèse(s) éventuelle(s) de la fonction est_compatible qui, étant donné deux triplets concerts, concert1 et concert2, renvoie True si la ﬁn de concert1 est avant le début de concert2. Sinon, la fonction renvoie False. Ainsi, on obtient : >>> est_compatible( (’Aube’, 6, 7), (’LesNoctambules’, 22, 23)) True >>> est_compatible( (’Aube’, 6, 7), (’Les7:9’, 7, 9)) True >>> est_compatible( (’LesPtitsDej’, 6, 10), (’Les7:9’, 7, 9)) False >>> est_compatible((’LesNoctambules’, 22, 23), (’LeveTot’, 2, 5)) False Réponse def est_compatible(concert1, concert2): """ list[(str, int, int)]**2 -> bool """ # n1, n2 : str # d1, f1, d2, f2 : int n1, d1, f1 = concert1 n2, d2, f2 = concert2 return f1 <= d2 Question 1.6 : [4/66] Donner une déﬁnition avec signature et hypothèse(s) éventuelle(s) de la fonction liste_compatible qui, étant donné une liste de triplets concerts triée L (suivant le début du concert), renvoie une nouvelle liste ne conservant que les triplets compatibles. >>> liste_compatible(Concerts) [(’LeveTot’, 2, 5), (’LesPtitsDej’, 6, 10), (’LesNoctambules’, 22, 23)] >>> liste_compatible(Concerts2) [(’LeveTot’, 2, 5), (’LesPtitsDej’, 6, 10), (’LeVingtHeure’, 20, 21), (’LesDer’, 22, 24)] c ⃝UPMC - Informatique - 1I001 - page 5 - Réponse def liste_compatible(L): """ list[(str, int, int)] -> list[(str, int, int)] """ if L == []: return [] # R : list[s(str, int, int)] liste resultat R = [ L[0] ] # i : int for i in range(1, len(L)): if est_compatible(R[-1], L[i]): R.append(L[i]) return R Exercice 2 : Réseaux Sociaux Dans cet exercice, on s’intéresse à une modélisation de deux types de réseaux sociaux sous forme de dictionnaires. Dans un premier temps, on modèlise un réseau social comme un dictionnaire (de type dict[str:set[str]]) dont les clefs sont les personnes inscrites dans le réseau et où la valeur associée à une personne p est l’ensemble des personnes du réseau que p a comme ami. Attention : la relation d’amitié représentée par un réseau n’est pas forcément réciproque. Par exemple ’Amine’ peut avoir ’Daniel’ dans ses amis sans que ’Daniel’ ait ’Amine’ dans ses amis. On utilise l’alias de type Reseau : # type Reseau = dict[str:set[str]] On suppose que dans un Reseau, les valeurs ne sont composées que d’éléments qui uploads/s3/ corrige-exam1-2016.pdf