Ubuntu-fr

MrFaelivrin

[RESOLU] Décalage de bits astucieux pour afficher un treillis

Bonjour tout le monde !

Aujourd'hui, je vais vous proposer un casse-tête sur les bits !
Je cherche à afficher un treillis . C'est-à-dire, un truc du genre :

{}
{A} {B} {C} {D}
{AB} {AC} {AD} {BC} {BD} {CD}
{ABC} {ABD} {ACD} {BCD}
{ABCD}

Je connais des algorithmes comme l'algorithme de Er, ... Mais moi c'est pas ce que je veux !
Je veux prendre en compte tous les éléments qui ne sont pas dans un itemset(un noeud du treillis)

L'idée d'utiliiser le binaire devient donc hyper intéressant. Ainsi le treillis précédent deviendrait :

0000
0001 0010 0100 1000
0011 0101 1001 0110 1010 1100
0111 1011 1101 1110
1111

L'objectif de ce défi est bien sûr de ne pas dépasser une complexité en O(2^N). avec N le nombre de variables.
C'est-à-dire que l'ensemble des opérations doivent tenir dans un

for(i=0; i < 2^N - 1; i++){

}

Des suggestions?

J'ai déjà commencé à me casser un peu la tête dessus en jouant sur les "opérateurs décalage de bits", "XOR" et les modulos N.
Mais malheureusement, je n'ai pas énormément de temps à consacrer sur ce problème..
Et c'est pour cette raison que je sollicite les autres ingénieurs qui ont déjà résolu ce problème.
J'ai essayé de chercher un peu sur internet, mais je n'ai rien trouvé de très intéressant. Comme le nom que porterait ce problème..
Donc si vous connaissez le nom de ce problème, je suis preneur ou si vous avez des liens qui sont en lien avec mon problème.

Merci pour tout !

Dernière modification par MrFaelivrin (Le 22/02/2016, à 19:08)

pingouinux

Re : [RESOLU] Décalage de bits astucieux pour afficher un treillis

Bonjour,
Je n'ai pas bien compris ce que tu voulais. Est-ce que ceci peut t'aider ?

$ cat affichage.py
from itertools import combinations

S='ABCD'
N=len(S)

for i in range(N+1):
   for k in combinations(S,i):
      print('{%s}'%''.join(k),end=' ')
   print()

$ python3 affichage.py
{} 
{A} {B} {C} {D} 
{AB} {AC} {AD} {BC} {BD} {CD} 
{ABC} {ABD} {ACD} {BCD} 
{ABCD}

MrFaelivrin

Re : [RESOLU] Décalage de bits astucieux pour afficher un treillis

Python et sa syntaxe toujours élégante !

C'est un peu ça que je recherche mais à moins haut niveau et avec une information supplémentaire. Car je veux explicitement faire apparaître les éléments qui ne sont pas dans chaque noeud du treillis.

C'est-à-dire pour le résultat que tu as obtenu, on chercherait à obtenir : (les nX pour signifier que X n'est pas dans un noeud)
{nAnBnCnD}
{AnBnCnD} {nABnCnD} {nAnBCnD} {nAnBnCD}
{ABnCnD} {AnBCnD} {AnBnCD} {nABCnD} {nABnCD} {nAnBCD}
{ABCnD} {ABnCD} {AnBCD} {nABCD}
{ABCD}

