Scambio di sequenze simili
Scambio di sequenze simili
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 !!).
Ultima modifica di rand il 25 gen 2010, 23:36, modificato 1 volta in totale.
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
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]
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
Sì, diciamo che ho parafrasato il testo.
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.
![Very Happy :D](./images/smilies/icon_biggrin.gif)
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]
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12