WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

Pages:     || 2 |

«ВВЕДЕНИЕ В ТЕОРИЮ ИНФОРМАЦИИ Учебное пособие 2 Содержание Введение Глава 1. Три подхода к понятию сложности сообщений 3 1.1. Алгоритмический подход 3 1.2. Комбинаторный подход 5 1.3. Вероятностный подход 7 Глава 2. ...»

-- [ Страница 1 ] --

В. Н. Потапов

ВВЕДЕНИЕ В ТЕОРИЮ ИНФОРМАЦИИ

Учебное пособие

2

Содержание

Введение

Глава 1. Три подхода к понятию сложности сообщений 3

1.1. Алгоритмический подход 3

1.2. Комбинаторный подход 5

1.3. Вероятностный подход 7 Глава 2. Определение и свойства энтропии разбиения 10 Глава 3. Цепи Маркова 17 3.1. Эргодическая теорема для марковской цепи 17 3.2. Закон больших чисел для марковской цепи Глава 4. Модели источников сообщений 4.1. Конечные автоматы 4.2. Параметры модели источника сообщений 4.3. Контекстная модель 4.4. Метод трансфер-матрицы 4.5. Скрытые марковские модели Глава 5. Энтропия источника сообщений 5.1. Стационарные источники. Энтропия стационарного источника 5.2. Энтропия марковского источника 5.3. Энтропия источника Бернулли Глава 6. Кодирование 6.1. Префиксные и разделимые множества слов 6.2. Кодирование натуральных чисел 6.3. Теорема кодирования Шеннона 6.4. Побуквенное кодирование 6.5. Равноблочное на выходе кодирование 6.6. Нумерационное кодирование 6.7. Арифметическое кодирование 6.8. Адаптивное и универсальное кодирования 6.9. Интервальное кодирование 6.10. Преобразование Барроуза Уилера Глава 7. Сложность слова относительно программы 7.1. Схема Лемпела Зива 7.2. Схема конкатенации Глава 8. Недоопределённые данные 8.1. Энтропия недоопределённых данных 8.2. Энтропия разбиения, при заданной точности воспроизведения 8.3. Кодирование недоопределённых данных Глава 9. Передача сообщений по каналам связи, допускающим ошибки 9.1. Канал связи и его пропускная способность 9.2. Теорема кодирования для канала связи, допускающего ошибки 9.3. Обращение теоремы о помехоустойчивом кодировании 9.4. Избыточность универсального кодирования как пропускная способность некоторого канала Предметный указатель Именной указатель Литература Глава 1.

Три подхода к понятию сложности сообщений Пусть A = {a1,..., ak } некоторый конечный алфавит. Упорядоченный набор, состоящий из букв алфавита, называется словом. Сложность слова естественно определить как количество информации, т. е. число двоичных символов, необходимое для однозначного задания слова. Существуют три основных подхода к понятию сложности слова: алгоритмический, комбинаторный и вероятностный, связанные с различными способами задания слов.

1.1. Алгоритмический подход Рассмотрим некоторую вычислимую функцию(программу) : {0, 1} A, где A = Ai. Общепринято считать вычислимыми те и только те функции, которые i= могут быть реализованы некоторой машиной Тьюринга (см., например, [1], [7] [22]).

Некоторые программы, реализованные на машине Тьюринга, могут иметь аргументы, на которых работа программы никогда не заканчивается, поэтому считается, что функция может быть определена не на всём множестве {0, 1}, а только на некотором его подмножестве, т. е. может быть частично вычислимой функцией. Двоичное слово v {0, 1} будем называть кодом слова w A относительно программы, если (v) = w. Определим сложность слова w относительно программы как K(w|) = min |v|.

w=(v) Здесь и далее |v| длина слова v. Если w ({0, 1} ), т. е. слово w не может быть получено применением программы, то K(w|) =. Естественно рассмотреть вопрос о возможности введения некоторого универсального понятия сложности, не зависящего от конкретной программы.

Т е о р е м а 1. (Колмогоров) Существует универсальная программа 0 такая, что для любой программы и слова w A выполнено неравенство K(w|0 ) K(w|) + C, где константа C зависит от программы, но не от слова w.

Д о к а з а т е л ь с т в о. Произвольная программа является набором команд, т. е. задаётся некоторым словом u. Рассмотрим программу 0, которая вначале по слову u записывает программу, а потом запускает программу на слове v.

Тогда кодом слова w относительно 0 будет пара слов: код программы и код слова 4 Глава 1. Три подхода к понятию сложности сообщений w относительно программы. Преобразуем слово u в двоичное слово (u ) так, чтобы его можно было отделить от кода слова w относительно программы, методы разделимого кодирования слов будут описаны ниже (см., главу 6). По построению получаем K(w|0 ) |(u )| + |K(w|)|.

Очевидно, если мы рассмотрим две универсальные программы 0 и 0, то сложности K(w|0 ) и K(w|0 ) отличаются на константу C0,0. Существование универсальной программы позволяет определить понятие сложности, асимптотически не зависящее от выбора конкретной универсальной программы. Если мы рассмотрим бесконечное слово и будем вычислять сложность K(wn |0 ), где wn начало слова w длины n, то величина K(wn |0 ) либо будет ограниченной, либо будет стремиться к бесконечности и тогда влияние константы, зависящей от выбора конкретной универсальной программы 0, станет ничтожным.

Сложность слова w относительно некоторой универсальной программы 0 называется колмогоровской сложностью. Предположим, что A = {0, 1} или что слова в алфавите A закодированы словами в алфавите {0, 1}. Длине слова как и любому натуральному числу можно поставить в соответствие его двоичную запись. Следовательно, функцию K(·|) можно рассматривать как функцию действующую из {0, 1} в {0, 1}. Тогда можно поставить вопрос о вычислимости, т. е. о реализации на машине Тьюринга функции K(·|).

У т в е р ж д е н и е 1. Если программа определена на всём множестве {0, 1}, то функция K(·|) является частично вычислимой.



Д о к а з а т е л ь с т в о. Определим линейный порядок на множестве {0, 1}, упорядочив двоичные слова вначале по возрастанию длины, а слова одинаковой длины лексикографически. Чтобы вычислить число K(w|), будем перебирать элементы v множества {0, 1} в этом порядке и вычислять (v). Когда слово w будет первый раз вычислено на некотором аргументе v, перебор следует остановить, так как K(w|) = |v|. Если слово w не вычисляется программой ни на каком аргументе, то перебор продлится бесконечно и, соответственно, K(w|) =.

Т е о р е м а 2. (Колмогоров) Колмогоровская сложность K(·|0 ) является невычислимой функцией.

Д о к а з а т е л ь с т в о. Предположим противное. Пусть найдётся такая программа 1, которая вычисляет колмогоровскую сложность двоичных слов, т. е. ставит в соответствие двоичному слову w двоичную запись числа K(w|0 ). Заметим, что программа 1 должна быть всюду определена, поскольку для любого слова w A найдётся вычисляющая его программа w и K(w|0 ) K(w|w ) + Cw <. Пусть на множестве {0, 1} задан линейный порядок, определённый в предыдущем утверждении. Построим программу 2, которая ставит в соответствие двоичной записи числа1 m N наименьшее из слов, удовлетворяющих неравенству K(w|0 ) m.

Программа 2 перебирает двоичные слова в порядке возрастания и посредством программы 1 вычисляет их сложность, пока не встретится первое слово удовлетворяющее неравенству K(w|0 ) m. Обозначим его wm. Из вычислимости (на любом аргументе) программы 1 следует, что и программа 2 вычислима на любом аргументе, так как множество слов сложности менее m конечно. Тогда2 K(wm |2 ) = log m, поскольку кодом wm относительно программы 2 является двоичная запись числа Здесь и далее буквой N обозначается множество натуральных чисел.

Здесь и всюду далее через log обозначается логарифм по основанию 2.

1.2. Комбинаторный подход m. Тогда из теоремы 1 получаем неравенство Переходя к пределу при m получаем противоречие с известным равенством lim log m = 0.

Таким образом, вычисление колмогоровской сложности не может быть реализовано в виде программы. И сама универсальная программа, как следует из утверждения 1 и теоремы 2, не может быть определена на всех всех двоичных словах. Невозможность вычисления сложности относительно универсальной программы оправдывает изучение сложности слов относительно некоторых неуниверсальных программ, которые выбираются для нужд конкретных исследований.

1.2. Комбинаторный подход Пусть M A некоторое множество слов и w M. Для однозначного задания слова из множества M достаточно указать его номер во множестве M относительно некоторого, например, лексикографического порядка. Поскольку словам из M присваиваются номера3 от 0 до |M | 1, то для записи номера достаточно log |M | битов. Соответственно определим комбинаторную сложность слова w относительно множества M равенством Определим множество M (r) как множество слов с частотным составом r = (r1,..., rk ), т. е. если w M (r), то в слове w имеется ровно ri букв ai для любого i = 1,..., k.

Д о к а з а т е л ь с т в о. Обозначим n = r1 +· · ·+rk. Сначала рассмотрим случай k = 2. Докажем формулу методом индукции по n. Очевидно, что |M (n, 0)| = |M (0, n)| = 1.

Поскольку любое слово из M (r1, n + 1 r1 ) получается приписыванием буквы a2 к слову из M (r1, n r1 ) или буквы a1 к слову из M (r1 1, n (r1 1)), то из предположения индукции (1.1) имеем Таким образом формула (1.1) доказана.

При k > 2 будем доказывать утверждение методом индукции по k. Любое слово w M (r1,..., rk, rk+1 ) можно получить из слова u M (r1,..., rk + rk+1 ) заменив rk+1 букв ak в слове u на буквы ak+1. По доказанному выше это можно сделать |M (rk, rk+1 )| = (rrkk+rk+1 !)! способами. Тогда Здесь и всюду далее если M множество, то через |M | обозначается его мощность.

Пусть b(, n) количество двоичных слов, содержащих не более единиц.

b(, n) 2nh(/n).

В дальнейшем нам понадобится следующее асимптотическое равенство У т в е р ж д е н и е 4. (формула Стирлинга) n! = nn en 2n(1 + o(1)) при n.

Д о к а з а т е л ь с т в о. Вначале докажем формулу Валлиса sinn x dx. Применяя формулу интегрирования по частям, получаем Пусть xn = Отсюда получаем рекуррентную формулу По индукции получаем формулы 1.3. Вероятностный подход Из монотонности последовательности (xn ) и равенства (1.2) имеем Рассмотрим последовательность an = nn+1/2. Из формулы Тейлора для логарифма имеем ln(1 + n ) = n 2n2 + O( n3 ) при n. Тогда дел. Тогда последовательность (an ), где an = a1 a2... an1 = a1 esn имеет конечный предел. Обозначим его через A. Из арифметических свойств предела, определения последовательности an и формулы Валлиса получаем Таким образом, имеем равенство A = 2. Формула Стирлинга эквивалентна равенству lim an = 2.

всех i = 1,..., k.

справедливое для любого x 1 и n N, можно показать, что (1+ n )n (1+ n+1 )n+1.

Из последнего неравенства методом индукции по n нетрудно вывести неравенство r1 !···rk ! ···rk Кроме того, из утверждения 2 и формулы Стирлинга имеем Из последнего неравенства и определения величины L(w|M ) получаем требуемое.

1.3. Вероятностный подход Рассмотрим некоторый опыт со случайными исходами. Естественно предположить, что количество информации, возникающее в результате получения сведений о некотором случайном исходе, зависит от вероятности исхода. Во всяком случае, если мы многократно записываем результаты однотипных опытов, то, выбирая для наиболее вероятнго исхода более короткое обозначение, можно получить более короткую запись результатов эксперимента. Например, если опыт имеет два равновероятных исхода, то для записи каждого из них достаточно одного бита. А если опыт имеет исходы a1, a2, a3 с вероятностями 1/2, 1/4, 1/4, то его итог можно записывать в виде пары результатов последовательного выполнения двух опытов: первого с равновероятными исходами a1 и a2 a3, и второго (в случае второго исхода в первом опыте) c равновероятными исходами a2 и a3.

Найдём функцию h(p1,..., pk ), которая определяет количество информации, содержащееся в результатах опыта, имеющего k случайных исходов с вероятностями (p1,..., pk ). Сначала предположим, что все исходы опыта равновероятны, тогда h(1/k, 1/k,..., 1/k) = (k). Естественно предположить, что опыт, имеющий большее число равновероятных исходов, имеет большую неопределенность, поэтому (k) возрастающая функция. Пусть опыт B состоит в последовательном выполнении двух независимых экспериментов A и A, имеющих по k равновероятных исходов.

Опыт B имеет k 2 равновероятных исходов, и для записи его результата нужно записать результаты опытов A и A. Следовательно должно быть справедливо равенство (k 2 ) = 2(k). Аналогичным образом заключаем, что (k i ) = i(k) для любых натуральных чисел i > 0. Покажем, что единственной с точностью до умножения на константу функцией, удовлетворяющей этим условиям, является log k, т. е.

(k) = C log k, где C > 0 постоянная величина.

Пусть n > 1 и a > 2 целые числа. Найдется такое натуральное m, что справедливы неравенства Тогда из монотонности функции имеем неравенство m(2) n(a) < (m + 1)(2).

