338
правок
Изменения
Нет описания правки
{{Определение
|definition=
'''Расстояние Хэмминга (Hamming distance)''' {{---}} число позиций, в которых различаются соответствующие символы двух строк одинаковой длины различны. }}
В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых k-ичных алфавитов и служит [[Метрическое пространство#def1 | метрикой]] различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности.
[[Файл:Hamming.JPG|thumb|180px|3-битный бинарный куб для нахождения расстояния Хэмминга]]
#<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>xyx</tex>и <tex>y</tex> на прямой, которая их соединяет). Это свойство обычно называют неравенством треугольника за его естественную геометрическую аналогию: сумма двух сторон треугольника всегда больше третьей стороны.)''
== Доказательство неравенства треугольника ==
