Newsgroup: it.hobby.enigmi
Titolo: [Lungo] Ancora sui tririduttori di 16 doppie

Scusate se inizio un nuovo thread, ma l'intervento di Livio
ha posto l'accento ed invitato ad un esame  più generale e
profondo sul problema postato il 25-03 alle ore 20:44 del
Gino, la Gina e le monetine.
Livio dice giustamente che "La soluzione ottimale dovrebbe
approdare ad un tririduttore puro da 16 doppie".
Ma può esistere il riduttore perfetto n-3 di 16 doppie?
La risposta è no. Vediamo perchè.
Le colonne totali sono 2^16 = 65536.
Rispetto a qualsiasi colonna, le colonne "utili" sono:
1 che realizza 16 punti, 16 che garantiscono il 15, 120 per
il 14 e 560 che danno il 13.  Totale = 697
Il riduttore n-3 teorico di 16 doppie dovrebbe quindi essere
di 65536/697 = 94,02582... colonne, e la presenza dei decimali
(oltre a semplici considerazioni sulla massima rappresentatività,
cioè sulla differenza dei segni nelle colonne) indica chiaramente
che qualsiasi riduttore non potrà essere perfetto.
Questo non esclude ovviamente che si possano costruire sistemi
"primato" con meno delle 256 colonne (8 bit) previsti dal problema,
anche se dubito si possano raggiungere aggregati esprimibili con
7 bit.
Ma limitiamoci ad utilizzare tririduttori da 256 colonne, come
quello 7/9 + 6/7 = 13/16 da me schematizzato in precedenza.
Livio dice che occorre fare una scelta ottimale per determinare
le 256 word che massimizzano la vincita media.
E propone un programma di ricerca operativa (che ovviamente io
non so fare) per poterle scovare.
Io mi limito quindi ad osservare che i 256 aggregati di 256
colonne che costituiscono tririduttori e che sono stati ricavati
mediante la medesima chiave, posseggono le stesse peculiarità
e presentano identica garanzia di vincita media.
Di seguito schematizzo i due esempi descritti nei post precedenti.
  A      B      C      D      E      F      G      H
 1 X    X 1    X 1    X 1    X 1    1 X    1 X    1 X
 1 X    X 1    1 X    1 X    1 X    X 1    1 X    1 X
 1 X    1 X    X 1    1 X    1 X    1 X    X 1    1 X
 1 X    1 X    1 X    X 1    1 X    1 X    1 X    X 1
  a      b      c      d
  1      X      1      X
  1      X      X      1
  A'     B'     C'     D'     E'     F'     G'     H'
  1      X      X      1      1      X      1      X
  1      X      1      X      X      1      1      X
  1      X      1      X      1      X      X      1
    r1     r2     r3      r4
   1 X    X 1    1 X     1 X
   1 X    1 X    X 1     1 X
   1 X    1 X    1 X     X 1
TRIRIDOTTO 9D+7D = colonne 16*16 = 256 vincita media 13,46875
 A  B  C  D  A  B  C  D      E  F  G  H  E  F  G  H
 a  b  c  d  b  a  d  c      a  b  c  d  b  a  d  c
 A' A' A' A' B' B' B' B'     A' A' A' A' B' B' B' B'
 -----------------------    ------------------------
  A     B     C     D         A     B     C     D
  r1    r2    r3    r4        r1    r2    r3    r4
 A  B  C  D  A  B  C  D      E  F  G  H  E  F  G  H
 a  b  c  d  b  a  d  c      a  b  c  d  b  a  d  c
 A' A' A' A' B' B' B' B'     A' A' A' A' B' B' B' B'
 -----------------------    ------------------------
  E     F     G     H         E     F     G     H
  r1    r2    r3    r4        r1    r2    r3    r4
Con semplici inversioni (A'B' con C'D' - E'F' - G'H') e
permutazioni (A B C D   e   F G H I)  dai 4 presentati
si ottengono i 256 tririduttori.
TRIRIDOTTO 13D+3D = colonne 128*2 = 256 vincita media 13,48438
 A  B  C  D  A  B  C  D      E  F  G  H  E  F  G  H
 a  b  c  d  b  a  d  c      a  b  c  d  b  a  d  c
 -----------------------     ------------------------
 A  B  C  D  A  B  C  D      E  F  G  H  E  F  G  H
 a  b  c  d  b  a  d  c      a  b  c  d  b  a  d  c
 1  1  1  1  X  X  X  X      1  1  1  1  X  X  X  X
 -----------------------     ------------------------
           r1                         r1
 A  B  C  D  A  B  C  D      E  F  G  H  E  F  G  H
 a  b  c  d  b  a  d  c      a  b  c  d  b  a  d  c
 -----------------------     ------------------------
 E  F  G  H  E  F  G  H      A  B  C  D  A  B  C  D
 a  b  c  d  b  a  d  c      a  b  c  d  b  a  d  c
 1  1  1  1  X  X  X  X      1  1  1  1  X  X  X  X
 -----------------------     ------------------------
           r1                         r1
Analogamente, permutando  A B C D   e   F G H I
e sostituendo r1 con r2 - r3 - r4  si ricavano i
256 riduttori diversi, che nel loro insieme riproducono
l'integrale delle 16 doppie.
Ciao, Nino

 [...]
E' dunque evidente che questi due sistemi derivati dalla combinazione
di due (perfetti?) sono entrambi "ridondanti". Essi danno una vincita
media leggermente diversa. Sorge dunque spontanea la domanda:
esiste un altro insieme di riduttori tale da fornire una vincita media
ancora superiore? Mi sembra probabile, anche se mi rendo conto che
per dimostrarne l'esistenza occorrera'... scovarli.  :o))
Ciao!!!  ((^__^))'
Livio


E' proprio questo il punto. Il sistema ridotto ideale dovrebbe essere quello
che garantisce le seguenti "prestazioni":
1 volta su 256 ottengo 16
16 volte su 256 ottengo 15
120 volte su 256 ottengo 14
le rimanenti volte (119) su 256 ottengo 13.
Questo garantirebbe una vincita media pari a 13,60546875, che è il massimo
possibile. Si tratta appunto di trovarlo! :-)
Ciao :-)
Giorgio

 il massimo possibile. Si tratta appunto di trovarlo! :-)
Si tratta di muoversi su una collina n-dimensionale con n=256.
Le colline sono discrete, a gradoni, piramidi azteche.
Le soluzioni (vette piu' alte) sono probabilmente tante. (questo aiuta)
I massimi relativi ancor di piu'. Occorre poterne uscire facilmente,
anche se potremmo accontentarci di qualcuno di loro. (se solo
15 volte su 256 ottengo 15, la vincita media sara' 13.59).
Una Darwin Machine?  :o))
Ciao!!!  ((^__^))'
Livio

 massimo possibile. Si tratta appunto di trovarlo! :-)
Puo' essere anche, come spesso succede ultimamente, che siano state
sviluppate delle teorie sotto il cappello di "compressione dati con
perdita di informazione", teorie che non conosco. Mi dicono che la
JPEG e' una compressione CON perdita, ad es.
Ciao!!!  ((^__^))'
Livio


La sistemistica classica, studiata a tavolino con solo foglio e matita
(come ho sempre fatto io), ha dovuto purtroppo ultimamente lasciare
spazio ai miglioramenti (di tipo colonnare, ma non sempre di eleganza
strutturale) ottenuti con sofisticati programmi computerizzati.
Ma a mio avviso, il piacere di un primato  ottenuto nei due modi
non dà la stessa intensità.
Ciao a tutti, Nino


Esatto, ma sono certo che non esiste.
Forse si potrà avvicinarsi...
Ciao, Nino

Qualcuno vuole consolarmi (matematicamente) sull'esperimento
(bruteforce) che ho fatto questa notte? Il risultato mi ha sorpreso.
Dunque, ho costruito un sistema ridotto di 256 word con il seguente
metodo: ho tirato a sorte con una moneta ciascun bit di ciascuna
delle 256 word. (!)
Poi sono andato a calcolare la vincita media. Risultato: 13.41... (!)
Ho ripetuto l'esperimento ottenendo sempre risultati compresi
tra 13.40 e 13.42, assai vicini ai sistemi ridotti "pensati".
Ciao!!!  ((^__^))'
Livio

"Livio Zucca"

