Répondre à la discussion
Affichage des résultats 1 à 20 sur 20

En joue... Feu !



  1. #1
    danyvio

    En joue... Feu !


    ------

    Je n’ai jamais terminé la démarche infernale du problème suivant, que j’avais relevé il y a … longtemps… :

    Le peloton d’exécution est composé de N soldats alignés face au mur, et d’un capitaine.
    Le capitaine est placé à gauche du soldat le plus à gauche de la ligne.
    A un certain moment, le capitaine donne l’ordre de feu. Alors l’information se transmet de proche en proche jusqu’au moment où l’ordre de feu est exécuté.

    Pour cela, chaque soldat est affecté d’un code d’état. Ce code état va de « REPOS » (l’état initial, à « FEU », en passant par un certain nombre d’états intermédiaires.

    Le capitaine a deux états : « REPOS » et « FEU ». La différence avec les soldats est que c’est lui-même qui prend l’initiative de passer de REPOS à FEU.

    L’état de tous les soldats est évalué simultanément à chaque cycle de calcul.

    Le changement d’état d’un soldat ne dépend que de trois paramètres :
    • son propre état,
    • l’état de son voisin de gauche (qui est un autre soldat ou le capitaine pour le soldat le plus à gauche)
    • l’état de son voisin de droite(ou l’absence de soldat pour le soldat le plus à droite).

    Autres contraintes rigolotes :

    Les soldats ne savent pas compter, et chaque soldat ignore d’ailleurs la composition du peloton.

    Les soldats sont identiques et parfaitement interchangeables avant la mise en place du peloton.
    Le passage à l’état « FEU » doit être simultané pour tous les soldats.

    La question infernale : combien faut-il prévoir, au minimum, d’états en fonction de N ?

    Avec un, deux ou trois soldats on arrive facilement à écrire les tables de changement d’états. Au-delà ça se complique…. A vous de jouer !!

    -----
    On trouve des chercheurs qui cherchent ; on cherche des chercheurs qui trouvent !

  2. Publicité
  3. #2
    CoucouHibou

    Re : En joue... Feu !

    Salut,

    Je vois un algorithme avec N+1 états, où les N soldats font feu tous en même temps au bout de N étapes après que le capitaine est passé à l'état feu, mais je suppose qu'on peut faire mieux :

     Cliquez pour afficher


    C'est du vite fait, je me trompe probablement, mais c'est tout ce que je vois et je trouve dommage que ce joli problème reste sans réponse... C'est chouette les problèmes d'informatique fondamentale . Merci et à bientôt, cordialement,

    Hibou

  4. #3
    invite986312212
    Invité

    Re : En joue... Feu !

     Cliquez pour afficher

  5. #4
    Médiat

    Re : En joue... Feu !

    Citation Envoyé par ambrosio Voir le message
     Cliquez pour afficher
    Marche pas
    Si j'ai bien compris ta solution, une fois les 1 propagés sur la droite on obtient : 1111111....1112 puis 1111111....1122 puis 1111111....1223, et le soldat le plus à droite est le seul à faire feu
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  6. A voir en vidéo sur Futura
  7. #5
    Médiat

    Re : En joue... Feu !

    Solution qui nécessite des soldats sachant compter ce qui est contraire à l'énoncé, mais cela peut, peut-être, débroussailler le problème (de plus cette solution utilise un maximum d'états)
     Cliquez pour afficher
    Et là ils font feu tous ensemble (berk !)
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  8. #6
    danyvio

    Re : En joue... Feu !

    Citation Envoyé par Médiat Voir le message
    Solution qui nécessite des soldats sachant compter ce qui est contraire à l'énoncé, mais cela peut, peut-être, débroussailler le problème (de plus cette solution utilise un maximum d'états)
     Cliquez pour afficher
    Et là ils font feu tous ensemble (berk !)
    Apparemment, ça ne marche pas avec 2 soldats ni même avec un seul
    On trouve des chercheurs qui cherchent ; on cherche des chercheurs qui trouvent !

  9. Publicité
  10. #7
    Médiat

    Re : En joue... Feu !

    Citation Envoyé par danyvio Voir le message
    Apparemment, ça ne marche pas avec 2 soldats ni même avec un seul
    Il est vrai qu'avec un seul soldat il y a conflit entre deux règles, il faudrait donc préciser ce cas.
    Mais pour deux soldats, voilà ce que cela donne
     Cliquez pour afficher
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  11. #8
    danyvio

    Re : En joue... Feu !

    Citation Envoyé par Médiat Voir le message
    Il est vrai qu'avec un seul soldat il y a conflit entre deux règles, il faudrait donc préciser ce cas.
    Mais pour deux soldats, voilà ce que cela donne
     Cliquez pour afficher
    Pour 2 soldats : OK.
    Maintenant, le problème initial était : quel est le nombre minimal d'états, autrement dit, existe t-il des solutions plus complexes en termes de diagrammes, mais avec moins de variables ? Je précise que je n'ai pas la solution.... Mais ton approche est très sympa !
    On trouve des chercheurs qui cherchent ; on cherche des chercheurs qui trouvent !

  12. #9
    invite986312212
    Invité

    Re : En joue... Feu !

    en y repensant avant de m'endormir j'ai compris que ma solution était fausse (il y a plus intéresant à faire au lit que penser aux énigmes de fs, mais bon, au moins je n'ai pas rêvé qu'on me fusillait). J'ai trouvé une autre solution, que je ne détaille pas, mais il faut beaucoup d'états puisque quelqu'un (le capitaine) doit compter les soldats. Comme le nombre de soldats est indéterminé, il doit avoir une mémoire de taille infinie et ça n'est pas très réaliste.

  13. #10
    yat

    Re : En joue... Feu !

    Citation Envoyé par danyvio Voir le message
    Pour 2 soldats : OK.
    Maintenant, le problème initial était : quel est le nombre minimal d'états, autrement dit, existe t-il des solutions plus complexes en termes de diagrammes, mais avec moins de variables ? Je précise que je n'ai pas la solution.... Mais ton approche est très sympa !
    Si le but est d'avoir moins de variables (donc d'états différents, je suppose), alors j'ai une meilleure solution, en N+2 états :
     Cliquez pour afficher

  14. #11
    CoucouHibou

    Re : En joue... Feu !

    Bonjour,

    après avoir regardé à tête plus reposée, je crois que ma solution n'est pas si mauvaise, mais par contre je me pose la question : qu'entends-tu par la contrainte « les soldats ne savent pas compter » ?

    Parce que là, on numérote ce que l'on définit comme états, mais on pourrait très bien imaginer que ces états sont des postures ou des paroles dites, des gestes etc... et alors plus besoin pour le soldat de savoir compter, mais de savoir faire ce qu'il faut quand il faut (normal pour un soldat non ?).

    Cordialement,

    Hibou

  15. #12
    yat

    Re : En joue... Feu !

    L'énoncé dit "Les soldats ne savent pas compter, et chaque soldat ignore d’ailleurs la composition du peloton.".

    Pour moi ça veut dire que les soldats ne savent pas combien ils sont dans le peloton. Si c'est le cas, ta solution ne convient pas, et quoi qu'il arrive, il faut que l'information fasse un aller-retour, ce qui élimine toute solution de l'ordre de N étapes.

  16. Publicité
  17. #13
    CoucouHibou

    Re : En joue... Feu !

    Pour moi ça veut dire que les soldats ne savent pas combien ils sont dans le peloton. Si c'est le cas, ta solution ne convient pas, et quoi qu'il arrive, il faut que l'information fasse un aller-retour, ce qui élimine toute solution de l'ordre de N étapes.
    Dans la solution que je propose, chaque soldat ne fait attention qu'à lui même, et éventuellement ses voisins. Donc il n'a pas besoin de savoir la composition du peloton. J'ai compris l'énoncé comme étant : « comment un opérateur extérieur peut-il configurer, par p états et une série de règles de passages d'un état à l'autre, un soldat d'un peloton de N soldats identiques à lui (i.e. qui ont les mêmes ordres) pour que tout le peloton arrive dans le même état à un moment donné ». Je ne compte pas le capitaine dans le peloton, alors c'est peut-être là que je me trompe, mais bon... Prenons un exemple avec 5 soldats.

     Cliquez pour afficher


    On arrive bien à tout le monde à FEU pour l'étape 5, de tels soldats ne savent pas forcément compter, ne connaissent pas forcément la composition du peloton, et sont interchangeables non ?

    Cordialement,

    Hibou

  18. #14
    Médiat

    Re : En joue... Feu !

    CoucouHibou >> si j'applique ta règle avec 6 soldats et non 5, les 5 premiers sont à FEU alors que le dernier est à R.

    La difficulté vient de ce qu'il faut une règle qui marche quel que soit le nombre de soldats (d'où l'aller-retour évoqué par yat).
    Sinon, pour 5 soldats il existe une solution avec 2 états supplémentaires et non 4.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  19. #15
    yat

    Re : En joue... Feu !

    Citation Envoyé par CoucouHibou Voir le message
    Dans la solution que je propose, chaque soldat ne fait attention qu'à lui même, et éventuellement ses voisins. Donc il n'a pas besoin de savoir la composition du peloton.
    Si : il a besoin de savoir le nombre de shadoks du peloton. Ou plus précisément, l'automate qu'il doit suivre est construit en fonction du nombre de soldats. On ne peut donc pas prendre les soldats d'un peloton de 5 et les mettre dans un peloton de 10 et leur faire appliquer le même algorithme. Ca ne marchera pas : les 5 premiers vont tirer à la cinquième étape, alors que les deux autres seront encore au repos.

    Edit : croisement avec Médiat

  20. #16
    CoucouHibou

    Re : En joue... Feu !

    Citation Envoyé par Médiat Voir le message
    La difficulté vient de ce qu'il faut une règle qui marche quel que soit le nombre de soldats.
    Ce n'est pas clairement spécifié dans l'énoncé donné par danyvio ! Enfin, après recherche, j'ai en effet vu qu'il faut prendre cela en compte dans le problème du firing squad.

    Mais bon, je crois que la réponse n'est pas triviale, jugez plutôt :

    http://mathworld.wolfram.com/FiringSquadProblem.html

    Résultat : 2n+1 étapes et 6 états... Un programme en COQ ici : http://coq.inria.fr/contribs/firing-squad.html

    Bonne fin de soirée, cordialement,

    Hibou

  21. #17
    yat

    Re : En joue... Feu !

    Citation Envoyé par CoucouHibou Voir le message
    Ce n'est pas clairement spécifié dans l'énoncé donné par danyvio
    Mais si ! "Les soldats ne savent pas compter, et chaque soldat ignore d’ailleurs la composition du peloton."...

    Si les soldats ne savent pas combien ils sont dans le peloton, l'automate doit pouvoir se passer de cette information...
    Citation Envoyé par CoucouHibou Voir le message
    Mais bon, je crois que la réponse n'est pas triviale, jugez plutôt :

    http://mathworld.wolfram.com/FiringSquadProblem.html

    Résultat : 2n+1 étapes et 6 états... Un programme en COQ ici : http://coq.inria.fr/contribs/firing-squad.html
    Voilà qui donne une toute autre dimension au problème Et de quoi cogiter encore pendant un petit moment.

  22. #18
    CoucouHibou

    Re : En joue... Feu !

    Bonjour,

    Une autre solution, assez jolie graphiquement mais moins performante :

    http://www.cs.hmc.edu/~hadas/firing_squad/continue.html

    23 états, 3n étapes.

    La solution de Mazoyer est peut-être la solution optimale puisqu'elle est en 2n étapes (aller-retour du signal) et qu'il a aussi démontré que c'était impossible de trouver une solution avec 4 états.

    Allez, qui trouve une solution intermédiaire entre les 23 états et les 6 états ? Voire en 5 ? (Mais là je suppose qu'il y a un papier à la clef, et que dans ce cas, la solution ne sera pas exposée ici avant sa parution )

    Cordialement,

    Hibou

  23. Publicité
  24. #19
    yat

    Re : En joue... Feu !

    Cette solution en 3n étapes a au moins le mérite d'être très facile à comprendre... parce que pour l'instant, la solution en 2n étapes avec 6 états, en ce qui me concerne...

  25. #20
    polo974

    Re : En joue... Feu !

    Citation Envoyé par danyvio Voir le message
    ...
    Autres contraintes rigolotes :
    Les soldats ne savent pas compter
    ...
    Compter, c'est quoi?
    • lister une suite d'états successifs 1, 2, 3, 4, ... ou A, B, C, ...
    • ou bien passer de n à n+1 avec une notion de quantité associée

    Si c'est la première hypothèse, il n'y a pas de solution car savoir passer de l'état A à B est indispensable à n'importe quelle machine à état.

    Si c'est la seconde hypothèse, la solution de Médiat est acceptable, et de toute façon, la quantité importe peu.

Discussions similaires

  1. [Brun] Lecteur cassette joue trop vite
    Par omalie dans le forum Dépannage
    Réponses: 12
    Dernier message: 14/10/2007, 19h33
  2. Quel rôle joue l EDTA en ionimétrie?
    Par misou14 dans le forum Chimie
    Réponses: 3
    Dernier message: 22/03/2005, 15h27
  3. proc a 100% quand je joue.
    Par Sauron dans le forum Matériel - Hardware
    Réponses: 11
    Dernier message: 05/02/2005, 23h29
  4. Combattre le feu avec le feu ;-)
    Par [RV] dans le forum Internet - Réseau - Sécurité générale
    Réponses: 1
    Dernier message: 26/08/2003, 03h30