Algorithmiques avancées 2007 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 2007. Retrouvez le corrigé Algorithmiques avancées 2007 sur Bankexam.fr.

Sujets

• 2007

Informations

• Publié par: bankexam
• Publié le: 15 août 2008
• Nombre de lectures: 30
• 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