Algorithmiques avancées 2005 Génie Informatique Université de Technologie de Belfort Montbéliard

De
Publié par

Examen du Supérieur Université de Technologie de Belfort Montbéliard. Sujet de Algorithmiques avancées 2005. Retrouvez le corrigé Algorithmiques avancées 2005 sur Bankexam.fr.
Publié le : vendredi 15 août 2008
Lecture(s) : 86
Tags :
Nombre de pages : 2
Voir plus Voir moins
AG51
18 janvier 05
Documents non autorisés
Exercice 1
La conception des algorithmes est basée sur l’utilisation de plusieurs concepts. Donnez ces concepts
en détaillant leurs fonctionnements.
Exercice 2
Nous avons vu en cours que le coût d’un algorithme en fonction de la taille des données en entrée peut
être constant, linéaire, logarithmique, polynomiale (quadratique, cubique, ….) ou encore exponentiel.
Donner des exemples pour chacun de ces cas.
Exercice 3
Donner les temps d’exécution des opérations pour les trois techniques de stockage :
Opération
Tableau Linéaire
Table de Hachage
Avec chaînage
Adressage ouvert
Rechercher
Insérer
Supprimer
Exercice 4
Donner les temps d’exécution des opérations suivantes supportées par les trois structures de données
respectives :
Opération
Tas Binaire
Tas Binomial
Tas de Fibonacci
Minimum
ExtraireMin
Insérer
Supprimer
Union
Exercice 5
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 5-1
: Donnez l’exemple d’un arbre 2-3.
Question 5-2
: Donnez les coûts respectifs des opérations suivantes :
ƒ
Recherche d’une clé
ƒ
Insertion d’une clé
ƒ
Suppression d’une clé.
1
2
Exercice 6
L’
arbre de priorité équilibré
(APE) intervient dans les problèmes de files d’attente avec priorité 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 un arbre de priorité équilibré s’il vérifie 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,
-
si
g
et
d
désignent les branches gauches et droite issues de
n
alors
N(g)-1 <= N(d) <= N(g)-1
.
On note par
N(x)
, le nombre de noeuds de l’arbre de racine
x
.
Par convention, un arbre vide est un
APE.
Question 6-1
: Donnez l’APE correspondant à l’insertion successives des tâches suivantes : 5 , 4, 1, 3,
2, 0. Les valeurs désignent le niveau de priorité.
Question 6-2
: Donnez la complexité 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’un APE avec
les tâches restantes.
Bon courage !
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.