Ci ho provato anch'io. Trovo però risultati un po' diversi: circa 13.23 di
media. Non credo che la differenza tra i miei e i tuoi risultati sia
imputabile alla bontà del generatore casuale. Probabilmente c'è qualche
errore (mio e/o tuo) nei conteggi. Io, per ogni word possibile, calcolo il
numero dei bit diversi rispetto a ogni word del sistema ridotto. Prendo il
valore minore e in base a questo stabilisco il punteggio.
Ciao :-)
Giorgio

 tra 13.40 e 13.42, assai vicini ai sistemi ridotti "pensati".
confermo: 13.42 con scarto medio molto basso
-- 
Ciao, Silv:o)

 ha scritto:

Mi sembra che il metodo di calcolo sia lo stesso (nelle intenzioni :o))
Per ogni valore 0..65535, considerati equiprobabili, cerco quel
pivot tra i 256 che l'avrebbe rappresentato al meglio. Infatti quello
avrei usato in fase di codifica...
Mi sembra di aver detto la stessa cosa. 'Sta notte verifichero' i conti.
Anche 13.23 non sarebbe cmq da buttare via, visto che il primo
sistema pensato dava un 13 secco. Il Caos batte l'Ordine piu' spesso
di quanto non immaginiamo!  :o)))
Ciao!!!  ((^__^))'
Livio

 ha scritto:

Ho anche implementato una Darwin Machine, pero' impiego un sacco
di tempo per calcolare la vincita media. Cosi' nella notte il sistema
si e' evoluto poco ed e' arrivato a 13.45 in poche decine di generazioni.
Se a qualcuno venisse in mente un metodo rapido di calcolo...
Io, per ogni word possibile, per ogni pivot, per ogni bit, faccio
268435456 loop ogni volta solo per determinare la Vmed.
Ciao!!!  ((^__^))'
Livio


Non so se intendi questo: per confrontare tra loro 2 word puoi usare
l'operatore Xor e poi contare i bit 1 del risultato.
Ho buttato giů un programma per generare ridotti. Per ora č arrivato a un
po' piů di 13.48 di vincita media. Vi allego le 256 word, se qualcuno le
volesse controllare. :-) Alcune combinazioni vincono solo 12 punti.
0000000000000000
0000000011110101
0000000111101010
0000001011011111
0000001111010100
0000010011001001
0000010110111110
0000011010110011
0000011110101000
0000100010011101
0000100110010010
0000101010000111
0000101101111100
0000110001110001
0000110101100110
0000111001011011
0000111101010000
0001000001000101
0001000100111010
0001001000101111
0001001100100100
0001010000011001
0001010100001110
0001011000000011
0001011011111000
0001011111101101
0001100011100010
0001100111010111
0001101011001100
0001101111000001
0001110010110110
0001110110101011
0001111010100000
0001111110010101
0010000010001010
0010000101111111
0010001001110100
0010001101101001
0010010001011110
0010010101010011
0010011001001000
0010011100111101
0010100000110010
0010100100100111
0010101000011100
0010101100010001
0010110000000110
0010110011111011
0010110111110000
0010111011100101
0010111111011010
0011000011001111
0011000111000100
0011001010111001
0011001110101110
0011010010100011
0011010110011000
0011011010001101
0011011110000010
0011100001110111
0011100101101100
0011101001100001
0011101101010110
0011110001001011
0011110101000000
0011111000110101
0011111100101010
0100000000011111
0100000100010100
0100001000001001
0100001100000010
0100001111110111
0100010011101100
0100010111100001
0100011011010110
0100011111001011
0100100011000000
0100100110110101
0100101010101010
0100101110011111
0100110010010100
0100110110001001
0100111001111110
0100111101110011
0101000001101000
0101000101011101
0101001001010010
0101001101000111
0101010000111100
0101010100110001
0101011000100110
0101011100011011
0101100000010000
0101100100000101
0101100111111010
0101101011101111
0101101111100100
0101110011011001
0101110111001110
0101111011000011
0101111110111000
0110000010101101
0110000110100010
0110001010010111
0110001110001100
0110010010000001
0110010101110110
0110011001101011
0110011101100000
0110100001010101
0110100101001010
0110101000111111
0110101100110100
0110110000101001
0110110100011110
0110111000010011
0110111100001000
0110111111111101
0111000011110010
0111000111100111
0111001011011100
0111001111010001
0111010011000110
0111010110111011
0111011010110000
0111011110100101
0111100010011010
0111100110001111
0111101010000100
0111101101111001
0111110001101110
0111110101100011
0111111001011000
0111111101001101
1000000001000011
1000000100111001
1000001000110000
1000001100100111
1000010000011100
1000010100010010
1000011000001010
1000011100000001
1000011111110110
1000100011101011
1000100111100000
1000101011010101
1000101111001010
1000110010111111
1000110110110100
1000111010101001
1000111110011110
1001000010010011
1001000110001000
1001001001111101
1001001101110010
1001010001100111
1001010101011111
1001011001010100
1001011101101000
1001100001011110
1001100101011001
1001101001010011
1001101101001111
1001110001001000
1001110100111101
1001111000110010
1001111101000010
1010000000110111
1010000100101100
1010001000101011
1010001101000000
1010010000111010
1010010101000101
1010011001000110
1010011101001011
1010100001000100
1010100101010010
1010101001001001
1010101100111110
1010110001010111
1010110101001110
1010111001100000
1010111101011101
1011000001011000
1011000101100001
1011001001101110
1011001110000001
1011010010000000
1011010101111100
1011011001110001
1011011110010100
1011100010001001
1011100110000010
1011101010001110
1011101110010111
1011110010010101
1011110110001100
1011111010000011
1011111101111011
1100000001110001
1100000101100110
1100001001011011
1100001101010101
1100010001001101
1100010101001010
1100011000111111
1100011100110100
1100100000101100
1100100100100001
1100101000010110
1100101100001011
1100110000000000
1100110011110101
1100110111101111
1100111011100110
1100111111101000
1101000011011111
1101000111010100
1101001011001001
1101001110111110
1101010010110111
1101010110101100
1101011010100001
1101011110011101
1101100010011100
1101100110010001
1101101010011011
1101101110100010
1101110010101010
1101110111000000
1101111011011110
1101111111110001
1110000011101000
1110000111011101
1110001011010010
1110001111000111
1110010010111100
1110010110110001
1110011010100111
1110011110101010
1110100010011111
1110100110010100
1110101010010001
1110101110011010
1110110010010010
1110110110000111
1110111010001100
1110111110110110
1111000010101011
1111000110111000
1111001010110101
1111001111001010
1111010011010001
1111011000011110
1111101000101000
1111110100100100
Ciao :-)
Giorgio

 ...
Controllate!  :o)
Le ho anche messe nella Darwin Machine che in un paio d'ore  :o)
ha portato la vincita media da 13.481+ a 13.487+.  Se non sbaglio e' il record!
Dovete per ora credermi sulla parola perche' ho azzerato il prog. prima di
salvare il sistema. :o(  Ci riprovero' cercando di velocizzare il calcolo.
Ciao!!!  ((^__^))'
Livio

tra 13.40 e 13.42, assai vicini ai sistemi ridotti "pensati".
Invece per spiegare il "piattume" della media puoi pensare che un
sistema triridotto puo' essere diverso di pochissimo da un sistema
composto dallo stesso numero di colonne ma che non e' un triridotto.
Se hai costruito il ridotto in modo casuale, e' estremamente
improbabile che tu abbia costruito un triridotto, cioe' un sistema
che dia  **garanzia** di fare 13/16. Quello della garanzia di un
risultato e' un caposaldo irremovibile della sistemistica!!!
E' invece quasi certo che tu abbia ottenuto un sistema a garanzia
11/16, e hai ottime probabilita' di aver ottenuto un 12/16.
(Lo dico anche sulla base di simulazioni che ho fatto io.) A me
viene che ridotti di 256 colonne generati a caso lasciano "scoperte"
tra le 3000 e le 5000 colonne del sistema integrale, nel senso che
su quelle non si fara' 13/16 ma un po' meno, generalmente 11/16.
Quindi tenuto conto che nel complesso le colonne sono 65536, 5000
di queste che fanno 11 anziche' 13 spostano poco la media.
La verita' e' che la garanzia del 13/16 puo' addirittura andare in
controtendenza rispetto al valore medio di sistemi con garanzia
inferiore! Cioe' e' possibile avere sistemi a garanzia di 12/16 che
hanno rendita media *superiore* a sistemi con garanzia 13/16.
Dal mio punto di vista, potendo scegliere, io preferirei sempre
un sistema con garanzia minima superiore e garanzia media inferiore
piuttosto che il viceversa. Ma questa e' questione di carattere. ;-)
A presto,
          iant

"Livio Zucca"  dice:

Disordine e aumento dell'entropia...
Con il massimo ordine (256 colonne costituite dall'accorpamento
di 8 doppie integrali) si realizza la minima vincita media, che
è pari a 12 (0,39% per l'8 e il 16, 3,125% per il 9 e il 15,
10,937% per il 10 e il 14, 21,875% per l'11 e il 13 e 27,344%
per il 12).
Sarebbe sorprendente se scegliendo colonne a caso si realizzassero
composizioni ordinate.... e quindi a bassa vincita media.
Però, altrettanto sorprendente, sarebbe ritrovarsi bell'e pronto
e senza fatica un ridotto a garanzia di vincita programmata e
a livello di primato.
Mi ha incuriosito il programma per generare ridotti fatto da Giorgio
(però, le 256 word presentate configurano un probabilistico, essendo
n-4).
Mi scuso quindi se approfitto delle vostre capacità informatiche
e vi chiedo se qualcuno volesse gentilmente controllare per la
vincita media le 256 word che ho schematizzato di seguito ( a mano
è un lavoro improbo e dal risultato incerto).
      0   1   1   0                           1    0    1    0
      0   1   1   0                           0    1    0    1
      0   1   0   1                           1    0    0    1
      0   1   0   1                           0    1    1    0
      0   0   1   1                           0    0    1    1
      0   0   1   1                           1    1    0    0
 -------------------------       +       ---------------------------
 0  1  1  0     1  0  1  0                0  1  1  0     1  0  1  0
 0  1  1  0     0  1  0  1                0  1  1  0     0  1  0  1
 0  1  0  1     1  0  0  1                0  1  0  1     1  0  0  1
 0  1  0  1     0  1  1  0                0  1  0  1     0  1  1  0
 0  0  1  1     0  0  1  1                0  0  1  1     0  0  1  1
 0  0  1  1     1  1  0  0                0  0  1  1     1  1  0  0
 ----------     ----------                ----------     ----------
   0    1         1    0                    1    0         1    0
   0    1         1    0                    0    1         0    1
   0    1         0    1                    1    0         0    1
   0    1         0    1                    0    1         1    0
colonne : 4*4*2 + 4*4*2          +             4*4*2 + 4*4*2
      1   0   1   0                           1    0    1    0
      1   0   1   0                           0    1    0    1
      1   0   0   1                           1    0    0    1
      1   0   0   1                           0    1    1    0
      1   1   0   0                           1    1    0    0
      1   1   0   0                           0    0    1    1
 -------------------------       +       ---------------------------
 1  0  1  0     1  0  1  0                1  0  1  0     1  0  1  0
 1  0  1  0     0  1  0  1                1  0  1  0     0  1  0  1
 1  0  0  1     1  0  0  1                1  0  0  1     1  0  0  1
 1  0  0  1     0  1  1  0                1  0  0  1     0  1  1  0
 1  1  0  0     1  1  0  0                1  1  0  0     1  1  0  0
 1  1  0  0     0  0  1  1                1  1  0  0     0  0  1  1
 ----------     ----------                ----------     ----------
   1    0         0    1                    0    1         0    1
   0    1         1    0                    0    1         0    1
   0    1         0    1                    1    0         0    1
   0    1         0    1                    0    1         1    0
colonne : 4*4*2 + 4*4*2          +             4*4*2 + 4*4*2
Ciao a tutti, Nino


Anche questo è verissimo, si tratta di vedere cosa privilegiare.
Ovvio che in sistemistica vale la garanzia minima, sarebbe terribile
indovinare il pronostico e non vincere quello che si era preventivato.
Ciao, Nino

 ...
Non male: 13.500+
Le tue word si sono "evolute" nella Darwin Machine tutta la notte.
Ciao!!!  ((^__^))'
Livio
0000000000100100
0000100011110111
0000000101101010
0000101011011111
0000001111010110
0000010011001001
0000110110111110
0000011010111011
0000011110111000
0000101010011101
0000100110011010
0000101010000011
0010101101111101
0000110001110101
0100110101100111
0000111001011011
0000111111000000
0001001001000101
0001000110110010
0001001000101111
0001001100100100
0001010000011000
0001010100001110
0001010000000011
0001011011111000
1001011111101101
0001100011100110
0001100111010111
0001101011001100
0001001111000001
0011110010011110
0001110110101011
0001111010100100
0001111110010100
0010000010001010
0010001101101111
0010011101110100
0011001100001000
0110010001011110
0011000101010011
0010011001001000
0000011100111101
0010100000110010
0011100100100111
0010101000011100
0010111100010001
0010111000000110
0010110011111001
0010110111110000
0010111011100111
0010111111011010
0011000111001111
0011000111010100
0011001010110001
0011001111101010
1011011000100011
0010010110011000
0011011010001101
0111010110000010
0011101001111111
0011100101101100
0001101001100001
1011111101010110
0011100101001011
0111110111000000
0111101000110101
0111111100101010
0100000000001011
0110000100010100
0100001100001101
0000000100000010
0101111011110111
1100010011101100
0100010111110001
0100011011000110
0100011111001011
0000100011000000
0100100110110101
0110101010101010
0100111110011111
0100110010010100
0100100110011001
0100111001111110
0100011111110011
0101000001101000
0100000101011101
0101001000011010
0101001101000111
0101110001111100
0101010100110001
0101011001100110
0101011100011011
0101100001010000
0111100100000001
1101100101111010
0101101010101111
1101101111100100
0101110111011001
0100101111101110
1101111011000011
0101101110111000
0110000010101101
0110000110100010
0111000010010111
0110001110101101
0110010010000001
0110010101110110
0110011001100111
0110011101100000
0100100001100101
0110100101001010
0110001000111111
0100101100110011
0110110000101001
0010110101011110
1110111100010010
0010111100001000
0110111111111101
0111000011110010
1111000111100001
0111001011011100
0111001111010001
1111010011000110
0111010011111011
0111011010110000
0111011110100111
0111100010000010
0111100111011110
0111101010000100
0111101101111001
0111110101101110
0111110101100011
0111111001011000
1111111001001111
1000001011000001
1000000100111001
1000001000110000
1010001100100111
1000010000011100
1000010100010011
0000011000001010
1000011110000001
1000011011110110
1000100111101001
1000101111100000
1000101011010101
1100001111001000
1000110010111011
1000110110111110
1000111010101001
1100011110011110
1001010010010011
0011000011000000
1001001001111101
1001001101110010
1001010001101111
0101010101011111
1001111000010100
0000011101101000
1001100011001110
1001100001011001
1001011001010011
1001101101001111
1001110001001000
1001100100111101
1101111000110010
1001111101000000
1010000010110111
1010000100101100
1010001001101011
1010001101010000
1011010111111000
1010010101000101
1010011000100110
1010011111001111
1010100001110100
1010100001010010
1010100001001001
1011101110111110
1111100001000111
1010110101000011
1010111001100000
1010111101011101
1011000001011110
1011000001100000
1011001011101110
1011001110000101
1011010010100011
1111010101111100
1011111000110101
1001011110010000
1011100110001001
1011100110000010
1011101000001010
1011101010010111
1011110010010101
1011110110001100
1001111010000111
1011111101111011
1100000001110000
1100000101100100
1100001011011011
1100001101010101
1100010101001101
1100010100001110
1100011100101111
1101111100110100
1100000000101100
1000100100100001
1100101000010110
1100101100001000
1100110000000000
1100100011110101
1110110111101111
1110101111100110
1100111111111001
0101000001111101
1101010111010100
1101011011001001
1101001110101110
1101010010110111
0101010110101101
1100011010100001
1111011100010101
1111110010011100
1101100110010001
0101101000001011
1101101110100010
1001110010101010
1101110111100000
1101111111011110
1101110101110001
1110100011101000
1110000101111101
0110101011110010
0110000111000111
1110010010111100
1110010100110101
1110011010100111
1110011110101010
1110100010011111
1110100110010100
1110101010010001
1110101110011011
1110110000000010
1100110110000011
1110011010001101
1110111110010100
1111000100101011
1111000010111000
1011001010110100
1111010111001010
1111010001010001
1111011000111110
1111101000101000
0111110100100100


Bene! Se si vince, facciamo a metà! :-))
Ciao :-)
Giorgio

  -------------------------       +       ---------------------------
