103 lines
3.3 KiB
Python
103 lines
3.3 KiB
Python
|
|
#I.1
|
|
|
|
def SelectionConstante(table,indice,constante):
|
|
sortie = []
|
|
for enregistrement in table:
|
|
if(enregistrement[indice]==constante):
|
|
sortie.append(enregistrement)
|
|
return sortie
|
|
|
|
#I.2
|
|
# Ce programme est de complexité O(n) avec n la taille de la table. En effet, toutes les instructions sont en temps constant et la boucle parcours chacun des n éléments de la table une et une seule fois.
|
|
|
|
#I.3
|
|
|
|
def SelectionEgalité(table,indice1,indice2):
|
|
sortie = []
|
|
for enregistrement in table:
|
|
if(enregistrement[indice1]==enregistrement[indice2]):
|
|
sortie.append(enregistrement)
|
|
return sortie
|
|
|
|
#I.4
|
|
def ProjectionEnregistrement(enregistrement,listeIndices):
|
|
newregistrement = []
|
|
for i in listindices:
|
|
newregistrement.append(enregistrement[i])
|
|
return newregistrement
|
|
#I.5
|
|
def Projection(table, listeIndices):
|
|
sortie = []
|
|
for enregistrement in table:
|
|
sortie.append(ProjectionEnregistrement(enregistrement))
|
|
return sortie
|
|
|
|
#I.6
|
|
|
|
def ProduitCartesien(table1,table2):
|
|
sortie = []
|
|
for enreg1 in table1:
|
|
for enreg2 in table2:
|
|
sortie.append(enreg1+enreg2)
|
|
return sortie
|
|
|
|
#I.7
|
|
|
|
def jointEnregistrementsSaufIndice(enreg1,enreg2,indice2):
|
|
sortie = [] + enreg1
|
|
for i in range(0,indice2):
|
|
sortie.append(enreg2[i])
|
|
for i in range(indice2+1,len(enreg2)):
|
|
sortie.append(enreg2[i])
|
|
return sortie
|
|
def Jointure(table1,table2,indice1,indice2):
|
|
sortie = []
|
|
for enreg1 in table1:
|
|
for enreg2 in table2:
|
|
if(enreg1[indice1]==enreg2[indice2]):
|
|
sortie.append(jointEnregistrementsSaufIndice(enreg1,enreg2,indice2))
|
|
return sortie
|
|
|
|
#I.8
|
|
# La complexité est en O(n1*n2*(k2-1))
|
|
# En effet, la fonction jointEnregistrementSaufIndice effectue une copie de l'enregistrement (copie = somme avec la liste vide) en temps constant, puis deux boucles qui s'executent respectivement (indice1) et (k2-indice1-1), donc une complexité pour cette fonction en O(k2-1)
|
|
# Enfin, la fonction Jointure est constituée d'une instruction en temps constant, de deux boucles imbriquées s'executant respectivement n1 et n2 fois. Le contenu de la boucle est en complexité O(1 ou k2-1) donc dans le pire des cas, O(k2-1) d'où la complexité donnée.
|
|
|
|
#I.9
|
|
def egal(liste1,liste2):
|
|
if(len(liste1) != len(liste2)):
|
|
return False
|
|
for i in range(len(liste1)):
|
|
if(liste1(i)==liste2(i)):
|
|
return False
|
|
return True
|
|
|
|
def SupprimerDoublons(table):
|
|
sortie = []
|
|
for ei in range(len(table)):
|
|
oups = False
|
|
for eii in range(ei):
|
|
if(egal(table[ei],table[eii])):
|
|
oups = True
|
|
if(not oups):
|
|
sortie.append(table[ei])
|
|
return sortie
|
|
|
|
|
|
#I.10
|
|
# La fonction égal est de complexité (dans le pire des cas) O(n*n) avec n la longeur commune des deux liste (on peut considérer n'importe laquelle des deux, puisque si l'une est plus longue que l'autre, le coût sera constant).
|
|
# La fonctions SupprimerDoublons effectue deux boucles s'executant n (longeur de la table) fois pour la première et ei pour la deuxième. Le tout s'execute donc 1+2+3+…+n fois , c'est à dire environ n*n/2.
|
|
# La fonction egal étant appelé à chaque fois sur des liste de taille k, l'arité de la table, la complexité totale est donc en O(n*n/2*k)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|