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

Gaga

Description

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.

Sujets

• 2003

Informations

• Publié par: bankexam
• Publié le: 15 août 2008
• Nombre de lectures: 43
• 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é.