Codes identifiants d’un graphe et ses applications

Comment appliquer ces algorithmes a des problèmes ?

Maintenant que l'on a pu voir deux algorithmes nous permettant de trouver des "sommets à problèmes", nous allons voir comment l'appliquer à des exemples de la vie réelle.

Cela prend en compte la modélisation d'un problème abstrait et la définition d'un code identifiant permettant de résoudre le problème de façon de optimale.

Processeurs défectueux dans un réseaux multiprocesseurs.

  • Qu'est-ce que c'est ?

    Un réseau de multiprocesseurs est un réseau de processeurs réliés entre eux qui nous permet de paralléliser par exemple les calculs d'un logiciel sur plusieurs processeurs pour avoir un temps de traitement plus rapide
  • Modélisation sous forme d'un graphe

    On peut imaginer un ensemble de processeurs reliés entre eux, chacun pouvant vérifier si ces voisins sont déféctueux ou non.

    Nous pouvons alors générer un graphe ou chaque sommet représenterait un processeur et les arêtes permettant de determiner si un processeur est voisin d'un autre.

    Un procésseur p sera dans la possibilité de tester si un de ces voisins est défectueux.
Exemple d'un graphe pour un réseaux multiprocesseurs
  • Comment les codes ID peuvent-ils résoudre le problème ?

    Pour trouver un code identifiant C d'un tel graphe qui nous permettra de résoudre le problème, il faut :
    - Si un des processeurs prévient qu'il est défectueux, alors on doit être capable de le localiser de manière unique (En vérifiant que les sommets de C trouve bien un disfonctionement en l'analysant)
    - Si il n'y a pas de problème, chaque sommet ne renverra pas d'erreur.

    Grâce à cela, nous sommes capables d'interroger les sommets C et ses voisins pour déterminer si un processeur est défectueux efficacement.

"Qui est-ce ?", le jeu

  • Qu'est-ce que c'est ?

    "Qui est-ce ?" est un jeu de société se jouant à deux joueurs. Chaque joueur a un plateau avec une liste de portraits de personnages. Ils ont également à chaque partie un personnage secret que l'autre joueur devra deviner en lui posant des questions dichotomiques (pouvant seulement être répondues par "oui" ou "non") sur le physique telles que : "Est-ce que ton personnage mystère est roux ?", "Est-ce qu'il a des lunettes ?". Evidemment, les joueurs ne devront pas mentir !
  • Modélisation sous forme d'un graphe

    Nous sommes dans un cas de figure proche du problème des alarmes incendie. Or, dans ce dernier cas, nous interrogions les sommets sur la détection d'incendie et cela faisait donc partie intégrante du code.
    Pour le jeu "Qui est-ce ?", cela va être différent puisque lorsqu'un joueur va poser une question comme "est-ce que le personnage mystère a un chapeau ?", le code devra s'intéresser aux personnages portant un chapeau ou non. Le chapeau n'étant pas un personnage, cela risque de compliquer le parcours si nous restons sur le même modèle que les alarmes incendie.
    La façon la plus simple de modéliser le jeu est donc de faire un graphe avec d'un côté les sommets représentant les catégories (femme, homme, blond, moustache, etc...) et de l'autre les sommets représentant les différents personnages.
    Par exemple nous aurions quelque chose ressemblant à cela :
Exemple de graphe pour le "Qui est-ce ?"
  • Comment les codes ID peuvent-ils résoudre le problème ?

    Nous avons les caractéristiques qui séparent les personnes. En séparant notre graphe comme ci-dessus, nous préservons ce paramètre, chaque sommet est donc unique.
    Chaque sommet étant unique, nous avons un code identifiant et cela devient très facile de retrouver la personne mystère.
11 Cliquer pour recommander cet article