Scambio di sequenze simili

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

Scambio di sequenze simili

Messaggio da rand »

Ci sono due persone A e B, che possiedono rispettivamente due sequenze binarie x e y.
Nessuno dei due conosce la sequenza posseduta dall'altro, ma si sa che x e y hanno la stessa lunghezza e differiscono in un solo bit (che è ovviamente ignoto sia ad A che a B).
Dimostrare che mediante una strategia prestabilita A riesce a comunicare x a B inviandogli solo $ \lceil \log_2 n\rceil $bits, dove n è la lunghezza di x o y.
(Notare che questo è il minor numero di bits necessari anche nel caso in cui A conosca in anticipo y !!).
Ultima modifica di rand il 25 gen 2010, 23:36, modificato 1 volta in totale.
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph »

$ \log_2\, $, I presume?
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand »

Yes...
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand »

... precisazione: la comunicazione è a senso unico da A verso B: ossia il tutto si riduce ad A che invia un unico messaggio a B di lunghezza logaritmica. Non è prevista nessuna interazione da B, che può ricevere da A ma non rispondere.
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai »

Lemma: se $ $G=(\{0,1\}^{2^n},E) $ è il grafo ipercubico di dimensione $ $2^n $, allora $ $G'=(\{0,1\}^{2^n},E^2\setminus E) $ ha numero cromatico $ $2^n $.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand »

E' vero, alla fine A e B non fanno altro che colorare un particolare ipergrafo, infatti il lemma è equivalente alla soluzione.

Ma se volete esiste anche un modo elementare e diretto per farlo, che usa al più l'aritmetica modulo 2 ...
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai »

Sì, diciamo che ho parafrasato il testo. :D
La cosa insidiosa è che conviene fare salti di potenze di 2 nell'impostare l'induzione, perché nel caso generale di lunghezza n non sempre basta comunicare un numero tra 0 e n-1 (come uno spererebbe!), ma a volte serve l'intero range di valori fino alla potenza di 2 più vicina.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand »

HINT: una specie di ricerca binaria e controllo di parità
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai »

Comunichiamo nel bit k-esimo la somma mod 2 dei bit della sequenza A la cui posizione scritta in binario ha un 1 come cifra k-esima.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]
Rispondi