IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Algorithme du parking


Sujet :

Algorithmes et structures de données

  1. #1
    Membre averti
    Homme Profil pro
    Étudiant
    Inscrit en
    Décembre 2012
    Messages
    43
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val d'Oise (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Décembre 2012
    Messages : 43
    Par défaut Algorithme du parking
    Salut a tous,

    Voila actuellement je travaille sur un algorithme je ne suis qu'au début voici un début que j'ai réaliser je voulais savoir si pour ce début cela et cohérent.

    Énonce :
    Un parking possède p portes par lesquelles des voitures peuvent entrer ou sortir. Le parking ne doit jamais contenir plus de N voitures. À chaque porte se trouve un gardien ; les gardiens communiquent en s’envoyant des messages (de façon asynchrone, par exemple à l’aide de pigeons voyageurs supposés fiables) ; ils doivent faire en sorte que la capacité du parking ne soit jamais dépassée. Il faut par ailleurs que, s’il y a régulièrement des sorties, toute voiture qui attend pour entrer par la porte de son choix y parvienne en un temps fini.

    Décrire un algorithme réparti, qui sera appliqué par chacun des gardiens, afin résoudre le problème.
    Cet algorithme utilisera des principes présentés en cours. Le nombre de messages échangés entre deux entrées de voitures devra être borné.

    Mises en gardes :

    – Une idée (incorrecte) serait de partager initialement les N places du parking en p lots de N / p places, à la responsabilité de chaque gardien. Dans ce cas le gardien peut laisser rentrer N / p voiture, plus autant de voitures qu’il a laissé sortir. Cependant, avec ce schéma si toutes les voitures sortent par la même porte, cette dernière porte devient la seule entrée possible et les voitures qui cherchent à rentrer par une autre porte y restent bloqués (ce qu’on ne veut pas).

    – Une autre idée (tout aussi incorrecte) serait d’imaginer que les gardiens tentent de garder le compte des places libres en diffusant (aux autres gardiens) des messages “entrée” ou “sortie” à chaque fois qu’une voiture entre ou sort par leur porte. Le problème est que ces diffusions ne sont pas délivrées instantanément et qu’elles peuvent aussi se croiser. Cela devient critique lorsqu’il n’y a plus beaucoup de places libres. Par exemple s’il ne reste plus qu’une place libre, deux gardiens pourraient simultanément laisser rentrer chacun une voiture.

    Réponse :
    On peut utiliser une variante des algorithmes d’exclusion mutuelle à jetons vus en cours. On stocke sur le jeton le nombre de places disponibles (en plus des informations nécessaires au protocole de d’exclusion).

    Un gardien ne peut laisser rentrer ou sortir une voiture que s’il a le jeton et qu’il peut mettre à jour le nombre de places libres.

    D’autre part si un gardien qui souhaite faire rentrer une voiture récupère un jeton indiquant qu’aucune place n’est libre, il ne fera pas rentrer la voiture et redemandera le jeton aussitôt qu’il l’aura cédé à un autre gardien.
    Algorithme:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    Variable :
    in
    auto
    parking [0…n-1]
     
    ENTRER(v)
    Debut
     
    Si(parking != vide && nbauto>0)
    Parking[in] = v
    In = (in + 1) % N
    Nbauto++
    Fin si
     
    Fin
    /*****************************/
    Variable :
    out
     
    SORTIE(v)
    Debut
     
    Fin

  2. #2
    Expert confirmé Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5 287
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5 287
    Par défaut
    Bonjour

    Les règles du forum sont claires:
    Nous ne sommes pas là pour faire vos exercices.
    (...)En aucun cas, nous ne ferons le travail à votre place.

    Merci de votre compréhension.
    Je vois bien un énoncé, mais pas de travail.
    Si tu crois que le pseudo-bout de code que tu as posté est une trace de travail, tu te trompes.

    Quelle est ta question ? (pas celle du prof)

  3. #3
    Membre Expert

    Homme Profil pro
    Développeur informatique
    Inscrit en
    Avril 2013
    Messages
    610
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Finance

    Informations forums :
    Inscription : Avril 2013
    Messages : 610
    Billets dans le blog
    21
    Par défaut
    Bon je dirais tout de même que c'est le commencement du début d'un travail

    Mais ce n'est pas un bon commencement:
    Si(parking != vide && nbauto>0)
    les deux conditions veulent dire la même chose et ce n'est pas la bonne chose. Si le parking est vide et qu'une voiture entre on ne fait rien?

    et puis...
    SORTIE(v)
    Debut

    Fin
    Si c'est une coquille vide à remplir pourquoi pas mais sinon...

    Pourquoi ne pas partir de la solution donnée dans l'énoncé? :
    On peut utiliser une variante des algorithmes d’exclusion mutuelle à jetons vus en cours. On stocke sur le jeton le nombre de places disponibles (en plus des informations nécessaires au protocole de d’exclusion).

Discussions similaires

  1. Formalisation graphique des algorithmes
    Par David R. dans le forum Algorithmes et structures de données
    Réponses: 14
    Dernier message: 08/12/2012, 10h21
  2. Algorithme de randomisation ... ( Hasard ...? )
    Par Anonymous dans le forum Assembleur
    Réponses: 8
    Dernier message: 06/09/2002, 14h25
  3. recherches des cours ou des explications sur les algorithmes
    Par Marcus2211 dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 19/05/2002, 22h18
  4. Recherche de documentation complète en algorithmes
    Par Anonymous dans le forum Algorithmes et structures de données
    Réponses: 1
    Dernier message: 29/03/2002, 12h09
  5. Algorithme génétique
    Par Stephane.P_(dis Postef) dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 15/03/2002, 17h14

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo