Base per serie numerica
Ho una serie numerica (monotona, crescente, più o meno esponenziale) composta da 1601 interi, con valori da 0 a 75010.
Allego un diagramma per facilitare la comprensione della serie.
(Non ho capito come allegare un file di testo, altrimenti avrei allegato anche la serie. Se qualcuno gentilmente me lo spiega, provvedo).
Devo trovare una base numerica che mi permetta di ottenere tutti i valori della serie a partire da un peso in formato binario. Utilizzando una base composta dalle potenze di 2, servirebbero 17 bit per esprimere tutti i valori da 0 a 75010, ma essendo i valori molto più sparsi (sono solo 1601), mi chiedevo se il numero di bit non potrebbe essere inferiore con un opportuna scelta della base (ovviamente dovrebbero essere almeno 11).
Ho pensato alla possibilità di scrivere un programma e andare per tentativi, ma è un po' deprimente. Non esiste un metodo più elegante?
Allego un diagramma per facilitare la comprensione della serie.
(Non ho capito come allegare un file di testo, altrimenti avrei allegato anche la serie. Se qualcuno gentilmente me lo spiega, provvedo).
Devo trovare una base numerica che mi permetta di ottenere tutti i valori della serie a partire da un peso in formato binario. Utilizzando una base composta dalle potenze di 2, servirebbero 17 bit per esprimere tutti i valori da 0 a 75010, ma essendo i valori molto più sparsi (sono solo 1601), mi chiedevo se il numero di bit non potrebbe essere inferiore con un opportuna scelta della base (ovviamente dovrebbero essere almeno 11).
Ho pensato alla possibilità di scrivere un programma e andare per tentativi, ma è un po' deprimente. Non esiste un metodo più elegante?
Risposte
Non so aiutarti con il problema in oggetto ma per quanto riguarda il file di testo, suggerimento: caricalo su servizi come Dropbox, Google Drive, Mega, MediaFire e condividi qui il link pubblico al file, dove aver eventualmente abilitato la condivisione pubblica del file su uno dei servizi di cui sopra qualora di default essa dovesse essere non abilitata.
Nel frattempo ho scritto un programma che esegue una ricerca delle basi.
In circa tre minuti ha eseguito tutta la ricerca, trovando 15 707 192 basi, purtroppo tutte composte da 17 elementi. Sic...
In circa tre minuti ha eseguito tutta la ricerca, trovando 15 707 192 basi, purtroppo tutte composte da 17 elementi. Sic...
Non so gli altri, ma io non ho capito. Perché la base 10 non va bene? Sospetto che per "base" tu non intenda la base descritta qui. Ma allora cosa intendi con "base"?
Inoltre, cosa intendi con "peso in formato binario"?
Inoltre, cosa intendi con "peso in formato binario"?
Mi era sorto il dubbio di non essere stato chiaro...
La serie è composta da n elementi
$S=(s_0, s_1, \ldots \, s_{n-1})$ con $s_i \in \mathbb{N}$
Si richiese che ogni elemento della serie $s_i$ si possa ottenere come
$s_i=a_{i_0} \cdot b_0 + a_{i_1} \cdot b_1 +\ldots + a_{i_{m-1}} \cdot b_{m-1}$
dove
$B=(b_0, b_1, \ldots \, b_{m-1})$ con $b_i \in \mathbb{N}$
è la base, mentre
$A_i= (a_{i_0}, a_{i_1}, \ldots \, a_{i_{m-1}} )$ con $a_{i_j} \in {0, 1}$
è il peso binario.
Spero di non aver usato a sproposito il linguaggio matemetico, e mi scuso per l'iniziale mancanza di chiarezza.
La serie è composta da n elementi
$S=(s_0, s_1, \ldots \, s_{n-1})$ con $s_i \in \mathbb{N}$
Si richiese che ogni elemento della serie $s_i$ si possa ottenere come
$s_i=a_{i_0} \cdot b_0 + a_{i_1} \cdot b_1 +\ldots + a_{i_{m-1}} \cdot b_{m-1}$
dove
$B=(b_0, b_1, \ldots \, b_{m-1})$ con $b_i \in \mathbb{N}$
è la base, mentre
$A_i= (a_{i_0}, a_{i_1}, \ldots \, a_{i_{m-1}} )$ con $a_{i_j} \in {0, 1}$
è il peso binario.
Spero di non aver usato a sproposito il linguaggio matemetico, e mi scuso per l'iniziale mancanza di chiarezza.
Ah, adesso ho capito. La mia intuizione è che a occhio una base formata da potenze di 2 sia la più flessibile in generale, nel senso che se per una certa serie una base formata da potenze di $b ge 3$ minimizza il numero di bit questa risulterebbe più o meno in una coincidenza (come quando hai diverse curve che si intersecano, in generale se prendi un punto a caso non starà nelle intersezioni, ma può succedere). Se invece $B$ può consistere di interi positivi arbitrari (non necessariamente potenze di un numero dato, tipo $2$) allora si può vedere cosa fare, sicuramente proverei con un programmino come hai fatto. Per un problema dato come il tuo non credo valga la pena fare disquisizioni in generale, anche perché tutto dipende molto dall'insieme di dati che hai. Penso che si possano facilmente trovare il "caso peggiore" e il "caso migliore", cioè l'insieme di dati che richiede più bit e quello che richiede meno bit, in qualsiasi (fissata a priori) base, ma non credo che sia questo ad interessarti.
Vediamo se ho capito. Tu hai una successione in uno \(\mathbb{Z}_2\)-spazio vettoriale (di dimensione 17) e vuoi trovare una base del sottospazio generato dagli elementi di quella successione. Giusto?
Se è così si tratta di un problema di algebra lineare. Che metodo hai usato per cercare le basi?
Se è così si tratta di un problema di algebra lineare. Che metodo hai usato per cercare le basi?
Grazie Martino.
Sì, la base può essere composta da numeri interi arbitrari.
Proprio per questo motivo speravo si potesse scendere dalla dimensione 17 (quella che si ottiene con la base composta da potenze di 2).
Purtroppo, il numero 17 è particolarmente "sfigato" (nomen omen) quando dalla carta si passa alla realizzazione fisica di qualcosa legato a questi numeri: trattare 17 bit è molto diverso dal trattarne 16...
Ad ogni modo, mi conforta che la scelta di utilizzare un programma non fosse poi così da "maniscalco matematico".
Sì, la base può essere composta da numeri interi arbitrari.
Proprio per questo motivo speravo si potesse scendere dalla dimensione 17 (quella che si ottiene con la base composta da potenze di 2).
Purtroppo, il numero 17 è particolarmente "sfigato" (nomen omen) quando dalla carta si passa alla realizzazione fisica di qualcosa legato a questi numeri: trattare 17 bit è molto diverso dal trattarne 16...
Ad ogni modo, mi conforta che la scelta di utilizzare un programma non fosse poi così da "maniscalco matematico".
@vic785
Non ci sono numeri negativi, pertanto direi più $\mathbb{N}$ che $\mathbb{Z}$.
Prima di rispondere alla tua prima domanda, devo andare a rivedere alcune cose (io e l'algebra lineare abbiamo litigato ai tempi dell'esame di Geometria e poi non abbiamo più fatto pace...).
Il programma utilizza una funzione ricorsiva che testa ogni elemento della serie con la base di prova. Questa base è settata inizialmente con il singolo elemento 1. Quando un elemento della serie non può essere generato con la base data, il programma spezza la serie in due parti (con tutti gli elementi possibili nella prima, e i restanti nella seconda). A questo punto aggiunge alla base un nuovo elemento scelto tra uno degli interi che vanno dalla somma di tutti gli elementi precedenti +1, al valore del primo elemento della serie che ha fallito il test e viene richiamata ricorsivamente la funzione di test sulla parte restante della serie, con la nuova base.
Allego un diagramma per facilitare la comprensione:
Non ci sono numeri negativi, pertanto direi più $\mathbb{N}$ che $\mathbb{Z}$.
Prima di rispondere alla tua prima domanda, devo andare a rivedere alcune cose (io e l'algebra lineare abbiamo litigato ai tempi dell'esame di Geometria e poi non abbiamo più fatto pace...).
Il programma utilizza una funzione ricorsiva che testa ogni elemento della serie con la base di prova. Questa base è settata inizialmente con il singolo elemento 1. Quando un elemento della serie non può essere generato con la base data, il programma spezza la serie in due parti (con tutti gli elementi possibili nella prima, e i restanti nella seconda). A questo punto aggiunge alla base un nuovo elemento scelto tra uno degli interi che vanno dalla somma di tutti gli elementi precedenti +1, al valore del primo elemento della serie che ha fallito il test e viene richiamata ricorsivamente la funzione di test sulla parte restante della serie, con la nuova base.
Allego un diagramma per facilitare la comprensione:
Per prima cosa \(\mathbb{Z}_2\) non è \(\mathbb{Z}\), ma il campo di elementi \(\{0, 1\}\). La somma è lo XOR e la moltiplicazione è l'AND. Comunque rimane un problema di algebra lineare anche se ci hai litigato.
Detto questo, una considerazione stupida: la tua successione contiene tutte le potenze di due fino a 2048 escluso. Contiene inoltre 16384. Quindi hai già 12 elementi della tua base senza neanche fare calcoli.
A questi puoi aggiungere, per esempio, 2051, 4110, 8206, 32821 e 75010. Non è difficile notare che sono linearmente indipendenti.
Detto questo, una considerazione stupida: la tua successione contiene tutte le potenze di due fino a 2048 escluso. Contiene inoltre 16384. Quindi hai già 12 elementi della tua base senza neanche fare calcoli.
A questi puoi aggiungere, per esempio, 2051, 4110, 8206, 32821 e 75010. Non è difficile notare che sono linearmente indipendenti.
Come vedi, l'errore su $\mathbb{Z}_2$ conferma ciò che dicevo prima.
Ad ogni modo, il problema non era trovare una base, ma vedere se era possibile trovarne una con 16 (o meno) elementi.
La base formata dalle potenze di due con esponente 0-16 è la prima candidata (che ovviamente funziona).
Ce ne sono poi oltre 15 milioni di altre, però tutte di 17 elementi. Purtroppo.
Ad ogni modo, il problema non era trovare una base, ma vedere se era possibile trovarne una con 16 (o meno) elementi.
La base formata dalle potenze di due con esponente 0-16 è la prima candidata (che ovviamente funziona).
Ce ne sono poi oltre 15 milioni di altre, però tutte di 17 elementi. Purtroppo.
Che errore? L'unica correzione che ho fatto è stata di cambiare la moltiplicazione in un AND per non creare confusione tra quella e la moltiplicazione di \(\mathbb{Z}_2[X]\). Ma in \(\mathbb{Z}_2\), la moltiplicazione è quella usuale: \(1\cdot 1 = 1\) e \(0\cdot 0 = 0 \cdot 1 = 1\cdot 0 = 0\).
Comunque, se esiste una base di 17 elementi, non può esisterne una di 16. Te lo dice l'algebra lineare.
Comunque, se esiste una base di 17 elementi, non può esisterne una di 16. Te lo dice l'algebra lineare.
L'errore mio, di aver confuso $\mathbb{Z}_2$ con $\mathbb{Z}$.
Riguardo all'affermazione sulle basi, invece non sono d'accordo (probabilmente perché parliamo di due cose diverse). Faccio un esempio:
La serie (0, 1, 2, 3, 4, 5, 6, 7) ha una come unica possibile base minima (1, 2, 4). Non sono possibili basi con due soli elementi.
Se tolgo alcuni elementi, lasciando ad esempio (0, 1, 7) la base qui sopra permette ancora di ottenere tutti gli elementi rimasti, ma anche con la base (1, 6) si ottiene lo stesso risultato.
Nel banale esempio qui sopra, la cosa si vede "ad occhio", ma nel problema posto all'inizio, con una serie di oltre 1600 elementi e valori da 0 a oltre 77 000, l'evidenza non c'è più.
Sappiamo per certo che bastano 17 valori, dato che $2^17$ è maggiore del valore di ogni elemento della serie, ma non possiamo sapere se anche con soli 16 valori si potrebbe ottenere lo stesso risultato.
Riguardo all'affermazione sulle basi, invece non sono d'accordo (probabilmente perché parliamo di due cose diverse). Faccio un esempio:
La serie (0, 1, 2, 3, 4, 5, 6, 7) ha una come unica possibile base minima (1, 2, 4). Non sono possibili basi con due soli elementi.
Se tolgo alcuni elementi, lasciando ad esempio (0, 1, 7) la base qui sopra permette ancora di ottenere tutti gli elementi rimasti, ma anche con la base (1, 6) si ottiene lo stesso risultato.
Nel banale esempio qui sopra, la cosa si vede "ad occhio", ma nel problema posto all'inizio, con una serie di oltre 1600 elementi e valori da 0 a oltre 77 000, l'evidenza non c'è più.
Sappiamo per certo che bastano 17 valori, dato che $2^17$ è maggiore del valore di ogni elemento della serie, ma non possiamo sapere se anche con soli 16 valori si potrebbe ottenere lo stesso risultato.
Sì, Vict ha ragione, basta calcolare la dimensione dello spazio generato da $S$. 
LucianoD, ti suggerisco di imparare le nozioni base dell'algebra lineare, perché con questo strumento il problema diventa davvero banale.
Basta convertire i numeri in base 2, vederli come vettori binari di lunghezza 17, metterli in una matriciona e calcolarne il rango.
Penso che con "base" LucianoD intenda quello che noi chiameremmo "insieme di generatori" (di uno spazio vettoriale).
LucianoD, ti suggerisco di imparare le nozioni base dell'algebra lineare, perché con questo strumento il problema diventa davvero banale.
Basta convertire i numeri in base 2, vederli come vettori binari di lunghezza 17, metterli in una matriciona e calcolarne il rango.
Penso che con "base" LucianoD intenda quello che noi chiameremmo "insieme di generatori" (di uno spazio vettoriale).
Sic... sentire che mi mancano le basi è un po' deprimente, se non altro perché l'esame a suo tempo lo passai!
Provo ad applicare il procedimento all'esempio che ho fatto sopra.
La matrice binaria per la serie (0, 1, 2, 3, 4, 5, 6, 7) è (ovviamente, dato che è completa)
000
001
010
011
100
101
110
111
Il rango è 3, e fino a qui, tutto bene.
Per la serie (0, 1, 7) si ha
000
001
111
Effettivamente il rango è 2...
Nel caso specifico mi ritroverei con una matrice binaria 17 X 1601. Dovrei poi procedere con l'eliminazione di Gauss e vedere cosa resta. Corretto?
Provo ad applicare il procedimento all'esempio che ho fatto sopra.
La matrice binaria per la serie (0, 1, 2, 3, 4, 5, 6, 7) è (ovviamente, dato che è completa)
000
001
010
011
100
101
110
111
Il rango è 3, e fino a qui, tutto bene.
Per la serie (0, 1, 7) si ha
000
001
111
Effettivamente il rango è 2...
Nel caso specifico mi ritroverei con una matrice binaria 17 X 1601. Dovrei poi procedere con l'eliminazione di Gauss e vedere cosa resta. Corretto?
"LucianoD":Sì, ma ovviamente lo faresti fare a un programma. Inoltre non lo devi fare su $RR$ ma su $ZZ_2$, occhio.
Nel caso specifico mi ritroverei con una matrice binaria 17 X 1601. Dovrei poi procedere con l'eliminazione di Gauss e vedere cosa resta. Corretto?
Beh, certo che lo farebbe un programma: credo sia umanamente impossibile ridurre una matrice 17 X 1601 a mano senza commettere errori!
Applicare Gauss in binario è intrigante... devo trovare il tempo di scrivere questo programma.
Intanto ringrazio entrambi per il supporto!
Applicare Gauss in binario è intrigante... devo trovare il tempo di scrivere questo programma.
Intanto ringrazio entrambi per il supporto!
La notte porta consiglio (e fare algebra lineare a mente, mentre si è a letto, toglie il sonno...).
Credo però di aver (finalmente) compreso ciò che vict85 scriveva nel suo ultimo post. Oltre a questo, ho notato che verificare l'indipendenza lineare in una matrice in $\mathbb{Z}_2$ è un'operazione molto più semplice che in $\mathbb{R}$, al punto che si può anche fare a mente. Ad esempio, tutte le righe
0...01X...X
con X qualsiasi, e l'elemento 1 in posizione diversa sono certamente linearmente indipendenti.
Con la premessa qui sopra ho pensato che la soluzione al mio quesito iniziale è in effetti molto semplice e potrebbe essere espressa in questo modo:
Una volta creata la matrice della serie in $\mathbb{Z}_2$, il numero minimo di elementi della base (dell'insieme di generatori) è dato dal numero di colonne non nulle della matrice.
E' corretto?
Credo però di aver (finalmente) compreso ciò che vict85 scriveva nel suo ultimo post. Oltre a questo, ho notato che verificare l'indipendenza lineare in una matrice in $\mathbb{Z}_2$ è un'operazione molto più semplice che in $\mathbb{R}$, al punto che si può anche fare a mente. Ad esempio, tutte le righe
0...01X...X
con X qualsiasi, e l'elemento 1 in posizione diversa sono certamente linearmente indipendenti.
Con la premessa qui sopra ho pensato che la soluzione al mio quesito iniziale è in effetti molto semplice e potrebbe essere espressa in questo modo:
Una volta creata la matrice della serie in $\mathbb{Z}_2$, il numero minimo di elementi della base (dell'insieme di generatori) è dato dal numero di colonne non nulle della matrice.
E' corretto?
Devi stare attendo ad usare i teoremi di algebra lineare su un \(\mathbb{Z}_2\)-spazio vettoriale. Infatti vari teoremi hanno i campi di caratteristica \(2\) come una eccezione.
Una cosa che devi considerare è che ogni elemento \(\mathbf{v}\) può essere scritto come \(\mathbf{v} = \sum_{i=1}^{n} \delta_i \mathbf{b}_i\) dove \(\delta_i \in \{0,1\}\). Se \(\mathbf{b}_i\) è una base, allora il modo è unico.
Come ho detto, su quei numeri, la somma come spazio vettoriale è lo XOR informatico. Nel tuo caso, le potenze di due sono una base del tuo sottospazio generato, ma non è necessariamente vero. Per esempio \(3\) e \(6\) sono linearmente indipendenti.
A livello informatico, non hai bisogno di usare matrici. Ti basta usare funzioni tipo ctz/BitScanForward spesso disponibili come funzioni intrinseche del compilatore. Il seguente codice C ha bisogno del compilatore gcc o clang. Su visual studio devi usare _BitScanForward che va tra l'altro usato diversamente.
[edit] Avevo fatto un errore nel codice, ho corretto.
Una cosa che devi considerare è che ogni elemento \(\mathbf{v}\) può essere scritto come \(\mathbf{v} = \sum_{i=1}^{n} \delta_i \mathbf{b}_i\) dove \(\delta_i \in \{0,1\}\). Se \(\mathbf{b}_i\) è una base, allora il modo è unico.
Come ho detto, su quei numeri, la somma come spazio vettoriale è lo XOR informatico. Nel tuo caso, le potenze di due sono una base del tuo sottospazio generato, ma non è necessariamente vero. Per esempio \(3\) e \(6\) sono linearmente indipendenti.
A livello informatico, non hai bisogno di usare matrici. Ti basta usare funzioni tipo ctz/BitScanForward spesso disponibili come funzioni intrinseche del compilatore. Il seguente codice C ha bisogno del compilatore gcc o clang. Su visual studio devi usare _BitScanForward che va tra l'altro usato diversamente.
#include "stdio.h"
#include "stdlib.h"
unsigned long
find_rank( unsigned long nums[], unsigned long N )
{
unsigned long rank = 0;
for ( unsigned long i = 0; i != N; ++i )
{
unsigned long ni = nums[ i ];
unsigned long mask = 1u << __builtin_ctz( ni );
if ( ni == 0 )
{
continue;
}
// elemento della base trovato
printf( "%lu\n", ni );
rank++;
for ( unsigned long j = i + 1; j != N; ++j )
{
if ( nums[ j ] & mask )
{
nums[ j ] ^= ni;
}
}
}
return rank;
}
int
main( )
{
#define MAX_SIZE 2000
unsigned long nums[ MAX_SIZE ];
FILE* file = fopen( "Serie.txt", "r" );
if ( !file )
{
perror( "Errore nella lettura del file\n" );
}
int i = 0;
for ( ; i < MAX_SIZE; ++i )
{
if ( fscanf( file, "%lu\n", &nums[ i ] ) != 1 )
{
break;
}
}
printf( "rank: %lu\n", find_rank( nums, i ) );
fclose( file );
#undef MAX_SIZE
}[edit] Avevo fatto un errore nel codice, ho corretto.
Che bel supporto, complimenti!
Sull'uso dell'EXOR in $\mathbb{Z}_2$ non ci sono problemi, è un concetto chiaro. Ho scritto un paio di righe di codice e confermo che ridurre una qualsiasi matrice in questo gruppo è molto più facile che farlo in $\mathbb{R}$.
Osservando il tuo programma, è interessante notare che il problema può essere aggredito in molteplici modi, tutti efficaci. Vorrei avere più tempo per "giocare" un po' di più con questo argomento, ma devo tradurlo in vile lavoro...
Che posso dire... ancora grazie!
Sull'uso dell'EXOR in $\mathbb{Z}_2$ non ci sono problemi, è un concetto chiaro. Ho scritto un paio di righe di codice e confermo che ridurre una qualsiasi matrice in questo gruppo è molto più facile che farlo in $\mathbb{R}$.
Osservando il tuo programma, è interessante notare che il problema può essere aggredito in molteplici modi, tutti efficaci. Vorrei avere più tempo per "giocare" un po' di più con questo argomento, ma devo tradurlo in vile lavoro...
Che posso dire... ancora grazie!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo