Неравенство МакМилана - История изменений

5.8.16.169: Перенаправление на Неравенство Макмиллана

2020-06-14T11:21:29Z

Перенаправление на Неравенство Макмиллана

Proshev в 15:24, 17 января 2012

2012-01-17T15:24:10Z

Krotser: неправильное название страницы

2011-10-30T20:30:50Z

неправильное название страницы

Krotser: Новая страница: «== Необходимые определения == Пусть нам дан '''''алфавит''''', то есть конечное множество, элеме...»

2011-10-30T20:24:30Z

Новая страница: «== Необходимые определения == Пусть нам дан '''''алфавит''''', то есть конечное множество, элеме...»

Новая страница

== Необходимые определения ==
Пусть нам дан '''''алфавит''''', то есть конечное множество, элементы которого называются '''''символами''''' или '''''буквами''''' этого алфавита. '''''Кодом''''' для алфавита <tex>A</tex> называется функция (таблица) <tex>\alpha</tex>, которая для каждого символа <tex>a</tex> из <tex>A</tex> указывает двоичное слово <tex>\alpha(a)</tex>, называемое '''''кодовым словом''''', или просто '''''кодом''''' этого символа. (Двоичное слово - конечная последовательность нулей и единиц.) Не требуется, чтобы коды всех символов имели равные длины.

Хороший код должен позволять декодирование(восстановление последовательности символов по ее коду). Пусть фиксирован алфавит <tex>A</tex> и код <tex>\alpha</tex> для этого алфавита. Для каждого слова <tex>P</tex> в алфавите <tex>A</tex> (то есть для любой конечной последовательности букв алфавита <tex>A</tex>) рассмотрим двоичное слово<tex>\alpha(P)</tex>, которое получается, если записать подряд коды всех букв из <tex>P</tex> (без каких либо разделителей). Код <tex>\alpha</tex> называется '''''однозначным''''', если коды различных слов различны: <tex>\alpha(P)\ne\alpha(P')</tex> при <tex>P\ne{P'}</tex>.
== Неравенство Макмиллана ==
{{Теорема
|statement=
<center>
[http://neerc.ifmo.ru/mediawiki/index.php/%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0 Неравенство Крафта{{---}}Макмиллана] выполняется не только для любого префиксного кода, но и вообще для любого однозначного кода.
</center>
}}
''Примечание: Именно это доказал Макмиллан, Крафт доказал неравенство для префиксных кодов.''
== Доказательство ==
Есть разные способы решить эту задачу, но будет приведено простое и красивое, хотя и несколько загадочное, решение. <br />
Пусть имеется однозначный код с <tex>k</tex> кодовыми словами <tex>P_1,P_2, ..., P_k</tex>. Необходимо доказать, что их длины <tex>n_i=|P_i|</tex> удовлетворяют Неравенству Крафта{{---}}Макмиллана.

Вместо нулей и единиц будем использовать <tex>a</tex> и <tex>b</tex> (из чего составлять коды разницы нет). Запишем формально сумму всех кодовых слов как алгебраическое выражение

<center><tex>P_1+P_2+...P_k</tex></center>

(многочлен от <tex>a</tex> и <tex>b</tex>, в котором одночлены записаны как произведения переменных <tex>a</tex> и <tex>b</tex>, без возведения в степень). Теперь (ещё боле странное на первый взгляд действие) возведём это в степень <tex>N</tex>(произвольное натуральное число) и раскроем скобки, сохраняя порядок переменных(не собирая вместе одинаковые переменные) в одночленах:

<center><tex>(P_1+P_2+...P_k)^N=</tex> сумма одночленов.</center>

Например, для кода со словами <tex>0,10,11</tex> (которые теперь записываются как <tex>a,ba,bb</tex>) и для <tex>N=2</tex> получаем

<center><tex>(a+ba+bb)^2=(a+ba+bb)(a+ba+bb)=aa+aba+abb+baa+baba+babb+bba+bbba+bbbb.</tex></center>

В этом примере все одночлены в правой части различны (если не переставлять переменные), и это не случайно: так будет для любого однозначного кода. В самом деле, по определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов.

Теперь подставим <tex>a=b=\frac{1}{2}</tex> в наше неравенство(если оно верно для букв, то оно верно и для любых их числовых значений). Слева получится

<center><tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_i})^N</tex></center>

(в скобке как раза выражение из неравенства Крафта{{---}}Макмиллана). Правую часть мы оценим сверху, сгруппировав слова пол длинам: имеется не более <tex>2^l</tex> слагаемых длины <tex>l</tex>, каждое из которых равно <tex>2^{-l}</tex>, и потому слагаемые данной длины в сумме не превосходят единицы, а правая часть не превосходит максимальной длины слагаемых, то есть <tex>Nmax(n_i)</tex>. Итак, получаем, что

<center><tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_i})^N<Nmax(n_i)</tex></center>

и это верно при любом <tex>N</tex>. Если основание степени в левой степени больше единицы, то при больших <tex>N</tex> это неравенство нарушится (показательная функция растет быстрее линейной). Поэтому, для однозначного кода выполняется неравенство Крафта-Макмиллана. Что и требовалось доказать.
== Ссылки ==
[[Неравенство Крафта]]
== Литература ==
А. Шень "Программирование: теоремы и задачи" (Издание четвёртое, Москва, Издательство МЦНМО, 2011)

