UTBM algorithmiques avancees 2003 gi ag51 genie informatique semestre 1 final

Publié par

ƒƒƒƒƒƒExamen de l’U.V. AG51 Sans documents 24/01/2003 J.Gaber (gaber@utbm.fr) Exercice I : Classez les fonctions suivantes dans l’ordre asymptotique du plus grand au plus petit n n100 1(100 ) n 2 log logn logn2 ,1,3 ,n ,logn,nlogn,n!,logn!,n ,( 2) , k, . ∑ ∑kk =1 k ...

Publié le : jeudi 21 juillet 2011
Lecture(s) : 128
Nombre de pages : 1
Voir plus Voir moins
Examen de l’U.V. AG51
Sans documents
24/01/2003
J.Gaber (gaber@utbm.fr)
Exercice I
:
Classez les fonctions suivantes dans l’ordre asymptotique du plus grand au plus petit
=
=
n
k
n
k
n
n
n
k
k
n
n
n
n
n
n
n
1
1
log
log
log
2
)
100
(
1
,
,
)
2
(
,
,
!
log
,
!
,
log
,
log
,
,
3
,
1
,
2
100
.
Exercice II :
Le parcours en largeur est à la base de nombreux algorithmes importants sur les graphes. Donnez
l’algorithme de parcours en largeur d’un graphe G=(S,A) ainsi que son coût.
Exercice III :
Le parcours en profondeur est à la base de nombreux algorithmes importants sur les graphes,
Question III-1 :
Donner l’algorithme de parcours en profondeur d’un graphe G=(S,A) ainsi que son
coût.
Question III-2 :
Le tri topologique d’un graphe orienté acyclique G=(S,A) consiste à afficher tous ses
sommets de sorte que si G contient un arc (
u,v
),
u
apparaisse avant
v
. En d’autres termes, le tri
topologique consiste à ordonner linéairement tous les sommets de G. Donnez l’algorithme
correspondant ainsi que son coût.
Exercice IV :
Une file de priorité (FP) est une structure de données qui intervient dans les problèmes de files
d’attente où l’on doit effectuer plusieurs tâches selon un ordre de priorité.
Soit
A
un arbre binaire dont les étiquettes appartiennent à un ensemble totalement ordonné (par
exemple des entiers). On dit que
A
est une file de priorité si pour tout noeud
n
de
A
, l’étiquette de
n
est
supérieure ou égale à celle de son ou ses fils s’il en a. Par convention, un arbre vide est une FP.
Question IV-1
: Donnez la FP correspondante à l’insertion successives des tâches suivantes : 5 , 4, 1,
3, 2, 0. Les valeurs désignent le niveau de priorité.
Question IV-2
: Donnez le coût des opérations suivantes :
a)
Insertion d’une nouvelle tâche ayant une certaine priorité.
b)
Extraction d’une tâche prioritaire (celle associée à la racine) et reconstitution d’une FP avec
les tâches restantes.
c)
Construction d’une FP à partir d’un vecteur non-ordonné donné.
Exercice V
La majeure partie des opérations sur une base de données consiste à rechercher l’emplacement d’un ou
plusieurs enregistrements. Afin d’accélérer les recherches, les systèmes de base de données utilisent
des index. Une manière d’implanter les index consiste à utiliser des B-arbres. Les B-arbres sont des
arbres de recherche équilibrés conçus pour minimiser les opérations d’entrées/sorties sur les disques.
Un arbre 2-3 est un B-arbre particulier qui possède les propriétés suivantes:
a)
un noeud contient 1 ou 2 clefs,
b)
chaque noeud interne possède
ƒ
2 enfants (s’il contient 1 clefs) ou
ƒ
3 enfants (s’il contient 2 clefs).
ƒ
Toutes les feuilles sont au même niveau dans l’arbre (qui est donc balancé).
Question V-1
: Donnez l’exemple d’un arbre 2-3.
Question V-2
: Donnez les coûts respectifs des opérations suivantes :
ƒ
Recherche d’une clé
ƒ
Insertion d’une clé
ƒ
Suppression d’une clé.
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.