[PDF] [PDF] SUJET + CORRIGE

Exercice 1: Automates de recherche de motifs Exercice 2: Parcours en profondeur de graphes Exercice 4: Variantes plus court chemin à origine unique



Previous PDF Next PDF





[PDF] Résolution de problèmes de plus court chemin/exercices/corrigé/p1

Résolution des problèmes de plus court chemin – exercices- corrigé I Le graphe qui permet de modéliser ce problème est analogue à celui vu dans le cours



[PDF] Le problème du plus court chemin : exercices- corrigé - AUNEGE

Le problème du plus court chemin /exercices/corrigé/p1 Le problème du plus court chemin : exercices- corrigé I 0 0 1 0 2 0 3 0 4 0 1 2 1 1 2 2 2 1 3 2 3 1



[PDF] TD9 : plus court chemin dans un graphe

Exercice 1 Un graphe orienté pondéré G est donné par la matrice d'incidence sui- vante, o`u les sommets du graphe sont s, a, b, c, d et t et o`u il existe une 



[PDF] Corrigé TD N° 2

Le graphe de l'exercice est planaire car on peut le représenter de la façon suivante : C un problème de plus courts chemins d'un sommet vers tous les autres, 



[PDF] SUJET + CORRIGE

Exercice 1: Automates de recherche de motifs Exercice 2: Parcours en profondeur de graphes Exercice 4: Variantes plus court chemin à origine unique



[PDF] TD dalgorithmique avancée Corrigé du TD 11 : Plus courts chemins

Corrigé du TD 11 : Plus courts chemins pour tout couple de sommets (la récursion portera ici sur le nombre d'arcs d'un plus court chemin) Pour m = 0 il existe 



[PDF] Exercices “Plus courts chemins” : Correction - Educnet

Exercices “Plus courts chemins” : Correction 19 octobre 2016 1 2 3 Il suffit d' appliquer la fonction log sur les poids 4 L'algorithme reste le même, mais on met 



[PDF] GRAPHES - EXERCICES CORRIGES Compilation réalisée à partir

Le nombre chromatique de ce graphe est donc égal à 4 4) On utilise l'algorithme du plus court chemin de Dijkstra pour déterminer une chaîne qui minimise la 



[PDF] AMD5 TD no 6 : Algorithmes de plus courts chemins II - IRIF

TD no 6 : Algorithmes de plus courts chemins II Exercice 1 : Dijkstra vs Bellmann Ford 1 Ecrire l'un à côté de l'autre les deux algorithmes de Bellmann-Ford et 



[PDF] TD 5 Plus courts chemins - LIRMM

Utiliser l'algo de Dijkstra pour calculer une arborescence des plus courts chemins issue de a 2 La longueur de l'arc ge est en fait -8 Refaire la question 

[PDF] exercice corrigé pompe ? chaleur

[PDF] exercice corrigé portique isostatique

[PDF] exercice corrigé préparation d'une solution tampon

[PDF] exercice corrigé probabilité jeu de 32 cartes

[PDF] exercice corrigé probabilité licence 2

[PDF] exercice corrigé probabilité loi normale

[PDF] exercice corrigé probabilité stmg

[PDF] exercice corrigé probabilité variable aléatoire continue

[PDF] exercice corrigé propagation des ondes electromagnetique

[PDF] exercice corrigé pythagore

[PDF] exercice corrigé radar

[PDF] exercice corrigé raisonnement par récurrence terminale s pdf

[PDF] exercice corrigé rdm portique

[PDF] exercice corrigé recherche opérationnelle pdf

[PDF] exercice corrigé recherche opérationnelle simplexe

Master BioInformatiqueAnnée :2011/2012Session de avril 2012

PARCOURS :Master 1

UE J1BS8203 :Méthodes et outils pour la biologie des systèmes

Épreuve :Examen

Date :Mardi 10 avril 2012

Heure :10 heures

Durée :2 heures

Documents : autorisés

Épreuve de M. AlainGriffaultSUJET + CORRIGE

Avertissement

La plupart des questions son tindé-

pendantes.

L"espace laissé p ourles rép onsesest

suffisant (sauf si vous utilisez ces feuilles comme brouillon, ce qui est fortement déconseillé).QuestionPointsScore

Automates de recherche de motifs4

Parcours en profondeur de graphes4

Graphes pondérés4

Variantes plus court chemin à origine unique8

Total:20

Exercice 1: Automates de recherche de motifs (4 points) (a) (2 p oints)P ourles mots sur l"alphab et =fa;bg, dessinez l"automate de recherche du motifaabab.

Solution:012345ab

a bba abb ab a

Figure1 - Recherche deaabab(b)(2 p oints)On dit d"un motif Pqu"il estnon recouvrablesi(PkwPq))(k= 0^k=q), c"est à dire

que si leskpremières lettres du motif forment un suffixe desqpremières lettres de ce même motif,

alors soitk= 0, soitk=q. Donnez la particularité de l"automate d"un motif non recouvrable.

Solution:Toutes les arcsretourreviennent à l"état initial.Exercice 2: Parcours en profondeur de graphes (4 points)

