Верещагин Н.К., Щепин Е.В. ИНФОРМАЦИЯ, КОДИРОВАНИЕ И ПРЕДСКАЗАНИЕ:
Введение в прикладную теорию информации. Информация по Хартли, энтропия Шеннона и колмогоровская сложность. Изд. 2, испр.

Информация, кодирование и предсказание: Введение в прикладную теорию информации. Информация по Хартли, энтропия Шеннона и колмогоровская сложность 2025. 248 с.

Серия: ФУНДАМЕНТ БУДУЩЕГО: Юбилейная серия в честь 270-летия МГУ имени М.В. Ломоносова

Серия: Основы защиты информации

Белая офсетная бумага

Твердый переплет

Аннотация

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

Автор первой части, Е. В. Щепин, рассматривает понятия теории информации как базу для решения задач машинного обучения, и прежде всего — задач построения классификатора по эмпирическим данным.

Особое внимание... (Подробнее)

Содержание

Предисловие к серии «Учебник Школы прикладной математики и информатики МФТИ»				5
Часть 1. Введение в прикладную теорию информации				7
Предисловие				7
Лекция 1. Информационная емкость символа				8
1.1. Двоичные коды				8
1.2. Оптимальное кодирование				9
1.3. Блокировка				10
1.4. Бит и трит				11
1.5. Формула Хартли				13
1.6. Задача сжатия файла				13
1.7. Равночастотное кодирование				14
1.8. Задача поиска				15
1.9. Количество информации по Хартли				17
Лекция 2. Энтропия				18
2.1. Вывод формулы Шеннона из формулы Хартли				18
2.2. Информативность двоичного слова с произвольной декомпозицией				19
2.3. Вывод формулы Шеннона				19
2.4. Асимптотические оценки				20
2.5. Сжатие файла с данной декомпозицией				21
2.6. Вероятностный подход				22
2.7. Префиксный код				23
2.8. Алгоритм Хаффмана				24
2.9. Свойства функции энтропия				25
2.10. Энтропия как мера неопределенности				26
2.11. Отгадывание слов. Вариант 1				26
2.12. Отгадывание слов. Вариант 2				28
Задания к лекциям 1 и 2				29
Лекция 3. Информационная зависимость				41
3.1. Энтропия и информация				41
3.2. Совместное распределение				41
3.3. Условная и взаимная информация				42
3.4. Функциональная зависимость				42
3.5. Критерий независимости				44
3.6. Относительное кодирование				46
3.7. Расщепляющее кодирование				47
3.8. Случайные последовательности				48
3.9. Суперпозиция неопределенностей				49
3.10. Задания к лекции				51
Лекция 4. Защита от шума				54
4.1. Ошибки при передаче информации				54
4.2. Контроль четности				54
4.3. Контрольная сумма				55
4.4. Локализация ошибки				55
4.5. Кодирование				56
4.6. Декодирование				56
4.7. Определение фальшивой монеты				57
4.8. Дерево алгоритма				57
Лекция 5. Информативность классификатора				62
5.1. Задача распознавания логов интернет-сессии				62
5.2. Точность-покрытие				64
5.3. Информативность классификатора				65
5.4. Неравенство Фано				66
5.5. Закон геометрической прогрессии (ЗГП)				68
5.6. Проверка закона геометрической прогрессии				69
5.7. Задания к лекции				69
Лекция 6. Проблема недостаточной статистики				71
6.1. Вычисления H1				71
6.2. Байесовская регуляризация				72
6.3. Вторичная статистика				73
6.4. Типичные вероятности				75
6.5. Третичная статистика				76
6.6. Алгоритм Малыхина				77
6.7. Закон сложения вероятностей				80
Часть 2. Лекции по теории информации				81
Предисловие				81
Лекция 7. Информация по Хартли				82
7.1. Игра в 10 вопросов				83
7.2. Упорядочивание n чисел: верхняя и нижняя оценки				84
7.3. Упорядочение 5 различных чисел с помощью 7 сравнений				85
7.4. Поиск фальшивой монетки из 81 за 4 взвешивания				88
7.5. Поиск фальшивой монетки из 12 за 3 взвешивания				88
7.6. Цена информации				91
7.7. Задачи для самостоятельной работы				94
Лекция 8. Логика знания				98
8.1. Сообщения и увеличение знаний				99
8.2. Карточки с цифрами				101
8.3. Задача о шляпах				102
8.4. Задачи для самостоятельной работы				103
8.5. Отступление: парадокс неожиданной контрольной				104
Лекция 9. Коммуникационная сложность				107
9.1. Среднее арифметическое и медиана мультимножества				109
9.2. Предикат равенства				110
9.3. Метод трудных множеств и метод размера прямоугольников				112
9.4. Метод ранга матрицы				114
9.5. Вероятностные протоколы				115
Лекция 10. Энтропия Шеннона				118
10.1. Определение				118
10.2. Коды				119
10.3. Коммуникационная сложность в среднем и энтропия Шеннона				131
10.4. Неравенство Макмиллана				132
10.5. Энтропия пары случайных величин				133
10.6. Условная энтропия				135
10.7. Независимость и энтропия				139
10.8. «Релятивизация» и информационные неравенства				141
10.9. Задачи для самостоятельной работы				146
Лекция 11. Кодирование текстов с учетом частотных закономерностей				148
11.1. Кодирование текста с известными частотами букв				149
11.2. Сбалансированные слова				152
11.3. Учет частот пар, троек и т. д.				155
11.4. Неинъективные кодирования				162
11.5. Передача информации при наличии дополнительной информации у принимающей стороны.Теорема Вольфа—Слепяна.				168
11.6. Каналы с помехами				171
Лекция 12. Предсказания				180
12.1. Предсказания в казино				180
12.2. Предсказания с экспертами				185
Лекция 13. Колмогоровская сложность				197
13.1. Что такое колмогоровская сложность?				197
13.2. Оптимальные способы описания				199
13.3. Сложность и случайность				202
13.4. Невычислимость KS и парадокс Берри				204
13.5. Перечислимость сверху колмогоровской сложности				206
13.6. Сложность и информация				208
13.7. Сложность пары слов				210
13.8. Условная колмогоровская сложность				214
13.9. Сложность и энтропия				225
13.10. Применения колмогоровской сложности				228
Задания к лекциям 7–13				234
Литература				242

