ECOLE SUPÉRIEURE D’ECONOMIE NUMÉRIQUE, UNIVERSITÉ DE MANOUBA
EXAMEN : SESSION PRINCIPALE
Module
Complexité Algorithmique
Enseignant
Chiheb-Eddine Ben N’Cir
Date
Durée
Janvier 2016
2h
Exercice 1 (4 points)
1. Quelle est la complexité asymptotique d’une fonction de recherche d’un élément dans un
tableau en utilisant le principe de hachage ?
2. L’utilisation du hachage peut conduire au problème de collision ? Expliquer ce problème.
Décrire alors une politique utilisée pour gérer les collisions.
3. Comparer la performance du tri-fusion et du tri-rapide en termes de complexité asymptotique,
complexité dans la pratique, et de gestion de l’espace mémoire.
Exercice 2 (6 points)
Publicité
On se donne n objets ayant pour valeurs {c1, . . . , cn} et pour poids {w1, . . . ,wn}. Le but est de
remplir un sac à dos en maximisant la valeur des objets rempli dans le sac. La capacité maximale
du sac à dos en terme de poids est Wsac.
1. Comment peut-on évaluer toutes les solutions possibles ? Quelle est la complexité
asymptotique de ce problème ?
2. Donner une solution de ce problème en utilisant le principe Glouton. (expliquer le principe
avant de donner l’algorithme).
3. Quelle est la complexité asymptotique de l’algorithme proposé?
Exercice 2 (10 points)
₁ ₂
m> deux séquences où a , a ,...,a
soit U=<a1,a2,...,an> et V=<b ,b ,...,b
m sont des
lettres, les entiers n est m sont les longueurs de U et V. On propose de calculer la (les) plus grande
sous-séquence commune de deux séquence U et V.
Une sous-séquence commune est maximale (plus longue sous-séquence commune) si elle est de
longueur maximale, Par exemple, les séquences <b,c,b,a> et <b,d,a,b> de longueur=4 sont les plus
longues sous séquences communes de <a,b,c,b,d,a,b> et <b,d,c,a,b,a>.
Publicité
n et b , b ,…,b
₁
₁
₂
₂
n> s’il
Formellement, on peut dire que V= <b , b ,...,b
existe des entiers i , i , i
k=U[im] pour k dans
[1,m]. Par exemple, V=<b,c,d,b> est une sous-séquence de U=<a,b,c,b,d,a,b> correspondant à la
suite d’indice <2,3,5,7>.
m> est une sous-séquence U=<a ,a ,...,a
₂
₁
m) tel que b =U[i ]
₁ , b =U[i ],…, b
₂ m (i <i <...<i
₁ ₂
Publicité
₁
₂
₁
₂
₁
₂
1. Quel est le nombre de sous-séquences qu’on peut générer à partir d’une suite finie
U=<a1,a2,...,an> de taille n.
ECOLE SUPÉRIEURE D’ECONOMIE NUMÉRIQUE, UNIVERSITÉ DE MANOUBA
EXAMEN : SESSION PRINCIPALE
Module
Complexité Algorithmique
Enseignant
Chiheb-Eddine Ben N’Cir
Date
Durée
Janvier 2016
2h
Publicité
2. Quel serait alors la complexité d’un algorithme qui cherche la plus grande sous-séquence
m> en énumérant et ensuite en comparant
commune de U=<a1,a2,...,an> et V=<b ,b ,...,b
toutes les sous-séquences ?
₁ ₂
On note L(n,m) la fonction permettant de chercher la longueur de la plus grande sous-séquence
commune à U et V de logeur n et m respectivement. On donne l’équation de récurrence suivante
permettant de résoudre le problème :
3. Donner une fonction récursive « PLSSC_recursive » permettant de déterminer la plus
longue sous-séquence commune de deux séquences U et V.
Quelle est la complexité asymptotique de cette solution ?
4.
5. En se basant sur le paradigme de la programmation dynamique, donner une fonction
PLSSC_dynamique permettant de résoudre le problème,
6. Quelle est la complexité asymptotique de cette solution,