Теория информации и кодирование. Лекция 2

Теория информации — математическая дисциплина, в которой одновременно применяются методы многих разделов математики: теории вероятностей, теории алгоритмов, комбинаторики. Она занимается, в числе прочих, вопросами — как лучше всего сжать файл? Сколько информации может содержать данное сообщение? Как возможно точно передать сообщение, несмотря на помехи в канале связи? Как защитить сообщение от несанкционированного доступа? Ключевые идеи о том как решать перечисленные задачи были изложены в статье К. Шеннона «Математическая теория информации», где впервые было введено понятие энтропии (количества информации) и намечены контуры будущей теории.
Мы займёмся введением в теорию сжатия дискретных данных (в отличие от непрерывных; там — своя специфика). Рассмотрим несколько алгоритмов, которые применяются в универсальных архиваторах (zip, rar). А также сделаем первые шаги (определим понятия и докажем начальные теоремы) на пути, ведущем к теоретическому обоснованию эффективности этих алгоритмов.
Программа
1. Три подхода к понятию сложности сообщений: алгоритмический, комбинаторный и вероятностный. Определение и свойства энтропии.
2. Марковские цепи. Эргодическая теорема для дискретной марковской цепи. Конечные автоматы. Марковские источники сообщений и их энтропия.
3. Префиксное кодирование. Неравенство Крафта–Макмиллана. Теорема кодирования Шеннона. Арифметическое кодирование. Преобразование Барроуза–Уиллера.
4. Метод кодирования Лемпела–Зива и его модификации. Оценка эффективности кодирования Лемпела–Зива.