Об авторах

Верещагин Николай Константинович

Доктор физико-математических наук, профессор кафедры математической логики и теории алгоритмов механико-математического факультета МГУ имени М. В. Ломоносова. Профессор факультета компьютерных наук НИУ ВШЭ и Школы анализа данных ООО «Яндекс». Учился в МГУ на механико-математическом факультете, который окончил в 1981 г. Там же окончил аспирантуру и защитил кандидатскую диссертацию под руководством В. А. Успенского в 1986 г. В 1996 г. защитил диссертацию на степень доктора физико-математических наук по теме «Релятивизуемость в структурной теории сложности вычислений». Специализируется в теории алгоритмов. Член Европейской академии по секции информатики. Автор и соавтор более 100 публикаций в международных рецензируемых научных изданиях и 8 книг.

Щепин Евгений Витальевич

Член-корреспондент РАН, доктор физико-математических наук, главный научный сотрудник математического института имени В. А. Стеклова РАН. Окончил механико-математический факультет МГУ в 1973 г. Основная математическая специальность — геометрия и топология. Его цикл работ по общей топологии был отмечен премией Московского математического общества для молодых математиков в 1977 г. В 1979 г. защитил докторскую диссертацию на тему «Метод обратных спектров в топологии бикомпактов». В 1980-е гг. его интересы сместились к геометрической топологии; он доказал гипотезу Гильберта—Смита для липшицевых отображений, и вместе со своим учеником А. Н. Дранишниковым решил старую проблему теории размерности, построив двумерное подмножество трехмерного евклидова пространства, которое остается двумерным после домножения на континуум. В 1990-е гг. увлекся приложениями топологии к распознаванию образов; под его руководством была разработана программа оптического распознавания символов Крипт, основанная на открытом им топологическом коде (ПРС-код).

Е. В. Щепин многие годы преподавал в Колмогоровском интернате (выпускником которого является) математический анализ. В Интернете известен курс анализа Щепина, прочитанный им в 2001 г. в Швеции — «Uppsala lectures on Calculus». Работа в «Яндексе» и Школе анализа данных (2007–2013) привели его к разработке метода вторичной статистики, позволяющего определять количество полезной информации в логах интернет-сессий. В 2011 г. избран членом-корреспондентом РАН.