CPGE OUJDA

DS 2 (2TSI1)

PROBLEME1

Soit le schéma relationnel suivant :

REPRESENTATION (n°représentation, titre_représentation, lieu) 
MUSICIEN (nom, n°représentation*) 
PROGRAMMER (date, n°représentation*, tarif)

Q1 - Donner la liste des titres des représentations.

Q2 - Donner la liste des titres des représentations ayant lieu à l'opéra Bastille.

Q3 - Donner la liste des noms des musiciens et des titres des représentations auxquelles ils participent.

Q4 - Donner la liste des titres des représentations, les lieux et les tarifs pour la journée du 14/09/96.

 PROBLEME2

 1.  Écrire une fonction insertion_sort qui trie de manière croissante une liste donnée en pa- ramètre avec l’algorithme du tri par insertion.Compexité ?

 2.  Écrire une fonction in_list qui détermine si, oui ou non, une valeur donnée existe dans une liste triée. Utiliser la recherche dichotomique.Complexité ?

 3.  Écrire une fonction poly_sort qui reçoit une liste de polynômes, et une valeur x et qui trie cette liste en se basant sur l’ordre défini par la valeur des polynômes en x(Les polynômes sont représentés  par les coefficients de leurs monômes). Par exemple :

p1  =  [4,  2,  3]   ‘’’p1=4+2x+3x²  ’’’

p2  =  [2,  1]

p3  =  [2,  -3,  4,  1]

p4  =  [-1,  2]

ls  =  [p1,  p2,  p3,  p4]

poly_sort(ls,  2)

print(ls) # ->[[-1, 2],  [2,  1],  [2,  -3,  4,  1],  [4,  2,  3]]

Vous utiliserez le tri par sélection.

Pour ce faire on décomposera la question en plusieurs fonctions :

a)Ecrire une fonction  swap(ls, i1, i2): qui permute les éléments d’indices i1 et i2 de la liste ls

b)Ecrire une fonction min_pos_from(ls, i, x): qui retourne La position du min de ls en   commençant en i.

c) Écrire une fonction p_eval qui évalue un polynôme en un x donné.

>>>  polynomial  =  [4,2,7,1] 

>>>  x  =  2

>>>  print(p_eval(polynomial,x))

44  ‘’’ .4*1+2*2+7*4+1*8=44’’’

d) Ecrire la fonction poly_sort(ls, x):

solutions

probleme1

Q1 - Donner la liste des titres des représentations.

R = PROJECTION(REPRESENTATION, titre_représentation)
Et en langage SQL...

SELECT titre_représentation 
FROM REPRESENTATION ;

Q2 - Donner la liste des titres des représentations ayant lieu à l'opéra Bastille.

R1 = SELECTION(REPRESENTATION, lieu="Opéra Bastille") 
R2 = PROJECTION(R1, titre_représentation)
Et en langage SQL...

SELECT titre_représentation 
FROM REPRESENTATION
WHERE lieu="Opéra Bastille" ;

Q3 - Donner la liste des noms des musiciens et des titres des représentations auxquelles ils participent.

R1 = JOINTURE(MUSICIEN, REPRESENTATION, Musicien.n°représentation=Représentation.n°représentation) 
R2 = PROJECTION(R1, nom, titre_représentation)
Et en langage SQL...

SELECT nom, titre_représentation
FROM MUSICIEN INNER JOIN REPRESENTATION ON MUSICIEN.n°représentation = REPRESENTATION.n°représentation ;

Q4 - Donner la liste des titres des représentations, les lieux et les tarifs pour la journée du 14/09/96.

R1 = SELECTION(PROGRAMMER, date=14/09/96) 
R2 = JOINTURE(R1, REPRESENTATION, R1.n°représentation=Représentation.n°représentation) 
R3 = PROJECTION(R2, titre_représentation, lieu, tarif)
Et en langage SQL...

SELECT titre_représentation, lieu, tarif
FROM REPRESENTATION INNER JOIN PROGRAMMER ON PROGRAMMER.n°représentation = REPRESENTATION.n°représentation
WHERE date='14/06/96' ;