Кроме того, имеем m n log a < m + 1. Из двух последних неравенств получаем, что Увеличивая n, число m можно сделать сколь угодно большим. Тогда из предыдущего неравенства следует, что (a) = (2) log a. Поскольку для записи результата опыта с двумя равновероятными исходами достаточно одного бита, неопределенность такого опыта естественно считать равной 1, т. е. (2) = 1.

Пусть опыт A имеет k исходов, вероятности которых равны некоторым рациональным числам pi. Тогда количество информации, необходимое для записи исхода pi. Рассмотрим опыт B, имеющий n равновероятных исходов. Сгруппируем исходы опыта B в k групп так, чтобы i-я группа имела вероятность mi. Тогда исход опыта B можно указать, определив сначала группу, в которую попал данный исход, а затем найдя место нужного исхода в этой группе. Проделаем n раз опыт B. Поскольку исходы опытов, содержащихся в каждой группе, равновероятны и опыт по определению места нужного исхода в i-й группе необходимо проводить в среднем в mi из n случаях, то функция h должна удовлетворять равенству Тогда 1.3. Вероятностный подход Также естественно предположить, что функция h непрерывна по всем своим аргументам. Из непрерывности следует, что предыдущая формула верна и для опытов с иррациональными вероятностями исходов. Нетрудно видеть, что полученная нами формула утверждает, что количество информации, содержащееся в исходе некоторого опыта, равняется логарифму от его вероятности взятому со знаком минус.

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

Говорят, что задан источник сообщений A, P с алфавитом A и распределением вероятностей P, когда на множестве слов A определена вероятность P : A [0, 1], удовлетворяющая условиям Определим сложность слова w A относительно вероятности P равенством Пусть w M (r), где r = (r1,..., rk ) и r1 + · · · + rk = n. Определим эмпирическую вероятность каждой буквы как частоту её встречаемостив слове w, а эмпирическую вероятность слова как произведение вероятностей, составляющих слово букв. Имеем равенства:

Нетрудно видеть, что эмпирические вероятности всех слов w M (r) равны и для любого слова w M (r) имеется равенство Тогда из утверждения 5 имеем |I(wn |Pr ) L(wn |M (r))| = o(n) = o(I(wn |Prn )), когда длина n слова wn стремится к бесконечности.

Занумеруем слова из M (r) в лексикографическом порядке. Каждое слово из M (r) получит номер из промежутка [1, |M (r)|], который можно записать в виде двоичного слова длины log |M (r)|. Определим программу r, которая ставит в соответствие этому номеру слово из M (r). Тогда |K(w|r ) L(w|M (r))| 1.

Таким образом, различные способы определения условной сложности слова приводят к приблизительно одинаковому результату при должном выборе условий.

Глава 2.

Определение и свойства энтропии разбиения Вероятностным пространством называется тройка, F, P, где множество элементарных событий, F = {a } -алгебра событий, a и P : F [0, 1] вероятностная мера. Вероятностной мерой (вероятностью) называется функция, которая удовлетворяет условиям P () = 1 и P ( i ai ) = i ai, где {ai }i произвольное конечное или счётное семейство попарно непересекающихся событий ai F. Для обозначения вероятности будем также пользоваться символом Pr, когда помимо основного вероятностного пространства приходится рассматривать ещё одно, возможно заданное неявно.

Случайной величиной называется измеримая функция : R, т. е. такая функция, что 1 (, c) F для любого c R. Случайная величина, принимающая конечное число значений, называется дискретной1. Набор дискретных случайных величин 1, 2,..., n называется независимым, если события 1 (c1 ), 2 (c2 ),..., n (cn ) независимы для любых c1, c2... cn R, т. е. справедливо равенство Математическим ожиданием (средним значением) дискретной случайной величины называется число E = ci P ( 1 (ci )), где суммирование ведётся по всеi возможным значениям случайной величины. Дисперсией случайной величины называется число D = E( E)2.

В дальнейшем нам понадобятся следующие известные (см., например, [2]) свойства случайных величин.

A1. E(1 + 2 ) = E1 + E2 для любых случайных величин 1 и 2.

A2. E(1 2... n ) = E1 E2... En для любого набора независимых случайных величин 1, 2,..., n.

A3. D(1 + 2 + · · · + n ) = D1 + D2 + · · · + Dn для любого набора независимых случайных величин 1, 2,..., n.

A4. P {|E| > } D для любой случайной величины и числа > 0 (неравенство Чебышёва).

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

понятие разбиения эквивалентно понятию дискретной случайной величины, заданной равенствами (ai ) = i при i = 1,..., k. Однако мы не будем использовать термин "случайная величина" если нет необходимости применять свойства A1–A4.

Энтропией разбиения A относительно вероятности P называется величина Когда вероятностная мера фиксирована, энтропию будем обозначать просто H(A).

Основными примерами пространств событий в дальнейшем будут служить источники сообщений. В этом случае событиями являются слова в некотором фиксированном алфавите A = {a1,..., ak }, причём считается, что когда слово w A выступает в качестве события, оно является объединением всех своих продолжений wai, i = 1,..., k. Это вполне естественно, если рассматривать слово как запись результатов некоторого повторяющегося опыта с исходами, закодированными буквами алфавита A. В частности, алфавит A будет порождать разбиение на множества, каждому из которых будут принадлежать слова начинающиеся с некоторой фиксированной буквы. Нетрудно видеть, что условия (1.3) обеспечивают свойство аддитивности вероятности на объединении непересекающихся событий.

Пусть задано слово с частотным составом r. Определим вероятность Pr слова ai1... aim в соответствии с формулой (1.4). Из формулы (1.5) вытекает равенство H(A, Pr ) = n I(w|Pr ) для любого слова w M (r). Величина H(A, Pr ) = H(w) называется эмпирической энтропией слова w.

П р и м е р 1. Рассмотрим слово w = abbaccbbbabbaaab. Слово w имеет частотный состав (6, 8, 2). Вычислим эмпирическую энтропию слова H(w) = 16 log 16 2 log Пусть имеется две вероятностные меры P и Q, определённые на разбиении A.

Информационной дивергенцией называется величина У т в е р ж д е н и е 6. Пусть A разбиение, |A| = k, P и Q вероятностные меры. Тогда 2) DA (P Q) = 0 тогда и только тогда, когда P (a) = Q(a) для любых a A.

Д о к а з а т е л ь с т в о. Рассмотрим функцию f (x) = log x. Поскольку f (x) < 0 при x > 0, функция f (x) выпукла вверх и для неё справедливо неравенство Йенсена Энтропия разбиения была определена К. Шенноном.

Если P (ai ) = Q(ai ) для любых событий ai A, то равенство DA (P Q) = 0 очевидно.

Пусть P (aj ) > Q(aj ) для некоторого события aj A. Предположим, что DA (P Q) = противоречию.

У т в е р ж д е н и е 7. Пусть |A| = k, тогда для любой вероятности P справедливо неравенство 0 H(A, P ) log k.

Д о к а з а т е л ь с т в о. Рассмотрим равномерное распределение вероятностей Q(ai ) = 1/k для всех i = 1,..., k. Из утверждения 6 получаем Неравенство 0 H(A, P ) непосредственно вытекает из определения энтропии.

Вероятность события a при условии b определяется равенством P (a|b) = P (ab).

Здесь и далее пересечение событий a и b обозначается через ab.

Для произвольного разбиения A = {a1,..., ak } справедливы формулы полной вероятности:

Пусть H(A|b) = P (ai |b) log P (ai |b). Для пары разбиений A и B определим условную энтропию П р и м е р 2. Рассмотрим слова w1 = abbaccbbbabbaaab w2 = cabbbacabbbcaccc.

Эмпирическую вероятность P (x|y) буквы x при условии y можно определить как частоту встречаемости буквы x над буквой y, когда одно слово записано под другим.

Например, P (a|b) = 1/3. Вычислим условную эмпирическую энтропию H(w1 |w2 ) = = 1 H(w1 |a) + 3 H(w1 |b) + 8 H(w1 |c) = 1 2 + 3 ( 3 + 1 log 3) + 8.

П р и м е р 3. Рассмотрим циклическое слово w1 = abbaccbbbabbaaab(a), т. е. считаем, что за последней буквой слова следует первая и далее по циклу. Определим P (xy) как частоту пары букв xy в слове w1. Например, P (ab) = 3/16. Соответственно определим условные вероятности. Нетрудно видеть, что условные вероятности получились такие же как если бы мы в предыдущем примере взяли вместо слова w сдвинутое слово w1, т. е. bbaccbbbabbaaaba.

Пусть A и B разбиения. Разбиение AB = {ai bj }ij определяется, как разбиение, состоящее из всевозможных пересечений событий ai и bj.

H(AB) = H(B) + H(A|B).

Доказательство.

Разбиения A и B называются независимыми, если события ai и bj попарно независимы, т. е. P (ai bj ) = P (ai )P (bj ) для всевозможных i, j.

У т в е р ж д е н и е 9. Пусть A, B разбиения, тогда H(A) H(A|B). Разбиения A и B независимы тогда и только тогда, когда H(A|B) = H(A).

Доказательство.

Из утверждения 8 следует, что для любого события bj B справедливо неравенство причём равенство возможно только в случае, когда P (ai |bj ) = P (ai ) для любых Используя формулу полной вероятности, получаем равенство По определению условной вероятности имеем Тогда справедливо неравенство H(A) H(A|B), причём равенство H(A) = H(A|B) возможно только в случае, когда P (ai |bj ) = P (ai ) для любых i = 1,..., k и Если разбиения A и B независимы, то равенство H(A|B) = H(A) очевидно.

Д о к а з а т е л ь с т в о. Из утверждения 6 и формулы (2.2) имеем Тогда Взаимной информацией разбиений A и B называется величина a) I(A, B) = H(A) + H(B) H(AB);

Доказательство этих свойств взаимной информации разбиений непосредственно вытекает из определения и предыдущих утверждений.

П р и м е р 4. Пусть w1, w2 An. Рассмотрим эмпирическую информацию I(w1, w2 ) = H(w1 ) H(w1 |w2 ). Нетрудно видеть, что эмпирическая информация между словами обладает свойствами a) e) и может использоваться как мера подобия слов. Пусть w1 = abbaccbbbabbaaab, w2 = cabbbacabbbcaccc. Тогда I(w1, w2 ) = Введённые в данном разделе понятия имеют свои комбинаторные и алгоритмические аналоги. Пусть задано произвольное конечное множество X и его разбиение A = {a1,..., ak }, где X = ai, причём множества ai попарно не пересекаются. Тогда комбинаторным аналогом энтропии разбиения A будет величина Исходя из того, что log |X| есть число битов, необходимое для указания некоторого бятся для указания элемента множества X если уже известно, какому из множеств ai принадлежит этот элемент, можно заключить, что энтропия разбиения есть разность между сложностью задания элемента при отсутствии информации и сложностью задания элемента, когда он известен приблизительно, с точностью до элемента разбиения.

При алгоритмическом подходе можно определить условную сложность как сложность преобразования одного слова из другого. Тогда энтропии будет соответствовать разность между колмогоровской сложностью слова и средней сложностью получения слова из некоторого набора образцов.

ных разбиений A, B и вероятностных распределений P и Q справедливо неравенство DAB (P Q) DA (P Q).

З а д а ч а 2. Докажите, что следующие условия эквивалентны:

1) Разбиения A и B независимы;

З а д а ч а 3. Для произвольных разбиений A, B, C докажите равенство H(AB|C) = H(A|C) + H(A|CB).

З а д а ч а 4. Для произвольных разбиений A, B, C докажите неравенства a) H(AB|AC) H(B|C) + H(A|CB);

b) H(A) + H(B) + H(C) + 3H(ABC) 2(H(AB) + H(BC) + H(CA)).

З а д а ч а 5. Для произвольного разбиения A и независимых разбиений B1, B докажите неравенство I(B1 B2, A) I(B1, A) + I(B2 |A).

З а д а ч а 6. Для пары разбиений A и B определим величину Докажите, что величина (A, B) обладает свойствами расстояния:

b) (A, A) = 0;

c) (A, B) = (B, A);

d) (A, B) + (B, C) (A, C).

З а д а ч а 7. Для пары разбиений A, B и C определим условную взаимную информацию равенством I(A, B|C) = H(A|C) H(A|BC). Докажите равенство I(A, B|C) = I(AC, B) I(C, B).

З а д а ч а 8. Пусть разбиения A, B, C таковы, что H(C|AB) = H(C|B). Докажите, что a) H(A|BC) = H(A|B);

b) I(A, B) I(A, C) (неравенство обработки информации).

Неравенство обработки информации означает, что в процессе обработки первоначальная информация может только теряться. Действительно, пусть A, B и C дискретные величины соответствующие разбиениям A, B и C. Предположим, что B = f1 (A ) и C = f2 (B ), где f1, f2 некоторые операции обработки информации.

Тогда выполнено условие H(C|AB) = H(C|B), поскольку P (c|ab) = P (c|b), для любых событий a A, b B, c C. Неравенство обработки информации утверждает, что в разбиении B, полученном посредством первого преобразования f1, не меньше информации о разбиении A, чем в разбиении C, полученном посредством преобразования f2 f1.

Глава 3.

Цепи Маркова Рассмотрим последовательность случайных испытаний, в которой вероятность исхода следующего испытания зависит только от исхода испытания, непосредственно предшествующего ему. Такая случайная последовательность называется цепью Маркова.

