Изменения

Перейти к: навигация, поиск

Расстояние Хэмминга

104 байта добавлено, 06:20, 4 ноября 2011
Нет описания правки
''Расстояние Хэмминга'' обладает свойствами метрики, так как удовлетворяет ее [[Метрическое пространство#def1 | определению]].
#<tex>~d(x, y) = 0 \iff x = y</tex> ''(Если расстояние от '''<tex>x''' </tex> до '''<tex>y''' </tex> равно нулю, то '''<tex>x''' </tex> и '''<tex>y''' </tex> совпадают ('''<tex>x''' равно '''= y'''</tex>))''#<tex>~d(x,y)=d(y,x)</tex> ''(Объект '''<tex>x''' </tex> удален от объекта '''<tex>y''' </tex> так же, как объект '''<tex>y''' </tex> удален от объекта '''<tex>x'''</tex>)''#<tex>~d(x,y) \le d(x,z) + d(z,y)</tex> ''(Расстояние от '''<tex>x''' </tex> до '''<tex>y''' </tex> всегда меньше или равно расстоянию от '''<tex>x''' </tex> до '''<tex>y''' </tex> через точку '''<tex>z''' </tex> (равенство достигается только в том случае, если точка '''<tex>z''' </tex> принадлежит отрезку '''<tex>xy'''</tex>). Это свойство обычно называют неравенством треугольника за его естественную геометрическую аналогию: сумма двух сторон треугольника всегда больше третьей стороны.)''
== Доказательство неравенства треугольника ==
II. Рассмотрим два варианта, когда <tex>x = y</tex> (1) и <tex>x \ne y</tex> (2):
#Пусть '''x <tex>x =y</tex> y''', тогда '''<tex>d = 0''' </tex> (по свойству №1), так как <tex>d(x,z)</tex> и <tex>d(z,y)</tex> не могут быть меньше нуля, значит их сумма также неотрицательна <tex>(0 \le d(x,z) + d(z,y))</tex>, следовательно неравенство <tex>~d(x,y) \le d(x,z) + d(z,y)</tex> выполняется.#Пусть слова '''<tex>x''' </tex> и '''<tex>y''' </tex> отличаются в некоторой позиции '''<tex>t'''</tex>. Тогда какое бы слово '''<tex>z''' </tex> мы ни взяли, оно в этой позиции будет отличаться по крайней мере от одного из слов '''<tex>x''' </tex> и '''<tex>y'''</tex>. Следовательно, суммируя в правой части <tex>~d(x, z)</tex> и <tex>~d(z, y)</tex>, мы обязательно учтем все позиции, в которых различались слова '''<tex>x''' </tex> и '''<tex>y'''</tex>.
Все неравенства выполняются, значит, их сумма тоже, ч.т.д.}}
338
правок

Навигация