Algorithmiques avancées 2006 Génie Informatique Université de Technologie de Belfort Montbéliard
2
pages
Français
Documents
2008
Cet ouvrage peut être téléchargé gratuitement
2
pages
Français
Documents
2008
Cet ouvrage peut être téléchargé gratuitement
Examen du Supérieur Université de Technologie de Belfort Montbéliard. Sujet de Algorithmiques avancées 2006. Retrouvez le corrigé Algorithmiques avancées 2006 sur Bankexam.fr.
Voir
AG51 17 janvier 07 Documents non autorisés
Exercice 1 Nous avons vu en cours que le coût d’un algorithme est défini en fonction de la taille des données en entrée. a) Dans les textes algorithmiques modernes, parmi les notations utilisées pour exprimer ces coûts, on trouve principalement les notations O( ),q( ),W( ). Donnez les définitions respectives de ces notations. b) Nous avons vu que le coût d’un algorithme peut être constant, linéaire, logarithmique, polynomiale (quadratique, cubique, ….) ou encore exponentiel. Donner des exemples pour chacun de ces cas.
Exercice 2 a) Donnez les temps d’exécution nécessairesaux opérations suivantes avec les trois techniques de stockage :
Opération Rechercher Insérer Supprimer
Tableau Linéaire
Table de Avec chaînage
Hachage Adressage ouvert
b) Donner le principe du fonctionnement du hachage avec la méthode de l’adressage ouvert
c) Donner le principe du fonctionnement du hachage avec la méthode du chaînage.
Exercice 3 Donner les temps d’exécution des opérations suivantes supportées par les trois structures de données respectives :
Opération Minimum ExtraireMin Insérer Supprimer Union
Tas Binaire
Tas Binomial
Tas de Fibonacci
Exercice 4 La construction d’un arbre couvrant permet de répondre de façon adéquate à plusieurs problématiques des communications dans les réseaux.
1
Donnez un algorithme de construction d’un arbre couvrant pour un graphe G=(S,A) ainsi que son coût.
Exercice 5 Donner l’algorithme de calcul des composantes connexes en utilisant les opérations supportées par les structures de données pour ensembles disjoints.
Bon courage !
2
