Теория информации и кодирование [1] // Владимир Потапов

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

[@Art-iu9pv]

ДАВАЙ, ЖГИ!