Пусть задано множество текстов в некотором алфавите. Предположим, что вероятность появления буквы на некоторой позиции в тексте зависит только от непосредственно ей предшествующей буквы и не зависит ни от позиции, ни от предыдущего текста. Такие тексты в алфавите E можно рассматривать как реализации некоторой цепи Маркова.

3.1. Эргодическая теорема для марковской цепи Дадим формальное определение. Пусть, F, P вероятностное пространство.

При изложении теории марковских цепей принято рассматривать дискретные случайные величины, областью значений которых является некоторое конечное множество E = {s1,..., sk }. Последовательность случайных величин 1,2,...,n,... образует однородную цепь Маркова (марковскую цепь), если для любых номеров n, i1,..., in справедливо равенство Исходы испытаний si, i = 1,..., k называются состояниями марковской цепи.

Матрица P составленная из чисел pij называется матрицей переходных вероятностей. Из определения и формулы полной вероятности (2.2) видно, что pij 0 и pij = 1 для всех j = 1,..., k. Матрицы, обладающие такими свойствами, называi= ются стохастическими.

В соответствии с определением марковской цепи и формулой полной вероятности (2.2), вероятность pij (n) = P (n+m = si |m = sj ) перехода за n шагов из состояния sj в состояние si вычисляется по рекуррентной формуле где pij (1) = pij.

У т в е р ж д е н и е 12. Пусть P (n) матрица, составленная из чисел pij (n).

Тогда P (n) = P, P (n) стохастическая матрица и для всех натуральных n, m и i, j = 1,..., k, причём, справедливы равенства Следовательно, справедливо равенство P n+m = P n P m, эквивалентное равенству (3.2).

Из определения видно, что pij (n) 0. Методом индукции по n докажем, что Пусть (3.3) верно. Тогда из (3.1) имеем Марковская цепь называется неразложимой, если для любых i, j = 1,..., k найдётся такое n, что pij (n) > 0.

Число d > 1 называется периодом состояния si, если d есть наибольший общий делитель таких чисел n, что pii (n) > 0, т. е. число d период состояния si, если в состояние si можно вернуться только за кратное d число шагов.

У т в е р ж д е н и е 13. Все состояния неразложимой марковской цепи имеют одинаковый период.

Д о к а з а т е л ь с т в о. Поскольку марковская цепь неразложима, найдутся такие n1, n2 N, что pij (n1 ) > 0 и pji (n2 ) > 0. Пусть di период состояния si, тогда di делит число n1 + n2. Рассмотрим произвольное n3 N такое, что pjj (n3 ) > 0.

Тогда di делит число n1 + n2 + n3 и, следовательно, делит число n3. Тогда di делит dj, где dj период состояния sj. Поскольку это верно для произвольных i, j, то di = dj для любых i, j = 1,..., k.

Если все состояния марковской цепи имеют период d > 1, то марковская цепь называется периодической. В противном случае марковская цепь называется непериодической.

Нам понадобится следущее N, что любое натуральное число n n0 представляется в виде n = 1 m1 + 2 m2 + · · · + t mt, где 1,..., t целые неотрицательные числа.

Д о к а з а т е л ь с т в о. Пусть НОД(m1, m2 ) = d, тогда из алгоритма Евклида нахождения наибольшего общего делителя следует, что найдутся такие целые числа 1, 2, что 1 m1 + 2 m2 = d. Пусть НОД(m1, m2,..., mr ) = dr, методом индукции по r покажем, что для r, 2 r t, найдутся целые числа 1, 2,..., r, для которых верно равенство Имеем НОД(dr, mr+1 ) = dr+1. Тогда найдутся целые числа 1, 2 такие, что 1 dr + 2 mr+1 = dr+1. По предположению индукции (3.4) имеем равенство 3.1. Эргодическая теорема для марковской цепи что и требовалось. Рассмотрим целые числа 1, 2,..., t, для которых выполняется равенство Пусть m0 = min(m1,..., mt ) и C = max{|i m0 |}. Если n C(m1 + m2 + · · · + mt ) = n0, x1 (n), x2 (n) < m0, чтобы выполнялось равенство Поскольку i C + x2 (n)i 0 для любого i = 1,..., t, требуемое представление числа n получено.

У т в е р ж д е н и е 15. Если марковская цепь неразложимая и непериодическая, то найдётся такое n0 N, что pij (n) > 0 для всех n n0 и i, j = 1,..., k.

Д о к а з а т е л ь с т в о. Поскольку марковская цепь непериодическая, то найдутся такие числа m1,..., mti, что НОД(m1, m2,..., mti ) = 1 и pii (mr ) > 0 для всех r = 1,..., ti. Из утверждения 14 следует, что найдётся такое число ni, что при всех n ni число n представимо в виде n = 1 m1 + 2 m2 + · · · + ti mti, где j целые. Тогда из формулы (3.2) имеем Из неразложимости марковской цепи для всех i, j = 1,..., k найдутся такие числа mij N, что pij (mij ) > 0. Рассмотрим n max mij + max ni. Тогда из формулы (3.2) имеем pij (n) pij (mij )pjj (n mij ) > 0.

Следующая теорема занимает центральное место в теории марковских цепей.

Т е о р е м а 3. (эргодическая) Марковская цепь является неразложимой и непериодической тогда и только тогда, когда для каждого i = 1,..., k существует предел lim pij (n) = i > 0, не зависящий от j.

Д о к а з а т е л ь с т в о. Необходимость (). Введём обозначения ai (n) = min pij (n) и b (n) = max pij (n). Поскольку из (3.2) имеем то bi (n + 1) bi (n). Аналогично получаем неравенство ai (n + 1) ai (n) для всех n N и i = 1,..., k. Таким образом, монотонные ограниченные последовательности ai (n) и bi (n) имеют конечные пределы. Докажем, что bi (n) ai (n) 0 при n.

Из утверждения 15 следует существование такого числа n0 N, что pij (n0 ) > для всех i, j = 1... k. Рассмотрим произвольную пару столбцов с номерами j1, j2 в матрице P (n0 ) и определим множествo L1 следующим образом: l L1, если plj1 (n0 ) plj2 (n0 ) 0, L2 = {1,..., k} \ L1.

Введём обозначение h = max hij < 1. Тогда для некоторых номеров j1, j2 из равенства (3.2) имеем Следовательно, bi (n + mn0 ) ai (n + mn0 ) (bi (n) ai (n))hm 0 при m.

Таким образом, некоторая подпоследовательность сходящейся последовательности (bi (n) ai (n)) сходится к нулю, тогда и (bi (n) ai (n)) 0 при n.

По определению имеем ai (n) pij (n) bi (n) для всех j = 1,..., k. По лемме о зажатой последовательности справедливы неравенства Обозначим этот предел через i. Из утверждения 15 имеем pij (n) > 0 и ai (n) > 0 для достаточно больших n. Поскольку последовательности (ai (n)) не убывают для всех i = 1,..., k, их пределы положительны, т. е. i > 0.

Достаточность (). Начиная с некоторого номера n0 N, для всех n n0 и i, j = 1...., k выполнено неравенство pij (n) > 0, так как lim pij (n) > 0. Тогда марn ковская цепь является неразложимой и непериодической.

Величины i называются стационарными или финальными вероятностями состояний цепи Маркова.

П р и м е р 5. Пусть P = 1/4 1/3 1/2 матрица переходных вероятностей марковской цепи. Нетрудно видеть, что соответствующая цепь Маркова является неразложимой и непериодической. Вычислим вектор стационарных вероятностей.

Из утверждения 16 видно, что является собственным вектором матрицы P, соответствующим собственному числу 1. Решим систему линейных уравнений (P E)x = 0.

Одним из решений системы будет вектор x = (2, 3/2, 1). Поскольку сумма координат вектора стационарных вероятностей равна 1, то = x/(9/2) = (4/9, 1/3, 2/9).

З а д а ч а 9. Пусть P матрица переходных вероятностей неразложимой периодической марковской цепи с периодом m. Докажите, что стохастическая матрица 3.2. Закон больших чисел для марковской цепи P m является матрицей переходных вероятностей некоторой разложимой непериодической марковской цепи.

З а д а ч а 10. Докажите, что модуль любого собственного числа стохастической матрицы не превосходит единицы.

З а д а ч а 11. Докажите, что если последовательность случайных величин 1..., n,... является цепью Маркова, то последовательность блоков (1,..., k ), (2,..., k+1 ),... также является цепью Маркова. Докажите, что последовательность блоков непериодична и неразложима, если первоначальная последовательность обладает этими свойствами.

3.2. Закон больших чисел для марковской цепи Говорят, что последовательность случайных величин (n ) сходится к случайной величине (или числу) по вероятности (n ), если Pr{|n | > } 0 при n для любого > 0. Последовательность случайных величин (n ) сходится к числу a R в среднем, если En a при n.

У т в е р ж д е н и е 17. Пусть (n ) ограниченная последовательность случайных величин, сходящаяся по вероятности к числу a R. Тогда последовательность (n ) сходится к числу a в среднем.

Д о к а з а т е л ь с т в о. Пусть |n | C. Рассмотрим произвольные, > 0.

Найдётся номер n, начиная с которого Pr{|n a| > } <. Тогда Поскольку числа, > 0 могут быть взяты произвольно малыми, получаем, что Т е о р е м а 4. (закон больших чисел) Пусть (n ) последовательность независимых одинаково распределённых случайных величин, причём E1 = a R и Доказательство.

Из свойств математического ожидания и дисперсии суммы случайных величин бышёва (A4, § 2) получаем для произвольных > 0 и натуральных n.

Пусть задана некоторая марковская цепь. Будем рассматривать в качестве пространства событий последовательности = 1, 2,..., n... её состояний, i {s1,..., sk }. Определим случайные величины ij (s), где i = 1,..., k, j натуральное, равенством Тогда ri (n) количество состояний si в слове 1 2... n удовлетворяет равенству ri (n) = Пусть марковская цепь неразложима и непериодична, тогда из эргодической теоремы следует существование стационарных вероятностей = (1,..., k ). Будем считать, что начальное состояние марковской цепи равно si с вероятностью i. Нетрудно видеть, что в этом случае вероятность любого слова в последовательности состояний не зависят от места слова в последовательности. В частности, из утверждений для любого натурального числа j. Тогда из (A1, § 2) получаем равенство Определим случайную величину i () = min{k | k = si }. Имеем где случайная величина ij определяется как разность номеров (j + 1)-го и j-го вхождения состояния состояния si в последовательность. Как было замечено выше, вероятности не зависят от того, начиная с какой позиции мы будем искать первое вхождение состояния si. Поэтому для любого j случайные величины ij одинаково распределены cо случайной величиной i и являются независимыми в отличие от случайных величин ij.

дится к числу i по вероятности при n.

Д о к а з а т е л ь с т в о. Из определения случайной величины i видно, что вероятности Pr{i = n} убывают экспоненциально при росте n. Тогда случайная величина i имеет конечные математическое ожидание и дисперсию. Пусть Ei = a, > 0, m(n, ) = ( + a)n. Из равенства (3.6) имеем где C > 0 некоторая константа. Аналогичное неравенство получается и для вероятности Pr rin a. Тогда, применяя закон больших чисел к последовательn) ности (in ), получаем, что a. Из утверждения 17 и равенства (3.5) следует, что a = i.

Таким образом, частота вхождений состояния si в неразложимую непериодическую марковскую цепь стремиться к стационарной вероятности i не только в среднем, но и по вероятности.

Глава 4.

Модели источников сообщений В этом разделе мы рассмотрим различные модели источников сообщений. Будут рассмотрены способы задания вероятности на множестве слов, порождённых той или иной моделью. Однако, наибольший интерес представляет обратная задача: выбор модели наилучшим образом соответствующей имеющемуся тексту. Выбор подходящей модели текста позволяет успешно сжимать текст, прогнозировать продолжение текста, а также устанавливать степень похожести одного текста на другой.

4.1. Конечные автоматы Наиболее известной моделью источника сообщений является конечный автомат.

Конечный автомат задаётся с помощью мультиграфа1 G = V, E. Вершины графа G называются состояниями автомата, среди них выделяется множество входных состояний Vb V и множество выходных состояний Ve V. Дуги графа G помечены буквами некоторого алфавита A, т. е. определена функция F : E A. Пути в графе G, начинающиеся в состояниях из множества Vb и заканчивающиеся в состояниях из множества Ve, будем называть допустимыми. Каждый допустимый путь считаем помеченным словом, которое состоит из букв, которыми помечены дуги этого пути, т. е. определим Таким образом, множество допустимых путей автомата порождает множество слов.

В теории автоматов используется эквивалентная терминология, когда не слова порождаются автоматом, а автомат проверяет принадлежность слова некоторому языку множеству слов.

Из сказанного выше видно, что конечный автомат определяется как G, Vb, Ve, A, F, где G мультиграф, Vb, Ve множества входных и выходных состояний, A алфавит, F функция, помечающая дуги графа G буквами алфавита A. Автомат называется детерминированным, если из каждой вершины графа выходит ровно по одной дуге, помеченной каждой из букв алфавита A. В противном случае автомат называют недетерминированным. Нетрудно видеть, что детерминированный автомат определяется множеством состояний V и функцией µ : V A V.