[cut]
Ecco, anche qui non mi è chiaro che cosa si deve fare. Se mi fai un
esempietto forse tutto si chiarisce. Forse, sforzandomi, ci potrei arrivare
da solo, ma considera che è domenica mattina e la pigrizia incombe. :-)
Una volta che hai chiarito come ottenere le 256 word, posso provare a
controllarle, anche se probabilmente lo può fare più rapidamente Livio, che
dovrebbe avere già implementato un modo per importare le word altrui! ;-)))
Ciao :-)
Giorgio

>n-4).
Il riduttore cosi' ottenuto, non da' l'assoluta certezza dello scarto 
massimo di 3 punti, visto che garantisce solo un n-4, per questo credo 
che Nino usi "probabilistico" anziche' "assoluto"
Non ho seguito bene il thread. Pero' vorrei buttare giu' qualche idea 
sperando di non dire stupidaggini.
Allora, se ho ben capito tu costruisci la libreria delle 2^16 = 65536 
parole, poi ne tieni una a caso e cancelli dalla libreria tutte quelle 
che non sono piu' lontane di 3 bit dalla stringa scelta.
E' chiaro che alla prima operazione verranno scartate tutte quelle 
"differenti" per:
1 bit = c(1,16)= 16
2 bit = c(2,16)= 120
3 bit = c(3,16)= 560
totale 696.
Ora con quale criterio il programma sceglie la prossima word?
Se la scelta e' random c'e' il rischio di selezionarne una non troppo 
lontana dalla prima che coprirebbe molte stringhe gia' cancellate, 
percio' sarebbe opportuno scegliere la piu' "differente" vale a dire la 
stringa complementare, in pratica quella con tutti i bit invertiti di 
segno, che sicuramente mi cancellera' altre 696 words dalla libreria.
Capito il concetto conviene allora lavorare solo sulle prime 32768 
stringhe, selezionarne 128 (vedremo poi come ottimmizzare questa scelta) 
eppoi integrarle con le 128 complementari, che coprono per simmetria le 
seconde 32768.
Ora per ottimizzare la scelta, ogni volta bisognerebbe controllare fra 
le rimaste nella libreria quella/e in grado di cancellarne il massimo. 
E' chiaro che con questo procedimento se non mi limito a selezionare 256 
stringhe, ma continuo fino all'esaurimento della libreria, ottengo un 
tririduttore assoluto. Con questo criterio pero' rimarrebbe la scelta 
aleatoria fra le words con la stessa "potenza" di copertura.
Un'idea per arrivare direttamente al risultato potrebbe essere quella di 
scegliere le 256 stringhe equidistanti come posizione es:
65536/256 = 256 selezionando quelle in posizione:
128,384,640.......65408, ma....
In quale modo sono state generate le stringhe? se ad es. hai 
semplicemente scritto i numeri da 1 a 65536 in binario, non si puo' fare
perche' la distribuzione degli "0" e degli "1" non e' omogenea.
Ogni volta che si arriva ad una potenza di 2, un bit "1" ne sostituisce 
molti altri.
Cosa succede se la libreria fosse invece generata in codice Gray ?
Non lo so, ma mi piacerebbe se qualcuno verificasse....


Ciao, Nino

salvare il sistema. :o(  Ci riprovero' cercando di velocizzare il calcolo.
Darwin Machine??? Intendi con quel termine l'implementazione di un
algoritmo genetico? Allora non sono l'unico pazzo!!!   ;-))
Stimolato dai tuoi risultati ono andato a rispolverare la mia Darwin
Machine, adattandola al problema dei Gini, e finora ho ottenuto un
ridotto con media 13.511673
16 256
15 4078
14 25682
13 34447
12 1073
1073 combinazioni realizzano 12 punti => non e' un triridotto.
Credo sia l'attuale record. Lo posto, cosi' controllate anche voi,
(e potete usarlo per inizializzare le vostre Darwin Machine).
Saluti,
        iant
0101110101001101
0011000111001110
0100101100001001
0111111000100000
0110100011001010
1011000100110101
1111010111011001
0100010100000000
1101011111010101
0110011101011000
1110010010111110
0011101111011011
1100100001101000
0110011111101011
0011010010000011
1110010100111011
1101111111101001
1111111001000011
0001110010101001
0100111111010011
0010101010110000
0000011111101010
0000100010100100
1011011001010000
1001011100110001
1000111000100101
1110100101000111
1101001001000110
0011001011010110
0111001010001000
0010010010011000
1011101001011110
0111100111011100
0101110001000011
0001011001111110
1000001111110011
0011011110000111
0010011000001110
0011101010100011
0001011100001000
1000110001100110
0110110001110111
1011101010001011
0100000111110100
0001101010111111
1110001110011010
1011110001101000
0010011000001011
0101010111110000
0111110001111010
0000000000111011
0001011101111000
0001010100011010
0101001010011101
1011001011110111
1001110111100100
1010011000100000
1011110100000111
1000101010111110
0001100100110001
0010010100101110
0111001001111010
1010101010000111
1111010101111101
0001100101010110
0010111101111000
1110101000111000
1001000100101101
0001101111000000
0001010011110010
0011000001001111
1000110010011001
1110110110000010
1101010101100111
0111111101000100
1110110010010011
0101000010010001
1110101011001100
1100100111100111
0010110111000101
0111100100000111
0101000101110010
1001001110100010
0110011111100110
1110010011111100
1010100100110010
1100110110101011
0111000100111011
0011100011000100
0101111011001110
1110100100100000
1000010110001000
1011000101000010
0010111100110011
0111001100110111
1100111100110111
0101011110111000
0110011101110001
0000101110101111
1001111101001101
1001000001100001
0010011011111101
1101011101101011
0110110011011011
0000001101000101
1110010000011111
1001111010000000
1000010000011100
0000010101011001
0001011001100111
1111000011100001
0110111110001100
0010101111100011
0010110000010101
1010100101111110
0111000000101001
0111100100010001
1110001100001100
1001100101011000
0100100011110111
1111011111010010
1001010111111111
1011100000011010
1111101110010101
1100110101111101
0100000100010100
0110000100100100
1111001011101100
0001100000100110
1100011011111111
1010010111001100
0101101101110100
1101111000010111
0000011010101101
0011000100010000
1000000110001111
0110101111101110
0001001011000100
0000011000010110
0110000111000000
1000000000111000
1000110011010101
1001010100110111
0011001110000110
0001101101101010
1010000110000001
1111110000001010
1000111011001111
1100001001010000
1101001110000110
0111011000001001
0111010110010111
0011010000111100
1101011110100001
1111110100101111
0100010011001000
0111111010111001
1110110101010001
1110000001000010
0101000001011100
0010001100011101
0000111111011100
1111110110100110
1011101101101000
0011000110111001
1101111000111001
1101000110001101
1011010100010110
1000010011000001
0000000000000011
1110101101001011
1011011011111011
0110001110100011
0010000011101010
1110100100010011
1111000001010011
1100101010000011
0011011111000001
0101111001000000
1111011100100110
0011010110011101
1011110111001011
0100110110010010
0011100110011111
0100100111111110
0010111011011111
1001111100110011
0110111110101001
1010011101010110
1101100011111101
1000001110110101
1000000101111001
1100000001001011
1100010001100100
0000101101001010
0010001000110001
1101111100011110
1111000110101111
1011110110110101
1001101001111001
0110001000101110
1010100011111001
1110110011100010
1100111001101010
0100000000001100
0100001101011111
0100010010110010
1101100110111000
1011111110111100
1001100000001000
0110111000010100
0010100001010010
0010110101100011
1111101111011001
0000111110011010
0011111101111101
0001110110110100
1001000011010010
1101010011001110
1100110110110101
0100011011100111
1100111011010110
0101101000110111
1010001001100111
0010000111101100
1011111011110111
0100001001110010
0111101001100101
0001110010000000
0011011010100100
1011011100000101
0000110101011110
1100101001111001
1000001011101000
0101001011111011
0101001000011010
1011000111101011
1111101111110010
0101000110001011
0100101011011001
0000110111110000
0010101101101001
1101011000000011
0101010010101101
1000101100010100
1111100010110100
1101110010011100
1010011110111010
1100000100101111
1101111000110110
1110011010000101
0100111100101100
1010000001001101
1110100000101101
1001000010111110
0011110111101110


A me Gray ricorda solo l'unità di misura della dose di radiazione
ionizzante assorbita....
Ciao, Nino

> altrui! ;-)))
Vero, ho costruito un macinino che analizza un file ascii come questi.
Ho anche tentatto di scrivere per esteso quest'ultimo di Nino, ma mi
si incrociano gli occhi. Facciamo cosi', se vi va: voi scrivete per
esteso il file di 256 righe e io lo metto nel macinino.  :o)
(Prometto di farlo per ogni sistemino che vi venga in mente!)
Ciao!!!  ((^__^))'
Livio

 ridotto con media 13.511673
