Дидактические цели
Что такое информация? Сколько она «весит»? Какие коды лучше? Можно ли исправить ошибки при передаче данных? Эта лаборатория для старшей школы и университета проводит через теорию информации — от самых основ до кодов с исправлением ошибок — по стопам Хартли, Шеннона и Хэмминга. 22 зала, примерно полчаса суммарно. Рекомендуем использовать вместе с нашей игрой «Лжец-оракул».
Чему учимся
Развиваем умение измерять неопределённость, проектировать эффективные системы кодирования и рассуждать о надёжности при искажении данных. Ученик не просто наблюдает, а строит: проектирует урны, дерево Хаффмана, префиксные коды и, наконец, собственный корректирующий код.
- Блок A — Измеряем информацию: вводится формула
i = −log₂ pи энтропия Шеннона — через слайдеры; ученик проектирует распределения с заданной энтропией и упорядочивает эксперименты по степени неопределённости. - Блок B — Кодируем: от декодирования таблиц к проблеме неоднозначного кода; строится префиксный код вручную и используется машина Хаффмана для сжатия несбалансированных сообщений (80/20) ниже 0,78 бит/символ.
- Блок C — Угадываем и лжём: ученик угадывает с помощью двоичного поиска, затем сталкивается с противником, который лжёт один раз; узнаёт, что нужно задать больше вопросов, и открывает стратегию Берлекэмпа.
- Блок D — Ошибки и устойчивость: вводится расстояние Хэмминга, коды с
d_min = 3, гиперкуб{0,1}⁴, и в конце проектируется корректирующий код, выдерживающий 10 % искажений битов.
Ключевые математические идеи
- Информация события равна
i = −log₂ pбит; редкие события несут больше информации. - Энтропия Шеннона
H = −Σ pᵢ log₂ pᵢизмеряет среднюю неопределённость источника; это нижняя граница любого кода без потерь. - Префиксный код гарантирует однозначное декодирование; алгоритм Хаффмана строит оптимальный код, итеративно объединяя две наименьшие вероятности.
- Расстояние Хэмминга между двумя двоичными словами — это количество различающихся битов; код с
d_min = 2t + 1может исправить t ошибок. - Гиперкуб
{0,1}^n— естественное пространство двоичных кодов: кодовые слова — вершины, разделённые непересекающимися шарами Хэмминга.
Содержание по залам
Зал 1 · Что такое информация?
Вводится центральная идея лаборатории: получить сообщение — значит исключить возможные миры. Ползунок показывает, сколько «миров» остаётся после каждого сообщения и сколько бит это стоило.
Задания для ученика
- Двигать ползунок и наблюдать, как сокращается число возможных миров.
- Замечать связь между исключёнными мирами и битами информации.
Зал 2 · Весы удивления
Вводится формула i = −log₂ p: чем маловероятнее событие, тем больше бит оно несёт. Ученик отрабатывает вычисление, решая три задачи подряд.
Задания для ученика
- Применить формулу i = −log₂ p к заданным событиям.
- Правильно решить три вычисления подряд.
Зал 3 · Лаборатория энтропии
Исследуется энтропия H как средняя неопределённость двоичного распределения. Интерактивный ползунок показывает кривую H(p) от края до края.
Задания для ученика
- Двигать ползунок от 0 до 1 и наблюдать, как изменяется энтропия.
- Найти значение p, при котором H = 0.5 бита.
Зал 4 · Спроектируй урну
Задание на проектирование: ученик распределяет шары по трём контейнерам, чтобы получить ровно H = 1.24 бита. Связывает формулу энтропии с конкретным выбором.
Задания для ученика
- Распределить шары по трём контейнерам.
- Убедиться, что полученная энтропия равна 1.24 бита.
Зал 5 · Упорядочи по неопределённости
Четыре эксперимента с различными вероятностными распределениями. Ученик упорядочивает их от меньшей к большей энтропии, перетаскивая карточки.
Задания для ученика
- Визуально проанализировать распределения каждого эксперимента.
- Перетащить их в правильный порядок от меньшей к большей энтропии.
Зал 6 · Кодирование = перевод в биты
Вводится блок кодирования: не все коды стоят одинаково, и энтропия задаёт нижнюю границу, которую не может пробить ни один эффективный код. Вводный/визуальный зал.
Задания для ученика
- Прочитать пояснение и рассмотреть примеры кодов разной стоимости.
Зал 7 · Декодируй это
Прямая практика: по таблице двоичных кодов ученик получает строку бит и должен написать исходное слово, которое она представляет.
Задания для ученика
- Применить таблицу кодов к полученной строке.
- Правильно написать декодированное слово.
Зал 8 · Ловушка неоднозначного кода
Строка бит допускает более одной правильной расшифровки. Ученик должен найти два разных варианта, что обосновывает необходимость префиксных кодов.
Задания для ученика
- Найти два разных варианта декодирования одной и той же строки.
- Понять, почему такой код не подходит для однозначной передачи.
Зал 9 · Машина Хаффмана
Анимированная визуализация алгоритма Хаффмана: ползунки вероятностей показывают, как на каждом шаге объединяются две наименьшие вероятности. Ученик ищет почти оптимальное распределение (L − H < 0.05).
Задания для ученика
- Двигать ползунки вероятностей и наблюдать объединения дерева.
- Найти распределение, где средняя длина L почти равна H.
Зал 10 · Построй префиксный код
Задание на построение: ученик изобретает двоичный код для 4 букв такой, что ни одно кодовое слово не является префиксом другого.
Задания для ученика
- Назначить строки бит четырём буквам.
- Проверить, что ни одна строка не является префиксом другой.
Зал 11 · Назначь коды буквам
Перетаскивание: ученик перетаскивает строки бит к каждой букве. Код должен быть префиксным, а средняя длина — не более 1.85 бит/букву.
Задания для ученика
- Перетащить правильную строку бит к каждой букве.
- Убедиться, что средняя длина ≤ 1.85 бит/букву и код является префиксным.
Зал 12 · Сожми смещённое сообщение
Источник выдаёт 80 % нулей и 20 % единиц. Ученик работает с парами символов и разрабатывает префиксный код, сжимающий до ≤ 0.78 бит/символ.
Задания для ученика
- Разработать код для пар символов (00, 01, 10, 11).
- Убедиться, что средняя длина на символ ≤ 0.78 бита.
Зал 13 · Угадай с вопросом «меньше N?»
Лаборатория загадывает число от 1 до 8; ученик должен угадать его ровно за 3 вопроса вида «меньше N?». Связывает двоичный поиск с битами информации.
Задания для ученика
- Задать 3 вопроса в оптимальном порядке.
- Угадать число не более чем за 3 попытки.
Зал 14 · Теперь компьютер угадывает
Ученик загадывает число от 1 до 8, а компьютер задаёт вопросы, следуя оптимальной стратегии двоичного поиска. Ученик наблюдает, как каждый раз делится диапазон пополам.
Задания для ученика
- Загадать число и честно отвечать «Да/Нет».
- Наблюдать стратегию компьютера и замечать деление диапазона пополам.
Зал 15 · Угадай, хотя можно солгать
Лаборатория может солгать один раз. Ученик должен угадать число от 1 до 4 за 5 вопросов «Да/Нет», несмотря на возможную ложь. Вводится необходимость избыточности.
Задания для ученика
- Разработать стратегию вопросов, допускающую одну ложь.
- Угадать число за 5 вопросов или меньше.
Зал 16 · Ты угадываешь, ты можешь солгать
Теперь ученик может солгать один раз; компьютер применяет стратегию Берлекэмпа и всё равно угадывает. Первое знакомство с надёжностью корректирующих кодов.
Задания для ученика
- Загадать число от 1 до 4 и отвечать, солгав если хочешь.
- Посмотреть, как компьютер угадывает несмотря на ложь.
Зал 17 · Расстояние Хэмминга
Определяется расстояние Хэмминга между двоичными строками одинаковой длины как число позиций, в которых они различаются. Ученик вычисляет расстояния на конкретных примерах.
Задания для ученика
- Изучить примеры пар строк.
- Вычислить запрошенное расстояние Хэмминга.
Зал 18 · Стратегия Берлекэмпа
Раскрывается, как компьютер угадал число из зала 16 с помощью 6 вопросов, несмотря на ложь: секрет — в корректирующем коде с d_min = 3. Пояснительный зал.
Задания для ученика
- Прочитать объяснение корректирующего кода с d_min = 3.
- Связать 6 вопросов предыдущего зала с кодовыми словами.
Зал 19 · Когда канал лжёт
Канал искажает 1 бит в каждом сообщении. Ученик получает несколько строк с 1 ошибкой и должен решить, к какому исходному слову принадлежит каждая, используя минимальное расстояние.
Задания для ученика
- Получить каждое искажённое сообщение и вычислить расстояние до каждого кодового слова.
- Решить, из какого слова пришло каждое сообщение.
Зал 20 · Спроектируй свой код
Ученик проектирует с нуля: сначала выбирает кратчайшие кодовые слова для трёх букв, затем вычисляет, какое минимальное расстояние нужно, чтобы пережить три ошибки.
Задания для ученика
- Построить кратчайшие кодовые слова для трёх букв.
- Определить минимальное расстояние, необходимое для исправления трёх ошибок.
Зал 21 · Гиперкуб
Геометрическая визуализация: ученик выбирает вершины гиперкуба {0,1}⁴, максимизируя минимальное расстояние между ними. Три уровня сложности (d ≥ 2, d ≥ 3, максимальное число вершин с d = 3).
Задания для ученика
- Выбрать вершины гиперкуба с минимальным расстоянием 2 между собой.
- Повторить с минимальным расстоянием 3 и найти максимальное число вершин.
Зал 22 · Спроектируй корректирующий код
Финальное задание: канал искажает 10 % бит. Ученик разрабатывает двоичный код для 4 сообщений, который правильно декодируется не менее чем в 90 % случаев, с штрафом за длину.
Задания для ученика
- Определить 4 кодовых слова и правило декодирования.
- Убедиться, что доля успеха ≥ 90 % и длина минимальна.
Залы для показа
Самые наглядные для показа и обсуждения в классе.