UTBM algorithmiques avancees 2003 gi ag51 genie informatique semestre 1 final

Description

ƒƒƒƒƒƒExamen de l’U.V. AG51 Sans documents 24/01/2003 J.Gaber ([e-mail]) 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 ...

Informations

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

Extrait

Examen de l’U.V. AG51

Sans documents

24/01/2003

J.Gaber ([e-mail])

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