Научно-образовательный центр при МИАН

Список спецкурсов на весенний семестр 2005/2006

Введение в теорию информации

д.ф.-м.н. Александр Семенович Холево

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

В лекциях излагаются основные понятия и результаты теории информации: энтропия случайного источника и оптимальное сжатие данных; количество информации и пропускная способность канала связи; дается понятие о методах оптимального кодирования. Значительное внимание уделено взаимосвязям со статистической механикой (Н-теорема, асимптотическая равнораспределенность) и математической статистикой (метод типов, большие уклонения). Главное внимание обращено на принципиальные вопросы, а не технические детали и обобщения, поэтому большая часть изложения ведется на широко доступном уровне дискретных случайных величин.

Лекция 1. Энтропия и информация

1. Энтропия и условная энтропия случайной величины
2. Количество информации. Относительная энтропия
3. Неравенства об обработке данных
4. Монотонность относительной энтропии и Н-теорема

Лекция 2. Асимптотическая равнораспределенность

1. Типичные последовательности и асимптотическая равнораспределенность
2. Оптимальное кодирование случайного источника и энтропия

Лекция 3. Оптимальное сжатие данных

1. Коды с переменной длиной слов
2. Неравенство Крафта
3. Коды Хаффмена
4. Генерирования дискретных распределений вероятностей

Лекция 4. Пропускная способность канала связи

1. Определение канала и пропускной способности
2. Блоковые коды для канала без памяти

Лекция 5. Теорема кодирования Шеннона

1. Доказательство прямого утверждения и метод случайных кодов
2. Неравенство Фано. Доказательство слабого обращения
3. Канал с обратной связью
4. Коды Хэмминга

Лекция 6. Метод типов

1. Метод типов
2. Универсальное кодирование случайного источника

Лекция 7. Теория информации и математическая статистика

1. Теорема Санова о больших уклонениях
2. Лемма Неймана–Пирсона. Лемма Стейна
3. Байесовское различение двух гипотез. Граница Чернова

Лекция 8. Энтропия стационарного источника

1. Энтропия цепи Маркова
2. Энтропия случайного блуждания на графе
3. Теорема Шеннона–Бреймана–Макмиллана
4. Теорема совместного кодирования источника и канала

Лекция 9. Применения теоретико-информационных методов

1. Универсальный код Лемпеля–Зива
2. Применения к стационарному рынку акций

Лекция 10. Дифференциальная энтропия

1. Асимптотическая равнораспределенность для непрерывных случайных величин
2. Плотность относительной энтропии и взаимной информации
3. Теорема кодирования для гауссовского канала связи

Лекция 11. Точность воспроизведения непрерывного источника

1. Дискретизация непрерывной случайной величины
2. Эпсилон-энтропия
3. Теорема о точности воспроизведения
4. Точность воспроизведения для гауссовского источника

Лекция 12. Теория информации и понятие сложности по Колмогорову

1. Модели вычислений
2. Алгоритмическая энтропия
3. Алгоритмически случайные последовательности
4. Универсальная вероятность
5. Число Чаитина
6. Достаточная статистика Колмогорова

Литература

1. T. M. Cover, J. A. Thomas, Elements of Information Theory. New York: Wiley, 1991.
2. Р. Галлагер, Теория информации и надежная связь. Москва: Сов. Радио, 1974.

Список спецкурсов на весенний семестр 2005/2006