Автоматы называют эквивалентными, если они порождают одинаковый язык.

Т е о р е м а 5. (Рабин и Скотт) Для любого конечного автомата найдётся эквивалентный ему детерминированный автомат.

Мультиграфом называется ориентированный граф с кратными дугами. В дальнейшим будем называть мультиграфы просто графами.

Д о к а з а т е л ь с т в о. Рассмотрим конечный автомат, задаваемый графом G = V, E. Пусть P(V ) множество всех подмножеств состояний автомата. На множестве вершин P(V ) построим мультиграф. Для любых множества P(V ) и буквы a A определим f (, a) P(V ) как множество состояний, которые являются концами путей, начинающихся в состояниях из множества, и помеченных буквой a A. В мультиграфе соединим вершины и f (, a) дугой, помеченной буквой a A. В качестве входных состояний выберем такие одноэлементные множества {v} P(V ), что v Vb. В качестве выходных состояний выберем такие множества P(V ), что Ve =. Полученный автомат является детерминированным по построению. Покажем, что он эквивалентен исходному конечному автомату. Достаточно показать, что в графе имеется путь из состояния {v0 } в состояние = {vi1,..., vim }, помеченный словом w тогда и только тогда, когда в графе G имеются пути из вершины v0 в каждую из вершин vij помеченные словом w.

Докажем последнее высказывание методом индукции по длине слова w. Для слов длины 1 утверждение верно по построению. Пусть утверждение справедливо для слова w. Рассмотрим слово wa. Принадлежность v f (, a) эквивалентна тому, что для некоторой вершины vij найдётся путь в графе G из vij в v помеченный буквой a. Так как автомат задаваемый графом детерминированный, то только один путь {v},...,, f (, a) помечен словом wa. По предположению индукции и определению множества f (, a), все вершины v f (, a) и только они являются концами путей в графе G с началом в вершине v0, помеченных словом wa.

Множество слов, порождаемое конечным автоматом, называется регулярным языком. Известно (см., например, [1]), что множество регулярных языков замкнуто относительно естественных операций над языками: пересечения, объединения и конкатенации.

4.2. Параметры модели источника сообщений Конечный автомат служит моделью источника сообщений(случайных слов). Для определения вероятностей слов необходимо задать параметры модели вероятности дуг графа. Пусть дана модель с графом G = V, E. Вероятности дуг p(e), e E должны удовлетворять условиям где сумма берётся по всем дугам с началом в любом фиксированном состоянии v V.

Кроме того, нужно определить вероятности входных состояний p(v) 0, где v Vb, удовлетворяющие равенству p(v) = 1, где сумма берётся по всем v Vb. Если входное v состояние единственное, то p(v) = 1. Вероятность pij перехода за один шаг из состояния vj в состояние vi определяется как p(e), где сумма берётся по всем дугам с началом в vj и концом в vi. Из (4.1) видно, что pij = 1. Таким обраi зом, последовательность состояний модели можно рассматривать как цепь Маркова, поэтому такие модели источников сообщений нередко называют марковскими.

Определим вероятность P (a|v) = p(e), где сумма берётся по всем дугам e E с началом в состоянии v V, помеченным буквой a A. Вероятность пути ei1... ein в графе G с началом в состоянии v Vb определяется равенством p(v)p(ei1... ein ) = = p(v)p(ei1 )... p(ein ). Вероятность P (w) слова w A в модели с графом G = V, E и параметрами p(e), e E и p(v), v Vb определяется как сумма вероятностей всех допустимых путей, помеченных словом w.

4.2. Параметры модели источника сообщений У т в е р ж д е н и е 19. Пусть все состояния марковской модели являются выходными. Тогда марковская модель с фиксированным набором параметров определяет источник сообщений, т. е. для любого слова w A справедливо равенство Д о к а з а т е л ь с т в о. Пусть u E допустимый путь. Тогда из (4.1) имеем P (ue) = P (u), где сумма берётся по всем дугам выходяшим из концевой вершины пути u. Из этого равенства и определения вероятности слова вытекает равенство P (wa) = P (w). Справедливость равенства P (w) = 1 нетрудно установить из предыдущего равенства методом индукции по длине слова.

Модель порождения слов будем называть автоматной, если она определяется детерминированным автоматом, все состояния которого являются выходными и только одно входным. Как было отмечено выше, детерминированный автомат определяется функцией µ : V A V, которая по состоянию v V и порождённой в этом состоянии букве a A определяет следующее состояние µ(v, a). Тогда имеется равенство pij = P (a|vj ), где µ(vj, a) = vi.

Простейшая автоматная модель, имеющая только одно состояние, называется моделью Бернулли. Источники сообщений с такой моделью называются источниками Бернулли.

У т в е р ж д е н и е 20. Пусть задан детерминированный автомат, тогда существует взаимно однозначное соответствие между допустимыми путями u V и порождаемыми автоматом словами w A. При этом справедливо равенство где vi1 = v0 входное состояние и vim = µ(vim1, aim1 ).

Д о к а з а т е л ь с т в о. Соответствующий слову ai1... ain допустимый путь vi1,..., vin получаем по правилу vi1 = v0 входное состояние и vim = µ(vim1, aim1 ).

Из определения детерминированного автомата видно, что найденный допустимый путь является единственным путём помеченным словом ai1... ain.

Таким образом, автоматная модель M и набор параметров P определяют некоторый источник сообщений. Отметим, что равенства (4.2) остаются справедливым и при более слабых требованиях на модель, для этого достаточно уже того, чтобы все состояния модели были выходными и все дуги были помечены буквами.

Предположим, что задана некоторая модель M и слово w A, которое может быть порождено источником сообщений с моделью M. Возникает вопрос: какими следует выбрать параметры модели, чтобы вероятность произвести слово w была максимальной? Если модель M является автоматной, то на этот вопрос нетрудно ответить.

Пусть w An и u V n соответствующий слову w набор состояний детерминированного автомата. Определим эмпирические вероятности порождения букв в различных состояниях v V равенствами Pw (a|v) = r(a|v), где r(v) число вхождений состояния v в набор состояний u V n и r(a|v) число раз, когда буква a A встречается в состоянии v V при порождении слова w. Если r(v) = 0, то вероятности Pw (a|v) можно назначать произвольно, например, равными для всех букв. Нетрудно видеть, что в модели Бернулли n log Pw (w) = H(w) для любого слова w An, где H(w) эмпирическая энтропия слова w. Индекс w у величины Pw будем опускать, если из контекста ясно, какое слово w A подразумевается. В частности, будем всегда предполагать, что P (w) = Pw (w).

У т в е р ж д е н и е 21. Пусть w A. Справедливо равенство P (w) = max P (w), где максимум берётся по всевозможным наборам параметров автоматной модели M.

Д о к а з а т е л ь с т в о. Пусть w = ai1... ain. Рассмотрим модель M с произвольным набором параметров. По формуле (4.3) имеем Тогда Из утверждения 6 имеем Тогда log P (w) log P (w) и P (w) P (w).

Из утверждения 21 можно сделать вывод: если задана модель M и слово w, порождённое источником сообщений с этой моделью, то наиболее вероятными параметрами модели являются Pw. Действительно, пусть {} множество параметров автоматной модели M. Предположим, что на {} задано некоторое распределение вероятностей Pr. Из формулы полной вероятности (2.2) нетрудно получить формулу Байеса где Pr(w|P ) = P (w). Естественно считать вероятности Pr() наборов параметров одинаковыми, тогда наибольшая условная вероятность Pr(|w) того, что параметры модели равны, при уcловии порождения источником слова w, достигается на параметрах P = Pw. Величину log Pw (w) естественно считать сложностью слова w относительно модели M.

4.3. Контекстная модель Модель будем называть контекстной, если состояние, в котором находится модель после порождения слова w, однозначно определяется этим словом w. Контекстом позиции в слове будем называть предшествующее этой позиции подслово произвольной длины. В контекстной модели имеется взаимно однозначное соответствие между порождаемыми словами и путями в соответствующем модели мультиграфе.

Действительно, если одно слово порождается двумя путями, то соответствующие этим путям наборы состояний различаются, а значит некоторый префикс слова приводит в разные состояния, что противоречит определению контекстной модели. Очевидно верно и обратное: если каждому слову соответствует единственный путь, то модель контекстная. Как показано в утверждении 20, автоматная модель является 4.3. Контекстная модель контекстной. Если для определения следующего состояния необходимо и достаточно знать контекст некоторой фиксированной длины m, то такая модель называется марковской порядка m. Марковская модель порядка m является автоматной. Действительно, определим множество состояний как V = Am. Произвольную вершину вида aw, где w Am1 соединим дугой с вершиной wb и пометим дугу буквой b A.

Полученный граф называется графом де Брёйна порядка m. Нетрудно видеть, что марковская модель порядка m есть автоматная модель с графом де Брёйна порядка m. При m = 1 множество букв и множество состояний совпадают и марковской модели соответствует цепь Маркова с множеством состояний A. Частным случаем марковской модели при m = 0 является модель Бернулли с единственным состоянием.

Пусть w A произвольное слово. Чтобы не было неопределённости в определении контекста первых букв, слова будем считать слово циклическим. Обозначим через Pm эмпирическую вероятность слова w в марковской модели порядка m.

У т в е р ж д е н и е 22. Для любого слова w A и натурального числа m верно неравенство Pm1 (w) Pm (w).

Д о к а з а т е л ь с т в о. Пусть w A. Определим пространство элементарных событий = Am+1 и P (x) = r(x), где r(x) число вхождений слова x Am+1 в слово w, учитывая и перекрывающиеся вхождения. Пусть разбиение B k состоит из множеств By = {zya | z Amk, a A}, где y Ak, k = 0,..., m, а разбиение A из множеств Aa = {za | z Am }. Тогда Поскольку B m1 B m = B m, из утверждения 10 следует, что log Pm (w) = nH(A|B m ) = nH(A|B m1 B m ) nH(A|B m1 ) = log Pm1 (w).

Откуда имеем Pm1 (w) Pm (w).

Таким образом, эмпирическая вероятность любого слова больше в марковской модели с большей длиной контекста. Будет ли из этого следовать, что модель с более длинным контекстом точнее моделирует механизм порождения текста? Если взять контекст длины равной длине слова без единицы, то эмпирическая вероятность слова будет равна 1. Однако, вряд ли такая модель осмысленна, поскольку она не выполняет своей роли служить кратким описанием слова. Для выбора модели, наилучшим образом соответствующей слову, мало минимизировать сложность слова относительно модели, нужно учитывать ещё и сложность самой модели. С этой целью Й. Риссанен ввёл понятие стохастической сложности St(w, M ) слова w относительно модели M. В § 6.8 будет дано формальное определение величины St(w, M ), а также величины n (M ), отвечающей за сложность модели, и доказано равенство Для автоматных моделей известно, что n (M ) = d log |w| + O(1), где d число независимых параметров модели. Не строго можно сказать, что сложность модели равняется количеству битов, необходимых для записи эмпирических параметров модели с точностью, которую обеспечивает длина слова.

Выбор такой модели текста той, в которой текст имеет минимальную стохастическую сложность, соответствует принципу кратчайшего описания: лучшим способом описания объекта будет тот, который имеет минимальную длину. Более того, нередко наиболее короткое описание объекта является и наиболее осмысленным описанием, поскольку не содержит ничего лишнего. Использование кратчайшего описания соответствует известному в естественных науках методологическому принципу Оккама:

не следует изобретать сущностей сверх необходимого.

Описанный выше подход применяется к марковским моделям конечного порядка следующим образом. Из-за того, что количество контекстов состояний марковской модели порядка m растёт экспоненциально относительно m, принято рассматривать контекстные модели, получающиеся из марковских объединением состояний с близкими параметрами, т. е. в графе де Брёйна вершины vi и vj отождествляютя, если P (a|vi ) P (a|vj ) для всех a A. Полученная модель уже может оказаться не автоматной, но сохраняет свойства однозначного соответствия между словами и допустимыми путями, т. е. является контекстной.

Краткость описания является также одной из причин рассмотрения наряду с детерминированными и недетерминированных автоматов. В теореме Рабина и Скотта утверждается, что для каждого недетерминированного автомата можно построить детерминированный, порождающий такое же множество слов. Однако, первоначальный недерминированный автомат нередко имеет значительно меньше состояний.

Недетерминированный автомат целесообразно использовать как модель источника сообщений, если сохраняется свойство однозначного соответствия между словами и допустимыми путями, т. е. соответствующая ему модель является контекстной. В контекстных моделях эмпирическая вероятность и стохастическая сложность слова может быть определена также как в автоматных моделях. Контекстные модели обладают фактически всеми полезными с точки зрения кодирования сообщений свойствами автоматных моделей.

4.4. Метод трансфер-матрицы В этом разделе рассмотрен вопрос о количестве слов фиксированной длины в регулярном языке. Пусть G = V, E некоторый мультиграф. Занумеруем произвольным образом его вершины V = {v1,..., vm }. Матрицей смежности мультиграфа G (трансфер-матрицей) называется квадратная матрица M размера nn, в которой компонента M [i, j] равняется количеству дуг, идущих из вершины vi в вершину vj.

У т в е р ж д е н и е 23. Количество путей длины n ведущих из вершины vi в вершину vj равно M n [i, j].