Ora vado ad esaminarlo!
Ciao!!!  ((^__^))'
Livio

 >
Grazie, Nino


Infatti
Ho trovato 16 colonne con inversioni;
prego tenere conto di questo sviluppo
e non considerare il precedente:

1 0 1 0 1 0 1 1 1 1 1 1 0 0 1 0
1 0 1 0 1 0 1 1 1 1 1 1 1 1 0 1
1 0 1 0 1 0 1 1 0 0 0 0 0 0 1 0
1 0 1 0 1 0 1 1 0 0 0 0 1 1 0 1
1 0 1 0 1 0 0 0 1 1 0 0 0 0 1 0
1 0 1 0 1 0 0 0 1 1 0 0 1 1 0 1
1 0 1 0 1 0 0 0 0 0 1 1 0 0 1 0
1 0 1 0 1 0 0 0 0 0 1 1 1 1 0 1
0 1 0 1 1 0 1 1 1 1 1 1 0 0 1 0
0 1 0 1 1 0 1 1 1 1 1 1 1 1 0 1
0 1 0 1 1 0 1 1 0 0 0 0 0 0 1 0
0 1 0 1 1 0 1 1 0 0 0 0 1 1 0 1
0 1 0 1 1 0 0 0 1 1 0 0 0 0 1 0
0 1 0 1 1 0 0 0 1 1 0 0 1 1 0 1
0 1 0 1 1 0 0 0 0 0 1 1 0 0 1 0
0 1 0 1 1 0 0 0 0 0 1 1 1 1 0 1
1 0 0 1 0 1 1 1 1 1 1 1 0 0 1 0
1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 1
1 0 0 1 0 1 1 1 0 0 0 0 0 0 1 0
1 0 0 1 0 1 1 1 0 0 0 0 1 1 0 1
1 0 0 1 0 1 0 0 1 1 0 0 0 0 1 0
1 0 0 1 0 1 0 0 1 1 0 0 1 1 0 1
1 0 0 1 0 1 0 0 0 0 1 1 0 0 1 0
1 0 0 1 0 1 0 0 0 0 1 1 1 1 0 1
0 1 1 0 0 1 1 1 1 1 1 1 0 0 1 0
0 1 1 0 0 1 1 1 1 1 1 1 1 1 0 1
0 1 1 0 0 1 1 1 0 0 0 0 0 0 1 0
0 1 1 0 0 1 1 1 0 0 0 0 1 1 0 1
0 1 1 0 0 1 0 0 1 1 0 0 0 0 1 0
0 1 1 0 0 1 0 0 1 1 0 0 1 1 0 1
0 1 1 0 0 1 0 0 0 0 1 1 0 0 1 0

Scusate di nuovo
Nino

Cosa succede se la libreria fosse invece generata in codice Gray ?
Sai che l'idea non e' male? Se ho un po' di tempo ci provo e ti
faccio sapere.
A presto,
           Antonio
 

è un lavoro improbo e dal risultato incerto). [...]
Ho sviluppato e controllato il tuo sistema.
16 256
15 4096
14 25856
13 35328
Vincita media: 13.53125
Semplicemente S-T-R-A-O-R-D-I-N-A-R-I-O, record di vincita media
e garanzia del 13!
Intanto il mio programma dopo una giornata di duro lavoro e'
arrivato solo a garanzia del 12 (per 928 colonne) e vincita
media 13.517532. A conferma del fatto che una solida base
teorica e' ancora uno strumento potentissimo!
Ancora complimenti e a presto,
                                iant
Posto qui di seguito lo sviluppo del ridotto record di Nino:

1111000101010011
1111001001101100
1111001001100011
1111000110101100
1111000110100011
1100111010011100
1100111010010011
1100110101011100
1100110101010011
1100111001101100
1100111001100011
1100110110101100
1100110110100011
0011111010011100
0011111010010011
0011110101011100
0011110101010011
0011111001101100
0011111001100011
0011110110101100
0011110110100011
1010101010100001
1010101010101110
1010100101100001
1010100101101110
1010101001010001
1010101001011110
1010100110010001
1010100110011110
0101101010100001
0101101010101110
0101100101100001
0101100101101110
0101101001010001
0101101001011110
0101100110010001
0101100110011110
1001011010100001
1001011010101110
1001010101100001
1001010101101110
1001011001010001
1001011001011110
1001010110010001
1001010110011110
0110011010100001
0110011010101110
0110010101100001
0110010101101110
0110011001010001
0110011001011110
0110010110010001
0110010110011110
1010101111110010
1010101111111101
1010100000110010
1010100000111101
1010101100000010
1010101100001101
1010100011000010
1010100011001101
0101101111110010
0101101111111101
0101100000110010
0101100000111101
0101101100000010
0101101100001101
0101100011000010
0101100011001101
1001011111110010
1001011111111101
1001010000110010
1001010000111101
1001011100000010
1001011100001101
1001010011000010
1001010011001101
0110011111110010
0110011111111101
0110010000110010
0110010000111101
0110011100000010
0110011100001101
0110010011000010
0110010011001101
1111111111111000
1111111111110111
1111110000111000
1111110000110111
1111111100001000
1111111100000111
1111110011001000
1111110011000111
0000111111111000
0000111111110111
0000110000111000
0000110000110111
0000111100001000
0000111100000111
0000110011001000
0000110011000111
1100001111111000
1100001111110111
1100000000111000
1100000000110111
1100001100001000
1100001100000111
1100000011001000
1100000011000111
0011001111111000
0011001111110111
0011000000111000
0011000000110111
0011001100001000
0011001100000111
0011000011001000
0011000011000111
1111111010100100
1111111010101011
1111110101100100
1111110101101011
1111111001010100
1111111001011011
1111110110010100
1111110110011011
0000111010100100
0000111010101011
0000110101100100
0000110101101011
0000111001010100
0000111001011011
0000110110010100
0000110110011011
1100001010100100
1100001010101011
1100000101100100
1100000101101011
1100001001010100
1100001001011011
1100000110010100
1100000110011011
0011001010100100
0011001010101011
0011000101100100
0011000101101011
0011001001010100
0011001001011011
0011000110010100
0011000110011011
1010010000001010
1010010000000101
1010011111001010
1010011111000101
1010011100111010
1010011100110101
1010010011111010
1010010011110101
0101010000001010
0101010000000101
0101011111001010
0101011111000101
0101011100111010
0101011100110101
0101010011111010
0101010011110101
1001100000001010
1001100000000101
1001101111001010
1001101111000101
1001101100111010
1001101100110101
1001100011111010
1001100011110101
0110100000001010
0110100000000101
0110101111001010
0110101111000101
0110101100111010
0110101100110101
0110100011111010
0110100011110101
1010011010011001
1010011010010110
1010010101011001
1010010101010110
1010011001101001
1010011001100110
1010010110101001
1010010110100110
0101011010011001
0101011010010110
0101010101011001
0101010101010110
0101011001101001
0101011001100110
0101010110101001
0101010110100110
1001101010011001
1001101010010110
1001100101011001
1001100101010110
1001101001101001
1001101001100110
1001100110101001
1001100110100110
0110101010011001
0110101010010110
0110100101011001
0110100101010110
0110101001101001
0110101001100110
0110100110101001
0110100110100110

 ...
Ecco il mio report sui tuoi dati, che ho gia' visto coincidente
con quello di Antonio:
***********************************
Vincita media = 13.53125
Punti/Colonne
 16:    256
 15:    4096
 14:    25856
 13:    35328
 12:    0
 11:    0
 10:    0
***********************************
Sono basito! Non ci posso credere!
Nino batte computer... alla grande!
Complimentoni!!!  ((^__^))'
Livio

 prima di procedere alla scelta di un'altra word?
