Algorithmiques avancées 2003 Génie Informatique Université de Technologie de Belfort Montbéliard
1
page
Français
Documents
2008
Cet ouvrage peut être téléchargé gratuitement
1
page
Français
Documents
2008
Cet ouvrage peut être téléchargé gratuitement
Examen du Supérieur Université de Technologie de Belfort Montbéliard. Sujet de Algorithmiques avancées 2003. Retrouvez le corrigé Algorithmiques avancées 2003 sur Bankexam.fr.
Voir
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é.
