FAQ, страница 4

Теорема редукции.Лемма редукции. Пусть для r символов А, появляющихся с вероятностями P: p1  p2  ...  pr,причем pi = q’+q’’ и pi  q’  q’’. Имеется оптимальный код C с кодовыми словами B1 B2 ... Br . Тогдадля алфавита A’, полученного ‘расщеплением’ i буквы на две (с вероятностями q’ и q’’) оптимальное кодирование имеет вид С’ = < B1 ... Bi Bi+1... Br (Bi0) (Bi1) >.Посчитаем стоимость С’: L(C’)=L(C)+ pi . Пусть С не есть оптимальный код и имеется код С* =<D1 ... Di Di+1... Dr D’ D’’> со стоимостью L(С*) < L(C’).

При этом D’ и D’’ - необходимо самыедлинные и отличаются только в последнем разряде, т.е. D’ = (D0) D’’=(D1). Но тогда с помощью С*можно построить код С** для первоначального алфавита и распределения вероятностей Р со стоимостью L(Ñ**) < L(C) (противоречие с оптимальностью С).44. Алгоритм построения кода с минимальной избыточностью.Строится код Хаффмана и доказывается его оптимальность (по индукции с помощью 43).45.

Самокорректирующиеся коды. Коды Хемминга.46. Коды с исправлением r ошибок. Оценка функции Mr(n).47. Машины Тьюринга. Вычислимые функции. Примеры вычислимыхфункций.48. Алгоритмическая неразрешимость проблемы самоприменимости машины Тьюринга..