C'est pour cette raison que l'utilisation du binaire est primordiale. o`u on utilise 0 pour signifier nX et 1 pour dire que X est dans un noeud considéré du treillis.

J'étais peut être pas très clair dans mes explications, du coup, je vais reformuler.
Concrêtement, je cherche à écrire en java, au sein d'une boucle for(j'utiliserai un while si vraiment y a pas le choix.. les instructions nécessaires à base d'opérateurs XOR, <<, |, &, ...

Pour pouvoir afficher le treillis binaire équivalent:
0000
0001 0010 0100 1000
0011 0101 1001 0110 1010 1100
0111 1011 1101 1110
1111

J'aurais du préciser aussi de ne pas utiliser des langages aussi puissants que Python. Limite l'algorithmique faisant apparaître les opérateurs XOR, <<,... suffit amplement.
En peu de lignes avec Python on arrive à obtenir ce genre de résultats qui peuvent s'avérer tordu à coder.
Mais le problème c'est qu'on on a un peu de mal à voir les instructions effectuées quand on désire réaliser ça dans un langage plus bas niveau (et surtout... plus verbeux comme java).

Dernière modification par MrFaelivrin (Le 19/02/2016, à 16:38)

claudius01

Re : [RESOLU] Décalage de bits astucieux pour afficher un treillis

Bonjour,

Je n'ai pas tout compris, sauf le programme de ... pingouinux ;-)

De plus, pour moi cela n'est que de la présentation pour dire que par exemple {0111} représente {ABCnD} ?!..

Rien ne t’empêche de réécrire ce qu'il faut en Java pour traiter les méthodes Generating all combinations of a list in python, Python String join() Method, etc. et obtenir ce que tu souhaites...

Non, désolé, je n'arrive pas à cerner ton besoin et surtout ce point:
En peu de lignes avec Python on arrive à obtenir ce genre de résultats qui peuvent s'avérer tordu à coder.
Mais le problème c'est qu'on on a un peu de mal à voir les instructions effectuées quand on désire réaliser ça dans un langage plus bas niveau (et surtout... plus verbeux comme java).

Maintenant, peut-être qu'avec un Langage comme l'Algol tu serais plus proche de l'algorithme que tout Langage permet soit dit en passant.

Dernière modification par claudius01 (Le 20/02/2016, à 16:43)

---

micros informations
- Enregistreur de traces GPS sur Clé USB
- Boussole GPS à Guidage Vocal
- Coprocesseur flottant uM-FPU et PIC16

MrFaelivrin

Re : [RESOLU] Décalage de bits astucieux pour afficher un treillis

Bah merci déjà pour vos réponses.

En fait, tout dépend de la sémantique des objets contenus dans le treillis.

Pour mon cas, ce n'est pas la même chose de parler de l'ensemble {A} et de l'ensemble {AnBnCnD}(celui qui m'intéresse).

J'explique pourquoi : dans le premier cas on va regarder l'ensemble des transaction o`u le motif A apparait.
Imaginons une série de transactions :
A
A B C
A B

le motif {A} apparait trois fois
Alors que le motif {A nB nC nD} apparait qu'une seule fois.

Du coup, dans la seconde notation, nous allons donc regarder et compter l'ensemble des transactions o`u A apparait et o`u il n'y a pas B, C, et ni D.

Mon treillis a pour but de dénombrer ces motifs. Je reconnais toutefois que je n'avais pas précisé l'ensemble des objets contenus dans le treillis et l'intérêt de ce treillis pour ma recherche.

Dernière modification par MrFaelivrin (Le 22/02/2016, à 19:06)

pingouinux

Re : [RESOLU] Décalage de bits astucieux pour afficher un treillis

À tout hasard, voici deux autres façons de faire en python (la seconde méthode utilise des fonctions élémentaires) :

$ cat affichage2.py
N=4

# Méthode 1
resul={}
for k in range(N+1): resul[k]=[]
for k in range(2**N): resul[bin(k).count('1')].append(k)
print('Méthode 1')
for k in range(N+1):
    for r in resul[k]:
       bl=1 if not r else r.bit_length()
       print("%s%*s"%('0'*(N-bl),bl,bin(r)[2:]),end=' ')
    print()
print()

# Méthode 2
def n1_s(i): # Retourne le nb de bits à 1, et sous forme de chaîne de caractères, le nombre en binaire sur N bits
   n1=0; s=''
   for k in range(N): j=i&1; n1+=j; s=str(j)+s; i>>=1
   return n1,s
resul={}
for k in range(N+1): resul[k]=[]
for i in range(1<<N): n1,s=n1_s(i); resul[n1].append(s)
print('Méthode 2')
for k in range(N+1): print(' '.join(resul[k]))
print()

$ python3 affichage2.py
Méthode 1
0000 
0001 0010 0100 1000 
0011 0101 0110 1001 1010 1100 
0111 1011 1101 1110 
1111 

Méthode 2
0000
0001 0010 0100 1000
0011 0101 0110 1001 1010 1100
0111 1011 1101 1110
1111

