Cette publication est accessible gratuitement
Lire

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

De
1 page
Examen du Supérieur Université de Technologie de Belfort Montbéliard. Sujet de Algorithmiques avancées 2004. Retrouvez le corrigé Algorithmiques avancées 2004 sur Bankexam.fr.
Voir plus Voir moins
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
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin