1. Объем информации

Формулы, типы задач и олимпиадные паттерны ИТМО

Центральная формула всей темы. Если есть N равновероятных вариантов, минимальное число бит для кодирования одного варианта:

примеры
N = 2    → i = 1 бит    // да/нет
N = 5    → i = 3 бита   // ⌈2.32⌉ = 3
N = 256  → i = 8 бит    // ровно 1 байт
N = 3232 → i = 12 бит   // ⌈11.66⌉ = 12

На ИТМО чаще записывают I = log₂(N), подразумевая потолок при хранении кода.

Что нужно помнить

Паттерн ИТМО: кодовая таблица + коды

Часто файл состоит из двух частей:

структура
V_файл   = V_таблица + V_коды
V_таблица = M × 16 бит          // M символов, каждый — 2-байтный Unicode
V_коды    = L × ⌈log₂(M)⌉ бит  // L символов текста

Типовая задача финала ИТМО: «Петя и Вася используют одинаковый метод, но у Пети алфавит 4M, а у Васи — M. Разница — X байт. Найти M.»

Типовые глубины цвета

Паттерн ИТМО: метод А vs метод Б (блочный код)

финал 2023
// Ч/Б изображение 1024 × 768

Метод А: 1 бит на пиксель
V_A = 1024 × 768 × 1 = 786 432 бит

Метод Б: блоки 4×4, в каждом ровно 8 чёрных
Число блоков: (1024/4) × (768/4) = 256 × 192 = 49 152
Различных блоков 4×4 с 8 чёрными: C(16,8) = 12870
Бит на блок: ⌈log₂(12870)⌉ = 14
V_Б = 49 152 × 14 = 688 128 бит

Экономия: 786432 − 688128 = 98 304 бит = 12 288 байт

Ключ: комбинаторный подсчёт числа состояний блока → потолок логарифма. Это «визитная карточка» задачи 2 финала ИТМО.

пример
// Стерео, 48 кГц, 16 бит, 2 мин
V = 48000 × 16 × 120 × 2 = 184 320 000 бит
  = 23 040 000 байт ≈ 21,97 МБ

На ИТМО звук встречается реже. Главное — не перепутать кГц и Гц, не забыть каналы.

На ИТМО не просто дают число цветов — его нужно вычислить через комбинаторику.

Формулы, которые нужны

формулы
// Сочетания (без повторений, порядок не важен)
C(n,k) = n! / (k! × (n−k)!)

// Размещения (порядок важен)
A(n,k) = n! / (n−k)!

// Перестановки
P(n) = n!

// Размещения с повторениями
nk    // k позиций, n вариантов на каждую

Типовые сюжеты ИТМО

Лайфхак: C(n,k) для маленьких n считай через треугольник Паскаля (держи в голове до n=16).

Это стержневой паттерн задачи 2 финала и отбора:

структура задачи
1. Дан объект (текст, изображение, звук)
2. Петя кодирует методом А → объём V_A
3. Вася кодирует методом Б → объём V_Б
4. Дана разница: V_A − V_Б = Δ байт (или бит)
5. Найти: параметр (мощность алфавита, размер блока…)

Алгоритм решения

метод
Шаг 1. Записать V_A через параметры.
Шаг 2. Записать V_Б через параметры (здесь «фишка»).
Шаг 3. Подставить V_A − V_Б = Δ.
Шаг 4. Решить уравнение (часто с ⌈log₂(x)⌉ — перебор по x).
Шаг 5. Проверить единицы: бит/байт/КБ.

RLE (Run-Length Encoding)

Текст разбивается на серии одинаковых символов. Каждая серия — пара (длина, символ):

формула
V_RLE = S × (b_len + b_sym) бит

// S — количество серий в тексте
// b_sym = ⌈log₂(A)⌉ — бит на код символа
// b_len = ⌈log₂(M)⌉ — бит на длину серии
// M — максимальная длина серии

Тонкость ИТМО: два варианта b_len

финал 2022
// Вася: b_len по максимальной длине серии M
b_len = ⌈log₂(M)⌉

// Таня: b_len по числу РАЗЛИЧНЫХ длин D
b_len = ⌈log₂(D)⌉
// D может быть намного меньше M
// → два разных объёма → система из двух уравнений

Блочное кодирование

формула
V_блок = (W/n × H/n) × ⌈log₂(D)⌉ бит

// D — число различных допустимых блоков
// Без ограничений: D = 2^(n²)
// С ограничением «ровно k чёрных»: D = C(n², k)

Формула Хартли работает, когда все N вариантов равновероятны. Если символы встречаются с разной частотой, минимальная средняя длина кода определяется энтропией Шеннона:

Что даёт эта формула

H — это нижняя граница средней длины кода. Ни один код (даже Хаффман) не может дать среднюю длину меньше H. При этом Хаффман всегда укладывается в H + 1.

пример
// Частоты: A = 1/2, B = 1/4, C = 1/8, D = 1/8

H = −(1/2·log₂(1/2) + 1/4·log₂(1/4) + 1/8·log₂(1/8) + 1/8·log₂(1/8))
  = −(1/2·(−1) + 1/4·(−2) + 1/8·(−3) + 1/8·(−3))
  = −(−0.5 − 0.5 − 0.375 − 0.375)
  = 1.75 бит/символ

// Хаффман для этих частот даёт ровно 1.75 — совпадение!
// Так бывает, когда все pᵢ — степени двойки.

когда не совпадает
// Частоты: A = 1/3, B = 1/3, C = 1/3

H = −3 × (1/3 · log₂(1/3)) = log₂(3) ≈ 1.585 бит/символ

// Хаффман: A=0, B=10, C=11 → средняя длина:
// 1/3·1 + 1/3·2 + 1/3·2 = 5/3 ≈ 1.667
// 1.667 > 1.585, но 1.667 < 1.585 + 1 ✓

Частные случаи