MrFaelivrin

Re : [RESOLU] Décalage de bits astucieux pour afficher un treillis

Elles sont très élégantes tes solutions !

Juste pour comparer la "compacité" entre les deux langages python et java..
Ma solution écrite en Java fait plus d' une 50ene de lignes................................

Au passage, j'ai pas tenu compte de l'algo que j'ai rédigé à l'arrache (je le redis, d'ailleurs, je vais l'effacer de ce qu'il est moche !! )
J'ai gardé l'idée du tableau de vects[] dont je décale les bits vers la gauche à chaque fois.

J'utilise l'opération key = key & vects[j] pour effacer le vects[j] (le bit)
Je décale le bit d'un cran vers la gauche vects[j] = vects[j] << 1 (je vérifie que je ne suis pas arrivé au bout si c'est le cas, j'incrémente inits[j] de 1 je déplace le vecteur d'après......etc etc... de manière récursive... breeeff... osef ! ahahahahah )
et je remets le vecteur dans key : key = key | vects[j]

En tout cas, merci à vous deux pour votre aide !

Dernière modification par MrFaelivrin (Le 22/02/2016, à 19:12)

claudius01

Re : [RESOLU] Décalage de bits astucieux pour afficher un treillis

Bonsoir,

Juste pour comparer la "compacité" entre les deux langages python et java..
Ma solution écrite en Java fait plus d' une 50ene de lignes................................
...
En tout cas, merci à vous deux pour votre aide !

De rien et merci pour ton retour.

Maintenant, un Langage n'est pas meilleur ou plus mauvais qu'un autre et je me refuse après des années d'expériences à les comparer car c'est mission impossible. Cela est juste une problématique d'objectifs à atteindre en fonction de tes besoins. Dans ton cas, peut-être, qu'un Langage Formel serait plus approprié...

Je ne crois plus à un Langage Universel qui regrouperait et synthétiserait "le meilleur de tous" comme il n'y aura pas de Langues Humaines Universelles (enfin je l'espère ;-) et je ne compte pas le nombre de Dialectes sur notre planète ;-).

La Nature survit et évolue avec la multiplicité des choix et périt avec la consanguinité ;-)

Dernière modification par claudius01 (Le 22/02/2016, à 20:00)

---

micros informations
- Enregistreur de traces GPS sur Clé USB
- Boussole GPS à Guidage Vocal
- Coprocesseur flottant uM-FPU et PIC16

MrFaelivrin

Re : [RESOLU] Décalage de bits astucieux pour afficher un treillis

C'est beeeaaaauuuu ça !

Je suis tout à fait d'accord avec toi.
Chaque langage a été conçu pour répondre à un besoin précis.

Lorsque je mettais Python sur un piedéstale, je ne voulais surtout pas dire que Python était supérieur.
Je vois un peu python comme le couteau suisse des langages.

Après, il a ses limites comme tout langage et je ne crois pas non plus à un langage universel.

Personnellement, j'effectue mes choix de langages de la façon suivante :
* Application cross-plateforme, logiciel ou application smartphones(avec le super framework libGDX) -> Java
* Optimisation combinatoire, métaheuristiques, ou tout besoin de perf via de la parallélisation, programmation linéaire...  -> C++
* Scripts pour automatiser des tâches --> Bash (voire parfois perl)
* IA  et résolution modélisation CSP : Prolog (Après C++ a de très bonnes librairies d'optimisation)
* Sécurité / Hacking : C-Assembleur  (+ framework Metasploit, ... )
* Maths formelles : Matlab, Mapple, ...
* Statistiques : R ( ou SAS)

Et pour moi Python arrive lorsqu'on veut faire des maquettes rapidement ou des scripts. ))
La dernière fois que j'ai codé sous python, c'était Spark, un framework pour faire du Big Data.
Et aussi pour le machine learning avec Scikit-learn, une lib sous Python.

Je crois que je déborde sur un tout autre sujet. ahah !

Sinon  par rapport au projet dont il était question dans ce topic.  Je cherchais à coder des treillis pour mettre en place une nouvelle façon d'apprendre des réseaux Bayésiens. Ma nouvelle technique a l'air de porter ses fruits. Mais comme je soutiens vendredi... ça va être short !

Dernière modification par MrFaelivrin (Le 22/02/2016, à 21:06)

claudius01

Re : [RESOLU] Décalage de bits astucieux pour afficher un treillis

Ok. Tout d'abord, repose toi bien avant ta soutenance ce vendredi, on pourra toujours en causer plus tard ;-)

Nous sommes sur la même longueur d'ondes et je me sens tout petit "algorithmiquement parlant" au vu de ton cursus...

La naissance, la popularité et la mort des Langages Informatiques m'a toujours passionnée et je regrette de ne pas pouvoir en pratiquer avec efficacité plus de ... 5 et je pense que c'est sans espoir (Snif ;-(). Malgré tout, j'attaque un petit dernier qui est Rust pour des raisons que j'estime en adéquation avec mes activités professionnelles et personnelles.

Allez, je te dis "merde" pour ta soutenance si cela peut te porter Bonne Chance...

---

micros informations
- Enregistreur de traces GPS sur Clé USB
- Boussole GPS à Guidage Vocal
- Coprocesseur flottant uM-FPU et PIC16

MrFaelivrin

Re : [RESOLU] Décalage de bits astucieux pour afficher un treillis

C'est gentil, merci beaucoup.

Désolé de n'avoir pas pu répondre plus tôt. J'étais immergé dans la rédaction de mon rapport. (120 pages... ahah )

J'ai d'ailleurs été très étonné des remarques faites sur mon projet. Orgueil mal placé, je pense. Car sans prétention sur mon travail .  Je pense avoir été le seul de ma promo de M2 à chercher à prouver par des preuves mathématiques tout ce que j'affirmais. Et surtout à avoir été le seul de ma promo à avoir résolu un problème comme le Problème de l'apprentissage de réseaux PCP-NET par réduction polynomiale des PCPNETs que je nomme "PCPNET sous forme normale" vers le problème de l'apprentissage de réseaux Bayésiens.

Et d'avoir trouvé une technique pour faire de l'apprentissage de réseaux Bayésiens de manière efficace en raisonnant sur la structure des Treillis de Galois et d'une dernière notion que j'ai appelée, Treillis Binaire.

C'est d'ailleurs cette dernière notion qui était associée à ce topic.

Pour expliquer de manière vulgarisée ces outils, un réseau Bayésien, c'est un outil de probas pour représenter les dépendances entre variables. Ca nous permet de faire des prédictions sur des phénomènes "aléatoires", c'est-à-dire, extremement compliqués et pour lesquels, nous ne possédons aucun modèle déterministe(c'est à dire tous les modèles sauf les probas! ahah)  permettant de modéliser ces phénomènes.
On essayait d'apprendre ces réseaux bayésiens avec diverses techniques mais on avait quand même beaucoup de mal.
Du coup, je prouve d'une part que le problème d'apprentissage des PCPNET peuvent se ramener à ce problème d'apprentissage de ces réseaux bayésiens et d'autre part je prouve qu'on peut résoudre ce dernier en travaillant dans cette algèbre des treillis de Galois.

Conclusion: on va bientôt être capables grâce à ces travaux de mettre en place ce genre d'outils pour anticiper le comportement des gens..
C'est donc une très mauvaise nouvelle !

Car si moi je suis capable de prouver ce genre de résultats, ça veut sans doute dire que potentiellement d'autres l'ont déjà fait avant moi et exploiter ces résultats.

Mais bon, c'est d'ailleurs ce que faisaient déjà les systèmes de recommandation. Mais à une échelle beaucouuup plus large.

Big Brother is Watching You.

Pire encore.....
Big Brother knows everything about you !

PS: Je connais pas Rust mais ça a l'air vachement cooool !

Je pense que maîtriser 5 langages, ça suffit amplement pour faire tout ce qu'on veut. (D'ailleurs un langage suffit en principe. Après tout dépend de la portée du langage. J'adorais mes cours de Théorie des Langages. Apprendre à coder des compilateurs, c'est drôle ! )

Dernière modification par MrFaelivrin (Le 26/02/2016, à 22:02)