Pagina 1 di 1

Scambio di sequenze simili

Inviato: 25 gen 2010, 20:47
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 !!).

Inviato: 25 gen 2010, 23:34
da fph
$ \log_2\, $, I presume?

Inviato: 25 gen 2010, 23:37
da rand
Yes...

Inviato: 25 gen 2010, 23:56
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.

Inviato: 26 gen 2010, 17:09
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 $.

Inviato: 26 gen 2010, 18:25
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 ...

Inviato: 26 gen 2010, 19:35
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.

Inviato: 27 gen 2010, 18:03
da rand
HINT: una specie di ricerca binaria e controllo di parità

Inviato: 27 gen 2010, 18:17
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.