Una particolare sequenza di bit

Programmazione, algoritmica, teoria dell'informazione, ...
Rispondi
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Una particolare sequenza di bit

Messaggio da rand »

Una sequenza di bit si dice quadrata quando è data dalla concatenazione di due sequenze uguali, ad es.:

00,11, 0101, 000000,...

sono tutte quadrate.
Generare sequenze quadrate non è difficile. Provate invece a dare un algoritmo che dato N genera una sequenza di N bit che non contiene sottosequenze quadrate di lunghezza strettamente maggiore di 2 (quindi può contenere 11 e 00), dimostrando in questo modo anche la sua esistenza. Ad esempio, per N = 5, 01001 è un output valido mentre 01011 non lo è perchè contiene 0101 che è quadrata.
Qual è la migliore complessità sia in tempo che spazio che riuscite a raggiungere con il vostro algoritmo?
MindFlyer

Messaggio da MindFlyer »

Un hint?
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand »

Il problema l'ho formulato in una maniera che un pò confonde, perchè
il fatto è che esiste almeno una sequenza infinita di bit libera da quadrati, cosa però non evidente. Il problema vero è trovare una procedura che la genera un bit alla volta, dopodichè ne deriva una soluzione del problema di sopra che ha tempo lineare e spazio costante.
MindFlyer

Messaggio da MindFlyer »

Certo, che debba esistere una sequenza infinita libera da quadrati si deduce dal tuo enunciato per "compattezza". Il problema, per quanto mi riguarda, è proprio capire come generarla in tempo decente!
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand »

Si, in realtà è più difficile di quanto pensassi! Avevo letto su un libro di algoritmi quella che credevo una soluzione elegante, ma mi sono reso conto che c'è un' incompletezza, e che la soluzione vera è in realta più complessa.
Comunque chi vuol sapere come costruire una sequenza infinita square-free può provare a fare una ricerca in rete sulle Thue-Morse words , un argomento che in realtà è combinatoria e ha poco legame con l'algoritmica in senso stretto.
dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: Una particolare sequenza di bit

Messaggio da dario2994 »

Riesumo per dire che o c'ho un bug o il testo era sbagliato o l'ho letto male...
Perchè con l'ausilio di potenti mezzi dovrei aver trovato tutte le stringhe di cui parla il testo... e in particolare la più lunga è lunga 18 caratteri!
Per gli interessati questo è il codice (c++) (con qualche giochetto idiota con i bit perchè pensavo che dovessi rendere il tutto veloce mentre invece vista la finitezza delle stringhe ciò non serviva! )

Codice: Seleziona tutto

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

const int k=18;

vector <int> belle[k+1];

bool test(int N,int bit){
	for(int l=2;l<=N/2;l++){
		if( (bit & ((1<<l)-1) )== ( (bit>>l) & ((1<<l)-1) ) )return false;
	}
	return true;
}

void aumenta(int it){
	for(int i=0;i<(int)belle[it].size();i++){
		if(test(it+1,(belle[it][i]<<1)))belle[it+1].push_back((belle[it][i]<<1));
		if(test(it+1,(belle[it][i]<<1)+1))belle[it+1].push_back((belle[it][i]<<1)+1);
	}
}

string stampa(int bit,int N){
	string res;
	for(int i=0;i<N;i++)res+=(bit&(1<<i))?'a':'b';
	return res;
}

int main(){
	belle[0].push_back(0);
	for(int i=0;i<k;i++){
		aumenta(i);
	}
	for(int i=0;i<(int)belle[k].size();i++)cout << stampa(belle[k][i],k) << "\n";
	cout << "Totale= " << belle[k].size() << "\n";
	for(int i=0;i<=k;i++)cout << i << ": " << belle[i].size() << "\n";
}
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Rispondi