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

Gaber

Description

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.

Sujets

• 2006

Informations

• Publié par: bankexam
• Publié le: 27 janvier 2008
• Nombre de lectures: 24
• Langue: Français

Extrait

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