← Предыдущая		Версия 11:21, 14 июня 2020
Строка 1:		Строка 1:
−	[[~~Категория: Удалить~~]]	+	#перенаправление [[Неравенство Макмиллана]]

← Предыдущая	Версия 15:24, 17 января 2012
Строка 1:	Строка 1:
−	+	[[Категория: Удалить]]

← Предыдущая		Версия 20:30, 30 октября 2011
Строка 1:		Строка 1:
−	~~== Необходимые определения ==~~
−	Пусть нам дан '''''алфавит''''', то есть конечное множество, элементы которого называются '''''символами''''' или '''''буквами''''' этого алфавита. '''''Кодом''''' для алфавита <tex>A</tex> называется функция (таблица) <tex>\alpha</tex>, которая для каждого символа <tex>a</tex> из <tex>A</tex> указывает двоичное слово <tex>\alpha(a)</tex>, называемое '''''кодовым словом''''', или просто '''''кодом''''' этого символа. (Двоичное слово - конечная последовательность нулей и единиц.) Не требуется, чтобы коды всех символов имели равные длины.

−	Хороший код должен позволять декодирование(восстановление последовательности символов по ее коду). Пусть фиксирован алфавит <tex>A</tex> и код <tex>\alpha</tex> для этого алфавита. Для каждого слова <tex>P</tex> в алфавите <tex>A</tex> (то есть для любой конечной последовательности букв алфавита <tex>A</tex>) рассмотрим двоичное слово<tex>\alpha(P)</tex>, которое получается, если записать подряд коды всех букв из <tex>P</tex> (без каких либо разделителей). Код <tex>\alpha</tex> называется '''''однозначным''''', если коды различных слов различны: <tex>\alpha(P)\ne\alpha(P')</tex> при <tex>P\ne{P'}</tex>.
−	~~== Неравенство Макмиллана ==~~
−	~~{{Теорема~~
−	~~\|statement=~~
−	~~<center>~~
−	[http://neerc.ifmo.ru/mediawiki/index.php/%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0 Неравенство Крафта{{---}}Макмиллана] выполняется не только для любого префиксного кода, но и вообще для любого однозначного кода.
−	~~</center>~~
−	}}
−	~~''Примечание: Именно это доказал Макмиллан, Крафт доказал неравенство для префиксных кодов.''~~
−	~~== Доказательство ==~~
−	Есть разные способы решить эту задачу, но будет приведено простое и красивое, хотя и несколько загадочное, решение. <br />
−	Пусть имеется однозначный код с <tex>k</tex> кодовыми словами <tex>P_1,P_2, ..., P_k</tex>. Необходимо доказать, что их длины <tex>n_i=\|P_i\|</tex> удовлетворяют Неравенству Крафта{{---}}Макмиллана.
−
−	Вместо нулей и единиц будем использовать <tex>a</tex> и <tex>b</tex> (из чего составлять коды разницы нет). Запишем формально сумму всех кодовых слов как алгебраическое выражение
−
−	~~<center><tex>P_1+P_2+...P_k</tex></center>~~
−
−	(многочлен от <tex>a</tex> и <tex>b</tex>, в котором одночлены записаны как произведения переменных <tex>a</tex> и <tex>b</tex>, без возведения в степень). Теперь (ещё боле странное на первый взгляд действие) возведём это в степень <tex>N</tex>(произвольное натуральное число) и раскроем скобки, сохраняя порядок переменных(не собирая вместе одинаковые переменные) в одночленах:
−
−	~~<center><tex>(P_1+P_2+...P_k)^N=</tex> сумма одночленов.</center>~~
−
−	~~Например, для кода со словами <tex>0,10,11</tex> (которые теперь записываются как <tex>a,ba,bb</tex>) и для <tex>N=2</tex> получаем~~
−
−	~~<center><tex>(a+ba+bb)^2=(a+ba+bb)(a+ba+bb)=aa+aba+abb+baa+baba+babb+bba+bbba+bbbb.</tex></center>~~
−
−	В этом примере все одночлены в правой части различны (если не переставлять переменные), и это не случайно: так будет для любого однозначного кода. В самом деле, по определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов.
−
−	Теперь подставим <tex>a=b=\frac{1}{2}</tex> в наше неравенство(если оно верно для букв, то оно верно и для любых их числовых значений). Слева получится
−
−	~~<center><tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_i})^N</tex></center>~~
−
−	(в скобке как раза выражение из неравенства Крафта{{---}}Макмиллана). Правую часть мы оценим сверху, сгруппировав слова пол длинам: имеется не более <tex>2^l</tex> слагаемых длины <tex>l</tex>, каждое из которых равно <tex>2^{-l}</tex>, и потому слагаемые данной длины в сумме не превосходят единицы, а правая часть не превосходит максимальной длины слагаемых, то есть <tex>Nmax(n_i)</tex>. Итак, получаем, что
−
−	~~<center><tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_i})^N<Nmax(n_i)</tex></center>~~
−
−	и это верно при любом <tex>N</tex>. Если основание степени в левой степени больше единицы, то при больших <tex>N</tex> это неравенство нарушится (показательная функция растет быстрее линейной). Поэтому, для однозначного кода выполняется неравенство Крафта-Макмиллана. Что и требовалось доказать.
−	~~== Ссылки ==~~
−	~~[[Неравенство Крафта]]~~
−	~~== Литература ==~~
−	~~А. Шень "Программирование: теоремы и задачи" (Издание четвёртое, Москва, Издательство МЦНМО, 2011)~~