Donnez un graphe orienté G tel qu"il existe deux sommetsuetvvérifiant : -u;v -u:debut < v:debut -vn"est pas un descendant deudans la foret en profondeur obtenue lors du parcours en profondeur.

Solution:suv

Figure2 - Parcours en profondeur dans l"ordre(s;u;v) UE J1BS8203 : Méthodes et outils pour la biologie des systèmes Session 1, Année 2011/2012

Exercice 3: Graphes pondérés (4 points)

Vous admettrez la propriété suivante :

Propriété 1SoitG(S;A;w)un graphe non orienté pondéré avecw:A!N. SoientTAetT0Adeux

arbres couvrants de poids minimal. SoientLT= (a0;:::;an)etLT0= (a00;:::;a0n)les listes triées par poids

croissant des arêtes deTetT0. Alors :8i2[0::n];w(ai) =w(a0i). Informellement, la liste ordonnée des poids

des arêtes constituant un arbre couvrant est unique.

SoitG(S;A;w)un graphe non orienté pondéré. Montrer que pour chaque arbre couvrant de poids minimal

TdeG, il existe un moyen pour que l"algorithme de Kruskal retourne comme résultatT. Solution:SoitG(S;A;w)un graphe non orienté pondéré avecw:A!N. SoitTAun arbre

couvrant de poids minimal. SoitLT= (a0;:::;an)la liste triée par poids croissant des arêtes deT.

SoitLATla liste triée par poids croissant des arêtes deAT. SoitLla liste triée par poids croissant des arêtes deTobtenue par fusion des listesLTetLAT, en donnant priorité aux éléments deLTen cas d"égalité.

Il suffit d"appliquer l"algorithme de Kruskal en utilisant la liste triéeL.Exercice 4: Variantes plus court chemin à origine unique (8 points)

L"algorithme de Dijkstra

I n i t i a l i s a t i o n (G, s ){ // G(S,A,w) oriente pour u dans S faire { u . d Relacher (u , v ,w){ si (v . d > u . d + w(u , v )) alors { v . d Dijkstra (G, s ){ // G(S,A,w) oriente

I n i t i a l i s a t i o n (G, s );

F Relacher (u , v ,w); vu en cours calcule : P ourc haquesommet u, la distanced(s;u)deuà la racines. E : Une arb orescencedes plus courts c heminsissus de s.

Page 2 sur 4

UE J1BS8203 : Méthodes et outils pour la biologie des systèmes Session 1, Année 2011/2012

SoitG(S;A;w)un graphe orienté pondéréacyclique. Il est alors possible d"améliorer l"algorithme de Dijkstra

pour calculer une arborescence des plus courts chemins. Dijkstraacyclique (G){ // G(S,A,w) oriente acyclique L I n i t i a l i s a t i o n (G, Tete(L )); tant que (L != n i l ) faire { u L pour v element de u . adjacents faire {

Relacher (u , v ,w);

(a) (2 p oints)Donnez le résultat ( u.detu.perepour chaque sommet) de l"algorithmeDijkstra-acyclique sur le graphe suivant.0123455 326
7 4 212
2 Figure3 - Un graphe orienté pondéré acycliquesommet012345 u.d0531075 u.perenil00222 (b) (2 p oints)Donnez la complexité de l"algorithme Dijkstra-acyclique.

Solution:

La complexité du tri top ologiqueest (jSj+jAj)(vu en cours). La complexité de l"initialisation est (jSj)(une boucle pour).

Le nom brede passage dans le tant queestjSj.

Le nom brede passage dans la b ouclein ternepourestjAj.

La complexité totale est donc :(jSj+jAj).Une variante de cet algorithme est utilisable pour calculer les chemins critiques dans un grapheG(S;A;w)

lorsque : Les arcs représen tentles tâc hesà faire. Les p ondérationsrep résententle temps nécessaire p oureffectuer la tâc he.

les arcs a1= (u;v)eta2= (v;w)représentent deux tâches qui doivent être effectuées dans l"ordrea1;a2.

Unchemin critiqueest unplus longchemin dans le graphe, qui correspond au temps maximum requis pour

effectuer une séquence ordonnée de tâches. Le poids d"un chemin critique est une borne inférieure du temps

total nécessaire à l"exécution de toutes les tâches. (c)

(2 p oints)A daptezles algorithmes préc édentsp ourcalculer les c heminscritiques d"un graphe orien té

pondéré acyclique.

Solution:Deux solutions :

1.

Les distance sson tinitialisée sà 1,

InitialisationCheminCritique (G, s ){ // G(S,A,w) oriente pour u dans S faire { u . d < MAXINT; //i n f i n i u . pere RelacherCheminCritique (u , v ,w){ si (v . d < u . d + w(u , v )) alors { v . d tithme normal, puis de nouveau multiplier par1les distances obtenues.(d)(2 p oints)Donnez le résultat ( u.d,u.perepour chaque sommet et le chemin critique) de votre algo-

rithme sur le graphe suivant.0123455 326
7 4 212
2 Figure4 - Un graphe orienté pondéré acycliquesommet012345 u.d057141517 u.perenil01234

Chemin critique :(0;1;2;3;4;5)de longueur17.

Page 4 sur 4

quotesdbs_dbs11.pdfusesText_17