Lo avevo inizialmente fatto, ma il programma si bloccava presto. Questo
perché avevo imposto il vincolo che almeno le 16 word da 15 punti dovessero
essere marcate tutte. Rimuovendo questo vincolo e marcando quelle da 13 le
cose migliorano. Nel tempo in cui prima arrivavo a 13.480+, adesso arrivo a
13.490+. Allego le word che danno questo risultato, se potessero essere
ancora utili a qualcuno.
Ciao :-)
Giorgio
0000000000000000
0000000011110101
0000000111101010
0000001011011111
0000001111010100
0000010011001001
0000010110111110
0000011010110011
0000011110101000
0000100010011101
0000100110010010
0000101010000111
0000101101111100
0000110001110001
0000110101100110
0000111001011011
0000111101010000
0001000001000101
0001000100111010
0001001000101111
0001001100100100
0001010000011001
0001010100001110
0001011000000011
0001011011111000
0001011111101101
0001100011100010
0001100111010111
0001101011001100
0001101111000001
0001110010110110
0001110110101011
0001111010100000
0001111110010101
0010000010001010
0010000101111111
0010001001110100
0010001101101001
0010010001011110
0010010101010011
0010011001001000
0010011100111101
0010100000110010
0010100100100111
0010101000011100
0010101100010001
0010110000000110
0010110011111011
0010110111110000
0010111011100101
0010111111011010
0011000011001111
0011000111000100
0011001010111001
0011001110101110
0011010010100011
0011010110011000
0011011010001101
0011011110000010
0011100001110111
0011100101101100
0011101001100001
0011101101010110
0011110001001011
0011110101000000
0011111000110101
0011111100101010
0100000000011111
0100000100010100
0100001000001001
0100001011111110
0100001111110011
0100010011101000
0100010111011101
0100011011010010
0100011111000111
0100100010111100
0100100110110001
0100101010100110
0100101110011011
0100110010010000
0100110110000101
0100111001111010
0100111101101111
0101000001100100
0101000101011001
0101001001001110
0101001101000011
0101010000111000
0101010100101101
0101011000100010
0101011100010111
0101100000001100
0101100100000001
0101100111110110
0101101011101011
0101101111100000
0101110011010101
0101110111001010
0101111010111111
0101111110110100
0110000010101001
0110000110011110
0110001010010011
0110001110001000
0110010001111101
0110010101110010
0110011001100111
0110011101011100
0110100001010001
0110100101000110
0110101000111011
0110101100110000
0110110000100101
0110110100011010
0110111000001111
0110111100000100
0110111111111001
0111000011101110
0111000111100011
0111001011011000
0111001111001101
0111010011000010
0111010110110111
0111011010101100
0111011110100001
0111100010010110
0111100110001011
0111101010000000
0111101101110101
0111110001101010
0111110101011111
0111111001010100
0111111101001001
1000000000111110
1000000100110011
1000001000101000
1000001100011101
1000010000010010
1000010100000111
1000010111111100
1000011011110001
1000011111100110
1000100011011011
1000100111010000
1000101011000101
1000101110111010
1000110010101111
1000110110100100
1000111010011001
1000111110001110
1001000010000011
1001000101111000
1001001001101101
1001001101100010
1001010001010111
1001010101001100
1001011001000001
1001011100110110
1001100000101011
1001100100100000
1001101000010101
1001101100001010
1001101111111111
1001110011110100
1001110111101001
1001111011011110
1001111111010011
1010000011001000
1010000110111101
1010001010110010
1010001110100111
1010010010011100
1010010110010001
1010011010000110
1010011101111011
1010100001110000
1010100101100101
1010101001011010
1010101101001111
1010110001000100
1010110100111001
1010111000101110
1010111100100011
1011000000011000
1011000100001101
1011001000000010
1011001011110111
1011001111101100
1011010011100001
1011010111010110
1011011011001011
1011011111000000
1011100010110101
1011100110101010
1011101010011111
1011101110010100
1011110010001001
1011110101111110
1011111001110011
1011111101101000
1100000001011101
1100000101010010
1100001001000111
1100001100111100
1100010000110001
1100010100100110
1100011000011011
1100011100010000
1100100000000101
1100100011111010
1100100111101111
1100101011100100
1100101111011001
1100110011001110
1100110111000011
1100111010111000
1100111110101101
1101000010100010
1101000110010111
1101001010001100
1101001110000001
1101010001110110
1101010101101011
1101011001100000
1101011101010101
1101100001001010
1101100100111111
1101101000110100
1101101100101001
1101110000011110
1101110100010011
1101111000001000
1101111011111101
1101111111110010
1110000011100111
1110000111011100
1110001011010001
1110001111000110
1110010010111011
1110010110110000
1110011010100101
1110011110011010
1110100010001111
1110100110000100
1110101001111001
1110101101101110
1110110001100011
1110110101011000
1110111001001101
1110111101000010
1111000000110111
1111000100101100
1111001000100001
1111001101111011
1111111110110111


Figurati che a me ricorda solo il nome di una cera per pavimenti! Però sono
andato a vedere di cosa si tratta. E' interessante, potete guardare qui:
http://www.nist.gov/dads/HTML/graycode.html
 .
Ho provato a infilarlo nel mio programma, ma le cose non migliorano, anzi
peggiorano. Ma
ormai non è più questo il punto. Il risultato di Nino, io non lo raggiungo
più! :-)
Ciao :-)
Giorgio


Ringrazio tutti dei complimenti, ma il risultato
non deve meravigliare, in questo campo è normale
battere la macchina, se non è istruita bene....
D'altronde, come sistemista di bi- e tri-ridotti
sono veramente scarso e non mi sembra di aver fatto
un'opera d'arte ;-)
Per fortuna, in questo NG non bazzicano specialisti
come F. Santisi e F. Di Pasquale, che saprebbero
certamente fare meglio.
Nino


Penso sia un metodo sicuramente efficace, anche se le mie scarse
conoscenze non mi consentono di afferrare il meccanismo pratico di
esecuzione. Dubito infine, almeno per quanto attiene la specie umana,
che questa filosofia abbia sempre a condurre ad una evoluzione....
Ciao, Nino

 piů! :-)
Piu' che battere record e' una mia curiosita', ad intuito ci dovrebbe 
essere una regolarita' nella posizione del gruppo di colonne che formano 
un riduttore in una libreria di stringhe generate con un criterio che 
tenga presente la distrubuzione dei segni. Allora ho fatto una prova 
all'incontrario. Ho generato (col metodo riflesso) le 128 7-tuple di 2^7 
in un codice Gray, poi sono andato a vedere che posizione occupano le 16
stringhe del classico riduttore n-1 di 7 doppie... Sorpresa!? vediamo:
0000000 -A
0000001
0000011 ---B
0000010
0000110
0000111
0000101
0000100
0001100 ---B      ***
0001101           ***
0001111 -A
0001110
0001010
0001011
0001001
0001000
0011000
0011001 -A
0011011
0011010 ---B
0011110
0011111
0011101
0011100
0010100
0010101 ---B
0010111
0010110 -A
0010010
0010011
0010001
0010000
0110000 ---B
0110001
0110011 -A
0110010
0110110
0110111
0110101
0110100
0111100 -A
0111101
0111111 ---B
0111110
0111010
0111011
0111001
0111000
0101000
0101001 ---B
0101011           ***
0101010           ***
0101110
0101111
0101101
0101100
0100100
0100101 -A
0100111
0100110 ---B
0100010
0100011
0100001
0100000
1100000
1100001
1100011
1100010
1100110 -A
1100111
1100101 ---B
1100100
1101100
1101101
1101111
1101110
1101010 ---B
1101011
1101001 -A
1101000
1111000
1111001
1111011
1111010
1111110
1111111 -A
1111101
1111100 ---B
1110100
1110101
1110111
1110110
1110010
1110011 ---B
1110001           ***
1110000 -A        ***
1010000
1010001
1010011
1010010
1010110 ---B      ***
1010111           ***
1010101 -A
1010100
1011100
1011101
1011111
1011110
1011010 -A
1011011
1011001 ---B
1011000
1001000
1001001
1001011
1001010
1001110
1001111 ---B
1001101
1001100 -A
1000100
1000101
1000111
1000110
1000010
1000011 -A
1000001
1000000 ---B
Ho scelto a caso 2 dei classici riduttori di 7 doppie.
Il primo riduttore e' segnato come A, i salti (contando le words 
comprese fra queste) sono 9,6,9,6,5,10,5,10,9,6,9,6,5,10,5
Nel secondo riduttore B, si contano: 5,10,5,6,9,6,9,10,5,10,5,6,9,6,9 il 
palindromo di quella sopra!
Gli asterischi invece intercettano le 8 stringhe di un biridotto.
Bhe' una certa regolarita' c'e'.

