UTBM algorithmiques avancees 2007 gi ag51 genie informatique semestre 2 final

Informations

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

Extrait

Algorithmique Avancée

24 Mai 07

Documents non autorisés

Exercice 1

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.

Donnez un algorithme de construction d’un arbre couvrant pour un graphe G=(S,A).

Exercice 5

Exercice 4

Les algorithmes de parcours sont à la base de nombreux algorithmes importants sur les

graphes. Donnez un algorithme de parcours d’un graphe G=(S,A).

Exercice 5

L’algorithme le plus connu permettant de résoudre le problème de la recherche d’un plus court chemin

à origine unique pour un graphe orienté pondéré est l’algorithme de Dijkstra.

a)

Donnez le principe de cet algorithme

b)

Donnez le texte de l’algorithme

Bon courage !

1