Д о к а з а т е л ь с т в о. Докажем это утверждение методом математической индукции по длине пути n. База индукции обеспечивается определением матрицы M. Пусть утверждение доказано для количества путей длины n. Тогда число путей длины n + 1, соединяющих вершину vi с вершиной vj равно M n [i, k]M [k, j], что в соответствии с определением операции умножения матриц совпадает с компонентой M n+1 [i, j] матрицы M n+1 = M n M.

Пусть v1 входное состояние некоторой контекстной модели. Тогда количество слов длины, порождаемых в этой модели равняется сумме элементов первой строки матрицы M n, где M матрица смежности мультиграфа модели. Числа M n [i, j] можно вычислять описанным ниже способом.

4.4. Метод трансфер-матрицы собственные числа матрицы M справедливо равенство где E единичная матрица, а через Bij обозначено алгебраическое дополнение элемента B[i, j] в матрице B.

= (E M )1. Приравнивая компоненты двух матриц в левой и правой части равенства, получаем требуемое.

Рассмотрим задачу вычисления количества слов алфавита A, несодержащих подслов из некоторого множества Z A. Пусть максимальная длина слова из множества запретов Z равняется n0 + 1. Рассмотрим граф де Брёйна порядка n0 для этого алфавита и удалим из него все дуги и вершины, соответстующие запрещённым словам. Полученный граф обозначим GZ. Ясно, что множество слов длины n > n в алфавите A, несодержащих запрещённых подслов, вычисляется как число различных путей длины2 n n0 в графе GZ.

П р и м е р 6. Вычислим f (n) количество слов длины n в алфавите {a1, a2, a3 }, несодержащих подслов из множества Z = {a1 a1, a2 a3 }. Матрица смежности графа GZ с вершинами a1, a2, имеет вид Тогда Таким образом, f (1) = 3, f (2) = 7, f (3) = 16, f (4) = 36.

З а д а ч а 12. Пусть M матрица смежности некоторого мультиграфа G. Докажите, что количество контуров длины n в мультиграфе G равно n + · · · + n, где 1,..., m набор собственных чисел матрицы M с учётом их кратности.

З а д а ч а 13. Пусть NZ (n) множество циклических слов длины n в алфавите, несодержащих подслова из множества Z. Пусть максимальное по модулю собственное число матрицы смежности графа GZ. Докажите, что log |NZ (n)| = = n log ||(1 + o(1)) при n.

Длину пути определяем как число дуг, составляющих путь.

4.5. Скрытые марковские модели Рассмотрим марковскую модель с некоторым фиксированным набором параметров. В случае произвольной марковской модели последовательность состояний модели не восстанавливается однозначно по последовательности букв, порождённых в этих состояниях. Обычно предполагается, что слова это наблюдаемые данные, а состояния модели неизвестны. Отсюда происходит название скрытые марковские модели.

Для простоты будем считать, что марковская модель имеет единственное входное состояние vb, все её состояния являются выходными и все дуги графа G помечены буквами алфавита A. Пусть ei1... ein путь в графе G с началом в состоянии vb, которому соответствует слово x A и последовательность состояний vb s, s V n.

Введём обозначения: P (x, s) = P (ei1... ein ) и P (s|x) = P (x, s)/P (x).

Рассмотрим следующую задачу: пусть задано слово x A, нужно найти наиболее вероятный путь его порождения, т. е. такую последовательность состояний s(x), что где максимум берётся по всевозможным последовательностям состояний.

Приведённый ниже алгоритм вычисления последовательности состояний s(x) был предложен А. Д. Витерби. Введём обозначение xn для префикса длины n слова x, n |x|. Из определений имеем где P (xn+1, sn+1 |sn ) = p(ein+1 ) вероятность дуги из состояния sn в состояние sn+1, помеченной буквой xn+1. Для более удобных вычислений следует перейти от умножений к сложениям, т. е. к логарифмам обратных вероятностей. Из (4.5) имеем где l(·) = log P (·). Задача (4.4) на поиск максимума превращается в задачу на поиск минимума где N = |x|.

Для всех v V, n 0 определим величину L(v|xn+1 ) = minn l(xn+1, sn v). Тогда из формулы (4.6) имеем Поскольку l(xn, s(xn )) = minvV L(v|xn ), формула (4.7) обеспечивает рекуррентную процедуру вычисления величины l(x, s(x)). Последовательность состояний s(xN ) можно получить двигаясь в обратном направлении и определяя состояния sn, на которых достигается равенство начиная с L(sN |xN ) = l(xN, s(xN )). Заметим, что максимум вероятности P (s|x) может достигаться на нескольких последовательностях состояний s(xN ).

4.5. Скрытые марковские модели Используя алгоритм Витерби, можно решать задачу о нахождении параметров марковской модели, при которых некоторое слово имеет максимальную вероятность порождения. А именно, сначала зададим параметры модели вероятности p(e) дуг графа, задающего модель как произвольный набор положительных чисел, удовлетворяющих условию (4.1). Для определённости положим p(e) = 1/d(v), где d(v) степень исхода вершины v. Для заданного слова x A вычислим последовательr(e) ность состояний s(x). Определим эмпирические параметры p(e) = r(v), где r(e) количество прохождений дуги e, а r(v) количество прохождений вершины v, являющейся началом дуги e при порождении слова x A на пути s(x). Повторим вычисление последовательности состояний s(x) для модели с новым набором параметров, вычислим новые эмпирические вероятности и т. д.

У т в е р ж д е н и е 25. Определённый выше процесс сходится, т. е. последовательность наборов эмпирических параметров, начиная с некоторой итерации, становится постоянной.

Д о к а з а т е л ь с т в о. Аналогично доказательству утверждения 21 можно показать, что величина P (x|s(x)) не возрастает после каждой итерации. Нетрудно видеть, что эмпирические параметры модели и, следовательно, величина P (x|s(x)) могут принимать только конечное число значений. Очевидно, что монотонная последовательность, принимающая конечное число значений, стабилизируется. Если стабилизируется величина P (x|s(x)), то стабилизируется и последовательность состояний s(x), а значит и набор эмпирических параметров.

Вообще говоря, найденный набор стабилизировавшихся параметров зависит от начального набора параметров модели.

На практике выбирают эмпирические параметры с поправкой p(e) = r(v)+d(v)/2, чтобы вероятности непройденных дуг не превращались в 0 и эти дуги не терялись на последующих итерациях. Кроме того, обнуление параметров эквивалентно удалению из графа соответствующих дуг, что может привести к уменьшению множества слов, порождаемых данной марковской моделью. Причины выбора величины сдвига, равной 2, обсуждается в § 6.8.

П р и м е р 7. Рассмотрим пример скрытой марковской модели. Имеются две монеты: правильная и погнутая, которые представляют два состояния модели.

Наблюдаемыми данными будут орлы и решки, которые выпадают при подбрасывании монеты, причём вероятности выпадения орла и решки при подбрасывании правильной монеты одинаковы, а при подбрасывании погнутой монеты различны.

Задача состоит в том, чтобы выяснить по последовательности орлов и решек, полученной в результате подбрасывания монеты, когда правильную монету меняли на погнутую, в предположении, что вероятность замены монеты мала.

Определим модель формально. Пусть {v, v} множество состояний модели, имеющей следующие параметры P (0|v) = P (1|v) = 1, P (0|v) = 8, P (1|v) = 8, P (v|v) = P (v|v) = 16. Пусть состояние v является входным. Рассмотрим последовательность 101000000. Построим таблицу где c = log 15. Имеет место неравенство 45 9c < 58 8c 6 log 7. Из таблицы получаем следующую последовательность состояний s(101000000) = vvvvvvvvv.

Глава 5.

Энтропия источника сообщений Напомним, что источником сообщений называется пара A, P, состоящая из конечного алфавита A и распределения вероятностей P на множестве конечных слов A, удовлетворяющего соотношениям Пусть Энтропией источника A, P называется предел если он существует.

Будем писать Hn (P ) вместо Hn ( A, P ) и H(P ) вместо H( A, P ) в тех случаях, когда алфавит фиксирован.

Энтропия является важнейшей характеристикой источника сообщений, отражающей среднее количество информации в сообщениях. Как будет показано в § 6.3 энтропия источника сообщений является точной нижней гранью количества двоичных символов, которые необходимо в среднем затратить на кодирование одного символа сообщения. В данном разделе будет доказано существование энтропии для широкого класса источников сообщений и предложены способы её вычисления.

5.1. Стационарные источники. Энтропия стационарного источника Пусть A = {a1, a2,..., ak } конечный алфавит. Рассмотрим в качестве пространства событий множество бесконечных в обе стороны последовательностей букв алфавита A, т. е. = A. Пусть множество Bij A состоит из последовательностей, имеющих на j-ом месте букву ai. Ясно, что множество B j = {Bij }i=1...k является разбиением A.

Известная теорема Каратеодори (см., например, [2]) утверждает, что вероятностная мера, определённая на некотором полукольце множеств (дробящейся системе множеств) однозначно продолжается на порождённую этими множествами -алгебру.

i1,..., ik {1,..., k} является полукольцом, поскольку она замкнута по отношению к взятию пересечений и если некоторое множество из этой системы содержится в другом, то последнее можно представить в виде объединения набора попарно не пересекающихся множеств из этой системы, включающего первое множество.

Пусть на -алгебре F, порождённой всевозможными событиями Bij, где i = 1,..., k, j целое, определена вероятностная мера P. Меру P будем называть стационарной, если она инвариантна относительно сдвигов бесконечных слов из A на произвольное число позиций, в частности, для любых наборов i1,..., in {1,..., k} и целых чисел j0, j1,..., jn должны быть справедливы равенства Если P стационарная мера, то события Bi11 Bi22... Bin можно отождествить со словами ai1 ai2... ain и определить P (ai1... ain ) = P (Bi11... Bin ). Таким образом, люn бая стационарная мера определяет источник сообщений, который также называется стационарным.

Из (5.2) следует, что для стационарного источника A, P верно равенство У т в е р ж д е н и е 26. Пусть A, P стационарный источник, тогда последоn 12 n вательность n = H(B |B B... B ) монотонно убывает.

равенства Тогда и из утверждения 10 следует, что Из (5.4) и последнего неравенства утверждение доказано.

Д о к а з а т е л ь с т в о. Пусть n = H(B n |B 1 B 2... B n1 ). Из определения энтропии следует, что n 0. Из утверждения 26 следует, что последовательность n монотонно убывает. Тогда существует предел lim n 0.

Покажем методом индукции, что 5.2. Энтропия марковского источника 8 имеем Известно, что предел среднего арифметического последовательности равен пределу последовательности, поэтому Из доказательства утверждения 27 видно, что последовательность (hn ), hn = Hn (P ) монотонно убывает (возможно нестрого) для любого стационарного источника.

5.2. Энтропия марковского источника Как было доказано в § 4.2 марковская модель M с алфавитом A и множеством состояний V при фиксированным наборе параметров P определяет некоторый источник сообщений A, P. Кроме того, последовательность состояний автоматной модели можно рассматривать как некоторую марковскую цепь s(M, P ). Соответственно определённый указанным выше образом источник сообщений называют марковским1.

Определим энтропию в состоянии v V равенством Для значительного класса марковских источников имеется простая формула вычисления энтропии.

У т в е р ж д е н и е 28. Пусть A, P марковский источник определённый контекстной моделью M c набором параметров P, причём марковская цепь s(M, P ) является неразложимой и непериодической. Тогда энтропия источника A, P существует и удовлетворяет равенству где v стационарные вероятности марковской цепи s(M, P ).

Д о к а з а т е л ь с т в о. Марковский источник определяет распределения вероятностей на множествах An при всех натуральных n. Пусть события Bij определены также как и ранее, т. е. Bij множество слов, имеющих на j-м месте букву ai. Из свойств энтропии разбиения имеем равенства Нередко марковскими называют только источники сообщений с контекстной или автоматной моделью.

где Nj состоит из таких наборов (i1, i2..., in1 ), что марковская модель M переходит из входного состояния v1 в состояние vj, когда порождает слово ai1 ai2... ain1.

Тогда из определения марковского источника для переходных вероятностей марковской цепи имеем равенство Кроме того, поскольку вероятность следующей буквы зависит только от текущего состояния, то H(B n |Bi11 Bi22... Bin1 ) = Hvj. Таким образом Тогда из равенства (5.5) имеем Из эргодической теоремы следует, что lim pj1 (n) = vj. Известно, что предел среднеn го арифметического последовательности равен пределу последовательности, поэтому n n m= от выбора начального состояния. Тогда Заметим, что если в контекстной модели все состояния считать начальными и определить исходные вероятности состояний равными стационарным вероятностям, то марковский источник с этой моделью и параметрами, обеспечивающими неразложимость и непериодичность последовательности состояний, будет стационарным.

Такие источники сообщений будем называть стационарными марковскими источниками.

Определение энтропии источника можно записать следующим образом:

где функция n (x) = log P (x) рассматривается как случайная величина, определённая на множестве бесконечных последовательностей в алфавите A, которая принимает значение log P (w) на последовательностях, начинающихся со слова w An. Докажем, что для стационарного марковского источника последовательность (n ) сходится к энтропии источника не только в среднем, но и по вероятности.