battere la macchina, se non è istruita bene....
Nino, sono lieto di annunciarti che, partendo dalla tua soluzione,
il mio programma e' stato in grado di spingere un pelino piu' in la'
l'attuale record.
A mio modo di vedere, questa e' una degli migliori conferme di
quanto sostieni: occorre istruire bene la macchina!
Il nuovo record e':
16 256
15 4096
14 25872
13 35312
Vincita media 13.531494
Il nuovo ridotto si ottiene dal tuo sostituendo due sole colonne:
1001011100000010  con  1001011110000011    e
0000110101100100  con  0000100101100101
Pertanto, se sei d'accordo, direi che la paternita' di questo
record e' 254/256 tua e 2/256 mia  ;-)))
Un caro saluto,
                 iant


Facciamo metà per uno, va bene? ;-))
Ciao, Nino

 Non hai mai pensato di proporlo sul mercato?
No, non ho mai pensato di proporlo sul mercato. L'ho scritto 6-7
anni fa per diletto personale e credo sia giusto farlo rimanere
in quell'ambito. Oltretutto essendo basato su un metodo non
deterministico, non sarebbe possibile dare alcuna garanzia a priori
sul risultato, e questo lo rende improponibile sul mercato.
Ti ringrazio comunque per l'apprezzamento!
A presto,
           iant


Peccato, inserendo primati esistenti potrebbe magari migliorarne
qualcuno (ricordandosi sempre di mettere la paternità congiunta
con il precedente detentore  ;-))
Saluti tristi (per la clamorosa sconfitta del Milan)
Nino

con il precedente detentore  ;-))
Quello si puo' sempre fare nell'ambito del diletto.
Solo che io ho sempre trovato siti che indicavano i risultati
ottenibili con i ridotti record, e mai IL ridotto in se'.
Se per caso tu ne hai sottomano qualcuno...  ;-)
(Io sono piu' interessato ai ridotti tipo Totogol o SuperEnalotto
 cioe' legati a concorsi del tipo "indovina k numeri su un totale
 di n", che trovo matematicamente piu' affascinanti del Totocalcio.)
Saluti,
        iant

  di n", che trovo matematicamente piu' affascinanti del Totocalcio.)
In questo caso si parla di "Covering Design" ecco alcuni siti che 
tengono i migliori risultati finora conseguiti:
http://www.ccrwest.org/cover.html
http://www.xs4all.nl/~rbelic/mainpage.htm
http://www.algonet.se/~peteros/index.htm
http://mladenmalik.www1.50megs.com/wheels7.html

  di n", che trovo matematicamente piu' affascinanti del Totocalcio.)
Dal punto di vista matematico non mi esprimo. Invece, come tipo di
gioco e convenienza pratica, secondo me, non c'è partita (a favore
del totocalcio). Non ti sei mai chiesto perchè questi giochi casuali
(lotto in primis) furoreggiano? A parte lo specchietto per le allodole
del premio elevatissimo (e immorale...), è perchè per "dare i numeri"
non occorre fatica ed approfondimento, e, in questo campo, Einstein e
lo scemo del villaggio sono sullo stesso piano.
Un po' come il successo per "Affari tuoi" di Bonolis.
Nel frattempo, ho effettuato queste altre sostituzioni:
1010010011111010   con   1010010001111011
0011111010011100   con   0011101010011101
1100000101101011   con   1100010101101010
e la vincita media diventa 13,532227.
Ho provato altre modifiche, ma mentre la vincita media aumenta, non
resta più la garanzia minima del 13.
Ciao a tutti e Buona Pasqua
Nino

e la vincita media diventa 13,532227.
Ho applicato le sostituzioni al record in mio possesso e ho ottenuto
13.532211 anziche' 13,532227, quindi c'e' qualche altra colonna
diversa tra il tuo e il mio. Potresti postare il tuo record?
Ciao e buone feste anche a te,
                                iant


http://mladenmalik.www1.50megs.com/wheels7.html
Era da un paio d'anni che non andavo a vedere quei siti. In
particolare l'ultimo non lo conoscevo proprio, e proprio li' ci
sono molti ridotti disponibili per il download.
Grazie per le segnalazioni!
Ciao,
      iant


Iant,
Anche in algonet ci sono molti sistemi scaricabili, basta cliccare nei 
bottoni numerati nella parte alta dello schermo.
L'archivio disponibile piu' fornito, pero' e' a La Jolla, l'universita' 
di San Diego, (primo sito) ma in questo momento sembra non connettersi.
ciao


0000000000000000

1111011010010010
1111000101011100
1111000101010011
1111001001101100
1111001001100011
1111000110101100
1111000110100011
1100111010011100
1100111010010011
1100110101011100
1100110101010011
1100111001101100
1100111001100011
1100110110101100
1100110110100011
0011101010011101
0011111010010011
0011110101011100
0011110101010011
0011111001101100
0011111001100011
0011110110101100
0011110110100011
1010101010100001
1010101010101110
1010100101100001
1010100101101110
1010101001010001
1010101001011110
1010100110010001
1010100110011110
0101101010100001

0101100000111101
0101101100000010
0101101110001100
0101100011000010
0101100011001101
1001011111110010
1001011111111101
1001010000110010
1001010000111101
1001011110000011

0011000000110111
0011001100001000
0011001100000111
0011000011001000
0011000011000111
1111111010100100
1111111010101011
1111110101100100
1111110101101011
1111111001010100
1111111001011011
1111110110010100
1111110110011011
0000111010100100
0000111010101011
0000100101100101
0000110101101011
0000111001010100
0000111001011011
0000110110010100
0000110110011011
1100001010100100
1100001010101011
1100000101100100
1100010101101010
1100001001010100
1100001001011011
1100000110010100
1100000110011011
0011001010100100
0011001010101011
0011000101100100
0011000101101011
0011001001010100
0011001001011011
0011000110010100
0011000110011011
1010010000001010
1010010000000101
1010011111001010
1010011111000101
1010011100111010
1010011100110101
1010010001111011
1010010011110101
0101010000001010
0101010000000101
0101011111001010
0101011111000101
0101011100111010
0101011100110101
0101010011111010
0101010011110101
1001100000001010
1001100000000101
1001101111001010
1001101111000101
1001101100111010
1001101100110101
1001100011111010
1001100011110101
0110100000001010
0110100000000101
0110101111001010
0110101111000101
0110101100111010
0110101100110101
0110100011111010
0110100001110100
1010011010011001
1010011010010110
1010010101011001
1010010101010110
1010011001101001
1010011001100110
1010010110101001
1010010110100110
0101011010011001
0101011010010110
0101010101011001
0101010101010110
0101011001101001
0101011001100110
0101010110101001
0101010110100110
1001101010011001
1001101010010110
1001100101011001
1001100101010110
1001101001101001
1001101001100110
1001100110101001
1001100110100110
0110101010011001
0110101010010110
0110100101011001
0110100101010110
0110101001101001
0110101001100110
0110100110101001
0110100110100110
Come vedi, ho tolto la tua ultima 0110101010011111
che sembra peggiorare un po' la vincita media.
Per le altre tue domande e osservazioni, a domani
Ciao, Nino


Paradossalmente, potrei considerarmi anch'io un po' affine ;-)
Ciao, Nino

Paradossalmente, potrei considerarmi anch'io un po' affine ;-)
Lungi da me iniziare uno di quei periodici, inutili e noiosi thread
sui ritardi nel lotto, che alla fine non riescono a convincere chi
non si riesce a convincere da solo che i numeri non hanno memoria,
e di contro avvelenano il clima nel newsgroup.
Mi fa pero' piacere leggere quel "paradossalmente" tra le tue parole! 
;-))
Un caro saluto,
                 iant

Fammi sapere se stiamo parlando di cose analoghe.
Ciao Livio. Ho letto il tuo articolo gia' diversi giorni fa, ma
solo ora ho avuto un po' di tempo per risponderti con calma.
Direi che di sicuro stiamo parlando di cose analoghe, cioe' di
metodi di ricerca guidati dall'introduzione di una componente
casuale nelle soluzioni che via via si esplorano.
Non credo pero' che stiamo parlando proprio della stessa cosa.
Per poter parlare di algoritmo evoluzionistico occorre infatti
capire in che modo si fa intervenire il caso nella ricerca della
soluzione, cioe' in che modo si prendono in prestito i meccanismi
della selezione naturale.
Sulle prime mi sembra che il metodo di cui parli tu sia un
metodo di ricerca casuale nello spazio delle soluzioni (noto
in letteratura come "Random Search"), e la selezione naturale
interviene solo nel fatto che si scelgono le soluzioni migliori.
Gli algoritmi genetici invece prendono a prestito anche i
meccanismi biologici che sono alla base della selezione naturale.
In particolare i meccanismi principali a cui mi riferisco sono 4:
a. Ogni individuo e' rappresentato solo ed esclusivamente dal
   proprio DNA, relativamente alla possibilita' di tramandare
   le proprie caratteristiche ai figli.
