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