UTBM algorithmiques avancees 2004 gi ag51 genie informatique semestre 1 final

Informations

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

Extrait

AG51

22 janvier 04

Documents non autorisés

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 2

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 3

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 4

La conception des algorithmes est basée sur l’utilisation de plusieurs concepts. Donnez ces

concepts en détaillant leurs fonctionnements.

Exercice 5

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.

Bon courage !

1