У т в е р ж д е н и е 29. Пусть A, P стационарный марковский источник, для любого > 0.

Д о к а з а т е л ь с т в о. Докажем это утверждение вначале для источников Бернулли. Пусть ri (x) количество букв ai в слове x An. Рассмотрим набор случайных величин j (x):

5.2. Энтропия марковского источника Тогда математическое ожидание случайной величины j (x) удовлетворяет равенi ству венству Кроме того, ri (x) = j (x). По определению источника Бернулли случайные велиi чины 1, 2,..., n независимы. Как следствие закона больших чисел получаем, что ri (x) Пусть V множество состояний марковского источника A, P. Если задано входное состояние, то для любого слова x An однозначно определяется последовательность состояний V n, где буква xi порождается источником в состоянии i V, произведения, соответствующую буквам, порождённым в состоянии v V, тогда Pv (x). Через rv (x) обозначим количество вхождений состояния v в послеP (x) = довательность состояний, соответствующую слову x. Справедливы равенства Подслова слова x, состоящие из букв порождённых в состоянии v V можно рассматривать как слова, порождённые источником Бернулли с вероятностями P (ai |v).

Тогда по доказанному выше имеем rv1 log Pv1 Hv 0 при n, чего как видно из равенства (5.8) и утверждения 28 достаточно для завершения доказательства.

З а д а ч а 14. Пусть задан некоторый стационарный марковский источник A, P.

Упорядочим слова w An по убыванию вероятностей и будем отбирать наиболее вероятные до тех пор, пока впервые суммарная вероятность отобранных цепочек не превзойдёт некоторый заранее заданный уровень, 0 < < 1. Число отобранных цепочек обозначим через M (n). Докажите, что для любого, 0 < < 1 существует один и тот же lim log M (n) = H(P ).

5.3. Энтропия источника Бернулли Источником Бернулли называется марковский источник с единственным состоянием. Последовательности букв, порождаемые этим источником, соответствуют последовательностям испытаний Бернулли, когда вероятности всех испытаний одинаково распределены и независимы. Ясно, что любой источник Бернулли является стационарным. Для энтропии H(P ) источника Бернулли и эмпирической энтропии H(x) слова x A справедливы следующие утверждения.

У т в е р ж д е н и е 30. Пусть A, P источник Бернулли. Тогда энтропия источника A, P существует и удовлетворяет равенству для любых натуральных n.

Утверждение 30 непосредственно вытекает из утверждения 9 и определения энтропии источника сообщений.

У т в е р ж д е н и е 31. Для источника Бернулли A, P справедливо неравенство количество букв ai в слове x, i = 1,..., k. Тогда из утверждения 6 следует неравенство Следовательно, из утверждения 30 имеем Чтобы доказать неравенство в другую сторону pассмотрим набор случайных величин j (x):

Имеем ri (x) = j (x). По определению источника Бернулли A, P случайные веi § 2) получаем 5.3. Энтропия источника Бернулли Откуда имеем Из равенств (5.9) и утверждения 30 получаем Тогда Докажем неравенство Из равенств (5.9) следует, что Функция log t выпукла вверх, тогда из неравенства Йенсена, (5.10) и (5.11) имеем Применив неравенство ln(1 + t) t, получаем искомое неравенство.

В утверждении доказано, что эмпирическая энтропия H(x) сходится к энтропии источника Бернулли в среднем. Теперь докажем, что сходимость имеет место и по вероятности.

при n.

Dri (x) = n(P (ai ) (P (ai ))2 ). Из неравенства Чебышёва (A4, § 2) имеем для любого натурального n и > 0.

Без ограничения общности можно считать, что min P (ai ) > 0, поскольку слоi ва, которые содержат буквы с нулевой вероятностью, сами имеют нулевую вероятность. Пусть x An таково, что для любого i = 1,..., k справедливо неравенство | rin P (ai )| <. Из теоремы Лагранжа о приращениях вытекает неравенство | log rin log P (ai )| < C ln 2, где C = min(P (ai ) ). Тогда неравенства (5.12).

Утверждения 31 и 32 можно обобщить на произвольные стационарные марковские источники, определив эмпирическую энтропию слова относительно марковской модели как log P (x), где P (x) эмпирическая энтропия слова в этой модели.

Глава 6.

Кодирование Пусть A некоторый конечный алфавит. Кодированием называется инъективное отображение f : A {0, 1}. Подразумевается, что обратная функция f декодирование должна быть частично вычислимой, т. е. является программой.

Кодирование применяется для сжатия данных, поэтому наиболее важными являются такие характеристики кодирования, как степень сжатия сообщений и эффективность выполнения операций кодирования и декодирования.

Кодирование сообщений с целью их сжатия как будет видно из содержания данной главы теснейшим образом связана с задачей распознавания модели порождения сообщений рассмотренной в главе 4. Оказывается, что с одной стороны имеются эффективные способы кодирования сообщений источников с известной марковской моделью, а с другой эффективное сжатие сообщения кодированием настроенным на некоторую модель говорит о том, что данная модель отражает некоторые статистические свойства сообщения.

6.1. Префиксные и разделимые множества слов Префиксом слова w называется произвольное начало u слова w, т. е. если w = uv, то u префикс слова w. Кодирование f называется префиксным, если из того, что кодовое слово f (u) является префиксом кодового слова f (w) следует, что и слово u является префиксом слова w. Свойство префиксности обеспечивает возможность декодирования кодового слова по частям: если мы декодировали некий префикс слова f (w) как слово u, то мы можем быть уверены, что слово u является началом закодированного слова w. Свойства отображения f быть префиксным достаточно для того, чтобы отображение являлось инъективным, так как из равенства f (u) = f (v) следует, что слова u и v являются префиксами друг друга и, следовательно, совпадают.

Множество D A называется префиксным, если для любой пары слов u, v D ни одно из них не является префиксом другого. Нетрудно видеть, что если f префиксное кодирование, то множества f (An ) являются префиксными для каждого натурального n. Кодирование f будем называть префиксным в сильном смысле если множество кодовых слов f (A ) префиксное.

Множество D A называется разделимым (однозначно декодируемым), если любая последовательность записанных подряд слов из D разделяется на слова из D единственным образом. Т. е. из равенства w1 w2... wm = w1 w2... wn при wi, wi D следует, что n = m и wi = wi при i = 1,..., n. Нетрудно видеть, что префиксное множество является разделимым.

Пусть : A {0, 1} некоторое отображение. Определим отображение f : A {0, 1} равенством Непосредственно из определений имеем У т в е р ж д е н и е 33. Отображение f, определённое формулой (6.1), является кодированием тогда и только тогда, когда (A) разделимое множество.

У т в е р ж д е н и е 34. Отображение f, определённое формулой (6.1), является префиксным кодированием тогда и только тогда, когда (A) префиксное множество.

Д о к а з а т е л ь с т в о. Необходимость (). Пусть (A) не префиксное множество. Тогда найдутся такие буквы ai1, ai2 A, что кодовое слово (ai1 ) = f (ai1 ) является префиксом кодового слова (ai2 ) = f (ai2 ). Противоречие.

Достаточность (). Пусть отображение f не обладает свойством префиксности, т. е. некоторое кодовое слово f (x1... xm ) является префиксом слова f (y1... yn ) или наоборот. Пусть xk первая из букв слова x1... xm, не совпадающая с соответствующей буквой yk слова y1... yn. Тогда (xk ) префикс слова (yk ) или наоборот, но (xk ) = (yk ). Противоречие с префиксностью множества (A).

Кодирование f, определяемое формулой (6.1), называется побуквенным. Побуквенным кодированием будем называть также и отображение. Как видно из утверждения 34, построение побуквенного префиксного кодирования сводится к построению префиксного множества.

Рассмотрим некоторое двоичное дерево T. Вершины двоичного дерева T пометим двоичными словами (т. е. построим функцию : T {0, 1} ) по следующему правилу (см. рис. 1): корень дерева пометим пустым словом, если вершина t T уже помечена словом u, то её левого сына пометим словом u0, а правого u1. Вершины k-ичного дерева можно аналогичным образом пометить словами k-буквенного алфавита.

Обозначим через L(T ) множество листьев(висячих вершин) дерева T.

6.1. Префиксные и разделимые множества слов У т в е р ж д е н и е 35. Множество D {0, 1} является префиксным тогда и только тогда, когда D (L(T )) для некоторого двоичного дерева T.

Д о к а з а т е л ь с т в о. Необходимость (). Рассмотрим такое дерево T, что D (T ). Из определения отображения видно, что если вершина t помечена словом (t), то префиксами слова (t) помечены предки вершины t и только они.

Значит вершины дерева T, помеченные словами из множества D, не являются предками друг друга. Удалив из дерева T всех потомков вершин, помеченных словами из D, получим искомое дерево T.

Достаточность (). Поскольку листья дерева T не являются предками друг друга, то и соответствующие им слова не являются префиксами друг друга. Таким образом, (L(T )) является префиксным множеством.

Исследуем свойство разделимости множества D {0, 1}. Для каждого слова w D рассмотрим его всевозможные представления вида где слова wij D не совпадают со словом w при j = 1... k, слово не содержит слова из D в качестве суффикса, а слово не содержит слова из D в качестве префикса. В этом представлении число k может быть равным нулю, а слова и могут быть пустыми. Определим ориентированный граф GD, вершинами которого являются слова, из всевозможных представлений вида (6.2) слов w D, причём слова, соединены дугой, если они содержатся в одном из представлений вида (6.2).

Л е м м а 1. (Марков) Множество D {0, 1} является разделимым тогда и только тогда, когда граф GD не содержит контур, проходящий через вершину, соответствующую пустому слову.

Доказательство.

Пометим каждую дугу (1, 2 ) в графе GD словом W12 D, если имеется представление w = 1 W12 2 вида (6.2) для некоторого слова w D. В ориентированном графе GD имеется контур тогда и только тогда, когда существует слово W {0, 1}, допускающее представление Нетрудно видеть, что слово W может быть представлено в виде двух различных конкатенаций слов из множества D. Первая конкатенация составлена из слов W01, 1 W12 2, W23 и т. д., вторая из слов W01 1, W12, 2 W23 3 и т. д.

Из предыдущего утверждения немедленно следует, что для проверки разделимости конечного множества слов достаточно проделать конечное число вычислений.

З а д а ч а 15. Пусть li длина i-го слова в неразделимом множестве D {0, 1}, |D| = n. Пусть K = max k по всевозможным представлениям вида (6.2) слов из D. Тогда найдётся конкатенация, состоящая не более чем из (K + 1)(l1 +...

+ln n + 2)/2 слов из D, которая имеет представление в виде другой конкатенации слов из D.

Т е о р е м а 6. (неравенство Крафта Макмиллана) D. Тогда справедливо неравенство 2) Если выполнено неравенство (6.3), то найдётся префиксное множество D {0, 1} с длинами кодовых слов l1, l2,..., lk.

Доказательство.

1) Пусть S(n, t) количество различных упорядоченных наборов по n слов из множества D, суммарная длина которых равняется t. Из определения разделимости множества видно, что различным наборам (w1,..., wn ) Dn соответствуют различные слова W = w1... wn, |W | = t. Поэтому S(n, t) 2t. Кроме того, S(n, t) = 0 при Следовательно xn = O(n) при n. Поскольку это асимптотическое равенство возможно только при |x| 1, получаем требуемое неравенство (6.3).

2) Будем считать, что l1 l2 · · · lk. Достаточно рассмотреть случай, когда является целым и, добавив к набору длин l1, l2,..., lk ещё m чисел lk, получим для Проведём доказательство методом индукции по k. При k = 2 имеем l1 = l2 = и D = {0, 1}. Пусть неравенство (6.3) доказано для k слагаемых. Поскольку мы рассматриваем случай, когда последние два слагаемых равны: lk = lk+1. В противном случае (lk < lk+1 ) после умножения на 2lk получим в равенстве (6.4) целое число справа и дробное слева.

Рассмотрим набор длин l1, l2,..., lk1, lk 1. Поскольку для этого набора справедливо равенство (6.4), по предположению индукции найдётся префиксное множество D с соответствующими длинами слов. Пусть u D и |u| = lk 1. Тогда определим D = (D \ {u}) {u0, u1}. Очевидно, что D префиксное множество и состоит из слов требуемой длины.

6.2. Кодирование натуральных чисел 6.2. Кодирование натуральных чисел Каждому натуральному числу можно поставить в соответствие его двоичную Нетрудно видеть, что k = log n + 1. Стандартная двоичная запись не является префиксной, поэтому из слитно записанной последовательности двоичных записей чисел нельзя восстановить последовательность чисел.

Ниже будет построено префиксное кодирование натурального ряда N. Поскольку двоичная запись любого натурального числа начинается с 1, первый символ слова Bin(n) не несёт информации. Определим Bin (n) как Bin(n) без первого символа, т. е.

Bin(n) = 1Bin (n) для любого n N. Пусть k = |Bin(n)|. Определим кодирование PBin натурального ряда формулой П р и м е р 8. PBin(1) = 1, PBin(2) = 0 10 0, PBin(3) = 0 10 1, PBin(10) = 00 100 010.

Если нужно кодировать также и число 0, то определяют PBin(0) = 10, PBin(1) = 11, а остальные числа в соответствии с формулой (6.5). Кодирование PBin было предложено П. Элайесом.

1) Кодирование PBin является префиксным.

2) |PBin(n)| log n + 2 log log(n + 1) + 2.

Доказательство.

1) Пусть слово PBin(n1 ) есть префикс слова PBin(n2 ) и ki = |Bin(ni )|, i = 1, 2.

Поскольку двоичные слова Bin(k1 ) и Bin(k2 ) начинаются с символа 1, число нулей в начале слова PBin(n1 ) должно совпадать с числом нулей в начале слова PBin(n2 ), т. е. |Bin(k1 )| = |Bin(k2 )|. Так как слово Bin(k1 ) префикс слова Bin(k2 ), Bin(k1 ) = = Bin(k2 ). Тогда k1 = k2 и |Bin(n1 )| = |Bin(n2 )|. А так как слово Bin(n1 ) есть префикс слова Bin(n2 ), то Bin(n1 ) = Bin(n2 ).

2) По определению (6.5) имеем Из равенств k = log n + 1 = |Bin(n)| и |Bin (k)| = log k и неравенства log(1 + log n) 1 + log log(n + 1) при натуральных n получаем требуемое.

Следующее кодирование множества N{0} было предложено В. И. Левенштейном.

Введем обозначение (n) = |Bin (n)| и k (n) = (k1 (n)), где 1 (n) = (n). Если k (n) = 0, то определим П р и м е р 9. Lev(0) = 0, Lev(1) = 10, Lev(5) = 1110 0 01, Lev(62) = 11110 0 01 11110.

Преобразование двоичной записи числа n в код Lev(n) осуществляется достаточно просто, поскольку (n) = |Bin (n)|, 2 (n) = |Bin ((n))| и так далее. Декодирование кода Lev(n) производится в обратном порядке, причем число итераций k равняется числу единиц в кодовом слове до первого нуля.

1) Кодирование Lev является префиксным.

2) Для любого натурального k справедливо асимптотическое равенство при n.

Доказательство утверждения 37 аналогично доказательству утверждения 36.

Следующее утверждение показывает, что кодирование Левенштейна нельзя существенно улучшить в асимптотическом смысле.

при n. Тогда кодирование B не префиксное.

Д о к а з а т е л ь с т в о. Пусть B префиксное кодирование. Тогда B(N) префиксное множество. Без ограничения общности будем считать B(n) B(n + 1) для любого натурального n. Из неравенства Крафта Макмиллана следует, что ся одновременно, если последовательность n монотонна. Применяя этот признак k лучаем, что ряд 2n(1+o(1)) сходится. Это неверно, поскольку 2n(1+o(1)) при n, что противоречит необходимому признаку сходимости ряда.

6.3. Теорема кодирования Шеннона Пусть заданы некоторый источник сообщений A, P и кодирование f : A {0, 1}. Стоимостью кодирования f источника A, P будем называть Таким образом, стоимость кодирования Cn (f, P ) равна средней длине кодового слова, вычисленной по всем исходным словам длины n.

Разность Rn (f, P ) = Cn (f, P ) Hn (P ) называется избыточностью. Величину r(f, P ) = lim n Rn (f, P ) будем называть предельной избыточностью кодирования f, если этот предел существует.

1) Для любого префиксного кодирования f и любого источника сообщений A, P избыточность неотрицательна, т. е. Rn (f, P ) 0.

6.3. Теорема кодирования Шеннона 2) Для любого источника сообщений A, P найдётся такое префиксное в сильном смысле кодирование f, что r(f, P ) = 0.

Доказательство.

1) Из определений, неравенства Йенсена для функции log t и неравенства Крафта Макмиллана для произвольного префиксного кодирования f имеем 2) Для любого слова w An определим lw = log P (w). Имеем Из неравенства Крафта Макмиллана следует, что найдётся префиксное кодирование fn : An {0, 1} с длинами кодовых слов |fn (w)| = lw. Определим кодирование f равенством f (w) = PBin(|w|)f|w| (w). Нетрудно видеть, что слово f (u) не может быть префиксом f (v) при |u| = |v|, из-за того, что PBin префиксное кодирование натурального ряда, а при |u| = |v| = n и u = v, из-за того, что fn префиксное кодирование A. Из утверждения 36 имеем В теории информации принято оценивать качество кодирования, исходя из сходимости стоимости кодирования к энтропии, т. е. сходимости в среднем длины кода к энтропии источника сообщений. Использованное при доказательстве теоремы Шенннона кодирование, а также многие из методов кодирования, которые будут рассмотрены ниже, обеспечивают сходимость длины кодовых слов к энтропии стационарного марковского источника не только в среднем, но и по вероятности.

Другим существенным качеством метода кодирования сообщений является эффективность выполнения операций кодирования и декодирования. Кодирование, использованное при доказательстве теоремы Шеннона, было задано неявно. В дальнейшем будут рассмотрены методы кодирования, имеющие эффективную реализацию.

З а д а ч а 17. Докажите, что для любого источника сообщений A, P и любого кодирования f справедливо неравенство r(f, P ) 0.

Здесь следует отметить связь кодирования с асимптотически нулевой избыточностью с задачей построения псевдослучайных последовательностей. Действительно, предположим нам удалось построить абсолютно эффективное кодирование, такое что полученный код любого слова имеет минимальную длину. Тогда текст преобразованный этим кодированием будет являться псевдослучайной последовательностью независимых испытаний с вероятностями нуля и единицы равными 1/2. Действительно, любое отклонение эмпирической вероятности какого-либо слова в кодовой последовательности сделало бы эмпирическую энтропию последовательности в некоторой марковской модели строго меньшей 1 и по теореме Шеннона обеспечило бы возможность повторного сжимающего кодирования кодовой последовательности.

6.4. Побуквенное кодирование Из определения побуквенного кодирования в § 6.1 видно, что для задания побуквенного кодирования f достаточно определить кодовые слова f (a) для всех букв a A. Кодовые слова f (w) для слов w A определяются в соответствии с формулой (6.1). В этом разделе будут рассмотрены классические коды Шеннона, Шеннона Фано, Хаффмена и получены оценки их избыточности.

У т в е р ж д е н и е 39. Пусть f побуквенное кодирование стационарного источника A, P. Тогда n Cn (f, P ) = C1 (f, P ) для любого натурального n.

Доказательство.

Докажем методом индукции равенство Cn (f, P ) = nC1 (f, P ). Из определения стоимости кодирования и формулы (6.1) имеем кодирование. Тогда для любого натурального n.

утверждения 30 имеем H(P ) = n Hn (P ) = H1 (P ). Тогда Построим кодирование Шеннона для произвольного источника сообщений A, P.

Пронумеруем буквы алфавита так, чтобы P (a1 ) P (a2 ) · · · P (ak ) > 0. Определим числа i рекуррентно: 1 = 0, i+1 = i + P (ai ) при 1 i k. Ясно, что 0 i < для любого i = 1,..., k. В качестве кодового слова fSh (ai ) возьмем log P (ai ) первых после запятой символов в позиционной двоичной записи числа i.

П р и м е р 10. Пусть P (a1 ) = 1/2, P (a2 ) = 1/3, P (a3 ) = 1/8, P (a4 ) = 1/24. Тогда имеем двоичные записи чисел: 1 = 0, 000.., 2 = 0, 1000.., 3 = 0, 1101.., 4 = 0, 11110... По определению кода Шеннона получаем fSh (a1 ) = 0, fSh (a2 ) = 10, fSh (a3 ) = 110, fSh (a4 ) = 11110.

6.4. Побуквенное кодирование 1) Кодирование Шеннона fSh префиксное.

2) R1 (fSh, P ) 1 для любого источника сообщений A, P.

Д о к а з а т е л ь с т в о. Из определения позиционной двоичной записи числа следует, что первые после запятой n двоичных знаков чисел a и b (1 > a > b > 0) совпадают, если и только если a b < 2n.

Пусть j > i, тогда Таким образом, первые после запятой |fSh (ai )| символов в двоичной записи числа j не совпадают с кодовым словом fSh (ai ). Поскольку P (aj ) P (ai ), имеем |fSh (aj )| |fSh (ai )|, и префиксность множества fSh (A) доказана. Тогда пункт 1) следует из утверждения 34. Неравенство R1 (fSh, P ) 1 непосредственно вытекает из равенства fSh (ai ) = log P (ai ).

Построим кодирование Шеннона Фано fSF для произвольного источника сообщений A, P. Пронумеруем буквы алфавита так, чтобы P (a1 ) P (a2 )...

· · · P (ak ) > 0. Не меняя порядка букв, разделим алфавит на две части так, чтобы суммы вероятностей букв в каждой из частей были наиболее близкими. Запишем 0 в качестве первого символа кода для всех букв первой половины алфавита и в качестве первого символа кода для всех букв второй половины. Каждую из двух половин алфавита делим опять на две части с возможно близкими вероятностями и приписываем к коду первых частей 0, к коду вторых частей 1. Процесс деления продолжаем пока в каждой из частей не останется лишь по одной букве.

P (a5 ) = P (a6 ) = 0, 1. Построим кодовые слова Шеннона Фано fSF для этого источника. Кодовое дерево изображено на рис. 2. Получаем кодовые слова:

fSF (a1 ) = 00, fSF (a2 ) = 01, fSF (a3 ) = 100, fSF (a4 ) = 101, fSF (a5 ) = 110, fSF (a6 ) = 111.

2) R1 (fSF, P ) R1 (fSh, P ) для любого источника сообщений A, P.

Доказательство.

1) Из построения видно, что кодовые слова Шеннона Фано являются пометками листьев некоторого двоичного дерева. Тогда из утверждений 34 и 35 следует, что кодирование fSF префиксное.

2) Заметим, что если P (ai ) = 2mi, где mi целые числа для любого i = 1,..., k, то |fSF (ai )| = mi. Действительно, поскольку вероятности букв ai i = 1... k упорядочены по убыванию, алфавит A можно, не меняя порядка букв, разделить на две части, с равными суммами вероятностей букв. Очевидно, что для каждой из частей алфавита верно то же самое. Таким образом, мы получаем, что все выделенные на k-й итерации части алфавита имеют одинаковые вероятности, равные 2k. Следовательно, буква ai, имеющая вероятность p(ai ) = 2mi, выделяется на mi -ом шаге и |fSF (ai )| = mi = |fSh (ai )|. Значит если числа mi целые, то утверждение пункта 2) верно.

Пусть некоторые из чисел mi не целые. Введем обозначение P (ai ) = 2mi. Тогда P (ai ) 1. Добавим к алфавиту A столько букв ak+1, ak+2,..., ak с вероятностями i= P (ak+j ) = P (ak ), чтобы P (ai ) = 1. Построим кодирование Шеннона Фано fSF для источника Бернулли A, P с алфавитом A = {a1,..., ak } и вероятностями букв P (ai ). По построению k k и P (ai ) P (ai ) при i = 1,..., k. Тогда после каждого деления на части алфавитов A и A часть алфавита A будет содержать не больше букв, чем соответствующая часть алфавита A. Следовательно Но |fSF (ai )| = log p(ai ) = |fSh (ai )| при любом i = 1,..., k. Тогда из неравенства (6.6) следует, что C1 (fSF, P ) C1 (fSh, P ).

Префиксное побуквенное кодирование f0 называется оптимальным для источника Бернулли A, P, если для любого префиксного кодирования f источника A, P справедливо неравенство R1 (f0, P ) R1 (f, P ). Заметим, что для оптимальности кодирования f0 достаточно выполнения неравенства R1 (f0, P ) R1 (f, P ) для произвольного префиксного побуквенного кодирования f, поскольку сужение на A любого префиксного кодирования можно рассматривать как побуквенное префиксное кодирование.

Для каждого источника Бернулли A, P существует оптимальное кодирование, поскольку множество префиксных кодирований источника A, P с избыточностью, меньшей либо равной 1, непусто и конечно. Для одного источника может иметься несколько оптимальных кодирований с разными наборами длин кодовых слов. Среди них всегда найдётся кодирование удовлетворяющее условиям следующего утверждения.

У т в е р ж д е н и е 43. Пусть A, P некоторый источник Бернулли с алфавитом A = {a1, a2,..., ak } и упорядоченными вероятностями появления букв:

P (a1 ) P (a2 ) · · · P (ak ) > 0. Тогда найдётся такое оптимальное кодирование f0 источника A, P, что |f0 (a1 )| |f0 (a2 )| · · · |f0 (ak1 )| = |f0 (ak )|, причем кодовые слова f0 (ak1 ) и f0 (ak ) отличаются только последним символом.

Д о к а з а т е л ь с т в о. Пусть f некоторое оптимальное кодирование источника A, P и |f (ai )| > |f (aj )| для некоторых i < j. Если P (ai ) > P (aj ), то, поменяв местами кодовые слова f (ai ) и f (aj ), соответствующие буквам ai и aj, мы получим код, имеющий меньшую стоимость, что противоречит оптимальности кодирования f.

