Изменения

'''Расстояние Хэмминга ''' (англ. ''Hamming distance)''' — ) {{---}} число позиций, в которых различаются соответствующие цифры символы двух двоичных слов строк одинаковой длины различны. }}

*<math>d(10{\<font color{Blue}="blue">1}</font>1{\<font color{Blue}="blue">1}</font>01, 10{\<font color{Red}="red">0}</font>1{\<font color{Red}="red">0}</font>01)=2</math>*<math>d(15{\<font color{Blue}="blue">38}</font>1{\<font color{Blue}="blue">24}</font>, 15{\<font color{Red}="red">23}</font>1{\<font color{Red}="red">56}</font>)=4</math>*<math>d(h{\<font color{Blue}="blue">i}</font>ll, h{\<font color{Red}="red">o}</font>ll)=1</math>

#<tex>~d(x,y) \le leqslant 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>). Это свойство обычно называют неравенством треугольника за его естественную геометрическую аналогию: сумма двух сторон треугольника всегда больше третьей стороны.)''

|statement=<tex>~d(x,y) \le leqslant d(x,z) + d(z,y)</tex>|proof=I. Все позиции независимы.

II. Рассмотрим два варианта, когда <tex>x = y</tex> (1) и <tex>x \ne y</tex> (2):#Пусть <tex>x = y</tex>, тогда <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 \ne y</tex>.а) ''База индукции:'' Пусть слова <tex>x</tex> и <tex>y</tex> отличаются в некоторой позициинекоторых позициях. Тогда какое бы слово <tex>z</tex> мы не ни взяли , оно будет отличатся хотя бы отличаться в каждой из этих позиций по крайне мере от одного из слов <tex>x</tex> или и <tex>y</tex>. А это означаетСледовательно, что неравенство суммируя в правой части <tex>~d(x,y) \le d(x,z) + d(z,y)</tex> выполняется. б) Пусть неравенство и <tex>~d(x,y) \le d(x,z) + d(z,y)</tex> выполняется при <tex>~d(x,y) = k</tex>. <tex>(*)</tex> Докажеммы обязательно учтем все позиции, что оно верно для <tex>~d(x,y) = k + 1</tex>. Для <tex>k</tex> позиций из <tex>k + 1</tex> общее количество отличий в которых различались слова <tex>x</tex> от <tex>z</tex> и слова <tex>y</tex> от <tex>z</tex>, благодаря предположению <tex>(*)</tex>, не меньше, чем количество отличий слова <tex>x</tex> от <tex>y</tex>. Рассмотрим оставшуюся позицию, в которой отличаются слова <tex>x</tex> и <tex>y</tex>Т. Так как какое бы слово <tex>z</tex> мы не взяли оно, в этой позиции, будет отличатся хотя бы от одного из слов <tex>x</tex> или <tex>y</tex>, то неравенство <tex>~d(x,y) \le d(x,z) + d(z,y)</tex> для <tex>~d(x,y) = k + 1</tex> выполняетсяе. Индуктивное предположение вернополучается, значит, неравенство что <tex>~d(x,y) \le leqslant d(x,z) + d(z,y)</tex> выполняется для любого натурального <tex>k</tex> (<tex>k</tex> - количество отличий слова <tex>x</tex> от <tex>y</tex>).

== Ссылки Источники информации ==