UTBM algorithmiques avancees 2005 gi ag51 genie informatique semestre 1 final

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

Informations

• Publié par: shura
• Nombre de lectures: 139
• Langue: Français

Extrait

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