Модель системы передачи информации
Схема Шеннона: источник, кодер, канал, декодер, приёмник. Количество информации, энтропия, избыточность.
Криптография и теория информации
Интерактивная лаборатория: кодирование, помехоустойчивые коды, шифры и теория чисел. Каждый алгоритм можно запустить на своём сообщении и посмотреть все промежуточные шаги, а рядом прочитать теорию, доказательства и примеры.
Источник→
Кодер→
Канал с шумом→
Декодер→
Приёмник
Как работать с сайтом
- Прочитайте теорию. В каждой статье — определения, теоремы с доказательствами, разобранный вручную пример и вопросы для самопроверки.
- Проверьте себя в лаборатории. Выберите алгоритм, введите сообщение или параметры и сравните пошаговый разбор со своими вычислениями.
- Пользуйтесь справочником. Глоссарий терминов, сводка формул, обозначения и список литературы собраны на одной странице.
Основы теории информации
Эффективное кодирование (сжатие)
Код Хаффмана
Оптимальный префиксный код: дерево строится снизу вверх объединением двух самых редких узлов.
Код Шеннона–Фано
Префиксный код «сверху вниз»: символы делятся на группы с близкими суммарными частотами.
Помехоустойчивое кодирование
Код Хэмминга
Линейный код, исправляющий одну ошибку: биты чётности на позициях 2ᵏ и синдром — номер ошибочного бита.
Код Адамара
Код из строк матрицы Адамара: расстояние n/2, декодирование по максимуму корреляции.
Криптография
Классические шифры
Перестановка и замена, шифр Цезаря, частотный анализ. Принцип Керкгоффса.
Шифр Эль-Гамаля
Асимметричное шифрование на задаче дискретного логарифма: ключи, сеансовый ключ k, стойкость.
Простые числа и тесты простоты
Пробное деление, тест Ферма, Миллер–Рабин и доказательство простоты по критерию Поклингтона.
Алгебра и теория чисел
Моноиды
Множество с ассоциативной операцией и нейтральным элементом. Полугруппы, группы, примеры.
Диофантовы уравнения
Линейные уравнения в целых числах, расширенный алгоритм Евклида, соотношение Безу.
Сравнения по модулю
Арифметика остатков, быстрое возведение в степень, теоремы Эйлера и Ферма, китайская теорема.
Вычеты и первообразные корни
Кольцо ℤₘ, функция Эйлера, порядок элемента, первообразные корни, дискретный логарифм.