![](/img/vague-bas-gauche.png) |
#1 - 23-04-2012 09:50:34
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Electronique en démineur (u mad bro
Hello,
Après pas mal de mini grilles de démineur, a germé, dans mon esprit, une idée "so geek but so fun" . Cette fois-ci il s'agit de défi de construction! Et c'est exactement ce que le titre dit que c'est: on va faire de l'électronique en démineur.
Considérons l'image suivante:
![http://www.prise2tete.fr/upload/Clydevil-Clydevil-MineWire.PNG](http://www.prise2tete.fr/upload/Clydevil-Clydevil-MineWire.PNG) La première remarque que l'on va faire concerne une équivalence. Dans une vraie grille de démineur la structure du bas ne peut pas exister, car les cases libres autour devraient indiquer le nombre de mines voisines. Cependant, en tant que constructeur du problème, si on ne désire pas donner trop d'indices on peut simplement coller des mines supplémentaires, ce qui donnerait la structure du haut totalement équivalente. Dans ce probleme de construction on ne va pas s'embêter à alourdir nos constructions avec des mines inutiles, on a le droit d'écrire comme la structure du bas avec des cases vides ne donnant pas d'information.
Parlons maintenant de choses intéressantes: Si on regarde la structure du bas, filiforme, on remarque qu'elle n'est pas déterminée. En revanche si on fixe l'état de la case A (mine ou pas mine) le déterminisme se repend dans la structure et fixe l'état de la case B, précisément au même que celui de A. On peut donc interpréter A comme une entrée binaire à deux états et la structure comme un fil électrique.
Les défis: -Réaliser la porte logique "non" (mise en jambe, ca doit être trivial): c'est à dire une structure ou on a une case d'état inconnue, notre entrée, pour laquelle fixer son état implique l'état d'une certaine case, notre sortie. La sortie valant toujours l'état opposé de l'entrée (On doit pouvoir brancher un fil du genre évoqué sur entrées et sorties)
-Réaliser les portes logiques "et, ou": c'est à dire une structure ou on a deux cases d'états inconnues, nos entrées, pour lesquelles fixer leur état implique l'état d'une certaine case, notre sortie. Pour la porte logique "et" cette sortie doit valoir "mine" si et seulement si les deux entrées valent "mine". Pour la porte logique "ou" cette sortie doit valoir "mine" si et seulement si au moins une des deux entrées vaut "mine" (On doit pouvoir brancher un fil du genre évoqué sur entrées et sorties)
-Réaliser un croisement de fil. (Le plus fun)
-Subsidiaire: Toute réalisation d'autre porte logique, "xor", "ou" multi-entrées etc... est la bien venue du moment qu'elle n'est pas un assemblage des portes et ou existantes, ie des versions plus compactes donc intéressantes.
Vos composants doivent être compatibles avec n'importe quel signal en entré. (ie: avoir au moins une solution valide).
Je donnerais des mentions spéciales aux composants les plus compactes/utilisables etc...
Bonne chance!
Solution: Spoiler : [Afficher le message] Voici une compilation des portes logiques les plus utiles dans leur version la plus compacte. Remerciement spécial à w9Lyl6n et Klimrod (L'image est zoomable)
![](http://www.prise2tete.fr/upload/Clydevil-MineLogic.png) (Cliquer pour zoomer)
Chapeau à scarta qui a eut le courage de construire un additionneur 4-bit (en page 2)
Quelques mots en plus: Avec simplement les portes logiques "et", "non", et le croisement de fil on dispose de suffisamment d'outils pour construire en démineur toute fonction calculable. Vous pouvez faire un additionneur n-bit, une multiplication si ça vous chante etc...
En présentant la chose autrement, on peut aussi remarquer qu'il est possible de construire une grille de démineur dont la résolution est équivalente à la satisfaction d'une formule logique de notre choix. (probleme SAT) ce qui démontre assez élégamment la NP-Completude du problème. (et comme ce n'est pas tous les jours qu'on démontre la NP-Completude d'un truc autant le remarquer lorsqu'on le fait).
#2 - 23-04-2012 11:11:34
- godisdead
- Expert de Prise2Tete
- Enigmes résolues : 22
- Messages : 747
Electronique en démineur (u ma dbro)
Je ne suis pas sur d'avoir bien compris (je ferais de joli dessin ce soir)
NON : A1B
ET A' A2x1B
OU A' A1x1B
#3 - 23-04-2012 11:22:10
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
electronique en démineir (u mad bro)
@godisdead: Oui tu as bien compris mais au détail important que les composants doivent pouvoir accepter n'importe quoi en entrée. Ici par exemple ta porte ET n'accepte pas l'entrée A=0 A'=0. Et ta porte OU n'accepte pas l'entrée A=1 A'=1
#4 - 23-04-2012 11:56:03
- Klimrod
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 4049
- Lieu: hébesphénorotonde triangulaire
electroniqie en démineur (u mad bro)
J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.
#5 - 23-04-2012 12:33:26
- w9Lyl6n
- Professionnel de Prise2Tete
- Enigmes résolues : 26
- Messages : 220
Electronique en démnieur (u mad bro)
Super idée, de faire de l'électronique avec le démineur J'ai déjà les trois premières portes:
![http://www.prise2tete.fr/upload/w9Lyl6n-demineur_non_et_ou.PNG](http://www.prise2tete.fr/upload/w9Lyl6n-demineur_non_et_ou.PNG) Les points verts sont bien sûr les entrés, et les rouges les sorties.
La porte "NON" peut aussi servir de fils si on en connecte un nombre pair
Je continue de chercher pour la suite...
#6 - 23-04-2012 14:03:51
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Electronique enn démineur (u mad bro)
@Klimrod: Je valide la porte "NON" ainsi que la porte mixte (ET/OU). En revanche la porte ET simple en bas à gauche est indéterminée sur 0|1 et la porte ET simple en bas à droite n'accepte pas 0|0.
@w9Lyl6n: Je valide tout.
@Tout le monde: Suspense, qui trouvera le premier le défi 3, le croisement de fil. ![big_smile](img/smilies/big_smile.png)
#7 - 23-04-2012 14:15:25
- LeXav
- Habitué de Prise2Tete
- Enigmes résolues : 18
- Messages : 16
- Lieu: Somewhere in Nevada
elrctronique en démineur (u mad bro)
Hello !
Voici mes propositions pour les trois premiers problèmes :
![http://www.prise2tete.fr/upload/LeXav-GrilleV1.PNG](http://www.prise2tete.fr/upload/LeXav-GrilleV1.PNG) J'ai essayé de faire le plus compacte possible ![wink](img/smilies/wink.png)
Pour le croisement de fil, on doit pouvoir au moins faire comme ça : http://matthieu.walraet.net/automate/croisement.html
je vais chercher si on peut trouver mieux...
Xav, Le Xav
#8 - 23-04-2012 14:26:27
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Electronique en démineeur (u mad bro)
@LeXav: Je valide le OU, le ET par contre est également un "OU", et étonnamment le "NON" ne marche pas.
#9 - 23-04-2012 14:31:48
- Klimrod
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 4049
- Lieu: hébesphénorotonde triangulaire
electrobique en démineur (u mad bro)
Porte simple à gauche de mon schéma : effectivement, je m'en étais rendu compte et j'avais édité entre-temps mon schéma (tu avais l'ancien schéma dans ton cache)
Porte simple à droite de mon schéma : tu as raison, elle n'est pas correcte.
Qu'est ce que tu entends par croisement de fils ?
Klim.
J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.
#10 - 23-04-2012 14:40:10
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Elctronique en démineur (u mad bro)
Porte simple à gauche de mon schéma : effectivement, je m'en étais rendu compte et j'avais édité entre-temps mon schéma (tu avais l'ancien schéma dans ton cache)
C'est toujours le cas, et je pense que le site merdouille un peu avec ce genre de cache, j'avais déjà vu ca avec P2Tower défense -> Utiliser un autre nom d'image, même si l'autre est supposée détruite.
Qu'est ce que tu entends par croisement de fils ?
Et bien, ici on a la possibilité de faire des fils, mais si on fait se croiser cette structure fil de mon image exemple évidemment ca merde au croisement. Il faut donc concevoir un croisement qui fait en sorte que toute information sur un des fils qui se croisent n'impacte pas l'information véhiculée par l'autre fil ![big_smile](img/smilies/big_smile.png)
#11 - 23-04-2012 15:09:56
- Palin01
- Passionné de Prise2Tete
- Enigmes résolues : 39
- Messages : 70
- Lieu: Lille
Ellectronique en démineur (u mad bro)
Salut, Vraiment maline l'idée, j'aime beaucoup.
![http://img11.hostingpics.net/pics/540294Portesclydevil.jpg](http://img11.hostingpics.net/pics/540294Portesclydevil.jpg)
La porte ET peut surement être plus compacte mais bon pour l'instant ça me suffit.
Edit : Je suis en train de réfléchir sur le croisement mais c'est pas simple du tout.
En fait j'ai l'impression qu'il faudrait une sorte de test pour savoir si l'entrée est une mine ou pas pour savoir si A et B ont le même "état" parce qu'ensuite ça coule de source...
#12 - 23-04-2012 18:12:26
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,952E+3
rlectronique en démineur (u mad bro)
Sauf erreur de ma part, mais je ne trouve pas encore de truc simple pour le OU exclusif...
EDIT erreur de ma part, le 3 du bas ne fonctionne pas. ![sad](img/smilies/sad.png)
![http://www.prise2tete.fr/upload/gwen27-demineurbooleen.jpg](http://www.prise2tete.fr/upload/gwen27-demineurbooleen.jpg)
#13 - 23-04-2012 18:41:25
- Klimrod
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 4049
- Lieu: hébesphénorotonde triangulaire
Electroniquue en démineur (u mad bro)
J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.
#14 - 23-04-2012 20:16:21
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
electronique zn démineur (u mad bro)
@Palin01: Je valide les 3 portes NON ET OU. @gwen27: Oui voila le 3 du bas ne fonctionne pas :p @Klimrod: Je valide ce croisement de fil! Tu es le premier.
#15 - 24-04-2012 00:14:15
- godisdead
- Expert de Prise2Tete
- Enigmes résolues : 22
- Messages : 747
Eelctronique en démineur (u mad bro)
#16 - 24-04-2012 08:27:30
- Klimrod
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 4049
- Lieu: hébesphénorotonde triangulaire
Electronique en déineur (u mad bro)
Bonjour,
La nuit portant conseil, voici ma contribution pour la prime à la simplicité :
![](http://www.prise2tete.fr/upload/Klimrod-16-Clydevil-Demineur03.jpg)
A suivre pour les XOR et XAND... Klim.
J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.
#17 - 24-04-2012 08:41:42
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1958
electronique en démibeur (u mad bro)
#18 - 24-04-2012 09:05:40
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Electronique en démineu r(u mad bro)
@gosidead: Je valide ce ET @Klimrod: Je valide ces portes en version compacte. @scarta: Merci pour les petits schémas, et comme tu peux le voir dessus certains "1" du losange n'ont parfois autour d'eux que des "non mines", ce qui invalide pas mal des portes proposées.
NB:Pour toute mise à jour d'image dans un post existant je conseille de changer de nom d'image même si on supprime l'ancienne. (Cache à différents niveaux).
#19 - 24-04-2012 09:31:27
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1958
Electronique en démineur (u mad broo)
AAAArgh Et dire que j'ai enlevé des cases supplémentaires à côté de chacun de ces 1 en me disant "ça sert à rien au final"... En remplaçant tous les "1 C 1" verticaux par des "X 1 C 1 Y", ça passe
#20 - 24-04-2012 10:36:27
- Klimrod
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 4049
- Lieu: hébesphénorotonde triangulaire
Elecronique en démineur (u mad bro)
J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.
#21 - 24-04-2012 12:00:24
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1958
electroniquz en démineur (u mad bro)
Voilà, c'est corrigé. En remarquant de plus que E=!A.B et F=A.!B dans le NAND/NOR, on peut ajouter le XOR pour avec une toute petite modif supplémentaire et sans avoir a faire une lourde combinaisons de 2 AND et d'un OR
![http://www.prise2tete.fr/upload/scarta-logidem_all_v2.png](http://www.prise2tete.fr/upload/scarta-logidem_all_v2.png)
#22 - 24-04-2012 14:23:05
- LeXav
- Habitué de Prise2Tete
- Enigmes résolues : 18
- Messages : 16
- Lieu: Somewhere in Nevada
electronique en démineue (u mad bro)
Re-Hello
En effet plusieurs erreurs de ma part... ![hmm](img/smilies/hmm.png) voici un update...
![http://www.prise2tete.fr/upload/LeXav-GrilleV3.PNG](http://www.prise2tete.fr/upload/LeXav-GrilleV3.PNG)
En réalité le "NON" est plutôt composé d'une simple succession d'une case indice à 1 et d'une case indéterminée... On ne transmet le signal que via des non...
Xav, Le Xav
#23 - 24-04-2012 15:55:11
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1958
electronique en démineur (u mzd bro)
Et voici le croisement de fil; obtenu de la manière suivante
![http://www.prise2tete.fr/upload/scarta-logidem_cross.png](http://www.prise2tete.fr/upload/scarta-logidem_cross.png)
Explication A XOR (A XOR B) = B. Partant de là, on prend 2 fils horizontaux A et B (disons A en haut); on insère un fil entre les deux qui vaut A XOR B, et avec un XOR entre ce fil et celui du haut on aura B en haut (et vice-versa, A en bas)
#24 - 24-04-2012 16:00:38
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
electronique en démineur (u mad beo)
@scarta: Moi aussi j'avais croisé les fils de cette manière, mais je me doutais qu'il y avait plus compacte et que l'un d'entre vous trouverait. Je pense que klimrod a la version la plus compacte possible.
#25 - 24-04-2012 16:19:13
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1958
Electronique en émineur (u mad bro)
Oui je pensais bien aussi, mais sans succès. Je voulais faire un additionneur 4 bits mais au vu de la tête du croisement...
Autre question: quelle est la validité de l'inverseur B=!A suivant:
On peut mettre une mine en C ou ne pas en mettre, le résultat sera toujours B=!A. Du coup, ça me fait penser à NOT non déterministe ![big_smile](img/smilies/big_smile.png)
Mots clés des moteurs de recherche
|
![](/img/vague-haut-droite.png) |