U.S.T.O. M.B./Dept.
Informatique 2ème Année Ingénieur - Informatique
Durée : 01h15’ TEST Mercredi 20 Novembre 2024
ALGORITHMIQUES ET COMPLEXITE
1. Trier les fonctions suivantes par ordre croissant de l’ordre de grandeur asymptotique : (4.5pts)
𝑓1(𝑛) = 𝑛! 𝑓2(𝑛) = 100 𝑓3(𝑛) = 𝑛²
𝑓4(𝑛) = 𝑛 𝑓5(𝑛) = 𝑛𝑙𝑜𝑔 𝑛 𝑓6(𝑛) = 𝑛√𝑛
𝑓7(𝑛) = 𝑛 𝑓8(𝑛) = 𝑙𝑜𝑔 𝑛 𝑓9(𝑛) = 100
2. Considérons l’algorithme suivant qui prend en entrée un tableau A de taille n : (8.5pts)
int exercice2(int *A, int n) {
int ms = -99999; // représente moins l’infini
for (int i=0; i<n; i++)
for (int j=i; j<n; j++) {
int cs = 0;
for (int k=i; k<=j; k++) cs += A[k];
ms = max(ms, cs);
}
return ms;
}
a) Quelle est la valeur retournée si A est égal à :
- {4 , 5 , 8}
- {4 , 5 , −8}
b) Analyser la complexité de cet algorithme.
c) Proposer une amélioration de cet algorithme.
3. Considérons l’algorithme récursif de tri par sélection d’un tableau de taille N : (4pts)
void triSelection(int *A, int deb, int fin)
{ if (deb<fin) {
int min = chercherMinimum(A , deb , fin);
int aux = A[deb]; A[deb] = A[min]; A[min] = aux;
triSelection(A , deb+1 , fin);
}
}
a. Quelle est la complexité de recherche du minimum d’un tableau de N entiers ?
b. Définir la complexité du tri par sélection récursif à l’aide d’une formule de récurrence.
c. A partir de cette formule de récurrence, montrer que la complexité de cet algorithme est O(N²).
4. Considérons le tri à bulles (voir code ci-dessous). Proposer une implémentation optimisée de
complexité "meilleur cas" linéaire (lorsque le tableau est déjà trié). (3pts)
void bubbleSort(int *A, int n) {
for (int i=0 ; i<n-1 ; i++)
for (int j=n-1 ; j>i ; j--) if (A[j]<A[j-1]) swap(A,j,j-1);
}
Bon courage…
Solution & Barème
Exercice n°1 : (4.5pts: 0.5pt for each well classified function)
Trier les fonctions suivantes par ordre croissant de l’ordre de grandeur asymptotique
1 𝑓2(𝑛) = 100
2 𝑓8(𝑛) = 𝑙𝑜𝑔 𝑛
3 𝑓4(𝑛) = 𝑛
4 𝑓5(𝑛) = 𝑛𝑙𝑜𝑔 𝑛
5 𝑓6(𝑛) = 𝑛√𝑛
6 𝑓3(𝑛) = 𝑛
7 𝑓9(𝑛) = 100
8 𝑓1(𝑛) = 𝑛!
9 𝑓7(𝑛) = 𝑛
Exercice n°2 : (8.5pts)
Considérons l’algorithme suivant qui prend en entrée un tableau A de taille n :
int exercice2(int *A, int n) {
int ms = -99999; // représente moins l’infini
for (int i=0; i<n; i++)
for (int j=i; j<n; j++) {
int cs = 0;
for (int k=i; k<=j; k++) cs += A[k];
ms = max(ms, cs);
}
return ms;
}
a) Quelle est la valeur retournée si A est égal à : (2pts : 1 + 1)
- {4 , 5 , 8} : 17
- {4 , 5 , −8} : 9
b) Analyser la complexité de cet algorithme. (3.5pts)
for (int i=0; i<n; i++)……………………………………………n = O(n)
for (int j=i; j<n; j++) { ………………………………n+(n-1)+…+1=n(n+1)/2 = O(n²)
int curS = 0;
for (int k=i; k<=j; k++) ……………………………(1+2+…+n)+(1+2+…+(n-1))+…+1 = O(n3)*
curS += A[k];
maxS = max(maxS, curS);
}
𝑘(𝑘 + 1) 1 𝑛(𝑛 + 1)(2𝑛 + 1) 𝑛(𝑛 + 1)
∗ 𝑝= = 𝑘 + 𝑘 = 1/2 − = 𝑂(𝑛 )
2 2 6 2
Boucle1 : 0.5pt
Boucle2 : 0.75pt
Boucle3 : 1.5pts
Résultat final : 0.75pt
c) Proposer une amélioration de cet algorithme. (3pts)
int maxSubarrayOptimized(int *A, int n) { //O(n²)
int ms = -99999;
for (int i = 0; i < n; i++) {
int cs = 0;
for (int j = i; j < n; j++) {
cs += A[j]; ms = max(ms, cs);
}
}
return ms;
}
int kadaneAlgorithm(int *A, int n) { //O(n)
int mh = A[0]; int mf = A[0];
for (int i = 1; i < n; ++i) {
mh = max(A[i], mh + A[i]);
mf = max(mf, mh);
}
return mf;
}
Exercice n°3 : (4pts)
a. Quelle est la complexité de recherche du minimum d’un tableau de N entiers ? (0.5pt)
O(N)
b. Définir la complexité du tri par sélection récursif à l’aide d’une formule de récurrence. (1pt)
T(N)=T(N-1)+O(N) avec T(1)=O(1)
c. A partir de cette formule de récurrence, montrer que la complexité de cet algorithme est O(N²).
(2.5pts)
T(N)=T(N-1)+N=T(N-2)+2N-1=T(N-3)+3N-3=T(N-p)+pN+p(p+1)/2 1.5pt
N-p=1 donc p=N-1 T(N) = 1+N(N-1)+N(N-1)/2 = O(N²) 1pt
Exercice n°4 : (3pts)
void improvedBubbleSort(int *A, int n) {
bool swapped;
for (int i = 0; i < n-1; i++) {
swapped = false;
for (int j = n-1; j > i; j--) {
if (A[j] < A[j-1]) {
swap(A,j,j-1);
swapped = true;
}
}
// Si aucun échange n'a eu lieu, le tableau est déjà trié
if (!swapped) break;
}
}