6.4. Побуквенное кодирование Если P (ai ) = P (aj ), то, поменяв местами кодовые слова f (ai ) и f (aj ), мы получим кодирование той же стоимости. Следовательно, существует оптимальное кодирование f0 источника сообщений A, P, для которого справедливы неравенства Пусть f0 (ak ) = w, {0, 1}. Предположим, что не существует кодового слова f0 (ai ), отличного от слова w только последним символом. Тогда множество f0 (A) {w} \ {w} является префиксным. Следовательно, заменив кодовое слово f0 (ak ) = w на слово w мы получим префиксное кодирование меньшей стоимости, что противоречит оптимальности кодирования f0. Значит предположение было неверным и найдется кодовое слово f0 (ai ), отличающиеся от f0 (ak ) только последним символом.

Тогда Поменяв местами кодовые слова f0 (ai ) и f0 (ak1 ), мы не изменим стоимости кодирования и получим оптимальное кодирование с требуемыми свойствами.

Определим процедуру сжатия источника A, P с алфавитом A = {a1, a2,..., ak }, состоящую в слиянии двух наименее вероятных букв. Полагаем, что буквы ai занумерованы по убыванию вероятностей p(a1 ) p(a2 ) · · · p(ak ). Пусть A = {a1, a2,..., ak2, ak1 }. Зададим вероятности букв P (ai ) = P (ai ) при i < k 1 и P (ak1 ) = P (ak1 ) + P (ak ).

Метод Хаффмена построения оптимального кодирования для источников Бернулли состоит в следующей рекуррентной процедуре. Для любого источника с двухбуквенным алфавитом A = {a1, a2 } побуквенное кодирование Хаффмена определяется равенствами fH (a1 ) = 0, fH (a2 ) = 1.

Пусть кодирование Хаффмена определено для всех источников Бернулли с алфавитом из k букв. Рассмотрим источник Бернулли A, P с алфавитом из k + буквы. Перенумеруем буквы ai по убыванию вероятностей P (a1 ) P (a2 )...

кодирование Хаффмена для источника A, P определяется следующим образом:

fH (ai ) = fH (ai ) для всех i = 1,..., k 1, fH (ak ) = fH (ak )0, fH (ak+1 ) = fH (ak )1.

У т в е р ж д е н и е 44. Кодирование Хаффмена является префиксным.

Д о к а з а т е л ь с т в о. Применим метод индукции по мощности алфавита k.



Pages:     || 2 |


Похожие работы:

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ Государственное образовательное учреждение высшего профессионального образования Московский государственный гуманитарный университет имени М. А. Шолохова ФАКУЛЬТЕТ ЖУРНАЛИСТИКИ Кафедра журналистики и медиаобразования МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ ВЫПУСКНЫХ КВАЛИФИКАЦИОННЫХ РАБОТ Москва, 2011 Утверждено Решением Ученого совета факультета журналистики 9 февраля 2011 г. Протокол № 6 Составители: Декан факультета журналистики, кандидат филологических наук,...»

«Министерство образования и науки, молодежи и спорта Украины Севастопольский национальный технический университет МЕТОДИЧЕСКИЕ УКАЗАНИЯ к выполнению курсовой работы по учебной дисциплине Планирование и контроль на предприятии для студентов направления 6.030504 Экономика предприятия всех форм обучения Севастополь 2013 Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) УДК Методические указания к выполнению курсовой работы по учебной дисциплине...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ А.А. Горбачёв, В.В. Коротаев, В.Л. Мусяков, А.Н. Тимофеев ИЗМЕРИТЕЛЬНЫЕ ОПТИКО-ЭЛЕКТРОННЫЕ ПРИБОРЫ И СИСТЕМЫ Методические указания к курсовому проекту по содержанию, оформлению и защите Санкт-Петербург 2008 УДК 621.383 + 681.7.013.6 + 681.586.5 Горбачёв А.А., Коротаев В.В., Мусяков В.Л., Тимофеев А.Н....»

«Государственное образовательное учреждение высшего профессионального образования Московская академия рынка труда и информационных технологий Дворец Н.Н., Дудников А.С., Фильченкова Е.А., Юрченко Е.В. ИНВЕСТИРОВАНИЕ В ЦЕННЫЕ БУМАГИ Учебно-методическое пособие Москва Издательство МАРТИТ 2012 1 УДК 330.1 ББК 65.01 Д-24 Дворец Н.Н., Дудников А.С., Фильченкова Е.А., Юрченко Е.В. Инвестирование в ценные бумаги: Учебно-методическое пособие. Изд-во МАРТИТ, 2012. 147 с. В учебно-методическом пособии...»

«Образец подзаголовка Q ВК Полховская Т.М. Стандарты ИСО серии 9000 и бережливое производство. XV Международный семинар Непрерывное совершенствование Образец подзаголовка деятельности организаций Москва, НИТУ МИСиС, 2010 Q ВК Комплекс стандартов ИСО серии 9000 Системы менеджмента качества. ИСО 9000:2005 Основные положения и словарь Системы менеджмента качества. ИСО 9001:2008 Требования Менеджмент для достижения устойчивого успеха организации. – ИСО 9004:2009 Подход на основе менеджмента качества...»

«Минобрнауки России Филиал государственного образовательного учреждения высшего профессионального образования Вятского государственного гуманитарного университета в г. Кирово-Чепецке Кафедра экономики и управления УТВЕРЖДАЮ Зав. кафедрой экономики и управления Савиных Г.П. Подпись 03.02.2011 УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС учебной дисциплины Социология и психология управления для специальности: 080505.65 Управление персоналом Кирово-Чепецк Учебно-методический комплекс составлен в соответствии с ГОС...»

«Московский государственный университет им. М.В.Ломоносова Факультет вычислительной математики и кибернетики Волкова И.А., Руденко Т.В. Формальные грамматики и языки. Элементы теории трансляции (издание второе, переработанное и дополненное) 1999 УДК 519.682.1+681.142.2 Приводятся основные определения, понятия и алгоритмы теории формальных грамматик и языков, некоторые методы трансляции, а также наборы задач по каждой из рассматриваемых тем. Излагаемые методы трансляции проиллюстрированы на...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ САНКТ-ПЕТЕРБУРГСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ В.М. Медунецкий Основы обеспечения качества и сертификации промышленных изделий Учебное пособие Санкт-Петербург 2013 УДК.004.12;.001.63 Медунецкий В.М. Основы обеспечения качества и сертификация промышленных изделий. Учебное пособие. – СПб НИУ ИТМО, 2013. - 61 с. Рецензент: к.т.н., Генеральный директор ООО Балт-Систем Жигалёв Н.Н. В...»

«Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ЛЕСОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ имени С.М. Кирова Кафедра лесной таксации, лесоустройства и геоинформационных систем ТАКСАЦИЯ ЛЕСА Методические указания по выполнению курсовой работы для подготовки бакалавров по направлению 250100 Лесное дело всех форм обучения САНКТ-ПЕТЕРБУРГ 2013 Рассмотрены и рекомендованы...»

«Федеральное агентство по образованию МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ И КОНТРОЛЬНЫЕ РАБОТЫ ПО ДИСЦИПЛИНЕ ФАРМАКОЛОГИЯ для студентов заочного отделения фармацевтического факультета. Часть 1 Учебно-методическое пособие для вузов Воронеж 2010 2 Утверждено Научно-методическим советом фармацевтического факультета 17.11.2009 г., протокол №1503-09. Авторы: А.В. Бузлама, В.В. Андреева, В.А. Николаевский, С.Я. Дьячкова Рецензент: заведующий кафедрой фармакологии ГОУ ВПО ВГМА им. Н.Н. Бурденко, д.м.н.,...»

«КРАТКИЙ ОБЗОР ВТОРИЧНОГО РЫНКА ЖИЛОЙ НЕДВИЖИМОСТИ г. НОВЫЙ УРЕНГОЙ. АПРЕЛЬ 2014г.1 ОСНОВНЫЕ РЕЗУЛЬТАТЫ В апреле 2014г. удельная цена вторичного жилья составила 102447 руб./кв.м., снизившись по сравнению с мартом 2014г. на 0,89%. Прирост удельной цены с начала года (январь 2014г.) составил 1,49% (или 1553 руб.). С начала года наблюдался постоянный рост объема предложения, однако в апреле он немного снизился (темп прироста по отношению к марту – 2,63%). Наибольший объем предложения представлен...»

«Пояснительная записка Рабочая программа составлена на основе Федерального Государственного стандарта, Программы для общеобразовательных учреждений. Химия //Программы для общеобразовательных учреждений. Химия. 8-11 классы. - М.: Просвещение, 2009. – 55 с.//. Н.Н.Гара. Изучение химии в 9 классе направлено на достижение следующих целей: освоение важнейших знаний о химической символике, об основных химических понятиях, фактах, теориях и законах химии; овладение умениями наблюдать химические...»

«СОДЕРЖАНИЕ Легкая промышленность Экономика Естественные и технические науки Общественные науки Прочая литература Текущий библиографический указатель Новые поступления состоит из перечня ежемесячных поступлений в фонд библиотеки УО ВГТУ новой литературы. Целью указателя является информирование профессорско-преподавательского состава, сотрудников, аспирантов, магистрантов, студентов университета, слушателей ФПК и ПК, ФДП и ПО о новых поступлениях литературы по следующим отраслям знаний: легкая...»

«1. ЦЕЛЕВАЯ УСТАНОВКА И МЕТОДИЧЕСКИЕ УКАЗАНИЯ Программа для подготовки к сдаче конкурсного вступительного экзамена в адъюнктуру предназначена для оказания методической помощи абитуриентам в подготовке к сдаче вступительного экзамена в адъюнктуру по специальности 12.00.02 – Конституционное право; конституционный судебный процесс; муниципальное право. Программа разработана в соответствии с требованиями государственного образовательного стандарта высшего профессионального образования. В программе...»

«К.А ПАШКОВ, А.В. БЕЛОЛАПОТКОВА, УЧЕБНО-МЕТОДИЧЕСКОЕ ПОСОБИЕ К СЕМИНАРСКИМ ЗАНЯТИЯМ ПО ИСТОРИИ МЕДИЦИНЫ МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ МЕДИКОСТОМАТОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ Министерства здравоохранения Российской Федерации К.А ПАШКОВ, А.В. БЕЛОЛАПОТКОВА УЧЕБНО-МЕТОДИЧЕСКОЕ ПОСОБИЕ К СЕМИНАРСКИМ ЗАНЯТИЯМ ПО ИСТОРИИ МЕДИЦИНЫ для студентов стоматологического факультета Рекомендуется Учебно-методическим объединением по медицинскому и фармацевтическому образованию вузов России в качестве учебного пособия...»

«Государственное учреждение образования Институт бизнеса и менеджмента технологий Белорусского государственного университета Кафедра экономики и финансов Методические указания по выполнению и защите курсовой работы по дисциплине Экономическая теория для специальности 1-26 02 01 Бизнес-администрирование МИНСК 2010 УДК ББК Рекомендовано к утверждению на заседании кафедры экономики и финансов ИБМТ БГУ протокол № 2 от 08.10.2010г. Авторы-составители: к.э.н., доц. О. Н. Ерофеева к.э.н., доц. И. В....»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОУ ВПО САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ГОРНЫЙ ИНСТИТУТ им. Г.В. ПЛЕХАНОВА (технический университет) Филиал СПГГИ (ТУ) в г. Кировск УТВЕРЖДАЮ Директор филиала А.И. Ганичева 2010г. ПОЛОЖЕНИЕ О ПОРЯДКЕ ОТЧИСЛЕНИЯ, ВОССТАНОВЛЕНИЯ И ПЕРЕВОДА СТУДЕНТОВ Зам. директора по В.А. Ганичева учебной работе Зав. организационнометодическим отделом Л.А. Баскакова Зав. отделением № 1 Н.В. Фирсова Зав. отделением № 2 Т.Ю. Сидорова Кировск 1.ОБЩИЕ ПОЛОЖЕНИЯ 1.1.Настоящее...»

«Кафедра ИСиКТ 1. Анализ данных. Методические рекомендации // Составитель: Грешнов М.В. – Самара: МИР, 2012. 2. Анализ данных. Методические рекомендации по организации самостоятельной работы // Составитель: Грешнов М.В. – Самара: МИР, 2012. 3. Архитектура предприятия. Методические рекомендации // Составитель: Хаймович И.Н. – Самара: МИР, 2012. 4. Архитектура предприятия. Методические рекомендации по организации самостоятельной работы // Составитель: Хаймович И.Н. – Самара: МИР, 2012. 5. Базы...»

«Министерство образования Республики Беларусь УО ПОЛОЦКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ МЕТОДИЧЕСКИЕ УКАЗАНИЯ к выполнению курсовой работы по дисциплине Анализ хозяйственной деятельности для студентов специальности 1-25 01 08 очной (заочной) формы обучения г. Новополоцк, ПГУ, 2010 УДК 657(075.8) ББК 65.052 (4 БЕИ) я 73 Одобрено и рекомендовано к изданию Методической комиссией финансово-экономического факультета в качестве методических указаний (протокол № от 20_г.) кафедра бухгалтерского учета и...»

«Министерство образования и науки Челябинской области государственное бюджетное образовательное учреждение среднего профессионального образования (среднее специальное учебное заведение) Южно-Уральский многопрофильный колледж ГБОУ СПО (ССУЗ) ЮУМК Вопросы к экзаменам и зачетам Задания для выполнения контрольных работ Вариант № 4 III курс правового заочного отделения Специальность: Право и организация социального обеспечения Челябинск 2013 г. 1 МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНЫХ РАБОТ...»






 
2014 www.av.disus.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.