User:Lopoc/minimum string
From UIC
well... il bello del brutto tempo( scusate la stupida battuta) è che non potendo uscire si pensa a problemi più o meno inutili :)
Contents |
Il problema
Dato un insieme S di simboli (ad esempio i caratteri a disposizione per la creazione di una pasword)
S = { a, A, c, 1, 2 , ... , z, Z} //un esempio come un'altro
|S| = cardinalità dell'insieme S // numero di simboli a disposizione
e un intero L = lunghezza di una sottostringa
qual'è la lunghezza minima N di simboli tale che le sue sottostringhe di lunghezza L siano tutte le possibili disposizioni(le volgari combinazioni con ripetizioni) di S di lunghezza L?
E una volta calcolato questo N come si può procedere alla costruzione di questo set?
Prime considerazioni
Il numero totale di disposizioni di lunghezza L su un insieme di |S| elementi è:
c = |S|^L
Il numero di sottostringhe di lunghezza L in una stringa di lunghezza N con L < N è:
m = N-L+1
vogliamo una stringa lunga N (incognito) le cui sottostringhe di lunghezza L siano tutte le possibili disposizioni di lunghezza L sull'insieme S
quindi poniamo:
m = c
da cui
|S|^L = N-L+1
quindi N:
N = |S|^L + L -1
questo è la lunghezza minima possibile sotto la quale non sarebbe possibile immagazzinare in questo modo l'informazione voluta. Pertanto chiameremo d'ora in poi questo valore Nmin
Dimostrazioni utili
ESISTE almeno una stringa di lunghezza N le cui sosttostringhe siano TUTTE le disposizioni di lunghezza L sull'insieme dei simboli S.
Dimostrazione
basta concatenare tutte le possibili disposizioni. questo comporta una lunghezza della stringa pari a:
N = |S|^L * L //numero di disposizioni per la lunghezza di ogni disposizione
prendiamo questo come soluzione banale del problema e la sua lunghezza come limite superiore alla lunghezza della stringa cercata
Sia la stringa di lunghezza N le cui sottostringhe di lunghezza L sono tutte le disposizioni di lunghezza L sull'insieme dei simboli S, essa contine anche tutte le disposizioni di lunghezza minore di L sull'insieme dei simboli S.
dimostrazione
le disposizioni di Lunghezza L possono essere ricorsivamente generate concatenando tutto gli elementi dell'insieme dei simboli S con le disposizioni di lunghezza L-1 sull'insieme S. Pertando esiste un passo della ricorsione tale che L-1 sia pari alla lunghezza delle sottostringhe cercate.
Congetture
Supposto che la stringa voluta sia di lunghezza pari al limite inferiore già trovato:
N = |S|^L+L-1 che chiameremo Nmin
confrontandolo con la stringa data dalla concanetazione di tutte le disposziozioni di lunghezza L la cui lunghezza è:
N = |S|^L*L che chiameremo Nmax
volendo sapere qual'è il risparmio in termini di spazio necessario ad immagazzinare queste due stringhe, definiamo R come il rapporto fra le lunghezze
R = Nmin/Nmax
R = (|S|^L+L-1)/(|S|^L*L)
sia L << |S|^L
otteniamo
R ~= (|S|^L)/(|S|^L*L) = 1/L
valore che per numeri alti di L comporta un risparmio davvero notevole
Problemi simili
Dopo varie ricerche ho trovato diverse campi in cui tale problema è un problema reale! Uno è nel sequenziamento del DNA, oppure è studiato per l'implemaentazione di algoritmi di compressione. la questione aperta è: il problema è dimostrato essere NP-hard ma lo è nel caso di stringhe di dimensione qualunque con na distribuzione random o quasi... nel nostro caso abbiamo una set di strinhe di lunghezza fissa L ed esistenti in tutte le configurazioni possibili...
Altro
Brain-storming
- Grafi
- Cammino Hamiltoniano (NP-Completo)
- SSP: Shortest Superstring Problem
