Examen COMPLEXITE
EXERCICE 01 : 5PT
1) Soit f(n)=n*logn le nombre d’opérations élémentaires du pire cas d’un algorithme A.
(a) Montrez que f(n)=O(n2).
(b) A-t-on f(n)=Θ(n2) ? Expliquez.
2) Soient Bob, Henzo et Alice ont trois algorithmes conçus pour la même tâche T, et dont les nombres d’opérations élémentaires du pire cas sont, respectivement, f1(n)=n20logn, f2(n)=n! et f3(n)=8n. Comparez les complexités des trois algorithmes. Expliquez.
Exercice 2 : 5pt
On suppose que l'on a un tableau T [1..n] (n≥3) avec la propriété suivante : T[2] ⩽T[1] et T[n-1] ⩽ T[n]. On dit qu'un élément T[i] est un minimum local de T, s'il est inférieure ou égal aux deux éléments qui lui sont adjacents, ou plus formellement, si T[i] ≤T [i-1]et T[i]⩽T[i+1].
1) Déterminer (par leurs indices) tous les minimums locaux du tableau : T= (9,7,7,2,1,3,7,5,4,7,3,3, 4, 8, 6,9}
2) Décrire un algorithme qui détermine un minimum local d'un tableau T [1..n] et calculer sa complexité.
3) En déduire un algorithme de type diviser qui détermine un minimum local d'un tableau T [1..n] et calculer sa complexité.
EXERCICE 03 : 5PT
On considère, pour effectuer la recherche d’un élément dans un tableau, la recherche séquentielle et la recherche dichotomique. On s’intéresse à leur complexité temporelle. Pour cela, considérer un tableau ayant mille éléments (version trié, et version non trié). Pour chaque algorithme, et pour chaque version du tableau, combien de comparaisons sont à effectuer pour :
trouver un élément qui y figure ?
trouver un élément qui n'y figure pas ?
Quels sont les cas où le tableau est parcouru complètement et les cas où un parcours partiel est suffisant ? Conclure en donnant la complexité temporelle pour chaque algorithme
EXERCICE 4 : 05PT
Nous considérons des pièces de monnaie de 1, 2, et 5 FCFA. Notons N (x) le nombre minimum de pièces pour obtenir x FCFA.
Quelle est la valeur de N (0), N (1), N (2), N (3), N (4), N (5) ?
Donner un algorithme qui calcule N (x) et sa complexité en termes d’opérations.
Appliquer cet algorithme qui calcule N (14) en consid´erant maintenant qu’on dispose des pi`eces de monaies de 1, 7 et 10 FCFA. Que constatez-vous ?