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