b. La bonta' di un DNA si verifica "sul campo". Cioe' se un DNA ha
   generato un individuo adatto o inadatto lo decidera' solo la
   relazione dell'individuo con l'ambiente e la pressione selettiva
   da esso esercitata, e alla fine solo i piu' adatti sopravviveranno.
c. I caratteri degli individui piu' adatti vengono tramandati ai
   figli mediante operazioni di incrocio (crossover) dei DNA dei
   due genitori.
d. Esiste la possibilita' di mutazione di singoli elementi del DNA
   che occasionalmente puo' far emergere individui con caratteri-
   stiche diverse da quelle dei propri genitori, e che occasional-
   mente puo' renderli piu' adatti alla sopravvivenza.
Detto questo, in due parole gli algoritmi genetici funzionano cosi':
1. Si istituisce un metodo di codifica delle soluzioni come
   stringhe di bit, una sorta di "DNA", nel senso che data una
   particolare stringa io ottengo una ben precisa soluzione
   (e viceversa).
2. Si genera a caso una "popolazione", cioe' un insieme di stringhe
   di bit che rispettino la codifica del punto 1.
3. Si decodificano le stringhe di bit generando le rispettive
   soluzioni, e si valuta la bonta' di ciascuna di esse semplicemente
   verificando il grado di soluzione che danno al problema. In gergo
   si dice che si applica a tutti gli individui della popolazione
   una "funzione di valutazione" (che e' quella da ottimizzare!). 
4. Si selezionano le soluzioni migliori, diciamo A e B, e si generano
   altre soluzioni mediante crossover tra i rispettivi DNA, cioe'
   spezzando le due stringhe di bit in un punto e incrociandole. Es
   A ->  110010101110
   B ->  010101110011
   le spezzo al quarto bit:
   A ->  1100  10101110
   B ->  0101  01110011
 
   e genero due nuovi individui A' e B' effettuando il "crossover"
   A' ->  1100  01110011
   B' ->  0101  10101110
   Siccome ogni bit rappresenta una certa caratteristica del genitore,
   A' e B' avranno in se', mescolati, i caratteri dei genitori e forse
   possono essere ancora piu' adatti a risolvere il problema.
   L'operatore crossover, in sostanza, e' volto a creare 
   miglioramenti di soluzioni in prossimita' di quelle trovate
   in precedenza, e quindi tende a trovare ottimi locali.
5. Occasionalmente una mutazione di uno o piu' bit (inversione di
   valore 0-1) nella stringa di un individuo, puo' far si' che questo
   abbia caratteristiche molto diverse dal genitore.
   L'operatore mutazione e' volto a esplorare nuove porzioni dello
   spazio di ricerca, e quindi tende a sbloccare il sistema dagli 
   ottimi locali.
Per dirla con il gergo dell'ottimizzazione, il metodo degli algoritmi
genetici ottiene un buon equilibrio tra "exploration" dello spazio di
ricerca ed "exploitation" delle buone soluzioni che via via si vanno
trovando.
Per una descrizione piu' approfondita e per esempi concreti di 
applicazione basta cercare qualcosa con Google, la rete e' piena
di siti che parlano dell'argomento, ad esempio:
http://www.cs.colostate.edu/~genitor/MiscPubs/tutorial.pdf
Se vuoi posso anche mandarti via email un ebook di circa 6.5Mb
sull'argomento.
Sono sicuro che se sei rimasto sorpreso dai risultati della Random
Search, rimarrai stupefatto dall'applicazione degli algoritmi
genetici!
Un caro saluto,
                  iant
P.S.: Nello specifico del problema dei Gini, non e' necessario passare
alla codifica in quanto il problema e' gia' posto in termine di
stringhe di bit. E' quindi sufficiente generare una popolazione di
possibili ridotti e poi far evolvere quella popolazione con i
meccanismi che ti ho descritto.

 ...
Mi fa piacere vedere che finalmente c'e' fermento sull'argomento.
IMHO tutti questi metodi si basano sul concetto clou del darwinismo
che possiamo sintetizzare con il ciclo:
A) Mutazione casuale
B) Selezione naturale
A supporto di questo concetto base possiamo cercare di rubare
alla natura altri meccanismi biologici, una volta che pero' ne abbiamo
compreso l'utilita' in un certo contesto e abbiamo speranze che
l'utilita' continui nel nostro contesto specifico.
Prendiamo ad esempio il meccanismo che chiami "crossover".
Che cosa rappresenta? Scimmiotta in qualche modo l'effetto che
in natura si ha con la riproduzione sessuata, metodo che e' stato
evidentemente favorito dall'evoluzione stessa essendo presente
(con numero sessi = 2) nella stragrande maggioranza delle specie
di una certa complessita', mentre la sua diffusione e' minore nelle
riproduzione di organismi relativamente semplici. (Ma quanto sono
relativamente semplici rispetto ad una nostra equazione?).
Per applicare quindi un tale metodo, mi farei prima alcune domande,
tipo "perche' le specie di una certa complessita' si riproducono
in modo sessuato?" e "perche i sessi sono sempre su base 2?"
(A parte un racconto di Isaac Asimov, non ho in mente alcuna
trattazione sulla possibilita' di una vita basata sulla triade anziche'
sulla coppia, sebbene in qualche caso dovrebbe pur avere qualche
vantaggio, forse con complessita' ancora maggiori).
L'unica risposta ragionevole che io abbia trovato alle domande
suddette e' che in natura c'e' il "rumore" che genera un certo
"tasso d'errore" nella "trasmissione" delle informazioni (DNA),
quello stesso rumore che genera l'invecchiamento. La riproduzione
sessuata con n=2 minimizza statisticamente l'effetto negativo del
rumore senza avere una grande ridondanza che ostacolerebbe la
mutazione casuale.
Se questa e' la risposta, allora c'e' da chiedersi che utilita' ci
darebbe una riproduzione sessuata (crossover) nella risoluzione
delle nostre equazioni, in cui la "trasmissione" e' cosi' pulita
che se vogliamo introdurre una mutazione, il rumore lo dobbiamo
fare noi.
Ciao!!!  ((^__^))'
Livio

 in modo sessuato?"
Evidentemente la Natura benigna ha voluto unire l'utile al dilettevole
:-)
ciao
paolo

fare noi.
Dal punto di vista algoritmico l'utilita' del crossover e' quella
di far si' che due soluzioni localmente buone possano generare una
soluzione globalmente buona.
(Se hai la pazienza di leggere il tutorial di cui ti ho dato il link,
 troverai anche il cosiddetto teorema dello Schema, che fornisce una
 spiegazione matematica del come e del perche' il crossover riesce ad
 essere efficace).
A titolo di esempio, nel problema dei Gini se tu hai due ridotti che
coprono bene due parti diverse del sistema integrale e li incroci tra
loro, e' possibile che i ridotti emergenti coprano l'integrale meglio
dei due da cui provenivano. E questo puo' avvenire molto piu'
rapidamente che non aspettando mutazioni casuali che portino un buon
ridotto a migliorare.
Come ti dicevo nel post precedente, gli AG realizzano una strategia
mista di grande efficacia tra lo sfruttamento delle buone soluzioni
che si vanno via via trovando, grazie al crossover, e l'esplorazione
incessante dello spazio di ricerca, grazie alla mutazione.
Nella mia esperienza personale l'usuale andamento dell'evoluzione di
un AG e' questo: all'inizio si trovano molte soluzioni che evolvono
rapidamente ed e' la fase in cui agisce molto il crossover. Poi ci
sono delle fasi di stasi in cui gli incroci non portano miglioramenti
(minimi locali), ed e' in queste fasi che l'unica possibilita' di
miglioramento e' affidata alla mutazione che e' in grado di portare
in una zona non esplorata in precedenza. Non appena viene trovata una
soluzione migliore se ne trovano subito in rapida sequenza delle altre
perche' rientra in gioco il crossover e cosi' via. Naturalmente 
l'andamento dell'evoluzione tende a diventare sempre piu' lento man
mano che le soluzioni trovate migliorano, e i miglioramenti stessi
sono sempre piu' lievi.
Spero di aver almeno in parte risposto alle tue perplessita'...
A presto,
          iant