Informatique Devoir N°3: Complexité Algorithmique: QCM Pour Commencer

Ecole Préparatoire (EP) 2015-2016
Module Informatique par Dr KADJO
Informatique
Devoir N°3
Durée : 2H00
« Ordinateurs, tablette et autres téléphones interdits, Documents non autorisés » »

Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il le signale sur sa
copie et poursuit sa composition en expliquant les raisons des initiatives qu'il est amené à prendre.
Exercice 1 Complexité algorithmique : QCM pour commencer
1) Soit la fonction suivante
def devine(a,b) :
if (a == 0) :
return b
return devine(a-1,a*b)
la complexité de cette fonction est
a)𝜃(𝑎) b) 𝜃(𝑎𝑏) c) 𝜃(𝑏 ) d) 𝜃(𝑎 )
2) laquelle de ces complexités est la plus petite ?

a)𝜃(𝑛!) b) 𝜃(𝑛 ) c) 𝜃(2 ) d) 𝜃(𝑛 )
3) laquelle de ces complexités est la plus grande ?

a)𝜃(𝑙𝑜𝑔 (𝑛!)) b) 𝜃(𝑛 ) c) 𝜃(2 ) d) 𝜃(𝑛√ )
4) Quelle la comlexité du meilleur algorithme pour le calcul de la puissance 𝑀 , avec M une matrice
d’entiers de taille 3x3 ?
a)𝜃(𝑙𝑜𝑔 (𝑛)) b) 𝜃(𝑛 ) c) 𝜃(3 ) d) 𝜃(𝑛𝑙𝑜𝑔 (𝑛))
5) On veut trier un tableau de n entiers à l’aide d’un algorthme de tri à bulles standard (chaque itération
déplace le plus grand élément à a fin du tableau). Combien d’itération au minimum faut-il pour etre certain
que le tableau est trié ?
a)1 b) 𝑛 − 1 c) 𝑛 d) 𝑛
6) Dans une implémentation normale de pile contenant 𝑛 éléments, quels sont les coûts respectifs des
opérations d’insertion et d’extraction ?
a)𝜃(1) et 𝜃(𝑛) b) 𝜃(1) et 𝜃(1) c) 𝜃(𝑛) et 𝜃(1) d)𝜃(𝑛) et 𝜃(𝑛)
7) soit la fonction suivante

def func(n) :
i=0
j=0
while (i≤ 𝑛 ) :
i = 2*j+i+1
j += 1
return (j-1)
a)𝜃(𝑙𝑜𝑔 (𝑛)) b) 𝜃(√𝑛) c) 𝜃(𝑛) d) 𝜃( ( )
)
Exercice 2 un peu plus complexe !
1) Determiner la complexité des algorithmes suivants en supposant que le coût de print("*") est 𝑐
Algorithme 1 Algorithme 2
for i in range(1,n+1) : for i in range(1,n+1) :

for j in range(1,n+1) : for j in range(i,n+1) :
print("*") print("*")
2) Donner et justifier la complexité des fonctions suivantes

def mystere1(n) : def mystere2(t) :
i=0 for i in range(len(t)-1) :
j=0 for j in range(i+1,len(t)) :
while (i< n) : if(t[i] == t[j]) :
if (i % 2 == 0) : return (False)
j += 1 return (True)
else :
j /= 2
i += 1
return (j)
3) Soit la fonction myster3(t,k) où t est un tableau d’entiers non vide et k vérifiant 0 ≤ 𝑘 < 𝑙𝑒𝑛(𝑡)
Quel est le nombre maximum d’appels récursifs (en fonction de n et k) de la fonction mystere3(t,k) si le
tableau t est de longueur 𝑛 ?
def mystere3(t, k) :
if(k == len(t) - 1) :
return (True)
if(t[k] > t[k+1]) :
return (False)
return (mystere3(t, k+1) )
Exercice 3 Manipulons les bases de données
Soit la base de données touristique ci-dessous :

Station(numStat, nomStat, altitude, region)
Hotel(numHotel, nomHotel, numStat, categorie)
Chambre(numChamb, numHotel, nbDeLits)
Client(numCli, nomCli, prenomsCli, AdressCli, telCli)
Reservation(numCli, numHotel, numChamb, dtaeDebut, dateFin, nbPers)
NB : Les clés primaires sont soulignées et les clés étrangères sont en gras
1) Donner l’instruction SQL sous MYSQL permettant de donner les noms des clients et le nombre de
personnes correspondantes pour les réservations de l’Hotel Président de Yamoussoukro.
2) Pour chaque station de Yamoussoukro, donner l’instruction SQL sous MYSQL permettant de fournir
le nombre de chambres réservées pour le 01/10/2015.
3) Pour chaque station de Yamoussoukro, Donner l’instruction SQL sous MYSQL permettant de
fournir le nombre de lits en catégorie 3 étoiles.
4) Donner l’instruction SQL sous MYSQL permettant de fournir les noms des hôtels de catégorie 2
étoiles de Yamoussoukro qui sont complets la semaine du 05/10/2015 au 11/10/2015.
5) Donner l’instruction SQL sous MYSQL permettant de fournir la liste des clients qui sont allés dans
au moins 3 régions ?
6) Donner l’instruction SQL sous MYSQL permettant de fournir la liste des clients qui sont allés dans
toutes les stations de MAN ?

Informatique Devoir N°3: Complexité Algorithmique: QCM Pour Commencer

Transféré par

Droits d'auteur :

Formats disponibles

Informatique Devoir N°3: Complexité Algorithmique: QCM Pour Commencer

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Informatique Devoir N°3: Complexité Algorithmique: QCM Pour Commencer

Transféré par

Droits d'auteur :

Formats disponibles

Ecole Préparatoire (EP) 2015-2016

Module Informatique par Dr KADJO

« Ordinateurs, tablette et autres téléphones interdits, Documents non autorisés » »

Exercice 1 Complexité algorithmique : QCM pour commencer

1) Soit la fonction suivante

2) laquelle de ces complexités est la plus petite ?

3) laquelle de ces complexités est la plus grande ?

7) soit la fonction suivante

Exercice 2 un peu plus complexe !

for i in range(1,n+1) : for i in range(1,n+1) :

2) Donner et justifier la complexité des fonctions suivantes

Exercice 3 Manipulons les bases de données

Soit la base de données touristique ci-dessous :

Vous aimerez peut-être aussi