UTBM algorithmiques avancees 2005 gi ag51 genie informatique semestre 1 final

Français
2 pages
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

ƒƒƒƒƒƒ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 ...

Sujets

Informations

Publié par
Nombre de lectures 139
Langue Français
Signaler un problème
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