Distanza di Hamming.
Ciao a tutti, riporto il testo dell'esercizio in inglese (sono diventato troppo pigro per tradurre):
Let $X$ be the set of all ordered triples of zeros and ones. Show that $X$ consists of eight elements and a metric $d$ on $X$ is defined by \(\displaystyle d(x, y) = \text{number of places where x and y have different entries} \).
Sequenze ripetute di due elementi da tre si calcolano dalla combinatoria elementare come $2^3=8$. La distanza proposta è sicuramente definita positiva, e nulla solo se $x$ e $y$ non differiscono per alcuna cifra, ovvero $x=y$. Anche la simmetria è evidente. Resta quindi la solita disuguaglianza triangolare: intuitivamente se una tripla dista da un altra $n$, allora per ottenere una dall'altra devo cambiare esattamente $n$ cifre; se considero un'altra tripla come step intermedio del cambiamento, e le due distanze fra essa e le triple originarie combinate fossero un numero minore di $m$, sarebbe possibile ottenere la seconda dalla prima con meno di $m$ cambi.
Tuttavia non so come rendere questo discorso adeguatamente matematicoso, se non provando a piazzare qualche simbolo. Secondo voi posso già considerare concluso l'esercizio con questo ragionamento?
Let $X$ be the set of all ordered triples of zeros and ones. Show that $X$ consists of eight elements and a metric $d$ on $X$ is defined by \(\displaystyle d(x, y) = \text{number of places where x and y have different entries} \).
Sequenze ripetute di due elementi da tre si calcolano dalla combinatoria elementare come $2^3=8$. La distanza proposta è sicuramente definita positiva, e nulla solo se $x$ e $y$ non differiscono per alcuna cifra, ovvero $x=y$. Anche la simmetria è evidente. Resta quindi la solita disuguaglianza triangolare: intuitivamente se una tripla dista da un altra $n$, allora per ottenere una dall'altra devo cambiare esattamente $n$ cifre; se considero un'altra tripla come step intermedio del cambiamento, e le due distanze fra essa e le triple originarie combinate fossero un numero minore di $m$, sarebbe possibile ottenere la seconda dalla prima con meno di $m$ cambi.
Tuttavia non so come rendere questo discorso adeguatamente matematicoso, se non provando a piazzare qualche simbolo. Secondo voi posso già considerare concluso l'esercizio con questo ragionamento?
Risposte
Beh, mi pare semplice.
Fondamentalmente, hai:
\[
\operatorname{d}(x,y) = |x_1-y_1| + |x_2-y_2| + |x_3-y_3|\; ,
\]
cioè \(\operatorname{d}\) è una distanza $L^1$.
Fondamentalmente, hai:
\[
\operatorname{d}(x,y) = |x_1-y_1| + |x_2-y_2| + |x_3-y_3|\; ,
\]
cioè \(\operatorname{d}\) è una distanza $L^1$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo