[Résolu] Graphes orientés & Fermetures relations

Aide à la résolution d'exercices ou de problèmes de niveau Supérieur.

Modérateur: gdm_aidesco

Règles du forum
Merci d'éviter le style SMS dans vos messages et de penser à utiliser la fonction Recherche avant de poster un message. Pour joindre des fichiers à vos messages, consulter ce sujet.
> Penser à utiliser le mode LaTeX (voir ici) afin de rendre vos formules plus lisibles.
> Ne poster qu'un exercice (ou problème) par sujet et indiquer son niveau précis dans le titre du message.

[Résolu] Graphes orientés & Fermetures relations

Messagepar stephanie » Mardi 02 Décembre 2014, 13:59

Bonjour à tous,

J’essaye de représenter un modèle de mémoire (informatique) sous forme de graphes orientés. Chaque nœud du graphe représente un accès à la mémoire et les contraintes imposées par le modèle de mémoire se traduisent par des relations entre les nœuds (arcs sur le graphe). J’ai trouvé un excellent papier qui formalise ce problème (http://diy.inria.fr/herd/herding-cats-bw.pdf), cependant j’éprouve quelques difficultés de compréhension sur certaines notions mathématiques. Toute explication serait la bienvenue, voici un aperçu de la formalisation proposée :

On considère 8 types "primitifs" de relations entre les nœuds du graphe :
  • « po »
  • « ppo »
  • « bar »
  • « rf » différenciée en « rfi » (interne) et « rfe » (externe)
  • « co »
  • « fr » différenciée en « fri » (interne) et « fre » (externe)

On définit les notations suivantes :
  • $(Relation\ 1) \cup (Relation\ 2)$ : «union » des relations 1 et 2.
  • $Relation^*$: fermeture réflexive et transitive de la relation.
  • $(Relation\ 1); (Relation\ 2)$: composition séquentielle des relations 1 et 2.

Un graphe orienté est conforme au modèle mémoire s’il vérifie les contraintes suivantes :
  1. $acyclic(po\ \cup\ com)$
    avec $com = co\ \cup\ rf\ \cup\ fr$
    et $fr\ =\ {(r,w1)\ |\ \exists\ w0.(w0,\ r)\ \in\ rf\ \wedge\ (w0,\ w1)\ \in\ co}$
  2. $acyclic(hb)$
    avec $hb\ =\ ppo\ \cup\ bar\ \cup\ rfe$
  3. $irreflexive(fre;\ prop;\ hb^*)$
    avec $A-cumul\ =\ rfe;\ bar$
    et $prop-base\ =\ (bar\ \cup\ A−cumul);\ hb^∗$
    et $prop\ =\ (prop-base)\ \cup\ (com^*;\ prop-base^*;\ bar;\ hb^*)$
  4. $acyclic(co\ \cup\ prop)$

Je pense avoir compris le sens des contraintes 1, 2 et 4 mais je bloque sur la contrainte 3 :
  • La contrainte « $irreflexive(fre;\ prop;\ hb^*)$ » se traduit-elle en réalité par l’absence de cycles impliquant des relations du type « $fre$ » puis « $prop$ » puis « $hb^*$ » ? Dois-je tenir compte d’un ordre entre les relations (« $fre$ » puis «$ prop$ » puis « $hb^*$ ») ? Une explication de la notion de fermeture transitive et réflexive d'une relation serait la bienvenue.
  • Comment se traduit graphiquement cette contrainte d'irréflexivité ?
  • Quelle est la différence « graphiquement » entre $hb$ et $hb^*$ ?

Voici deux exemples de graphes illustrant le problème. Les numéros des nœuds ne représentent aucune information particulière (il fallait juste leur donner un nom).
Exemple 1:
http://hpics.li/ef9d9a7

Je sais que l'exemple 1 ne respecte pas le modèle de mémoire. Si je comprends bien, il viole la contrainte 3 (cf. chemin en jaune formant un cycle):
http://hpics.li/856acae

Exemple 2: même graphe que pour l’exemple 1 mais les deux relations « bar » entre les nœuds 3, 4 et 5 sont remplacées par deux relations « ppo ». En voyant ce graphe et les contraintes, j’ai envie de dire qu’on peut tracer le même chemin jaune que pour l’exemple 1 cependant je sais que cela est faux car ce scenario respecte le modèle mémoire. Quelqu’un a une explication ?
http://hpics.li/881b75e

Merci d’avance à ceux qui auront eu le courage de lire jusqu’au bout :)
Dernière édition par stephanie le Lundi 08 Décembre 2014, 09:42, édité 1 fois.
stephanie
Méga-utilisateur
 
Messages: 295
Inscription: Dimanche 09 Septembre 2007, 20:00
Statut actuel: Post-bac | CPGE

Publicité

Re: Graphes orientés & Fermetures relations

Messagepar stephanie » Lundi 08 Décembre 2014, 09:41

Bonjour à tous,

Pour information, je pense avoir compris pourquoi un cas est valide et l'autre non.
$com^*;\ prop-base^*;\ bar;\ hb^*$ implique que l'on ait une relation du type $com^*$ suivie de $prop-base^*$ suivie de $bar$ et enfin suivie de $hb^*$ sachant que le ";" signifie la composition séquentielle. Cela signifie que si le graphe ne comporte pas de relation du type "bar", il n'existe aucune relation qui puisse vérifier la propriété $com^*;\ prop-base^*;\ bar;\ hb^*$ . Cela explique mon problème.
stephanie
Méga-utilisateur
 
Messages: 295
Inscription: Dimanche 09 Septembre 2007, 20:00
Statut actuel: Post-bac | CPGE


Retourner vers Exercices et problèmes : Supérieur

 


  • Articles en relation
    Réponses
    Vus
    Dernier message

Qui est en ligne

Utilisateurs parcourant ce forum: Google [Bot] et 3 invités