Se osserviamo un cubo e consideriamo 2 vertici lungo una diagonale, come nella figura seguente, gli altri 6 vertici sono "vicini", ovvero collegati con un solo passo a uno dei 2 vertici precedenti. Diciamo allora che un insieme formato da 2 vertici lungo una diagonale costituisce un codice C, detto anche insieme dominante minimo.
Possiamo rappresentare il cubo tramite la seguente grafica che dà un'idea migliore di come il codice può essere rappresentato.
Il problema di trovare un codice è dunque facile da risolvere nel caso del cubo (ipercubo 3-dimensionale), ma cosa succede se la dimensione spaziale aumenta?
L'ipercubo 4 dimensionale di 16 vertici
Possiamo rappresentare l'ipercubo 4-dimensionale (e in generale n-dimensionale) preparandoci cosi ad un repentino aumento della dimensione spaziale come nella figura seguente: ci sono 16 vertici numerati da 0 a 15distribuiti in 5 livelli.
Nella figura è rappresentato l'ipercubo 4-dimensionale a sinistra e a destra il codice ricoprente: in verde sono le sue parole. I segmenti, anche essi verdi, collegano le parole del codice ai restanti vertici dell'ipercubo di colore bianco.
Il codice è C = {0,1,14,15}. Ha 4 parole con somma 30. Tutti i codici hanno tale somma
La formula rispettata è (2^n-1)*(b/2) con n = hyper dim and b = numero parole del codice.
sostituendo i valori si ha: (2^4-1)*(4/2) = 15*2 = 30.
Si noti che tutti i vertici bianchi sono "toccati" da almeno uno dei segmenti verdi e ciò accade solo se C è un codice. Se non lo fosse uno o più nodi bianchi sarebbero isolati o scoperti.
0 copre 1,2,4,8 (in binario: 0000 copre 0001,0100,0010,1000)
1 copre 0,3,5,9 (in binario: 0001 copre 0000,0011,0101,1001)
14 copre 6,10,12,15 (in binario: 1110 copre 0110,1010,1100,1111)
15 copre 7,11,13,14 (in binario. 1111 copre 0111,1011,1101,1110).
0 copre 1,2,4,8 (in binario: 0000 copre 0001,0100,0010,1000)
1 copre 0,3,5,9 (in binario: 0001 copre 0000,0011,0101,1001)
14 copre 6,10,12,15 (in binario: 1110 copre 0110,1010,1100,1111)
15 copre 7,11,13,14 (in binario. 1111 copre 0111,1011,1101,1110).
0 in binario si scrive 0000 e quindi si trova a livello 0
1,2,4,8 si scrivono 0001, 0010, 0100, 1000 e sono a livello 1.
3,5,9,6,10,12 si scrivono 0011, 0101,1001,0110,1010,1100 e sono a livello 2.
7,11,13,14 si scrivono 0111,1011,1101,1110 e sono a livello 3.
15 si scrive 1111 ed è a livello 4.
I vicini di un nodo sono i nodi a lui collegati ovvero i nodi con un solo bit differente in notazione binaria: ad esempio il nodo 15 (1111) ha come vicino il nodo 14 (1110), 13 (1101), 11(1011) e 7 (0111).
I nodi indicati in verde 0,1,14,15 costituiscono un codice C per l'ipercubo 4-dim: lo si capisce in quanto l'unione insiemistica tra {0,1,14,15} e l'insieme dato da tutti i vicini di ognuno di essi {1,2,4,8,0,3,5,9,6,10,12,15,7,11,13,14} dà come risultato un insieme che contiene almeno una volta tutti i vertici dell'ipercubo.
Quanto vale la somma S delle parole del codice?
Qui il bound è pari cosi vi sarà un solo valore possibile per S.
Formula: S = (2^n-1) * (b/2) = (2^4-1) * (4/2) = 15*2 = 30.
Tutti i codici hanno somma S = 30.
Il codice della figura infatti ha S = 0+1+14+15=30.
L'ipercubo 5 dimensionale di 32 vertici
Un caso un pò più complesso è l'ipercubo 5-dimensionale: 32 vertici e codici C da 7 parole.(Perchè 7? Per approfondimenti vedere la tabella dei lower e upper bound: http://www.sztaki.hu/~keri/codes/ o http://www.eng.tau.ac.il/~litsyn/tablecr/)
Il codice C è il seguente: C = {2,5,14,22,24,25,27}.
Quanto vale la somma S delle parole del codice?
Qui il bound è dispari e quindi vi sarà un intervallo di valori per S.
Formula (2^n-1) * (b/2) calcola un intervallo chiuso [a,b] dove
a = (2^5-1) * inf (7/2) = 31*3 = 93, con inf 7/2 primo numero naturale < 3,5.
b = (2^5-1) * sup (7/2) = 31*4 = 124, con sup 7/2 primo numero naturale > 3,5.
Cosi i codici avranno tutti somma S tra 93 e 124.
Quello illustrato in figura ha S = 2+5+14+22+24+25+27=119.L'ipercubo 6 dimensionale di 64 vertici
L'ipercubo di 6 dimensioni ha 64 vertici. Il codice ha 12 parole con somma 378.
Questa sembra una regola generale (anche se non so se vi sia un teorema che lo dimostri).
La formula rispettata è (2^n-1)*(b/2) con n = hyper dim and b = numero parole del codice.
sostituendo i valori si ha: (2^6-1)*(12/2) = 63*6 = 378 (il numero magico).
Finora tutti i codici calcolati dal mio algoritmo (varie decine) hanno 378 come somma delle parole.
Ciò non è prova sicura che la somma di tutti i codici sia 378 però.
Infatti il numero di combinazioni è 64 binomiale 12 (il numero di sottoinsiemi possibili di 12 elementi presi da 64 elementi) ovvero un grande numero: 3.284.214.703.056 (oltre 3 mila miliardi) e fra tutti questi alcuni (pochi in percentuale) sono codici con raggio di copertura 1. Potrebbe esserci una piccola parte di essi con somma diversa da 378. Sarei contento di trovarne o riceverne uno anche se ciò minerebbe una mia quasi certezza personale.
Il seguente è un esempio di codice C con somma 378: C = {3,8,19,20,29,30,37,38,40,47,51,56}
Quanto vale la somma S delle parole del codice?
Qui il bound è pari cosi vi sarà un solo valore possibile per S.
Formula: S = (2^n-1) * (b/2) = (2^6-1) * (12/2) = 63*6 = 378.
Tutti i codici hanno somma S = 378.
Il codice della figura infatti ha S = 3+8+19+20+29+30+37+38+40+47+51+56 = 378.
L'ipercubo 7 dimensionale di 128 vertici
Se la dimensione è 7 l'ipercubo ha 128 nodi e la formula della somma è ancora rispettata: S = (2^7-1)*(16/2) = 127*8 = 1016. Accade anche che il codice è perfetto nel senso che ogni nodo dell'ipercubo che non appartiene al codice è "toccato" solo una volta dai link verdi o rossi (si veda la figura seguente)
Quanto vale la somma S delle parole del codice?
Qui il bound è pari cosi vi sarà un solo valore possibile per S.
Formula: S = (2^n-1) * (b/2) = (2^7-1) * (16/2) = 127*8 = 1016.
Tutti i codici hanno somma S = 1016.
Il codice della figura infatti ha S = 2+5+25+30+40+47+51+52+75+76+80+87+97+102+122+125 = 1016
L'ipercubo 8 dimensionale di 256 vertici
Il seguente codice, ottenuto a partire dal precedente per l'ipercubo di 7 dimensioni e a cui si sono aggiunte 16 parole non casuali (126,127,...) come input per l'algoritmo di calcolo, è stato calcolato in un paio di secondi e ha le prime 16 parole coincidenti col codice precedente.
C = {2, 5, 25, 30, 40, 47, 51, 52, 75, 76, 80, 87, 97, 102, 122, 125, 134, 139, 144, 157, 161, 172, 183, 186, 197, 200, 211, 222, 226, 239, 244, 249}
Vi sono quattro cose interessanti da osservare:
1) Ancora una volta la somma delle parole rispetta la formula sulla somma.
S = (2^8-1) * (32/2) = 255*16 = 4080.
S = 2+ 5+ 25+ 30+ 40+ 47+ 51+ 52+ 75+ 76+ 80+ 87+ 97+ 102+ 122+ 125+ 134+ 139+ 144+ 157+ 161+ 172+ 183+ 186+ 197+ 200+ 211+ 222+ 226+ 239+ 244+ 249 = 4080
2) Ci sono esattamente 32 nodi con coefficiente di copertura pari a 2, cioè lo stesso numero delle parole del codice. I restanti 224 nodi hanno cdc=1.
3) Nessuno dei nodi dell'ipercubo con cdc=2 (quelli colorati in magenta nella figura seguente) appartengono al codice C.
4) La somma S' dei nodi con cdc pari a 2 è uguale anche essa a 4080. Cioè S = S'.
Quanto vale la somma S delle parole del codice?
Il bound è pari cosi vi sarà un solo valore possibile per S.Formula: S = (2^n-1) * (b/2) = (2^8-1) * (32/2) = 255*16 = 4080.Tutti i codici hanno somma S = 4080.Il codice della figura infatti ha S = 2+5+25+30+40+47+51+52+75+76+80+87+97+102+122+125+134+139+144+157+161+172+183 +186+197+200+211+222+226+239+244+249 = 4080.
L'ipercubo 9 dimensionale di 512 vertici
Questo ipercubo ha codici C di 62 parole in accordo alle ricerche di pochi anni fa (Il primo codice di 62 parole di Raspanti Alessio fu calcolato nel 1996 poco dopo la sua tesi di laurea nella quale si riportava l'allora conosciuto bound di 64 parole invece del 62 da lui stesso scoperto pochi giorni dopo tramite un algoritmo di sua invenzione scritto in linguaggio C e girante su un 486 DX 2).
Quanto vale la somma S delle parole del codice?
Qui il bound è pari cosi vi sarà un solo valore possibile per S.
Formula: S = (2^n-1) * (b/2) = (2^9-1) * (62/2) = 511*31 = 15841.
Tutti i codici hanno somma S = 15841? La risposta questa volta è negativa.
Formula: S = (2^n-1) * (b/2) = (2^9-1) * (62/2) = 511*31 = 15841.
Tutti i codici hanno somma S = 15841? La risposta questa volta è negativa.
S = 4+6+7+13+14+15+50+53+57+60+83+88+96+97+106+127+144+145+154+163+168+191+197+203+204+214+221+230+237+244+246+257+264+283+299+304+306+310+317+322+329+340+341+350+359+364+386+393+407+412+420+421+430+448+450+463+497+499+504+505+ 506+507 = 15830.
Vi è quindi una differenza di 11 rispetto al valore suggerito dalla formula. Ciò dimostra che essa non è più valida per l'ipercubo di 9 dimensioni.
Un pò difficoltoso è ora esaminare la figura? Si perchè per ogni incremento dimensionale i nodi raddoppiano!
Cosi abbiamo finora esaminato ipercubi con dimensione da 3 a 9: il numero dei nodi è 8,16,32,64,128,256,512.
La cosa inaspettata è che nel 1996 il minimo numero di parole del codice di copertura di raggio 1 per l'ipercubo 9-dimensionale si credeva cadere in [54,64].
Con 64 parole si formula era rispettata in generale e cioè la somma delle parole del codice è S = (2 ^ n-1) * (b / 2) = (2 ^ 9-1) * (64/2) = 511 * 32 = 16352 e ciò mi indusse a pensare che 64 fosse il minimo.
Ma un giorno provando con 63 parole ecco che la euristica degli scambi sistematici aveva calcolato un codice.
Il quale aveva pure un nodo ridondante, un nodo che poteva essere eliminato dal codice che dunque possedeva solo 62 parole.
Per concludere: nessun codice con 63 parole sembra esistere, l'algoritmo trova sempre un nodo ridondante.
I codici con 62 parole in generale non rispettano la formula della somma.
La teoria ha poi dimostrato che 62 è il minimo effettivo. Prima di ciò l'input con 61 nodi porta al massimo coperture di 506 su 512 nodi, il 98.82% dell'ipercubo. Ciò con pochi secondi di computazione usando gli attuali computer (siamo nel 2014, nel 1996 le cose erano differenti).
L'ipercubo 10-dimensionale con 1024 vertici
Qui iniziano le difficoltà anche con i moderni calcolatori. Si suppone che il minimo cada nell'intervallo [107,120], ma in realtà dovrebbe essere 120 o forse 119.
Ho calcolato molti codici con 120 parole e l'algoritmo impiega tempi dell'ordine dei minuti solitamente.
Ancora una volta la formula della somma non è valida in generale.
S = (2 ^ n-1) * (b / 2) = (2 ^ 10-1) * (120/2) = 1023 * 60 = 61380, ma i codici trovati hanno somme diverse.
Ma la vera questione è: è veramente 120 il minimo numero di parole di un codice in grado di coprire tutti i 1024 nodi?
Ho provato con input di 119 nodi: in alcuni minuti mediamente si ottengono insiemi che coprono l'ipercubo con una percentuale di 1022 su 1024 (99,804%): è come salire su un'alta montagna la cui vettà è li a pochi passi ma poi risulta irraggiungibile. Perchè?
Perchè dopo aver trovato una copertura di 1022 su 1024 nessun miglioramento è mai avvenuto in anni di tentativi (dal 1996 al 2013)
L'anno scorso ho avuto un enorme sorpresa: il 23 maggio 2013 alle 03:24 è stato calcolato (e da allora non è più successo) un insieme incredibile di 119 elementi (da me chiamato il "quasi codice") che è in grado di ricoprire ben 1023 nodi (99,902%) su 1024.
Centinaia di tentativi sono stati fatti in seguito ma mai si è arrivati a tale risultato.
Il calcolo di un insieme di 119 nodi avvenuto nel 2013, che copre 1023 nodi su 1024 è l'unico significativo miglioramento rispetto al 1996: i risultati finora esposti per gli ipercubi fino a 9 dimensioni li avevo trovati allora e sono stati confermati ultimamente con eleboratori più potenti (dal 486 dx2 del 1996 al pentium xxx del 2013-2014).
In effetti non ha importanza, o meglio ha importanza relativa, l'uso di elaboratori anche 10 volte più veloci nell'eseguire i calcoli se l'algoritmo di ricerca è ben progettato ed efficiente.
Infatti il numero di sottoinsiemi di 119 elementi ottenibili dall'ipercubo di 1024 nodi è
(1024 119) = 2,3974883870271410533826039235738e+158 ovvero circa 2,4 * 1 seguito da 158 zeri: un numero talmente grande da "ridicolizzare" anche i moderni elaboratori.
L'insieme di 119 elementi che ne copre 1023 fu calcolato dopo circa due settimane di computazione (con un pentium del 2003) ovvero dopo aver esaminato potenzialmente 3 mila miliardi di insiemi: 3.000.000.000.000 = 3 * 1 seguito da 12 zeri. Ma questo è solo una percentuale minima della totalità: lo 1,25 *10 alla -144%.
In sostanza è "bastato" esaminare una minima percentuale dei casi possibili per trovare un insieme che copre 1023 nodi, ciò fa supporre che forse esistono (pochi ma esistono) insiemi che arrivano a coprire 1024 nodi con solo 119 elementi.
La ricerca continua ... per arrivare la dove nessuno è mai giunto prima (to boldly go where no one has gone before).
Recentemente (ottobre 2014) il programma sta girando dal 21 settembre (da tre settimane) e ha esaminato
Infatti il numero di sottoinsiemi di 119 elementi ottenibili dall'ipercubo di 1024 nodi è
(1024 119) = 2,3974883870271410533826039235738e+158 ovvero circa 2,4 * 1 seguito da 158 zeri: un numero talmente grande da "ridicolizzare" anche i moderni elaboratori.
L'insieme di 119 elementi che ne copre 1023 fu calcolato dopo circa due settimane di computazione (con un pentium del 2003) ovvero dopo aver esaminato potenzialmente 3 mila miliardi di insiemi: 3.000.000.000.000 = 3 * 1 seguito da 12 zeri. Ma questo è solo una percentuale minima della totalità: lo 1,25 *10 alla -144%.
In sostanza è "bastato" esaminare una minima percentuale dei casi possibili per trovare un insieme che copre 1023 nodi, ciò fa supporre che forse esistono (pochi ma esistono) insiemi che arrivano a coprire 1024 nodi con solo 119 elementi.
La ricerca continua ... per arrivare la dove nessuno è mai giunto prima (to boldly go where no one has gone before).
Recentemente (ottobre 2014) il programma sta girando dal 21 settembre (da tre settimane) e ha esaminato
4.500.000.000.000 (4,5 mila miliardi) insiemi con 119 nodi ... il miglior risultato trovato è la copertura di 1022 su 1024 nodi. In realtà mi aspettavo che il programma trovasse almeno un altro insieme che coprisse 1023 nodi dell'ipercubo, ma era una speranza ed è rimasta tale.
Cosi, quanti potrebbero essere gli insiemi da 119 nodi che coprono 1023/1024 nodi dell'ipercubo 10-dim?
Vorrei ricordare che il numero totale di insiemi da 119 nodi è (1024 119) ~= 2,3975*10 ^ 158. Cosi, se supponiamo che ve ne sia uno (che copre 1023 nodi) ogni n (sconosciuto) migliaia di miliardi ...
