Делимся записью открытой лекции Александра Смаля «Как измерить количество информации?».
Александр — сотрудник ПОМИ РАН, куратор Computer Science клуба, читает лекции в ИТМО, СПбГУ и ВШЭ.
Мы ежедневно работаем с информацией из разных источников и поэтому имеем интуитивные представления о том, что означает, когда один источник является более информативным, чем другой. Однако далеко не всегда понятно, как это правильно определить формально. Не всегда большое количество текста означает большое количество информации. Например, среди СМИ распространена практика, когда короткое сообщение из ленты информационного агентства переписывают в большую новость, но при это не добавляют никакой «новой информации». Или другой пример. Рассмотрим текстовый файл с романе Л.Н. Толстого «Война и мир» в кодировке UTF-8. Его размер 3.2 Мб. Сколько информации содержится в этом файле? Изменится ли это количество, если файл перекодировать в другую кодировку? А если заархивировать? Сколько информации вы получите, если прочитаете этот файл? А если прочитаете его второй раз? На лекции Александр расскажет про различные подходы к тому, как можно отвечать на эти вопросы.
В лекции рассмотрим три подхода к определению «количества информации»: комбинаторный (информация по Хартли), вероятностный (энтропия Шеннона) и алгоритмический (Колмогоровская сложность). Кроме этого мы поговорим про различные применения аппарата теории информации в различных областях компьютерных наук.
Для комфортного прослушивания лекции желательно иметь базовые познания в теории вероятностей и программировании.
Слушатели научатся отвечать на вопросы:
— Как сообщить дробное число битов информации?
— Сколько информации в среднем содержит один символ некоторого текста?
— Сколько информации в романе Л.Н. Толстого «Война и мир»?
— Сколько информации в числе пи?
— Как определить, что некоторая последовательность символов является случайной?