Представление информации и её кодирование: простыми словами о сложном

Как компьютер понимает тексты, картинки и звуки? Почему иногда информация занимает много памяти, а иногда мало? Ответ кроется в том, как информация кодируется и хранится внутри устройства. В этой статье разберём, что такое информация, зачем её нужно кодировать и почему правильное кодирование — залог успешной работы любой информационной системы.

0. Вступление. Что такое информация и зачем её кодировать

0.1 Информация ≠ данные. Понятие однозначного декодирования

Информация — это то, что имеет смысл и ценность для нас.

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

Чтобы компьютер мог хранить и передавать информацию, он преобразует её в последовательность битов (0 и 1).

И здесь возникает важный принцип — однозначное декодирование. Это значит, что после кодирования мы должны всегда чётко понять, что за информация была передана.

Нельзя допускать, чтобы сообщение можно было трактовать двояко — иначе компьютер просто запутается и выдаст неверный результат.

0.2 Три семейства задач курса

Весь наш курс построен вокруг трёх больших семейств задач. Каждое из них помогает освоить свой подход к работе с информацией:

• Семейство A (Задания 4 ЕГЭ): задачи про префиксные и неравномерные коды, когда буквы и символы кодируются по-разному, в зависимости от частоты их использования. Здесь важно уметь строить удобные, компактные и однозначно декодируемые коды.
• Семейство B (Задания 7 ЕГЭ): задачи, связанные с расчётом объёмов мультимедийной информации (тексты, звуки, изображения и видео). Здесь мы узнаем, как компьютер хранит картинки и музыку, и почему они занимают столько памяти.
• Семейство C (Задания 11 ЕГЭ): задачи на кодирование баз данных и идентификаторов (ID). Здесь ключевым становится грамотное использование памяти, экономия места и выбор оптимальной структуры хранения.

Каждое семейство раскрывает определённый набор навыков, полезных не только для экзаменов и олимпиад, но и в повседневной IT-практике.

0.3 Пример: почему «010» + «0100» нельзя расшифровать без разделителей

Допустим, у нас есть две буквы: А = «010» и Б = «0100». Представим, мы получили сообщение «0100010». Как его расшифровать?

• Это может быть: «0100» (Б) + «010» (А).
• Но также это может быть: «010» (А) + «0010» (какой-то другой символ).

Возникает неоднозначность. Компьютер не понимает, где заканчивается один символ и начинается другой. Именно поэтому используются префиксные коды, у которых нет такой проблемы: никакое кодовое слово не является началом другого кодового слова. Это называется условием Фано, и мы подробно разберём его чуть позже.

0.4 Пять быстрых вопросов, чтобы проверить себя

Вот 5 вопросов, которые помогут тебе быстро убедиться, что базовые понятия понятны и ты готов идти дальше:

1. Что такое бит?
   — Минимальная единица измерения информации, имеющая только два значения: 0 или 1.
2. Что такое байт?
   — Единица информации, равная 8 битам.
3. Что означает термин «префиксный код»?
   — Код, в котором ни одно кодовое слово не является началом другого.
4. Что такое условие Фано?
   — Условие, обеспечивающее однозначность декодирования (префиксность кодов).
5. Что такое суффиксный код?
   — Код, в котором ни одно кодовое слово не является окончанием другого (обратный аналог префиксного кода).

0.5 Попробуй построить собственное двоичное сообщение

Лучший способ понять, как важно соблюдать однозначность, — построить своё собственное небольшое сообщение. Сделаем это шаг за шагом:

1. Выбери любые три символа (например, А, Б, В).
2. Придумай для них двоичный код, так, чтобы один код был началом другого. Например:
   А = 10, Б = 101, В = 0.
3. Теперь попробуй составить сообщение, например, «АБВ». Получается:
   10 + 101 + 0 → 101010.
4. А теперь попробуй расшифровать получившееся «101010» без подсказок и разделителей. Получается неоднозначность!
   • Может быть, это «А» (10) + «Б» (101) + «0» (В)?
   • Или это «В» (0) + «А» (10) + «Б» (101)?

Вот почему так важно использовать коды, которые исключают подобную путаницу. Префиксные коды делают расшифровку лёгкой и однозначной.

0.6 Пример задания ЕГЭ на проверку условия Фано и префиксных кодов с решением.

Для кодирования некоторой последовательности, состоящей из букв С, М, О, Т, Р, И, Ё, Ж,, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв С, М, О, Т, Р, И использовали соответственно кодовые слова 000, 001, 101, 1101, 1100, 010. Укажите кратчайшее возможное кодовое слово для буквы Ж, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

[ root ]
├─ 0
│  ├─ 0
│  │  ├─ 0 : С  (000)
│  │  └─ 1 : М  (001)
│  └─ 1
│     ├─ 0 : И  (010)
│     └─ 1 : Ж  (011)
└─ 1
   ├─ 0
   │  └─ 1 : О  (101)
   └─ 1
      └─ 0
         ├─ 0 : Р  (1100)
         └─ 1 : Т  (1101)

Пояснение дерева:

• Левая ветвь «0 → 0 → 0» ведёт к коду С «000».
• Ветка «0 → 0 → 1» — к М «001».
• Ветка «0 → 1 → 0» — к И «010».
• Ветка «0 → 1 → 1» — к Ж «011» (новый код).
• Правая большая ветвь «1 → 0 → 1» — к О «101».
• Ветка «1 → 1 → 0 → 0» — к Р «1100».
• Ветка «1 → 1 → 0 → 1» — к Т «1101».

Такой выбор кода «011» для буквы Ж сохраняет свойство Фано (префиксности), и это самое короткое (длиной 3) и наименьшее по числовому значению (3) возможное слово.

Задания Блок 0. Введение: информация и её кодирование

Задание 0.1.
Объясните, в чём принципиальная разница между «данными» и «информацией». Приведите по одному примеру данных и соответствующей им информации.

Задание 0.2.
Определите, что такое «префиксный код» и «непрефиксный код». Почему префиксное свойство гарантирует однозначность декодирования?

Задание 0.3.
Рассмотрите два набора кодовых слов:

• Набор A: {0, 10, 110, 111}
• Набор B: {01, 010, 10}

Для каждого набора:
1) Расшифруйте битовую строку «0110110…» по первым четырём битам.
2) Покажите, возникнет ли неоднозначность (т. е. два разных разбора) и на каком шаге.

Задание 0.4.
Сформируйте свой набор из трёх–пяти двоичных кодовых слов (любые символы, но длины не равны между собой).
1) Выпишите любую битовую последовательность длиной не менее 10 бит, которая даёт двусмысленность при декодировании «без разделителей».
2) Объясните, в чём состоит неоднозначность.

0.1.
- Данные — это сырые символы или числа (например, «2023-07-15»).
- Информация — это инсайт, полученный из данных (например, «15 июля 2023 года пользователь совершил платёж»).

0.2.
- Префиксный код: ни одно кодовое слово не является началом другого (например, {0,10,110,111}).
- Непрефиксный: есть такое начало (например, {01,010,10} — «01» является началом «010»).
- Благодаря префиксному свойству при чтении слева направо в любой момент, встретив полное слово, мы знаем, где оно кончается, и не ошибёмся дальше.

0.3.
- Набор A:
  - Читаем «0 | 110 | 110…» — первые 4 бита «0110» однозначно разбираются как [0][110].
  - Неоднозначность не возникает.
- Набор B:
  - Читаем «01|01|…»: первые 4 бита «0101» могут быть [01][01] или [010][1] → неоднозначность на 3-4 бите.

0.4.
- Пример набора: {0, 10, 1011}.  
- Последовательность: «10110…».  
- Разбор:
  - Вариант 1: [10][11][0…]  
  - Вариант 2: [1011][0…]  
- Неоднозначность из-за того, что «10» является началом «1011».  

# Для 0.3 можно имитировать «пошаговое» сканирование:
def decode_prefix(bits: str, code_set):
    i = 0
    result = []
    while i < len(bits):
        # пытаемся найти слово из code_set, совпадающее с префиксом bits[i:]
        match = None
        for w in sorted(code_set, key=len):  # короче первым
            if bits.startswith(w, i):
                match = w
                break
        if match is None:
            return result, f"Ошибка на позиции {i}"
        result.append(match)
        i += len(match)
    return result, "Успех, без остатков"

# Набор A
print(decode_prefix("0110110", {"0","10","110","111"}))
# → (['0','110','110'], 'Успех, без остатков')

# Набор B
print(decode_prefix("01010", {"01","010","10"}))
# → может выдать ['01','010'] но затем остаток '0' – неоднозначность разбора.

# Для 0.4 — просто демонстрация двух вариантов разбора:
bits = "10110"
print("Вариант 1:", [bits[:2], bits[2:4], bits[4:]])
print("Вариант 2:", [bits[:4], bits[4:]])

1. Единицы измерения и базовые пересчёты

1.1 Бит, байт и приставки: KiB / KB, MiB / MB

Бит — это минимальная единица измерения информации, способная принимать два состояния: 0 или 1. Всё, что хранится на компьютере, в итоге сводится именно к битам.

Однако бит — слишком маленькая единица для практического использования, поэтому её объединяют в байты. Один байт равен 8 битам и может кодировать, например, один символ текста или небольшой участок изображения.

Чтобы обозначать большие объёмы данных, используют приставки:

• 1 KB (килобайт) = 1000 байт, а 1 KiB (кибибайт) = 1024 байта.
• 1 MB (мегабайт) = 1 000 000 байт, а 1 MiB (мебибайт) = 1 048 576 байт.

Приставки KiB, MiB, GiB (двоичные приставки) отличаются от KB, MB, GB (десятичные приставки) именно тем, что они основаны на степенях двойки (1024 вместо 1000).

1.2 Правила округления: сколько бит или байт нужно?

При вычислении минимального количества бит, нужного для кодирования m различных вариантов, используют формулу:

⌈log₂ m⌉ бит — это означает, что нужно взять логарифм по основанию 2 и округлить вверх до целого.

Например, чтобы закодировать 12 вариантов, нужно ⌈log₂12⌉ = ⌈3.5849⌉ = 4 бита.

Чтобы перевести количество бит в байты, округляем вверх до целого число бит, разделённое на 8:

⌈(число бит) / 8⌉ = количество байт

1.3 Примеры пересчётов

Разберём на простом и сложном примерах:

• Простой: «Сколько байт нужно, чтобы хранить 12 000 бит?»
  Ответ: ⌈12000 / 8⌉ = ⌈1500⌉ = 1500 байт (ровно).
• Сложный: «Во сколько раз 27 MiB больше 27 MB?»
  Решение:
  27 MiB = 27 × 1 048 576 байт = 28 310 552 байт.
  27 MB = 27 × 1 000 000 байт = 27 000 000 байт.
  Разница: 28 310 552 / 27 000 000 ≈ 1,0489 раза.
  То есть, 27 MiB примерно на 4,89% больше, чем 27 MB.

1.4 Быстрый тест на приставки (проверь себя)

1. Сколько байт в 1 KiB? (ответ: 1024)
2. 1 MiB больше 1 MB? (ответ: да)
3. Что больше — 1 GiB или 1 GB? (ответ: 1 GiB)
4. Сколько байт в 2 MB? (ответ: 2 000 000)

1.5 Удобный скрипт-подсказка для пересчётов (Python)

Для удобного перевода битов в байты используй простой Python-скрипт:

def calc_bytes(bits):
    return (bits + 7) // 8

Эта одна строка автоматически выполняет нужное округление вверх и используется для проверки своих решений в задачах семейства C (например, в задачах C-1, C-6).

Задания. Блок 1. Единицы измерения и базовые пересчёты

Задание 1.1.
Объясните, что такое бит и байт. В чём разница между KiB и KB, MiB и MB? Приведите численные соотношения.

Задание 1.2.
Опишите правило округления при переводе «m символов» в биты и байты:

• — сколько нужно бит: ⌈log₂ m⌉;
• — сколько нужно байт: ⌈⌈log₂ m⌉ / 8⌉.

Приведите короткий вывод-формулу.

Задание 1.3.

• Простой: Сколько байт нужно, чтобы хранить 12 000 бит?
• Сложный: Во сколько раз 27 MiB больше 27 MB?

Задание 1.4.
Выберите правильный ответ (несколько тестов на приставки):

1. «1 KB» — это сколько байт?
   1 000
   1 024
2. «1 KiB» — это сколько байт?
   1 000
   1 024
3. «1 MB» — это сколько байт?
   10⁶
   2²⁰
4. «1 MiB» — это сколько байт?
   10⁶
   2²⁰

Задание 1.5.
Напишите на Python однострочный «скрипт-подсказку» calc_bytes(bits), который по числу бит возвращает минимальное число байт.

1.1.  
- 1 бит = минимальная единица информации (0 или 1).  
- 1 байт = 8 бит.  
- 1 KB (decimal) = 10³ байт = 1 000 B;  
- 1 KiB (binary) = 2¹⁰ байт = 1 024 B;  
- 1 MB = 10⁶ B; 1 MiB = 2²⁰ B (~1.048 MiB = 1 MB).

1.2.  
- bits = ⌈log₂ m⌉  
- bytes = ⌈⌈log₂ m⌉ / 8⌉

1.3.  
- 12 000 бит → 12 000 / 8 = 1 500 байт (ровно).  
- 27 MiB / 27 MB = (27·2²⁰) / (27·10⁶) ≈ 1.048576

1.4.  
1) 1 KB = 1 000 B  
2) 1 KiB = 1 024 B  
3) 1 MB = 10⁶ B  
4) 1 MiB = 2²⁰ B

1.5.  
calc_bytes = lambda b: -(-b // 8) #(или math.ceil(b/8))

# 1.2 — пояснение: 
# import math 
# bits = math.ceil(math.log2(m)) 
# bytes = math.ceil(bits / 8) 
# 1.3 — расчёты: bits = 12000 bytes_needed = bits // 8 
# 1500 ровно print(bytes_needed) 
# → 1500 
# двойной перевод MiB→MB: ratio = (27 * 2**20) / (27 * 10**6) print(ratio) 
# → ~1.048576 
# 1.5 — однострочник: calc_bytes = lambda b: -(-b // 8) 
# тест: for b in [1,7,8,9,15]: print(b, calc_bytes(b)) 

2. Равномерное посимвольное кодирование

2.1 Как узнать, сколько бит нужно для символа?

Когда мы кодируем текст, цифры или любые другие символы, нам нужно, чтобы для каждого символа выделялось одинаковое количество бит. Такое кодирование называется равномерным.

Если у нас алфавит мощностью m символов, то количество бит, необходимых для одного символа, вычисляется так:

⌈log₂ m⌉ бит на символ

Например, чтобы закодировать все буквы русского алфавита (33 буквы), нужно ⌈log₂33⌉ = 6 бит на букву.

2.2 Выравнивание до целого байта

Когда информация записывается в память компьютера, количество битов обычно округляется до целого числа байт (1 байт = 8 бит).

Поэтому, если текстовая строка фиксированной длины содержит, допустим, 12 символов, каждый из которых занимает по 5 бит, мы сначала считаем общее количество бит (12 × 5 = 60 бит), а затем округляем до байтов:

⌈60 / 8⌉ = 8 байт

2.3 Примеры на кодирование

• Простой: «Дата (числа от 1 до 31) — сколько бит нужно?»
  Решение: ⌈log₂31⌉ = 5 бит, поскольку 2⁵ = 32 достаточно для кодирования 31 числа и даже остаётся запас.
• Средний: «Строка из 20 заглавных букв ASCII (26 букв) — сколько байт?»
  Решение: ⌈log₂26⌉ = 5 бит/символ, всего 20 × 5 = 100 бит. ⌈100 / 8⌉ = 13 байт.
• Сложный: «Идентификатор: 11 десятичных цифр (0-9) и 4 шестнадцатеричных цифры (0-F) — сколько байт?»
  Решение:
  — Цифры (10 вариантов): ⌈log₂10⌉ = 4 бита на каждую цифру, итого 11 × 4 = 44 бит.
  — Шестнадцатеричные (16 вариантов): ⌈log₂16⌉ = 4 бита на каждый символ, всего 4 × 4 = 16 бит.
  — Всего: 44 + 16 = 60 бит ⇒ ⌈60 / 8⌉ = 8 байт.

┌─────────┐
│   m     │
└───┬─────┘
    ↓
┌─────────┐
│ log₂(m) │
└───┬─────┘
    ↓
┌───────────────┐
│ ⌈log₂(m)⌉      │
└───┬───────────┘
    ↓
┌───────────────┐
│ ⌈log₂(m)⌉ × n  │
└───┬───────────┘
    ↓
┌───────────────┐
│ (⌈log₂(m)⌉×n)  │
│    ÷ 8        │
└───┬───────────┘
    ↓
┌─────────────────────┐
│ ⌈ (⌈log₂(m)⌉×n) / 8 ⌉ │
└─────────────────────┘

2.4 Мини-тест «Выбери правильное округление»

1. Алфавит из 8 символов → … бит (ответ: 3)
2. Алфавит из 33 символов → … бит (ответ: 6)
3. 100 бит → … байт (ответ: 13)
4. Алфавит из 64 символов → … бит (ответ: 6)
5. 150 бит → … байт (ответ: 19)

2.5 🔧 Python-функция: расчёт размера записи

Удобная функция, помогающая быстро посчитать размер записи по мощностям полей (например, в задачах C-2, C-5, C-7, C-15):

def record_size(fields):
    bits = sum((field - 1).bit_length() for field in fields)
    return (bits + 7) // 8

Как пользоваться? Передай функции список мощностей полей (например, [31, 12, 256]), и она вернёт размер записи в байтах:

print(record_size([31, 12, 256]))  # выведет 3 байта

Задания. Блок 2. Равномерное посимвольное кодирование

Задание 2.1.
Дан алфавит мощности m. Сколько бит требуется на кодирование одного символа при равномерном посимвольном кодировании? Запишите формулу.

Задание 2.2.
Объясните, как «выравнивается» строка фиксированной длины до целого числа байт. Почему иногда приходится добавлять неиспользуемые (padding) биты?

Задание 2.3.

• Простой: Сколько бит нужно, чтобы закодировать день месяца (1–31)?
• Средний: Сколько байт потребуется для хранения строки из 20 заглавных ASCII-букв (A–Z)?
• Сложный: Идентификатор состоит из 11 десятичных цифр и 4 шестнадцатеричных символов (0–9, A–F). Сколько байт потребуется для его хранения?

Задание 2.4.
Мини-тест «выберите верное округление»:

1. ⌈log₂(26)⌉ = ?
   4
   5
2. ⌈5 бит / 8⌉ байт = ?
   0
   1
   2
3. ⌈log₂(16)⌉ = ?
   3
   4
4. ⌈9 бит / 8⌉ байт = ?
   1
   2
5. ⌈log₂(1000)⌉ = ?
   9
   10
   8

Задание 2.5.
Напишите на Python функцию record_size(field_alphabets: List[int]) -> int, которая по списку мощностей алфавитов полей возвращает общий размер записи в байтах (посимвольно, выравнено до байта).

2.1.  
bits_per_symbol = ⌈log₂(m)⌉

2.2.  
После расчёта общего числа бит строки (⌈log₂(m)⌉ × длина) дополняют до ближайшего целого числа байт: байты = ⌈bits_total / 8⌉. Padding-биты нужны, чтобы выровнять упакованные биты на границы байта.

2.3.  
— День 1–31: ⌈log₂(31)⌉ = 5 бит.  
— 20 заглавных ASCII: каждый в 7 бит, но обычно хранят 1 байт → 20 B.  
— Идентификатор:  
   • 11 цифр → ⌈log₂(10)⌉ = 4 бит ×11 = 44 бит  
   • 4 hex → ⌈log₂(16)⌉ = 4 бит ×4 = 16 бит  
   Всего 60 бит → ⌈60/8⌉ = 8 байт.

2.4.  
1) 5  
2) 1  
3) 4  
4) 2  
5) 10

2.5.

def record_size(field_alphabets):
    from math import ceil, log2
    bits = sum(ceil(log2(m)) for m in field_alphabets)
    return ceil(bits / 8)

 import math from typing import List 
# 2.1 
def bits_per_symbol(m: int) -> int:
 return math.ceil(math.log2(m)) 
# 2.3 — проверки 
print("День 1–31:", bits_per_symbol(31)) # 5 бит 
print("20 ASCII-букв:", 20 * 1, "байт") # обычно 1 байт на символ → 20 B 
# 11 цифр + 4 hex: 
bits = math.ceil(math.log2(10))*11 + math.ceil(math.log2(16))*4 
print("Идентификатор:", math.ceil(bits/8), "байт") 
# 8 B 
# 2.5 
def record_size(field_alphabets: List[int]) -> int: 
    bits = sum(math.ceil(math.log2(m)) for m in field_alphabets) 
    return math.ceil(bits / 8) 
# Пример: 
print(record_size([10, 26, 1000])) # ⌈(4+5+10)/8⌉ = ⌈19/8⌉ = 3 байта 

3. Неравномерные коды и условие Фано

3.1 Что такое префиксный код, суффиксный код и условие Фано?

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

• Верно: {0, 10, 110}, потому что ни один код не начинается с другого.
• Неверно: {0, 01, 011}, потому что «0» является началом «01» и «011».

Суффиксный код — наоборот: ни одно кодовое слово не должно быть окончанием другого. Если соблюдается суффиксный код, то говорят, что соблюдается обратное условие Фано. Используется реже.

Условие Фано прямое или обратное — требование, чтобы код был либо префиксным, либо суффиксным. Это обеспечивает однозначное декодирование. То есть сообщение всегда можно расшифровать!

3.2 Формула Крафта–Макмиллана и минимальная оценка

Чтобы проверить, можно ли создать префиксный код с заданными длинами кодовых слов, используют формулу Крафта–Макмиллана (для b-ичного кода):

∑ b^-li ≤ 1, где li — длина кодовых слов

Пример: возможно ли создать двоичный код для букв A, B, C длинами 1, 2, 2?

Проверим:

• 2^-1 + 2^-2 + 2^-2 = 0.5 + 0.25 + 0.25 = 1 ≤ 1 — условие выполняется, код возможен.

3.3 Как «коротить» код без нарушения префиксности

Если хочешь сократить длину кодового слова, надо убедиться, что оно не станет префиксом других слов:

• Исходный код: {010, 0110, 0111}
• Можно ли «010» заменить на более короткий «00»? Проверим:
  — «00» не является началом других слов. Можно!
• Результат: {00, 0110, 0111}

Оригинальный префиксный код:
   {010, 0110, 0111}

Построим дерево:

[root]
├─ 0
│  └─ 1
│     ├─ 0 : 010
│     └─ 1
│        ├─ 0 : 0110
│        └─ 1 : 0111
└─ 1 (пусто)

Проверяем замену «010» → «00»:

1. Новый кодовой знак «00»:
   ─ по дереву: [root] → 0 → 0
   ─ Входит ли «00» в путь к другим словам?
     • Пути к «0110» и «0111» начинаются с 0 → 1…, а не с 0 → 0.
     • Значит, «00» не является префиксом «0110» и «0111».

2. Строим дерево после замены:

[root]
├─ 0
│  ├─ 0 : 00       ← новый код для прежнего «010»
│  └─ 1
│     ├─ 0 : 0110
│     └─ 1 : 0111
└─ 1 (пусто)

Итоговый код: {00, 0110, 0111} — по-прежнему префиксный.

Можно ли сделать код еще короче?

3.4 Двоичные vs троичные коды

Чем больше символов в алфавите, тем короче становятся кодовые слова для того же набора букв. Например:

• Двоичный код (0, 1): три символа требуют хотя бы 2 бита.
• Троичный код (0, 1, 2): три символа кодируются всего одним знаком каждый (0, 1, 2).

Бинарный код (алфавит {A, B, C}, 2‐ичный):

          [root]
           /   \
         0      1
        / \    /
      0/   \1 0
      /     \  \
    [A]     [B] [C]
   (00)     (01) (10)

Тернарный код (алфавит {A, B, C}, 3‐ичный):

           [root]
          /   |   \
        0/   1|   2\
        /     |     \
      [A]    [B]    [C]
     (0)     (1)    (2)

3.5 Пошаговый разбор примеров

Очень простой: {A, B, C} с длинами {1, 2, 2}

Возможное решение:

• A = 0, B = 10, C = 11

Проверим на префиксность: слово «0» не пересекается с «10», «11». Условие соблюдается.

Средний: сократить код 1100 (задача типа A-3)

Дано слово «1100», надо сократить, если возможно. Проверяем варианты:

• «1», «11», «110» заняты другими словами? Если нет, можем взять самое короткое незанятое.
• Допустим, свободно «10» — тогда берём «10».

Важно: всегда проверять, чтобы код остался префиксным.

Сложный: минимально закодировать слово «КОРОМЫСЛО» (задача A-7)

Шаг 1. Выпишем буквы: К, О, Р, М, Ы, С, Л (7 букв).

Шаг 2. Частота букв (О чаще других — код покороче):
O → 2 бита (00), К → 2 бита (01), остальные → 3-4 бита.

Шаг 3. Примерный код:

• О — 00, К — 01, Р — 100, М — 101, Ы — 110, С — 1110, Л — 1111

Шаг 4. Проверим префиксность — всё верно. Код минимальный.

3.6 Опрос: «Является ли набор префиксным?»

• {0, 10, 11}
• {01, 011, 10}
• {00, 01, 10, 11}
• {001, 01, 1}
• {100, 101, 110, 111}
• {00, 0001, 00001}

3.7 🔧 Python-код для проверки префиксности и сокращения кодов

Попробуй этот код:

def is_prefix_free(codes):
    for c in codes:
        for other in codes:
            if c != other and other.startswith(c):
                return False
    return True

print(is_prefix_free(['0', '10', '11']))  # True
print(is_prefix_free(['01', '011', '10']))  # False

# Генератор коротких вариантов
from itertools import product

def shorten_code(codes, old_code):
    for length in range(1, len(old_code)):
        for bits in product('01', repeat=length):
            new_code = ''.join(bits)
            if all(not new_code.startswith(c) and not c.startswith(new_code)
                   for c in codes if c != old_code):
                yield new_code

# Пример
codes = ['1100', '01', '001']
short_options = list(shorten_code(codes, '1100'))
print(short_options)  # возможные короткие варианты вместо '1100'

Теперь ты можешь самостоятельно проверять префиксность и искать короткие коды!

3.8 Практика: функция code_length и её применение

Зачем нам нужна code_length?
В задачах блока A (ЕГЭ-уровня) часто просят оценить минимальную суммарную длину кодовых слов при заданных частотах символов или проверить, уложится ли заданный набор длин в условие Крафта–Макмиллана. Функция code_length автоматизирует эти расчёты и позволяет:

• Быстро получить нижнюю оценку суммарного числа бит для неравномерного кода по формуле Шеннона–Фано;
• Проверить выполнение неравенства Крафта–Макмиллана (∑2<sup>–li</sup> ≤ 1);
• Применить к реальным задачам — от оценки компрессии текста до расчёта длины сетевых заголовков.

3.8.1 Шаг 1. Импорт необходимых модулей

import math

3.8.2 Шаг 2. Собираем статистику частот

# Пример: символы и их частоты
freqs = {
    'A': 45,
    'B': 13,
    'C': 12,
    'D': 16,
    'E': 9,
    'F': 5
}

3.8.3 Шаг 3. Пишем функцию code_length

1. Считаем total = sum(freqs.values()) — общее количество символов.
2. Для каждого символа частота f определяем оптимальную длину кода по Шеннону:
   l = math.log2(total/f), но округляем вверх (ceil), чтобы получить целое число бит.
3. Собираем список длин lengths = [ceil(log2(total/f)) for each f].
4. Проверяем условие Крафта–Макмиллана:
   sum(2**(-l) for l in lengths) <= 1.
5. Вычисляем суммарный вес:
   sum(f * l for f,l in zip(freqs.values(), lengths)).

def code_length(freq_dict: dict[str,int]) -> int:
    """
    Возвращает минимально возможную суммарную длину кода (в битах)
    по формуле Шеннона–Фано и проверяет неравенство Крафта.
    """
    total = sum(freq_dict.values())
    # 1) Рассчитываем длины каждого кодового слова
    lengths = [
        math.ceil(math.log2(total / f))
        for f in freq_dict.values()
    ]
    # 2) Проверяем условие Крафта–Макмиллана
    kraft = sum(2 ** (-l) for l in lengths)
    assert kraft <= 1 + 1e-12, f"Нарушено неравенство Крафта: {kraft:.4f}"
    # 3) Подсчитываем суммарное число бит
    return sum(f * l for f, l in zip(freq_dict.values(), lengths))

3.8.4 Шаг 4. Пример: считаем для частот Фано–Шеннона

result = code_length(freqs)
print("Минимальная суммарная длина кода:", result)
# Ожидаемый вывод: 224
# Пояснение:
# total = 100
# lengths = [ceil(log2(100/45))=2, ceil(log2(100/13))=3, ...
# Тогда sum = 45*2 + 13*3 + 12*3 + 16*3 + 9*4 + 5*5 = 224

3.8.5 Шаг 5. Применение к задачам блока A

• Задача A-3: «Даны частоты символов… Найдите минимальную суммарную длину двоичного кода».
  Вызываем code_length(freqs) и получаем ответ «в один шаг».
• Задача A-5: «Проверьте, возможно ли при заданных длинах кодовых слов составить префиксный код».
  Кодируем частоты как «обратные» длины и проверяем sum(2<sup>−li</sup>) ≤ 1.
• Реальный пример: оценка объёма сжатия лог-файла:
  с помощью code_length получаем нижнюю границу, а затем сравниваем с реальными результатами Huffman-алгоритма.

3.8.6 Итог и самопроверка

1. Почему длину кода для каждого символа берём как ceil(log2(total/f))?
2. Что означает проверка sum(2<sup>−li</sup>) ≤ 1?
3. Какой результат code_length({'X': 10, 'Y': 30, 'Z': 60})?

3.8.7 Пример 1: слово AbraCadabra

Условие: по каналу связи передаются шифрованные сообщения, содержащие строчные и прописные буквы. Определите минимальное число бит для кодирования слова AbraCadabra с неравномерным двоичным кодом, удовлетворяющим условию Фано.

1. 1. Соберём частоты символов:

from collections import Counter
word = "AbraCadabra"
freqs1 = Counter(word)  
# → {'a':4, 'b':2, 'r':2, 'A':1, 'C':1, 'd':1}

1. 1. Подключаем нашу функцию code_length (описанную в 3.8.3) и считаем:

result1 = code_length(freqs1)
print("Минимальная суммарная длина:", result1)
# → Минимальная суммарная длина: 32

1. Пояснение:
   • Всего символов len("AbraCadabra") = 11.
   • Длины оптимальных кодовых слов (по Шеннону–Фано) получились:
     [4,3,3,2,4,4] (соответственно для частот [1,2,2,4,1,1]).
   • Суммарное число бит =
     1·4 + 2·3 + 2·3 + 4·2 + 1·4 + 1·4 = 32.

3.8.8 Пример 2: сжатие списка ОГРН

Условие (реальная практика): передаётся список всех ОГРН кредитных организаций. Цифры встречаются неравномерно:

0:3000  
1:1300  
7:1000  
2:1000  
3:500  
4:500  
5:500  
6:500  
8:500  
9:500  

Найдите минимальное количество бит для кодирования полного списка при условии Фано.

1. 1. Собираем словарь частот:

freqs2 = {
    '0':3000, '1':1300, '7':1000, '2':1000,
    '3':500,  '4':500,  '5':500,  '6':500,
    '8':500,  '9':500
}

1. 1. Считаем нижнюю оценку:

result2 = code_length(freqs2)
print("Минимальное число бит:", result2)
# → Минимальное число бит: 32900

1. Пояснение:
   • Всего цифр 3000+1300+1000+1000+6×500 = 9300.
   • Оптимальные длины кодовых слов:
     [2,3,4,4,5,5,5,5,5,5] бит (для частот в том же порядке).
   • Суммарная длина =
     3000·2 + 1300·3 + 2·1000·4 + 6·500·5 = 32900.

Таким образом, функция code_length позволяет быстро и надёжно получить оценку сжатия как для учебных примеров блока A, так и для реальных статистических задач.

Задания. Блок 3. Неравномерные коды и условие Фано

Задание 3.1.
Дайте определение:

• префикс-код;
• суффикс-код;
• условие Фано (префиксность).

Задание 3.2.
Для двоичного кода проверьте неравенство Крафта–Макмиллана для кодовых длин {l₁, l₂, l₃, l₄} = {2,3,3,4}. Является ли такой набор длин допустимым префикс-кодом?

Задание 3.3.
Дан префикс-код:

A → 0  
B → 10  
C → 110  
D → 111  

Можно ли укоротить какой-либо код?

Задание 3.4.
Объясните, в чём основная разница между двоичными и троичными префикс-кодами. Приведите по одному простому примеру для каждого случая.

Задание 3.5.

• Очень простой: Постройте любой префикс-код для алфавита {A,B,C} с кодовыми длинами {1,2,2}.
• Средний: Дан код для A→11, B→1100, C→1101. Как можно укоротить код B, сохранив постфиксность?
• Сложный: Минимально закодируйте слово «КОРОМЫСЛО» неравномерным двоичным префикс-кодом (условие Фано), выбрав оптимальные длины символов и указав итоговую длину последовательности.

Задание 3.6.
Мини-тест: для каждого набора кодовых слов определите, является ли он префикс-кодом (Да/Нет):

1. {0, 10, 11}
2. {0, 01, 10, 11}
3. {10, 110, 1101, 111}
4. {2, 20, 201, 202}
5. {00, 01, 10, 11}
6. {0, 10, 100, 101}

Задание 3.7.
Напишите на Python:

1. функцию is_prefix_code(code: Dict[str,str]) -> bool, проверяющую условие Фано;
2. генератор всех возможных «укорочений» заданного кода (замена одного слова на более короткое), отбрасывающий невыполнимые варианты.

3.1.
– Префикс-код: ни один кодовый слово не является началом другого.
– Суффикс-код: ни одно кодовое слово не является окончанием другого.
– Условие Фано = префиксность (первая из двух альтернатив).

3.2.  
Сумма 2⁻²+2⁻³+2⁻³+2⁻⁴ = 0.25+0.125+0.125+0.0625 = 0.5625 ≤ 1 → можно.

3.3.  
Никакое слово из {“0”, “10”, “110”, “111”} нельзя сделать короче (выбросить последний бит) без того, чтобы оно не стало префиксом другого.

3.4.  
– Двоичные: биты {0,1}, условие Фано через 2-ичную дерева. Пример {0,10,11}.  
– Троичные: символы {0,1,2}, ветвление «в 3». Пример {0,10,11₂,2}.

3.5.  
– Очень простой: A→0, B→10, C→11.  
– Средний: можно заменить B→110.  
– Сложный: оптимальные длины по частотам (Huffman) → итоговая длина, например, 23 бита.

3.6.
1) Да  
2) Нет (0 — префикс)  
3) Нет (110 — префикс 1101)  
4) Да  
5) Да  
6) Нет (10 — префикс 100)

3.7.  
Функция и генератор написаны в разделе «Решения».

from math import log2, ceil
from typing import Dict, List, Iterator

# 3.2: проверка Крафта
lengths = [2,3,3,4]
K = sum(2**(-l) for l in lengths)
print("Kraft sum:", K)  # ≤1

# 3.3: пример укорочения
code = {'A':'0','B':'10','C':'110','D':'111'}
# укоротим D → '11'
new_code = dict(code)
new_code['D'] = '11'

# 3.6: проверка префиксности
def is_prefix_code(code: Dict[str,str]) -> bool:
    words = list(code.values())
    for w in words:
        for v in words:
            if w!=v and v.startswith(w):
                return False
    return True

# 3.7: генератор укорочений
def shorten_variants(code: Dict[str,str]) -> Iterator[Dict[str,str]]:
    for sym, w in code.items():
        for L in range(1, len(w)):
            cand = w[:L]
            trial = dict(code)
            trial[sym] = cand
            if is_prefix_code(trial):
                yield trial

# Пример использования:
for variant in shorten_variants(code):
    print(variant)

4. Битовые операции и инструменты Python

Почему это важно? Во многих олимпиадных задачах нужно быстро работать с «низкоуровневыми» данными: сетевые флаги, упаковка чисел в бинарные форматы, анализ битовых масок. Побитовые операции и встроенные методы Python помогут решать их надёжно и эффективно.

4.1 Основные побитовые операторы и методы

4.1.1 Сдвиги

• << n — сдвиг влево на n бит (аналог умножения на 2ⁿ).
  Пример: 5 << 2 == 5×2² == 20.
  Когда пригодится: при формировании масок: 1<<n даёт число с единицей на позиции n.
• >> n — сдвиг вправо на n бит (целочисленное деление на 2ⁿ).
  Пример: 20 >> 2 == 20÷2² == 5.
  Когда пригодится: при извлечении старших битов: x>>16 даёт старшие 16 бит.

4.1.2 Побитовое «И», «ИЛИ», «XOR», «NOT»

Важно: Python хранит целые в «дополнительном коде» бесконечной длины, поэтому после ~x нужно «обрезать» 32 бита: ~x & 0xFFFFFFFF.

4.1.3 Методы для целых

• int.bit_length() — число бит в минимальном двоичном представлении (без ведущих нулей).
  Пример: (3000).bit_length() == 12 (3000₂ занимает 12 бит).
• int.to_bytes(length, byteorder) — переводит число в bytes фиксированной длины length, big-endian или little-endian.
  Пример: 3000.to_bytes(2,'big') == b'\x0b\xb8' (0x0BB8 = 3000).

Что такое big-endian / little-endian?
big-endian хранит старший байт первым: 0x0B B8 → b'\x0b\xb8'.
little-endian — наоборот: b'\xb8\x0b'.
Это важно при взаимодействии с сетевыми протоколами и бинарными файлами.

4.2 Пример: найти старший установленный бит числа 3000

n = 3000
# bit_length() даёт длину двоичной без ведущих нулей:
length = n.bit_length()      # 12
pos = length - 1             # старший бит на позиции 11 (0-based)
print(f"3000 = {bin(n)}; старший бит индекс {pos}")

# Если нужно само значение бита:
highest = 1 << pos           # 2^11 = 2048
print("Значение старшего бита:", highest)

bin(3000) = 0b101110111000
                ↑
      старший '1' на позиции 11 (счёт справа от 0)

Зачем? При анализе флагов и при определении диапазонов мощности (2ᵏ) чаще всего нужно знать, какую «высоту» даёт число.

4.3 Мини-код-квесты

Разделите вопросы по типам, решайте в интерактивном Python REPL:

4.3.1 Сдвиги и логика

1. Что выдаст (7 << 3)?
2. Что выдаст 0b101101 & 0b110011?
3. Чему равно (~0b001011) & 0xFF (8-битная инверсия)?

4.3.2 Методы

1. Как получить 4-байтовое представление числа 12345678 в big-endian?
2. Сколько единиц в 0b101011? (bin(...).count('1'))
3. Какая bit_length() у 1023?

4.4 🔧 Практическая задача: анализ сетевого флага

Задача: В протоколе есть 32-битный флаг flags = 0b10100100010010001100101000000011.
Нужно:

1. Извлечь 8-битные поля: field1 (старшие 8 бит), field2, field3, field4 (младшие 8 бит).
2. Определить, сколько «1» в каждом поле.
3. Проверить: все ли поля непустые (хотя бы один бит «1»)?

flags = int('10100100010010001100101000000011', 2)

# Разбиваем на октеты:
oct1 = (flags >> 24) & 0xFF
oct2 = (flags >> 16) & 0xFF
oct3 = (flags >> 8)  & 0xFF
oct4 = flags & 0xFF

for i, octet in enumerate((oct1, oct2, oct3, oct4), start=1):
    bstr = format(octet, '08b')
    ones = bstr.count('1')
    print(f"Field{i}: {bstr}, ones={ones}")

Такой подход помогает парсить заголовки сетевых пакетов, работать с битовыми масками в алгоритмах сжатия и шифрования.

4.5 Итоговые вопросы и самопроверка

1. Какое значение даст 5 << 4? Почему?
2. Как получить младшие 16 бит числа x? Запишите через & и сдвиг.
3. Почему после ~x нужно делать & 0xFFFFFFFF?
4. Что вернёт (12345678).to_bytes(4,'big')? В каком формате?
5. Для числа n как получить номер самого старшего бита (0-based)?

Задания. Блок 4. Битовые операции и инструменты Python

Задание 4.1.
Перечислите и кратко поясните назначение следующих операторов и методов в Python для работы с битами:
<<, >>, &, |, ^, ~, метод .bit_length() и метод .to_bytes().

Задание 4.2.
Напишите однострочное Python-выражение, которое для числа n = 3000 выводит номер (индекс) самого старшего установленного бита (где младший бит имеет индекс 0).

Задание 4.3. «Мини-код-квест» — быстро напишите в консоли результаты следующих выражений:

1. (15 << 3) \| 7
2. bin(0b101011).count('1') — сколько единиц?
3. «Инверсия» младших 8 бит числа 0b00110011: (~0b00110011) & 0xFF
4. Битовая длина числа 1023: (1023).bit_length()

Задание 4.4.
Напишите на Python функцию
def code_length(freq_dict: dict[str,int]) -> int:
которая по словарю частот символов возвращает теоретически минимально возможную сумму длин всех кодовых слов (ниже оценки по биномиальной формуле Шеннона–Фано), вычисляемую как

total = sum(freq_dict.values())
return sum(freq * math.ceil(math.log2(total/freq))
           for freq in freq_dict.values())

и дополнительно проверяет, что распределённые длины удовлетворяют неравенству Крафта:
sum(2**(-l) for l in lengths) <= 1.

 (3000).bit_length() - 1

 code_length({'a':5, 'b':3, 'c':2}) 
# total=10, длины = [ceil(log2(10/5))=1, ceil(log2(10/3))=2, ceil(log2(10/2))=3] 
# суммарная длина = 5⋅1 + 3⋅2 + 2⋅3 = 5 + 6 + 6 = 17 17 

 import math 
# 4.2 — однострочник: 
highest = (3000).bit_length() - 1 print(highest) # 11 
# 4.3 — примеры «на лету»: print((15 << 3) | 7) # 127 
print(bin(0b101011).count('1')) # 4 
print((~0b00110011) & 0xFF) # 204 
print((1023).bit_length()) # 10 
# 4.4 — оценка по Шеннону–Фано + проверка Крафта 
def code_length(freq_dict: dict[str,int]) -> int:
    total = sum(freq_dict.values()) 
    lengths = [math.ceil(math.log2(total / f)) for f in freq_dict.values()] # проверка неравенства Крафта 
    assert sum(2**(-l) for l in lengths) <= 1 + 1e-12 
    return sum(f * l for f, l in zip(freq_dict.values(), lengths)) 
# Пример: print(code_length({'a':5, 'b':3, 'c':2})) # 17 

5. Числа в компьютере и выравнивание (struct)

Во всех низкоуровневых задачах — от сетевых протоколов до бинарных форматов файлов — нам нужно точно знать, как числа лежат в памяти: сколько байт они занимают, как меняются биты при переполнении и как Python позволяет работать с этими битами.

5.1 Целые числа в памяти

5.1.1 Беззнаковый (unsigned) формат

• Диапазон: от 0 до 2ⁿ – 1.
  Пример для 8 бит: 0…255.

5.1.2 Знаковый (signed) формат и «дополнительный код»

• Диапазон: от –2ⁿ⁻¹ до 2ⁿ⁻¹ – 1.
  Пример для 8 бит: –128…+127.
• Как хранится −5?
  1. Записываем +5 → 00000101₂.
  2. Инвертируем биты → 11111010₂.
  3. Прибавляем 1 → 11111011₂.
  Это «дополнительный код» числа −5.

+127 →  0 1111111    
   …  
   +5  → 0 0000101    
   –5  → 1 1111011    
…  
       –128 →  1 0000000    
  sign ↑ |———— magnitude ————|

5.1.3 Выбор типа на практике

• Если значение никогда не отрицательно (см. счётчики, длины буферов) — используем unsigned, чтобы расширить диапазон вверх.
• Для отрицательных смещений (координаты относительно центра, переполнение) — signed.

5.2 Вещественные числа и IEEE-754

5.2.1 Формат float32

• 32 бита:
  [sign:1][exponent:8][mantissa:23]
• Экспонента хранится со смещением (bias=127), реальный порядок = exp_field – 127.
• Мантисса = 1.fraction (для нормализованных чисел).

┌───1───┬─────8─────┬──────────────23──────────────┐
│ sign  │ exponent  │         mantissa (frac)      │
└───────┴───────────┴──────────────────────────────┘

5.2.2 Формат float64

• 64 бита:
  [sign:1][exponent:11][mantissa:52]
• bias=1023; порядок = exp_field – 1023.

5.2.3 Почему важно?

• Ошибки округления при работе с дробными числами (например, проверка 0.1 + 0.2 == 0.3 даёт False).
• При передаче по сети или в бинарных форматах нужно знать порядок байт и точную раскладку.

5.3 Пример: «Сколько байт нужно для долготы с точностью 1″?»

1. Диапазон: –180…+180° → 360° в сумме.
2. Шаг: 1″ = 1/3600° → 360×3600 = 1 296 000 возможных значений.
3. Биты: ⌈log₂1 296 000⌉ = 21 бит.
4. Байты: ⌈21/8⌉ = 3 байта.

Почему unsigned? Потому что долгота кодируется без отрицательной части: смещаем диапазон на +180° и кодируем 0…360°.

5.4 Мини-тест: диапазоны целых чисел

1. Unsigned 12 бит: 0…2¹²–1 = 4095.
2. Signed 16 бит (2’s complement): –2¹⁵…2¹⁵–1 = –32768…+32767.
3. Сколько бит надо, чтобы представить 1 000 000?
   ⌈log₂1 000 000⌉ = 20 (2²⁰ = 1 048 576).

5.5 🔧 Разбор float32 бит за битом через struct

Покажем, как Python упаковывает float и разберём поля.

import struct

def float32_bits(x):
    # '>f' — big-endian float32
    b = struct.pack('>f', x)
    bits = ''.join(f'{byte:08b}' for byte in b)
    sign = bits[0]
    exponent = bits[1:9]
    mantissa = bits[9:]
    return sign, exponent, mantissa

s,e,m = float32_bits(0.1)
print("0.1 =", s, e, m)
# Пример вывода:
# sign=0 exponent=01111011 mantissa=10011001100110011001101

0 | 1111011 | 10011001100110011001101
↑    ↑               ↑
sign exp             mantissa

Little-endian? Если использовать ‘<f‘ в pack, байты пойдут в обратном порядке.

5.6 Итоговые вопросы и задания

1. Как по «дополнительному коду» получить биты отрицательного числа?
2. Почему у float32 bias = 127, а у float64 = 1023?
3. Какой структурный формат Python-struct нужен для little-endian double?
4. Рассчитайте, сколько байт понадобится для хранения широты с точностью 0.1″.

Задания. Блок 5. Числа в компьютере и выравнивание (struct)

Задание 5.1.
Объясните разницу между беззнаковыми и знаковыми целыми в Python/C:

• Какой диапазон значений может храниться в n-битном беззнаковом числе?
• Какой диапазон хранится в n-битном знаковом в дополнительном коде?

Задание 5.2.
Опишите устройство формата IEEE-754 для float32 и float64:

• Сколько бит занимает знак, экспонента и мантисса?
• Как рассчитывается действительный числовой диапазон?

Задание 5.3.
Сколько байт требуется для хранения географической долготы с точностью до 1 секунды (1″ ≈ 1/3600°), если её значение лежит в диапазоне от −180° до +180°?
Предложите минимальный целочисленный тип (беззнаковый или знаковый) и укажите его размер в байтах.

Задание 5.4.
Мини-тест на диапазоны (ответьте числом):

1. Максимальное беззнаковое значение в 12 бит: ?
2. Минимальное знаковое значение в 16-битном дополнительном коде: ?
3. Максимальное знаковое значение в 8-битном дополнительном коде: ?

Задание 5.5.
Напишите на Python однострочный скрипт, который для десятичного числа x выводит его IEEE-754 представление в формате float32 в виде 32-битной двоичной строки.
(Подсказка: используйте struct.pack, int.from_bytes и format(..., '032b').)

5.1.
— n-битный беззнаковый: 0 … 2ⁿ−1  
— n-битный знаковый (доп. код): −2ⁿ⁻¹ … 2ⁿ⁻¹−1

5.2.
— float32: 1 бит знак, 8 бит экспонента (смещение 127), 23 бита мантисса  
— float64: 1 бит знак, 11 бит экспонента (смещение 1023), 52 бита мантисса

5.3.
Диапазон ±180° = ±648 000″ → всего 1 296 001 значений  
⌈log₂ 1 296 001⌉ = 21 бит → 3 байта

5.4.
1) 2¹²−1 = 4095  
2) −2¹⁵ = −32768  
3) 2⁷−1 = 127

5.5.

import struct
x = 3.14
bits = int.from_bytes(struct.pack('>f', x), 'big')
print(format(bits, '032b'))

import struct
import math

# 5.1. Диапазоны:
def ranges(n):
    unsigned = (0, 2**n - 1)
    signed   = (-2**(n-1), 2**(n-1) - 1)
    return unsigned, signed

print("12-бит unsigned / signed:", ranges(12))
# → (0, 4095), (-2048, 2047)

# 5.3. Вычисление точности секунды:
# ±180° → ±648000" → 1296001 позиций → ceil(log2(1296001)) = 21 бит → 3 байта

# 5.4. Проверки:
print("2^12-1 =", 2**12 - 1)   # 4095
print("-2^15 =", -2**15)        # -32768
print("2^7-1 =", 2**7 - 1)      # 127

# 5.5. Однострочник:
x = 3.14
bits = int.from_bytes(struct.pack('>f', x), 'big')
print("float32 bits:", format(bits, '032b'))

6. Кодирование текста

В олимпиадных задачах и в реальных системах (сети, базы данных, файлы) строки могут «распухать» при разных кодировках. Чтобы оценить объём передаваемых или хранимых данных, нужно точно знать, сколько байт займёт каждый символ в UTF-8, UTF-16 и других.

6.1 ASCII vs UTF-8 vs UTF-16

6.1.1 ASCII (7-бит)

• Кодирует U+0000…U+007F (0…127) по 1 байту (старший бит = 0).
• Пример: 'A' → 0x41, '{' → 0x7B.

6.1.2 UTF-8 (1–4 байта)

Байтовый шаблон по Unicode-кодовой точке U+0000…U+10FFFF:

U+0000…U+007F   0xxxxxxx  
U+0080…U+07FF   110xxxxx 10xxxxxx  
U+0800…U+FFFF   1110xxxx 10xxxxxx 10xxxxxx  
U+10000…U+10FFFF 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx  

6.1.3 UTF-16 (2 или 4 байта)

• U+0000…U+FFFF → 2 байта (16-bit code unit).
• U+10000…U+10FFFF → суррогатная пара:
  high-surrogate (0xD800–0xDBFF) +
  low-surrogate (0xDC00–0xDFFF) (всего 4 байта).

U' = code_point – 0x10000   20-bit value
high = 0xD800 + (U' >> 10)
low  = 0xDC00 + (U' & 0x3FF)

6.2 Пример: «Hello, мир!» в разных кодировках

text = "Hello, мир!"

6.3 Проверка «ручками»

Посчитайте, сколько байт займёт строка в UTF-8:

1. "Привет🌍" → ?
2. "12345" → ?
3. "中文字符" → ?

Подсказка: суммируйте len(ch.encode('utf-8')) для каждого символа.

6.4 🔧 Python-код: длина и сам байт-массив

# Пример 1: UTF-8 и hex-вывод
s = "Привет🌍"
b = s.encode('utf-8')
print("UTF-8 bytes:", b.hex())
print("Length:", len(b))

# Пример 2: UTF-16 с BOM
b2 = s.encode('utf-16')      # по умолчанию BOM + little-endian
print("UTF-16 bytes:", b2.hex())
print("Length:", len(b2))

# Пример 3: UTF-16LE без BOM
b3 = s.encode('utf-16le')
print("UTF-16LE:", b3.hex(), "Length:", len(b3))

6.5 Итоговые вопросы и задания

1. Какой шаблон UTF-8 и сколько байт займёт U+07FF?
2. Почему в UTF-16 возникает BOM и как его избежать?
3. Посчитайте байты для строки "Hello 😊" в UTF-8.
4. Как в Python увидеть hex-представление байтов для любой кодировки?

Задания. Блок 6. Кодирование текста

Задание 6.1.
Опишите основные характеристики кодировок:

• ASCII (7-битный, фиксированная длина 1 байт).
• UTF-8 (переменная длина: от 1 до 4 байт).
• UTF-16 (переменная длина: 2 или 4 байта, с surrogate-парами).

Задание 6.2.
Сравните объём строки "Hello, мир!" при хранении в:

• • ASCII + UTF-8 (т.е. каждый ASCII-символ 1 байт, не-ASCII в UTF-8).
  • UTF-16 (без BOM).

Для каждого формата укажите итоговый размер в байтах.

Задание 6.3.
Мини-тест: если у нас строка из 5 русских букв, каждую в UTF-8 кодируют 2 байта, то объём = 5×2 = 10 байт.
Верно ли, что для строки из 5 эмодзи (каждый в UTF-8 занимает 4 байта) объём = 5×4 = 20 байт? Ответьте «да» или «нет» и объясните.

Задание 6.4.
Напишите короткий Python-скрипт, который выводит длину в байтах любого Юникод-строчного литерала s в UTF-8 и в UTF-16:

s = "Пример😊"
print(len(s.encode('utf-8')), "bytes in UTF-8")
print(len(s.encode('utf-16le')), "bytes in UTF-16 (LE without BOM)")

6.1.
— ASCII: 7-bit, 1 byte per char, 128 symbols.  
— UTF-8: 1–4 bytes per char; ASCII-range =1 byte, Cyrillic =2 bytes, emoji =4 bytes.  
— UTF-16: 2 bytes per BMP char, 4 bytes for code points > U+FFFF via surrogate pairs.

6.2.
"Hello, мир!":
— ASCII+UTF-8:  
  "Hello, " = 7 ASCII bytes  
  "мир" = 3 Cyrillic ×2=6 bytes  
  "!" = 1 ASCII byte  
  Total = 7+6+1 = 14 bytes  
— UTF-16 (LE):  
  9 chars ×2 bytes = 18 bytes

6.3.
Да. Каждый эмодзи U+… требует 4 байта в UTF-8, значит 5×4 = 20 bytes.

6.4.
Скрипт (пример вывода для "Пример😊"):
# UTF-8: 12 bytes  
# UTF-16: 14 bytes

# 6.2 Проверка:
s = "Hello, мир!"
utf8 = len(s.encode('utf-8'))
utf16 = len(s.encode('utf-16le'))
print("UTF-8 bytes:", utf8)    # 14
print("UTF-16 bytes:", utf16)  # 18

# 6.3 Мини-проверка:
emoji_str = "😊" * 5
print(len(emoji_str.encode('utf-8')))  # 20

# 6.4 Универсальный скрипт:
def show_lengths(s: str):
    b8 = len(s.encode('utf-8'))
    b16 = len(s.encode('utf-16le'))
    print(f"UTF-8: {b8} bytes; UTF-16: {b16} bytes")

show_lengths("Пример😊")

7. Изображения: как считать объём растровых картинок

В веб-разработке, мобильных приложениях и задачах по обработке графики важна оценка объёма RAW-изображений до компрессии и после. На олимпиадах иногда встречаются задачи о передаче фотографий или создании PDF-альбомов, где нужно точно рассчитать объём.

7.1 RAW-объём: базовая формула

Формула:

Size_bytes = Width_px × Height_px × bpp ÷ 8

• Width_px, Height_px — размеры в пикселях
• bpp (bits per pixel) — бит на пиксель, например:
  • TrueColor (24-bit RGB): bpp=24
  • 256-цветная палитра: bpp=⌈log₂256⌉=8
  • Для M-цвет: bpp=⌈log₂M⌉
• Почему ÷8? Переводим биты в байты.

[Width_px × Height_px]  — площ. в пикселях
           ↓ × bpp      — бит на пиксель
          ↓ ÷ 8         — байты

7.2 DPI → пиксели и масштабирование

7.2.1 DPI → пиксели

Width_px  = Width_inch  × dpi  
Height_px = Height_inch × dpi

dpi (dots per inch) — сколько пикселей помещается в дюйме.

7.2.2 Линейное масштабирование

При уменьшении на k% каждая линейная сторона становится k/100 от оригинала, а число пикселей:

New_px = Old_px × (k/100)²

7.2.3 Глубина цвета и сжатие

• Смена bpp в M раз → объём меняется в M раз.
• После raw-вычисления объём JPEG ≈ raw_bytes × (1 – compression_ratio).

7.3 Подробные примеры

7.4 Быстрый опрос

7.5 🔧 Python-калькулятор

import math

def image_size(width, height, colors, dpi=1, compression=0.0):
    """
    width, height — в пикселях (или inches если dpi>1);
    colors — число цветов;
    dpi — коэффициент перевода дюймов в пиксели (по умолчанию 1);
    compression — доля сжатия JPEG (0.0–0.9).
    Возвращает dict с объёмом в B, KiB, MiB.
    """
    w_px = width * dpi
    h_px = height * dpi
    bpp = math.ceil(math.log2(colors))
    raw_bits = w_px * h_px * bpp
    raw_bytes = math.ceil(raw_bits / 8)
    comp_bytes = math.ceil(raw_bytes * (1 - compression))
    return {
        'raw_B': raw_bytes,
        'raw_KiB': raw_bytes / 1024,
        'raw_MiB': raw_bytes / (1024**2),
        'compressed_B': comp_bytes,
        'compressed_KiB': comp_bytes / 1024,
        'compressed_MiB': comp_bytes / (1024**2),
    }

# Пример:
print(image_size(128,128,2**24))  
# {'raw_B':49152, 'raw_KiB':48.0, 'raw_MiB':0.046875, ...}

print(image_size(6,4,256,dpi=300, compression=0.7))  
# печатное фото 6″×4″ @300dpi, 256 цветов, JPEG 70%  

Быстрые задания

1. Рассчитайте raw-объём фото 4000×3000 px, 48 bpp.
2. Для печати 5″×7″ @150 dpi, 16 цветов: сколько байт займет изображение?
3. Сколько байт останется после 80%-го сжатия при исходном raw_Bytes=10 000 000?

Задания. Блок 7. Изображения

Задание 7.1.
Напишите формулу для вычисления объема несжатого растрового изображения:

Размер (в байтах) = W × H × (bpp) / 8

Объясните, как переходят dpi → пиксели и как из мощности палитры M получается bpp = ⌈log₂ M⌉.

Задание 7.2.
Опишите, как меняется размер изображения при:

• масштабировании (линейный коэффициент k);
• изменении глубины цвета в p раз (например, bpp/2);
• последующем сжатии на k % (т. е. сохраняется k% от исходного объема).

Запишите итоговую формулу через W, H, bpp, k₁ (масштаб), p (глубина), k₂ (сжатие).

Задание 7.3.

• Простой: raw-BMP 128×128 пикселей, 24 bpp. Сколько КБ занимает?
• Средний: исходно 96″×54″ при 600 ppi, 24 bpp, размер 27 MiB; уменьшили до 64″×36″, глубину цвета в 1.5 раза меньше и разрешение вдвое. Сколько MiB сэкономлено?
• Сложный: 32 изображения 2048×1536 пикселей занимают 16 MB (десятичные). Сколько цветов в палитре каждого (bpp)?

Задание 7.4.
Мини-тест «Сколько КБ?»

1. 512×512, 8 bpp → ?
2. 800×600, 16 bpp → ?
3. 300 dpi → пиксели на дюйм: ?
4. 1024×768, палитра 4096 цветов → bpp = ?
5. 64×64, 1 bpp (черно-белое) → ?
6. 100×100, 256 цветов, сжатие на 50% → ?

Задание 7.5.
Напишите на Python функцию, которая по размеру фото по-вертикали и горизонтали, а также количеству цветов, возвращает размер в байтах изображения. Доработайте функцию. Добавьте параметр «Процент сжатия» для вычисления размера с учетом сжатия.

7.1.  
V = W·H·bpp/8;  
dpi→px: пикселей = дюймы·dpi;  
bpp = ⌈log₂ M⌉.

7.2.  
После масштабирования: W' = k₁W, H' = k₁H;  
глубина: bpp' = bpp/p;  
сжатие: ×k₂/100;  
Итого: V = k₂/100 · (k₁W)·(k₁H)·(bpp/p)/8.

7.3.  
— 128×128, 24 bpp: 128·128·24/8 = 49 152 B = 48 KB.  
— 96→64, 54→36, dpi 600→300, bpp 24→16:  
  исходно: 27 MiB;  
  новый px: (64·300)×(36·300)=19 200×10 800;  
  бpp=16; V'=19 200·10 800·16/8 ≈ 41472 KiB ≈ 40.5 MiB;  
  экономия ≈ 27−40.5 (отрицательно — пересчитайте!).  
(см. Решения)

— 32×(2048×1536) = total pixels;  
  16 MB =1.6×10⁷ B;  
  bpp = 16 000 000·8/(32·2048·1536) ≈ 2 bpp → 4 цвета.

7.4.  
1) 32 KB  
2) 1200 KB  
3) 300 dpi  
4) 12 bpp  
5) 512 B = 0.5 KB  
6) 100×100×8/8=10 KB

7.5.  

def image_size(w: int, h: int, colors: int) -> int:
    """
    Возвращает размер изображения в байтах:
      width=w, height=h, palette size=colors.
    """
    import math
    bpp = math.ceil(math.log2(colors))
    return w * h * bpp // 8

import math

# 7.3 Простой
print(128*128*24//8, "bytes")  # 49152

# 7.3 Средний
# исходное 27 MiB = 27*2**20 bytes
w1, h1, dpi1, bpp1 = 96, 54, 600, 24
w2, h2, dpi2, bpp2 = 64, 36, 300, 16
px1 = w1*dpi1, h1*dpi1
px2 = w2*dpi2, h2*dpi2
V2 = px2[0]*px2[1]*bpp2//8
print("new MiB:", V2/2**20)

# 7.3 Сложный
total_pixels = 32*2048*1536
bpp = 16_000_000*8/total_pixels
print("bpp ≈", bpp)

# 7.4 Примеры:
print(image_size(512,512,256)/1024, "KB")  # 32
print(image_size(800,600,65536)/1024)      # 1200
print("dpi→px: 300")
print("bpp:", math.ceil(math.log2(4096)))
print("1bpp 64×64:", image_size(64,64,2)/1024)
print("50% compression:", image_size(100,100,256)*0.5/1024)

# 7.5 Функция:
def image_size(w: int, h: int, colors: int) -> int:
    bpp = math.ceil(math.log2(colors))
    return w*h*bpp//8

8. Звук и видео: как считать объём аудио- и видеопотоков

На олимпиадах и в реальных кейсах (запись подкастов, потоковое видео, хранение архивов) нужно понимать, сколько памяти займёт чистый (raw) аудио- или видеопоток прежде чем применять кодеки.

8.1 Несжатый звук (PCM)

Цифровой звук—это последовательность семплов (отсчётов), каждый из которых хранит амплитуду сигнала.

Size_bytes = SampleRate (Hz) × BitDepth (bits) × Channels × Duration (s) ÷ 8

Пример: WAV 30 с, стерео, 48 kHz, 16 bit

Внимание! В WAV-файле ещё есть RIFF-заголовок (~44 B), но на олимпиадах обычно считают только payload.

8.2 Несжатое видео (raw)

Несжатое видео — это поток кадров (frames), каждый кадр как отдельное изображение + служебная информация.


FrameSize_bytes = Width_px × Height_px × bpp ÷ 8
TotalSize = (FrameSize_bytes + Header_bytes) × FPS × Duration_s


Пример: 4K (3840×2160), 24 bpp, 60 fps, Duration until 1 TB filled

Чтобы перевести байты в MiB, делим на 2²⁰ (1 MiB = 1 048 576 B).

8.3 Во сколько раз изменится объём?

8.4 🔧 Python-скрипт для raw-аудио и raw-видео

import math

def audio_size(sr_hz, bit_depth, channels, duration_s, include_header=0):
    """
    sr_hz        — частота дискретизации (Hz)
    bit_depth    — глубина семпла (bits)
    channels     — число каналов
    duration_s   — длительность (сек)
    include_header — bytes дополнительного заголовка
    """
    bits = sr_hz * bit_depth * channels * duration_s
    total_bytes = math.ceil(bits / 8) + include_header
    return {
        'bytes': total_bytes,
        'KiB': total_bytes / 1024,
        'MiB': total_bytes / (1024**2),
    }

def video_size(width, height, bpp, fps, duration_s, header_bytes=0):
    """
    width, height — размеры кадра (px)
    bpp           — бит на пиксель
    fps           — кадров в секунду
    duration_s    — длительность (сек)
    header_bytes  — служебных байт на кадр
    """
    frame_bits = width * height * bpp
    frame_bytes = math.ceil(frame_bits / 8) + header_bytes
    total_bytes = frame_bytes * fps * duration_s
    return {
        'bytes': total_bytes,
        'KiB': total_bytes / 1024,
        'MiB': total_bytes / (1024**2),
    }

# Примеры:
print(audio_size(48000, 16, 2, 30))              # WAV 30 s
print(video_size(3840, 2160, 24, 60, 60))        # 1 мин. 4K без header
print(video_size(1920,1080,24,30,10, header_bytes=1024))  # 10 s + 1 KiB header/frame

Практические задания

1. Рассчитайте размер RAW-аудио 2 min, 44.1 kHz, 24 bit, mono.
2. Сколько минут видео 1080p@30 fps вмещает 128 GiB при 24 bpp и 512 B header/frame?
3. Во сколько раз изменится объём, если перейти с 16→24 bit и стерео→mono одновременно?

Контрольные вопросы:

• Что такое семпл и BitDepth?
• Почему используем ceil(bits/8) вместо простого деления?
• Чем RAW-видео отличается от потока с кодеком?

Задания. Блок 8. Звук и видео

Задание 8.1.
Напишите формулу для вычисления размера звукового файла без сжатия и поясните каждый параметр:

Size (bytes) = freq (Hz) × bit_depth (bits) × channels × duration (s) / 8

Задание 8.2.
Напишите формулу для вычисления размера видеоролика без сжатия, учитывая служебные заголовки:

Size (bytes) = (W × H × bpp / 8) × fps × duration (s)
               + header_size (bytes per frame) × fps × duration (s)

Задание 8.3.

• Средний: WAV, стерео, 48 kHz, 16 bit, 30 s. Сколько Мбайт занимает?
• Сложный: Видео 4K (3840×2160), 60 fps, RGB 8 bit×3, продолжительность 1 h. SSD-ресурс 1 PB полного перезаписи: сколько часов видео «износят» диск?

Задание 8.4.
Мини-тест «во сколько раз изменится объём?»

1. Стерео 44 kHz → 96 kHz
2. 16 bit → 24 bit
3. 30 fps → 60 fps
4. Full HD → 4K (1920×1080 → 3840×2160)
5. WAV → MP3 (10× сжатие)

Задание 8.5.
Напишите на Python функцию:

def video_size(w: int, h: int, bpp: int, fps: int,
               sec: int, hdr_per_frame: int = 0) -> int:
    """
    Возвращает размер видео в байтах без сжатия:
      w,h = разрешение,
      bpp = бит/пиксель,
      fps = кадров/с,
      sec = длительность в секундах,
      hdr_per_frame = служебные байты на кадр.
    """

8.1.  
Size = freq × bit_depth × channels × duration / 8  
— freq = частота дискретизации в Гц  
— bit_depth = глубина кодирования в битах  
— channels = число каналов (1=моно, 2=стерео)  
— duration = длительность в секундах  

8.2.  
Size = (W×H×bpp/8)×fps×duration + header_size×fps×duration  
— W, H = ширина и высота в пикселях  
— bpp = биты на пиксель  
— fps = кадров в секунду  
— duration = длительность в секундах  
— header_size = служебные байты на кадр  

8.3.  
— WAV 48 kHz,16 bit,стерео,30 s:  
  samples = 48000×30 = 1 440 000  
  bytes_per_sample = 16/8×2 = 4  
  size = 1 440 000×4 = 5 760 000 bytes ≈ 5.76 MB  

— 4K 60 fps, RGB8×3,1 h:  
  bytes/frame = 3840×2160×24/8 = 38 4 ×2160×3 = 24 883 200 bytes  
  bytes/sec = 24 883 200×60 = 1 493 e6  
  bytes/hour = ×3600 ≈ 5.375×10¹² bytes ≈ 5.375 TB  
  SSD 1 PB =10¹⁵ bytes → 10¹⁵/5.375×10¹² ≈ 186 h  

8.4.  
1) 96/44 ≈ 2.18×  
2) 24/16 = 1.5×  
3) 60/30 = 2×  
4) (3840×2160)/(1920×1080) = 4×  
5) 1/10 = 0.1×  

8.5.  
— Функция video_size возвращает байты по формуле из 8.2.
[/pre]

# 8.3 — расчёты
# WAV:
freq, depth, ch, dur = 48000, 16, 2, 30
size_wav = freq * (depth//8) * ch * dur
print(size_wav / (1024**2))  # → 5.76 MB

# 4K видео:
w, h, bpp, fps, sec = 3840, 2160, 24, 60, 3600
byte_per_frame = w * h * bpp // 8
bytes_per_sec = byte_per_frame * fps
bytes_per_hour = bytes_per_sec * sec
print(bytes_per_hour / 1e12)  # → ≈5.375 TB
print(1e15 / bytes_per_hour)  # → ≈186 h

# 8.5 — пример использования:
def video_size(w: int, h: int, bpp: int, fps: int,
               sec: int, hdr_per_frame: int = 0) -> int:
    frame_bytes = w * h * bpp // 8 + hdr_per_frame
    return frame_bytes * fps * sec

# Тест:
print(video_size(1920,1080,24,30,60))  # Full HD, 1 min, no header

9. Сжатие и проценты экономии

На олимпиадах и в реальных проектах (архивирование, передача медиа, оптимизация хранилищ) важно оценивать, насколько данные можно «ужать»—и при этом уложиться в лимиты по памяти или каналу.

9.1 Виды сжатия и коэффициент экономии

• Lossless (без потерь) – после распаковки восстанавливаем точную копию исходных данных (ZIP, PNG, FLAC).
• Lossy (с потерями) – часть информации отбрасывается, обычно незаметно для пользователя (JPEG, MP3).

Формула:
NewSize = OldSize × (1 – k/100)

9.2 Пример lossless: RLE (Run-Length Encoding)

RLE заменяет каждую «прогонку» одинаковых символов (run) на пару (длина, символ).

1. Исходная строка:
   12300000000000555
2. Найти прогонки:
   (1×’1′), (1×’2′), (1×’3′), (11×’0′), (3×’5′)
3. Записать RLE-код:
   (1,'1'), (1,'2'), (1,'3'), (11,'0'), (3,'5')
4. Декодирование обратно:
   repeat('1',1) + repeat('2',1) + … = '123000…00555'

В реальных форматах после каждой пары могут идти метки границ или флаги, чтобы отличить цифру «1» от разделителя.

9.3 Цепочка операций: scale → compress

Часто нужно выполнить несколько операций подряд: сначала изменить объём (scale), затем сжать (compress).

9.4 Мини-квиз: «Сколько останется?»

Контрольные вопросы:

• Как переводить между B, KiB, MiB (2¹⁰)?
• Почему при scale 2× мы делим, а не умножаем?
• Как различить lossless-сжатие и scale-операцию?

9.5 🔧 Универсальная функция after_chain

import math

def after_chain(size_bytes, operations, unit='B'):
    """
    size_bytes — исходный объём в байтах (int)
    operations — список кортежей:
       ("scale", factor)      # делим на factor
       ("compress", percent)  # умножаем на (1-percent/100)
       ("increase", percent)  # умножаем на (1+percent/100)
    unit — "B", "KiB", "MiB" для вывода
    """
    result = float(size_bytes)
    for op, val in operations:
        if op == "scale":
            if val == 0: raise ValueError("scale factor must be non-zero")
            result /= val
        elif op == "compress":
            result *= (1 - val/100)
        elif op == "increase":
            result *= (1 + val/100)
        else:
            raise ValueError(f"Unknown op: {op!r}")
    # Округляем до целых байт
    result_bytes = math.ceil(result)
    # Переводим в нужную единицу
    factors = {'B':1, 'KiB':1024, 'MiB':1024**2}
    return {
        'bytes': result_bytes,
        'KiB': result_bytes / factors['KiB'],
        'MiB': result_bytes / factors['MiB'],
    }

# Примеры:
print(after_chain(100_000, [("scale",1.5), ("compress",40)]))
# → {'bytes':40000, 'KiB':39.0625, 'MiB':0.0381…}

print(after_chain(1_048_576, [("compress",50), ("increase",20)], 'KiB'))
# → {'bytes':629146, 'KiB':614.38…}

Задания для закрепления

1. С помощью after_chain посчитайте, сколько байт займёт видео, если сначала уменьшить глубину на 25%, а потом сжать на 60%.
2. Допишите проверку в функцию, чтобы операции с неожиданными аргументами (percent>100) вызывали предупреждение.
3. Приведите пример real-world: за какую секунду аудио (PCM, 48 kHz, 16 bit, stereo) уместится в 1 MiB.

Задания. Блок 9. Сжатие и проценты экономии

Задание 9.1.
Объясните разницу между «сжатием без потерь» и «с потерями». Определите, что такое коэффициент сжатия k% и как вычислить оставшийся объём после такого сжатия.

Задание 9.2.
Реализуйте RLE (Run-Length Encoding) для десятичных цифр: повторяющиеся цифры заменяются на пару «длина серии + цифра», серии длиной >9 разбиваются на части длины 9 и остаток.
Какой будет результат RLE и сколько байт займёт кодирование числа
12300000000000555
если каждый символ (цифра или длина) кодируется 4 битами?

Задание 9.3.
Пример цепочки преобразований:
— уменьшили глубину цвета в 1.5 раза,
— затем сжали на 40 %.
Вопрос: во сколько раз изменился объём по сравнению с исходным?

Задание 9.4.
Мини-квиз «во сколько раз останется»: для каждого пункта запишите множитель, на который умножится исходный объём:

1. уменьшили на 30 %
2. сжали до 25 % (коэффициент 75 % сжатия)
3. увеличили без сжатия в 2 раза (дубляж)
4. сначала уменьшили в 2 раза, затем сжали на 50 %

Задание 9.5.
Напишите на Python функцию:

def after_chain(size: float, ops: list[tuple[str, float]]) -> float:
    """
    size — исходный объём,
    ops — список операций:
      ("bpp_reduce", factor) — глубину цвета уменьшить в factor,
      ("compress", remain) — после сжатия остаётся remain доля (0–1),
      ("duplicate", times) — увеличить объём в times раз.
    Возвращает итоговый объём.
    """

9.1.
— Без потерь: данные восстанавливаются полностью.  
— С потерями: часть информации отбрасывается без возврата.  
— k % сжатия → остаётся (100−k)%:  
  объём_new = объём_old × (100−k)/100.

9.2.
RLE("12300000000000555") = "11 12 13 90 20 35" → "111213902035"  
Длина = 12 символов → 12×4 бит = 48 бит = 6 байт.

9.3.
1/1.5 × 0.6 = 0.4 → объём стал в 0.4 раза (40%) от исходного.

9.4.
1) 0.70  
2) 0.25  
3) 2.00  
4) (1/2)×0.5 = 0.25

9.5.
При вызове:
    after_chain(100, [("bpp_reduce",1.5),("compress",0.6)])
функция вернёт 40.0

# 9.2 — RLE для цифр
def rle_encode_digits(s: str) -> str:
    res = []
    i = 0
    while i < len(s):
        j = i + 1
        while j < len(s) and s[j] == s[i] and (j - i) < 9: j += 1 res.append(str(j - i)) res.append(s[i]) i = j return "".join(res) s = "12300000000000555" enc = rle_encode_digits(s) # "111213902035" bits = len(enc) * 4 bytes_len = bits // 8 print(enc, bytes_len) # → "111213902035", 6 # 9.3 и 9.4 — проверки def after_chain(size: float, ops: list[tuple[str, float]]) -> float:
    for op, v in ops:
        if op == "bpp_reduce":
            size /= v
        elif op == "compress":
            size *= v
        elif op == "duplicate":
            size *= v
    return size

print(after_chain(1.0, [("bpp_reduce",1.5),("compress",0.6)]))  # 0.4
print(after_chain(1.0, [("compress",0.7)]))                    # 0.7
print(after_chain(1.0, [("compress",0.25)]))                   # 0.25
print(after_chain(1.0, [("duplicate",2)]))                     # 2.0
print(after_chain(1.0, [("bpp_reduce",2),("compress",0.5)]))   # 0.25

10. Базы, пакеты, идентификаторы

В реальных СУБД и бинарных протоколах данные хранятся компактно, но при этом должны быстро читаться и записываться. Выравнивание (alignment) и «пакетирование» (packetizing) помогают процессору и диску работать эффективнее.

10.1 Поля, выравнивание и padding

В записи (row) могут быть поля разного размера: целые, булевы флаги, строки фиксированной длины. Чтобы CPU читал их быстрее, обычно:

• Каждое поле занимает минимально достаточное число бит по диапазону.
• Поля выравниваются на границы байта/слова: между ними могут вставляться padding — пустые биты/байты.
• Вся запись часто выравнивается на границу, кратную 4 или 8 байтам («структурное выравнивание»).
• Записи могут объединяться в пакеты фиксированного размера (например, 4 KiB страницы или N записей).

Что такое padding и alignment?

• Padding — дополнительные нулевые байты между полями, чтобы следующее поле начиналось на нужной границе.
• Alignment — требование: адрес поля должен быть кратен его размеру (например, 4-байтовый int на адрес, кратный 4).

 Offsets →       0    1     2    3    4  5  6  7   8  9  10      11
                ┌───────┬────────────┬────────────┬─────────┬────────────┐
                │"int16"│"padding2B" │"int32"     │"char[3]"│"padding1B" │
                └───────┴────────────┴────────────┴─────────┴────────────┘

Пример: структура C++

struct Record {
    int16_t  a;   // 2 байта, выравнивание 2
    // padding 2 байта
    int32_t  b;   // 4 байта, выравнивание 4
    char     c[3]; // 3 байта
    // padding 1 байт, чтобы размер Record был кратен 4
}; // sizeof(Record) == 12 байт

10.2 Примеры вычислений

10.2.1 Простой:

Букмекерская контора завела для хранения результатов скачек лошадей базу данных. В базе данных решено хранить следующую информацию — номер лошади и ее кличку. Номер лошади находится в диапазоне от 1 до 1000 и кодируется с помощью одинакового и минимально возможного количества байт. Сколько байт нужно для кодирования 1000 номеров?

10.2.2 Средний

Сотрудникам компании выдают электронную карту, на которой записаны их личный код, номер подразделения (целое число от 1 до 1200) и дополнительная информация. Личный код содержит 17 символов и может включать латинские буквы из 26-⁠символьного латинского алфавита (заглавные и строчные буквы различаются), десятичные цифры и специальные знаки из набора @#$%^&*(). Для хранения кода используется посимвольное кодирование, все символы кодируются одинаковым минимально возможным количеством битов, для записи кода отводится минимально возможное целое число байтов. Номер подразделения кодируется отдельно и занимает минимально возможное целое число байтов. Известно, что на карте хранится всего 48 байтов данных. Сколько байтов занимает дополнительная информация?

• Один символ идентификатора: ⌈log₂(26*2+10+9)⌉ = 7 бит
• Полный идентификатор (код): ⌈(17*7)/8⌉ = 15 байт
• Номер подразделения 1…1200 → ⌈log₂1200⌉=11 бит → ⌈11/8⌉=2 байта
• Padding/другие поля → 48−(15+2)=31 байт

Ответ: 31 байт на дополнительные данные.

10.2.3 Сложный

В информационной системе хранится информация об объектах определённой структуры. Описание каждого объекта включает в себя идентификатор объекта, описание структуры объекта и дополнительную информацию.

Идентификатор объекта состоит из 7 заглавных латинских букв. Каждая буква идентификатора кодируется минимально возможным числом битов, а для хранения всего идентификатора отводится минимально возможное целое число байтов.

Структура объекта описывается как последовательность простых элементов.

Всего существует 1789 различных простых элементов. Каждый простой элемент кодируется одинаковым для всех элементов минимально возможным количеством битов. Для описания структуры объекта выделяется одинаковое для всех объектов минимальное количество байтов, достаточное для записи 70 простых элементов.

Для хранения дополнительной информации выделяется одинаковое для всех объектов целое число байтов.

Известно, что для хранения данных о 16 384 объектах потребовалось 2 Мбайт.

Сколько байтов выделено для хранения дополнительной информации об одном объекте? В ответе запишите целое число  — количество байт.

10.3 Мини-тест: выравнивание и пакеты

Контрольные вопросы:

• В чём разница между KB (10³) и KiB (2¹⁰)?
• Почему мы округляем вверх при выравнивании?

10.4 🔧 Функция для расчёта партии изделий

import math

def batch_storage(party_size, id_bits, counter_bits, extra_bytes,
                  align=1, packet_size=None):
    """
    Рассчитывает объём памяти:
    - party_size: число записей;
    - id_bits: бит для ID;
    - counter_bits: бит для счётчика;
    - extra_bytes: остальные данные в байтах;
    - align: выравнивание записи (в байтах, default=1);
    - packet_size: размер пакета (в байтах), optional.
    Возвращает словарь с итоговыми расчётами.
    """
    # поля в байтах, с padding
    id_b = math.ceil(id_bits/8)
    cnt_b = math.ceil(counter_bits/8)
    record = id_b + cnt_b + extra_bytes
    # выравнивание записи
    record_aligned = math.ceil(record/align)*align

    total = party_size * record_aligned

    # опционально пакеты
    if packet_size:
        packets = math.ceil(total/packet_size)
        total_aligned = packets * packet_size
    else:
        packets = None
        total_aligned = total

    return {
        'id_bytes': id_b,
        'counter_bytes': cnt_b,
        'record_raw': record,
        'record_aligned': record_aligned,
        'total_bytes': total,
        'packets': packets,
        'total_with_packets': total_aligned
    }

# Пример:
res = batch_storage(
    party_size=1000,
    id_bits=19*5,               # 19 букв латиницы
    counter_bits=math.ceil(math.log2(1000)),
    extra_bytes=40,
    align=16,                   # выравнивание записи на 16 B
    packet_size=1024            # пакеты по 1 KiB
)
print(res)

10.5 Дополнительные материалы

• Статья: «Memory Alignment in C/C++» (на английском)
• Видео-лекция: «How CPUs Access Memory Efficiently»
• Документация SQLite: PRAGMA page_size и выравнивание страниц

Задания. Блок 10. Базы, пакеты, идентификаторы

Задание 10.1.
Объясните, почему при хранении записи с полями разного типа часто требуется выравнивание до границы байта или K–байта. Что такое padding?

Задание 10.2.

• Простой: Нужно сохранить 1000 последовательных номеров (1…1000). Сколько бит занимает поле, если кодируем равномерно и храним в минимальном целочисленном числе байт?
• Средний: На карточке сотрудника отведено 48 байт. В ней хранятся: 17-символьный личный код (посимвенно, минимально), номер подразделения (1…1200), плюс дополнительная информация остатком. Сколько байт занимает дополнительная информация? (Задача C-15)
• Сложный: Для описания 16 384 объектов каждый отдал 2 Мбайт. Поля: идентификатор (7 букв латиницы), описание структуры (70 элементов из 1789, посимвенно), остальное — дополнительная информация. Сколько байт отведено на доп. информацию об одном объекте? (Задача C-16)

Задание 10.3.
Мини-тест «выравнивание»:

1. Вычислите ⌈13 бит / 8⌉ байт = ?
2. Вычислите ⌈100 байт / 1024⌉ Кбайт = ?
3. Вычислите ⌈17 символов×5 бит / 8⌉ байт = ?
4. Вычислите ⌈65 536 записей×3 байта / 1024⌉ Кбайт = ?
5. Вычислите ⌈246 символов×log₂(Σ) / 8⌉ байт, где Σ мощность алфавита = 2000.

Задание 10.4.
Напишите на Python шаблон-функцию для расчёта объёма партии изделий:

def batch_storage(party_code_len: int,
                  code_alphabet_size: int,
                  max_items: int,
                  extra_info_per_item: int) -> int:
    """
    party_code_len — длина кода партии (символов);
    code_alphabet_size — мощность алфавита кода;
    max_items — максимальное число изделий (номер поля бит.);
    extra_info_per_item — доп. информация в байтах.
    Возвращает максимальный объём в байтах для всей партии.
    """

10.1.
Padding — неиспользуемые биты/байты, вставляемые для выравнивания полей на границу (выравнивание ускоряет доступ и соответствует архитектуре).

10.2.
— Простой: 1000 → ⌈log₂(1000)⌉=10 бит → ⌈10/8⌉=2 байта.  
— Средний (C-15):  
  • Личные символы: 17×ceil(log₂(26+26+…+спец))=17×6=102 бит → 13 байт  
  • Подразделение 1…1200 → ⌈log₂(1200)⌉=11 бит → 2 байта  
  • Итого занято 13+2=15 байт → доп. = 48−15 = 33 байта.  
— Сложный (C-16):  
  • Идентификатор: 7×ceil(log₂(26))=7×5=35 бит  
  • Структура: 70×ceil(log₂(1789))=70×11=770 бит  
  • Всего бит = 805 → ⌈805/8⌉=101 байт  
  • Всего для 16 384 объектов: 2 097 152 байт / 16 384 = 128 байт/объект  
  • Доп. информация = 128−101 = 27 байт.

10.3.
1) ⌈13/8⌉=2  
2) ⌈100/1024⌉=1  
3) ⌈17×5/8⌉=⌈85/8⌉=11  
4) ⌈65 536×3/1024⌉=⌈196 608/1024⌉=⌈192⌉=192  
5) ⌈246×ceil(log₂2 000)/8⌉=⌈246×11/8⌉=⌈2706/8⌉=339 байт.

10.4.
Функция возвращает требуемый объём в байтах для заданных параметров.

from math import ceil, log2

# 10.2 — простой
bits = ceil(log2(1000))
print(ceil(bits/8))  # 2

# 10.2 — средний (C-15)
bits_code = 17 * ceil(log2(64+...))  # пример 6 бит/симв
bits_dep  = ceil(log2(1200))
occupied = ceil(bits_code/8) + ceil(bits_dep/8)
print(48 - occupied)  # 33

# 10.2 — сложный (C-16)
bits_id = 7 * ceil(log2(26))
bits_struct = 70 * ceil(log2(1789))
total_bits = bits_id + bits_struct
per_obj = 2_097_152 // 16_384
print(per_obj - ceil(total_bits/8))  # 27

# 10.3 — проверки
print(ceil(13/8))                     # 2
print(ceil(100/1024))                 # 1
print(ceil(17*5/8))                   # 11
print(ceil(65536*3/1024))             # 192
print(ceil(246*ceil(log2(2000))/8))   # 339

# 10.4 — шаблон
def batch_storage(party_code_len, code_alphabet_size, max_items, extra_info_per_item):
    bits_code = party_code_len * ceil(log2(code_alphabet_size))
    bits_num  = ceil(log2(max_items + 1))
    rec_bytes = ceil((bits_code + bits_num) / 8) + extra_info_per_item
    return rec_bytes * max_items

11. Типовые шаблоны решения

11.1 Шаблоны для задач раздела A (коды и условие Фано)

• Подбор длин по условию Крафта–Макмиллана
  Формула ∑ b^–lᵢ ≤ 1.
  Примеры:
  А-1. По каналу связи передаются шифрованные сообщения, содержащие строчные и прописные буквы латинского алфавита. Для передачи используется неравномерный двоичный код. Каким минимальным количеством бит можно закодировать слово AbraCadabra при условии, что для всех символов выполняется условие Фано?
  А-5. По каналу связи передаются сообщения, содержащие только семь букв: А, М, Н, Е, З, И, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для букв известны: А — 010, М — 000, Н — 100, Е — 101, З — 001, И — 011, Я — 1101. Как можно сократить код для буквы Я таким образом, чтобы суммарная длина всех кодовых слов осталась прежней, а также сохранилось выполнение условия Фано? При этом допускается изменять коды, соответствующие остальным буквам. В качестве ответа укажите количество возможных (более коротких) кодовых слов для буквы Я.
  А-6. Для кодирования некоторой последовательности, состоящей из букв C, G, I, R, A, E, S, T решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв S и A использовали кодовые слова 10 и 111 соответственно. Определите наименьшую возможную сумму длин всех восьми кодовых слов, учитывая, что кодовые слова оставшихся букв имеют разную длину.
• Сокращение существующего кода
  Генератор всех вариантов коротких префиксов и проверка префиксности.
  Примеры:
  A-3. Для кодирования некоторой последовательности, состоящей из букв Т, Ы, К, О, И решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв Т и О использовали кодовые слова 1111 и 1010 соответственно. Какое количество двоичных знаков требуется для кодирования слова ТЫКОТИК, если известно, что оно закодировано минимально возможным количеством двоичных знаков и при этом каждое кодовое слово содержит чётное количество единиц?
  A-5. По каналу связи передаются сообщения, содержащие только семь букв: А, М, Н, Е, З, И, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для букв известны: А — 010, М — 000, Н — 100, Е — 101, З — 001, И — 011, Я — 1101. Как можно сократить код для буквы Я таким образом, чтобы суммарная длина всех кодовых слов осталась прежней, а также сохранилось выполнение условия Фано? При этом допускается изменять коды, соответствующие остальным буквам. В качестве ответа укажите количество возможных (более коротких) кодовых слов для буквы Я.
• Оценка суммарной длины слова
  Частоты символов → нижняя граница по Шеннону ≈ ∑f · (–log₂ p).
  Примеры:
  A-7. По каналу связи передаются сообщения, содержащие все буквы русского алфавита. Для передачи используется двоичный код, удовлетворяющий условию Фано. Какое наименьшее количество двоичных знаков потребуется для кодирования слова КОРОМЫСЛО? В ответе укажите только число.
  A-13. Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: И  — 110, Н  — 011, Ф  — 00, О  — 1111, Р  — 11100, М  — 11101, А  — 1001, Т  — 101, К  — 1000. Сколько существует способов назначить для буквы Ю код, длина которого не превышает шести двоичных знаков?

11.2 Шаблоны для задач раздела B (мультимедиа)

• Изображения: изменение dpi / bpp / масштаб
  Формула W×H×bpp/8 + пересчёт пикселей по dpi.
  Примеры:
  B-1. Для экономии памяти скан полотна размером 96х54 дюймов и разрешением 600 ppi решили уменьшить. Для этого полотно уменьшили в размере до 64×36 дюймов, глубину цвета уменьшили в 1.5 раза и разрешение уменьшили вдвое. Сколько Кбайт сэкономили на хранении изображения, если известно, что размер исходного изображения составлял 27 Мбайт?
  B-4. В информационной системе хранятся изображения размером 2048 × 1536 пк. При кодировании используется алгоритм сжатия изображений, позволяющий уменьшить размер памяти для хранения одного изображения в среднем в 4 раза по сравнению с независимым кодированием каждого пикселя. Каждое изображение дополняется служебной информацией, которая занимает 128 Кбайт. Для хранения 32 изображений потребовалось 16 Мбайт. Сколько цветов использовано в палитре каждого изображения?
  B-14. Музыкальный фрагмент был оцифрован и записан в виде файла без использования сжатия данных. Получившийся файл был передан в город А по каналу связи за 15 секунд. Затем тот же музыкальный фрагмент был оцифрован повторно с разрешением в 2 раза выше и частотой дискретизации в 1,5 раза меньше, чем в первый раз. Сжатие данных не производилось. Полученный файл был передан в город Б; пропускная способность канала связи с городом Б в 2 раза выше, чем канала связи с городом А. Сколько секунд длилась передача файла в город Б? В ответе запишите только целое число, единицу измерения писать не нужно.
• Сжатие и экономия
  Последовательность операций: «масштаб» → «глубина» → «сжатие %».
  Примеры:
  B-3. Следы инопланетных цивилизаций предлагается искать на Луне, потому как следы там сохраняются десятки миллионов лет. Для этого требуется отсканировать в монохроме поверхность нашего спутника с разрешением 10 см на пиксель в 255 оттенках серого. Сколько Тбайт (10**12) необходимо для хранения обработанной карты в этом разрешении? Ответ округлить до целых. Средний радиус Луны 1737,1 км. Поверхность Луны принять за сферу. Число π не округлять!
  B-8. Вася смотрел смешные видео на Рутубе. 3 из них ему настолько понравились, что он решил поделиться ими с другом. Каждое из них представляет из себя видео разрешением 3840 x 2160 пикселей, а также цветовой палитрой из 220 цветов и частотой 60 кадров в секунду. Длительность каждого видео — 30 секунд. Звук к видео был записан в формате стерео, частотой дискретизации 48 кГц и глубиной кодирования 16 бит.
  После отправки видео сжимается до разрешения 1920×1080 пикселей, цветовая палитра содержит 216 цветов. Звук также становится хуже. Его новые параметры после отправки — стерео формат, 36 кГц, глубина кодирования — 8 бит. Сколько Гбайт сэкономит Вася при отправке видео другу?
• Видео без сжатия
  (кадр_size + header)×fps×t.
  Примеры:
  B-2. Алексей написал генератор серии картинок в разрешении 4к (3840 x 2160) на 16 млн цветов, которые сохраняются без сжатия на 1TБ SSD для дальнейшего сжатия в видеопоток 60 FPS (Гц). Известно, что память TLC SSD не переживет 1000 циклов полной перезаписи. Посчитайте суммарное время всех сгенерируемых фрагментов видео за ожидаемое время жизни SSD. Ответ дайте в часах. Округляйте в меньшую сторону. (1TБ у производителей неравен 1 Тебибайту, а равен 10**12 байт)
  B-10. Ваня снимал видео в разрешении 3840 x 2160 пикселей с цветовой палитрой в x цветов и частотой 60 кадров в секунду. Звуковая дорожка записывалась в стерео формате с частотой дискретизации 48 кГц и глубиной кодирования 16 бит. Видео длилось 1,5 минуты и заняло 54691875 Кбайт. Найдите чему равно максимальное количество цветов в палитре, используемой Ваней при съёмке этого видео.
  B-18. Токсичный информатик съездил в Калининград. Помимо фотографий Калининграда он привез из поездки также и видео. Снимая это видео, он хотел показать то насколько красив Калининград, поэтому снимал в формате Ultra HD (3840×2160 пикселей) с палитрой, содержащей 232 цветов. При попытке загрузить видео выяснилось, что оно превышает 4 Гбайта, и поэтому загрузить его целиком в Telegram нельзя. Так как делить видео на несколько частей не хотелось, токсичный информатик поступил иначе. Он поменял разрешение в видео на Full HD (1920×1080 пикселей) с палитрой, содержащей 216 = 65536 цветов, больше никаких технологий сжатия он не использовал. Звук в видео кодировался отдельно и было принято решение поменять заодно и его, так что в итоге размер преобразованного звука оказался в четыре раза меньше изначального. Во сколько раз размер преобразованного видео будет меньше оригинального, если известно, что общий размер преобразованных изображений вдвое больше размера изначальной аудиодорожки? Ответ округлите в меньшую сторону.
• Аудио без сжатия
  freq×bits×channels×t/8.
  Примеры:
  B-12. Музыкальный фрагмент был записан в формате стерео, оцифрован и сохранён в виде файла. Перед сохранением файл сжали, в результате чего его объём уменьшился на 40%. Затем тот же музыкальный фрагмент был записан повторно в формате моно и оцифрован с разрешением в 4 раза выше и частотой дискретизации в 16 раз выше, чем в первый раз. В результате сжатия нового файла его объём уменьшился на 60%. Во сколько объём второго файла больше первого? Ответ округлите до ближайшего целого числа.
  B-14. Музыкальный фрагмент был оцифрован и записан в виде файла без использования сжатия данных. Получившийся файл был передан в город А по каналу связи за 15 секунд. Затем тот же музыкальный фрагмент был оцифрован повторно с разрешением в 2 раза выше и частотой дискретизации в 1,5 раза меньше, чем в первый раз. Сжатие данных не производилось. Полученный файл был передан в город Б; пропускная способность канала связи с городом Б в 2 раза выше, чем канала связи с городом А. Сколько секунд длилась передача файла в город Б? В ответе запишите только целое число, единицу измерения писать не нужно.

11.3 Шаблоны для задач раздела C (базы и ID)

• Фиксированная строка + числовое поле
  Поле длиной L символов → L×⌈log₂ m⌉ бит; число → ⌈log₂ N⌉ бит; всё в байты.
  Примеры:
  C-3. Вася решил закодировать персональные данные всех 1347 учеников всей школы. Для каждого ученика был сформирован ID из нескольких полей: номер класса, буква (а,б,в,г,д), пол, день и месяц рождения, номер имени по таблице имен (всего 103), номер фамилии по таблице фамилий (всего 733). Сперва Вася для каждого поля выделил минимальное количество байт. Затем попробовал закодировать все поля непрерывной битовой строкой и для каждого ID выделил минимальное количество байт. Сколько байт сэкономил Вася во втором случае для кодирования всех учеников школы?
  C-5. В базе данных регистрационных данных о каждом пользователе хранятся следующие данные: дата рождения, номер паспорта и адрес проживания.Дата рождения состоит из дня (1-31), месяца (1-12) и года (1900-2500), при этом для хранения даты отводится битовая последовательность одинаковой минимальной длины для всех пользователей, которая представляет собой одно двоичное число. Номер паспорта представлен как строка из 12 цифр от 0 до 9, каждая из которых кодируется одинаковым и минимально возможным количеством бит. Известно, что для кодирования информации об одном пользователе выделяется целое, одинаковое для всех пользователей минимальное количество байт. Известно, что адрес проживания содержит символы из алфавита мощностью 32, при этом используется посимвольное кодирование, и каждый символ кодируется одинаковым и минимально возможным количеством бит.Известно, что для хранения данных о 1316 пользователях понадобилось 27 Кбайт памяти. Найдите максимальную длину строки, которая может быть адресом пользователя.C-15. Сотрудникам компании выдают электронную карту, на которой записаны их личный код, номер подразделения (целое число от 1 до 1200) и дополнительная информация. Личный код содержит 17 символов и может включать латинские буквы из 26-⁠символьного латинского алфавита (заглавные и строчные буквы различаются), десятичные цифры и специальные знаки из набора @#$%^&*(). Для хранения кода используется посимвольное кодирование, все символы кодируются одинаковым минимально возможным количеством битов, для записи кода отводится минимально возможное целое число байтов. Номер подразделения кодируется отдельно и занимает минимально возможное целое число байтов. Известно, что на карте хранится всего 48 байтов данных. Сколько байтов занимает дополнительная информация?
• Пакетирование серий измерений
  Серия из K значений → K×⌈log₂ M⌉ бит, округлить до байта/KiB.
  Примеры:
  C-12. Датчик считывает значения интенсивности поступающего света. Известно, что при считывании значение округляется до одного из 2000 возможных. Каждое считанное значение кодируется одинаковым минимально возможным количеством бит. Также известно, что значения считываются сериями по 50 измерений. Каждая такая серия сохраняется на жесткий диск, на котором занимает целое количество байт. Если последняя переданная серия меньше 50 значений, переданные в ней значения также сохраняются в файле с помощью минимального целого количества байт.
  За время своей работы датчик считал 12312 значений. Найдите минимальное целое количество килобайт, которого хватит для хранения считанных значений.
  В качестве ответа запишите одно число – найденное количество килобайт.
  C-24. Предприятие выпускает партии изделий. Каждая партия получает уникальный код, состоящий из 30 символов, среди которых могут быть заглавные латинские буквы и цифры. Все изделия в партии получают последовательные номера от 1 до общего числа изделий в партии. Запись о каждом изделии заносится в информационную систему. Запись содержит код изделия и некоторую дополнительную информацию. Код изделия состоит из кода партии и номера изделия в партии. Для записи кода партии используется посимвольное кодирование, каждый символ кодируется минимально возможным количеством битов. Номер изделия записывается как целое число, для записи каждого номера используется одинаковое минимально возможное количество битов. Для записи кода изделия в целом используется минимально возможное целое количество байтов. Для записи дополнительной информации о каждом изделии требуется 110 байт. Известно, что для хранения информации обо всех изделиях одной партии используется не более 45 Кбайт. Какое наибольшее количество изделий может быть в партии?
• Словарь + посимвольное кодирование
  Выбираем мощность алфавита по объёму памяти:
  total_bytes / count / record_size ≥ m → m_max.
  Примеры:
  C-1. На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 261 символов. Для его хранения отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 252 500 серийных номеров отведено более 31 Мбайт памяти. Определите минимально возможную мощность алфавита, из которого составляются серийные номера. В ответе запишите только число.
  C-9. При регистрации в компьютерной системе каждому файлу выдается идентификатор фиксированной длины из набора символов, включающего десятичные цифры, а также маленькие и большие латинские буквы. Каждый символ кодируется с помощью одинакового и минимального количества бит. А все биты символов записываются один за другим и округляются до целого количества байт. Сколько всего различных идентификаторов можно создать (максимум), если для хранения одной тысячи идентификаторов достаточно четыре килобайта.
  C-23. На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 246 символов. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 703 569 серийных номеров доступно не более 77 Мбайт памяти. Определите максимально возможную мощность алфавита, используемого для записи серийных номеров. В ответе запишите только целое число.

11.4 Обобщённый опрос: 15 вопросов

1. Как вычислить bpp для палитры из M цветов?
2. Формула Крафта–Макмиллана для двоичного кода?
3. Как пересчитать dpi → пиксели?
4. Размер WAV-файла: freq=48 kHz, 16 bit, stereo, t=10 s?
5. Сколько байт займёт запись числа до 1 000 000?
6. Что останется, если сжать на 30 %?
7. Диапазон signed 16-bit?
8. Как получить биты float32 через struct?
9. Сколько байт нужно для идентификатора из 19 латинских букв + номер 1…N?
10. Перевод RLE-сжатия цифр: “0001111” → …?
11. Как округлять до целого числа байт?
12. Кодовое слово «10» является ли префиксом «101»?
13. Какой метод считать size после цепочки операций?
14. Как подсчитать число единиц в IP-адресе через count?
15. Пример Python-функции для расчёта image_size?

11.5 🔧 Готовые Python-скрипты для самопроверки

# A-шаблон: проверка префиксности
def is_prefix_free(codes):
    return all(not c.startswith(o) for c in codes for o in codes if c!=o)

# B-шаблон: размер изображения
def image_size(w,h,colors):
    import math
    bpp = math.ceil(math.log2(colors))
    return w*h*bpp//8

# B-шаблон: аудио
def audio_size(freq, bits, ch, t):
    return freq*bits*ch*t//8

# B-шаблон: видео
def video_size(w,h,bpp,fps,sec,header=0):
    frame = w*h*bpp//8
    return (frame+header)*fps*sec

# C-шаблон: размер записи
import math
def record_size(fields):
    bits = sum(math.ceil(math.log2(f)) for f in fields)
    return math.ceil(bits/8)

# C-шаблон: размер партии изделий
def batch_storage(n, id_bits, counter_bits, extra):
    rec = math.ceil(id_bits/8) + math.ceil(counter_bits/8) + extra
    return n * rec

# Универсальный шаблон: цепочка преобразований
def after_chain(size, ops):
    res = size
    for op,val in ops:
        if op=='scale':      res /= val
        elif op=='compress': res *= (1-val/100)
    return res

Задания. Блок 11. Типовые шаблоны решения

Задание 11.1.
Перечислите и кратко опишите три основных A-шаблона для работы с неравномерными префиксными кодами:

• Подбор длин по неравенству Крафта–Макмиллана.
• Сокращение существующего префикс-кода без нарушения условия Фано.
• Оценка суммарной длины закодированного слова по частотам (Шеннон–Фано).

Приведите по одной примерной строке Python-кода или формуле для каждого шаблона.

Задание 11.2.
Перечислите и кратко объясните три основных B-шаблона для оценки мультимедийных объёмов:

• Пересчёт пикселей при изменении dpi и глубины цвета (bpp).
• Расчёт времени видео на основе кадр/сек и заголовков.
• Доля аудио/видео при смешанном потоке (например, сколько раз уменьшится общий объём).

Для каждого шаблона приведите по одной ключевой формуле или строке Python.

Задание 11.3.
Перечислите и кратко опишите три основных C-шаблона для расчёта объёмов баз и идентификаторов:

• Фиксированная строка + число → выравнивание до байта.
• Пакет измерений (RLE, блоки k значений) → округление в байты.
• Вычисление размера поля по мощности алфавита → суммирование.

Приведите по одной строке Python для каждого шаблона.

Задание 11.4.
Мини-тест из 5 вопросов (один для каждого класса задач A, B, C и два общих):

1. Как проверить, что заданный набор кодовых слов удовлетворяет неравенству Крафта? (шаблон A)
2. Как пересчитать объём RAW-BMP при изменении размера на 50 %? (шаблон B)
3. Как вычислить битовую длину поля «номер 1…N»? (шаблон C)
4. Как оценить суммарную длину текста по частотам символов? (A/C)
5. Как смоделировать цепочку операций «bpp_reduce» и «compress»? (B/C)

Запишите для каждого короткий ответ (формула или код).

Задание 11.5.
Соберите три небольших Python-скрипта для самопроверки:

1. Проверка неравенства Крафта: check_kraft(lengths: list[int]) → bool.
2. Вычисление объёма изображения: image_size(w,h,colors) → int.
3. Расчёт размера записи: record_size(fields: list[int]) → int.

Поместите их в один файл templates.py.

11.1.
— A1: lengths = [...] → sum(2**(-l) for l in lengths) <= 1  
— A2: сокращение: удалить последнюю «0» в каждом коде, если ни один не становится префиксом другого.  
— A3: L_total = sum(f_i * ceil(log₂(Total/f_i)))

11.2.
— B1: size = W·H·ceil(log₂(colors))/8  
— B2: video_bytes = (W·H·bpp/8)*fps*t + header_bytes  
— B3: new_size = old_size * audio_ratio + video_ratio

11.3.
— C1: bytes = ceil(bits_string/8)  
— C2: bytes = ceil((k * bits_value)/8)  
— C3: total = sum(ceil(log₂(m_i)) for m_i in alphabets); bytes=ceil(total/8)

11.4.
1) check_kraft: sum(2**(-l) for l in lengths) <=1  
2) new_pixels=old_pixels*0.5²  
3) bits_num=ceil(log₂(N+1))  
4) L_total as в 11.1.A3  
5) after_chain(size, ops)

11.5.
См. файл templates.py

# templates.py

from math import ceil, log2

def check_kraft(lengths: list[int]) -> bool:
    return sum(2**(-l) for l in lengths) <= 1 def image_size(w: int, h: int, colors: int) -> int:
    bpp = ceil(log2(colors))
    return w * h * bpp // 8

def record_size(fields: list[int]) -> int:
    bits = sum(ceil(log2(m)) for m in fields)
    return ceil(bits / 8)

Практикум по задачам: от простых к сложным

Практикум. Часть 1. 10 простых задач в одно действие

Задача A1.
Для префиксного двоичного кода заданы длины кодовых слов: {2, 3, 3, 3}. Проверьте, удовлетворяет ли набор неравенству Крафта–Макмиллана (∑ 2⁻ˡ ≤ 1).

Задача A2.
Дан префиксный двоичный код для букв {A,B,C}: A→0, B→10, C→11. Сократите код A, если возможно, не нарушая свойства префиксности. Если нельзя – укажите «нельзя».

Задача A3.
Сколько бит нужно, чтобы равномерно закодировать символ из алфавита мощности m=20?

Задача A4.
Для троичного Фано-кода заданы слова: A→0, B→10, C→11. Какова минимальная длина слова D, если D≠префикс ни одного и ни одно не префикс D?

Задача B1.
Сколько байт занимает raw-BMP 128×128 при глубине цвета 24 bpp?

Задача C1.
Число от 1 до 1000 посимвольно. Сколько бит потребуется на хранение одного числа равномерным кодом?

Задача C2.
Идентификатор состоит из 7 заглавных латинских букв. Сколько байт займёт его хранение, если каждую букву кодировать ⌈log₂26⌉ = 5 бит и затем выровнять до байта?

Практикум. Часть 2. 20 задач в несколько действий

Задача A5.
Дан частотный словарь символов: {‘A’:50, ‘B’:30, ‘C’:20}.
1) Вычислите по формуле Шеннона–Фано оценку минимальной суммарной длины (∑ f·⌈log₂(T/f)⌉).
2) Проверьте, удовлетворяет ли полученный набор длин неравенству Крафта–Макмиллана.

Задача A6.
Частично задан префикс-код для букв {A,B,C,D}: A→0, B→10.
1) Определите допустимые длины кодовых слов для C и D по Фано.
2) Приведите пример конкретных слов минимальной длины.

Задача A7.
Дан префикс-код для русского слова «КОРОНА»:
К→110, О→10, Р→1110, Н→1111, А→0.
Найдите суммарное число бит, которое потребуется, чтобы закодировать текст «КОРОНАКОРОНА».

Задача A8.
В троичном коде заданы слова: A→0, B→10, C→11, D→21.
1) Сколько символов нужно в слове E, чтобы оно не было префиксом и не имело префиксами остальные?
2) Перечислите все возможные E минимальной длины.

Задача A9.
Частоты десяти букв: fᵢ = [100,90,80,…,10] (шаг –10).
1) Подсчитайте оценку Шеннона–Фано для суммарной длины.
2) Оцените, сколько букв с длиной 1 бита (если возможно).

Задача A10.
Проверьте для набора слов {‘0’, ‘01’, ‘011’, ‘10’, ‘110’}:
1) является ли это префиксным кодом?
2) если нет – удалите минимальное число слов, чтобы получилось префиксное множество.

Задача B4.
32 изображения 2048×1536, палитра неизвестна, после сжатия общий размер 16 MB, служебная часть 128 KB/изображение.
1) Найдите исходный bpp.
2) Какое M (число цветов) соответствует этому bpp?

Задача B5.
По каналу 224 бит/с, сеанс 10 с передачи +2 с простоя, отправляют подряд raw-файлы 1600×1200, M=2000 цветов.
1) Сколько бит кодируется каждый пиксель?
2) Сколько целых изображений уместится за 100 с?

Задача B6.
20 изображений 1600×1200 передали за ≤10 с по каналу 223 бит/с.
1) Найдите максимально возможное количество цветов в палитре.
2) Сколько bpp это даёт?

Задача B7.
Аудио WAV: стерео, 48 кГц, 16 бит, длительность 30 с.
1) Вычислите объём в МB.
2) Если сжали в 4× – на сколько МB уменьшился?

Задача B8.
Видео Ultra HD 3840×2160, 60 fps, палитра 232, без сжатия, длина 90 с. Звук в оригинале 48 кГц/16 бит стерео, после обработки – 36 кГц/8 бит.
1) Найдите объём исходного звука.
2) На сколько раз уменьшится общий размер при передаче (картинка+звук)?

Задача B9.
Телефон сохраняет фото 3840×2160, 20 bit/pixel, потом мессенджер уменьшает до 1280×720 с неизвестным bpp, 120 штук сэкономили 2 322 000 KB.
Найдите bpp сжатых фото.

Задача B10.
Видео 3840×2160, x цветов, 60 fps, звук 48 кГц/16 бит стерео, длина 1.5 мин, файл 54 691 875 KB.
Определите x.

Задача C3.
В таблице поля: день (1–31), месяц (1–12), год (1900–2500), паспорт (12 цифр), адрес длины L символов из алфавита m=32.
Всего на запись отводится B байт.
1) Запишите формулу B(L).
2) При B=27 KB для N=1316 записей найдите максимальное L.

Задача C4.
Датчик выдал 12 312 значений (2000 уровней) сериями по 50, последние дополняются битами до байта.
Сколько KB займёт файл?

Задача C5.
RLE: число 12300000000000555 → «1230×11 555».
1) Опишите последовательность серий.
2) Сколько бит потребуется, если все цифры кодировать ⌈log₂10⌉=4 бит и упаковать в байты?

Задача C6.
Сообщения длиной 100 символов, равномерный код, алфавит: английские и русские буквы, цифры и 15 знаков.
1) Сколько символов всего?
2) Какой объём (байт) займёт текст?
3) При словаре: 1 B–№,2 B–код,1 B–длина, + 600 бит текста (неравномерный) – при каком n (в сотнях) второй метод выгоднее?

Задача C7.
ID из 7 эмодзи (U+1F000–U+1FFFF) и 10 трёхзначных чисел (0–999).
1) Определите число бит на эмодзи и число бит на число.
2) Сколько KB займут 256 записей?

Задача C8.
Для хранения 65 536 идентификаторов из цифр (10) + спец-алфавит (1234) потребовалось ≤2050 KB.
Найдите максимальную длину ID.

Задача C9.
1789 элементов по 70 штук описаны равномерным кодом, + 7-буквенный ID. Всего 2 MB на 16 384 объекта.
Сколько байт отведено на доп. информацию в одной записи?

Задача C10.
Партия изделий: код из 19 букв (латинские) + порядковый номер в партии. Код целиком выровнен до байта, доп. инфо 40 B.
Всего ≤20 KB на всю партию.
Найдите максимально возможное число изделий в партии.

Практикум. Часть 3. 25 задач повышенной сложности

Задача A11.
Дан словарь частот букв в тексте:
{‘A’:120, ‘B’:80, ‘C’:60, ‘D’:40, ‘E’:20}.
Постройте двоичный префикс-код с минимумом средней длины (алгоритм Хаффмана) и вычислите среднюю длину кодового слова.

Задача A12.
Для алфавита из 8 символов требуется префикс-код.
1) Какое минимальное и максимальное число символов может быть длиной 1?
2) Приведите пример распределения длин, удовлетворяющего неравенству Крафта.

Задача A13.
Дан минимальный двоичный код для русских букв (33 символа).
Сколько бит минимум потребуется, чтобы закодировать слово длиной 100 символов, если частоты равномерные?

Задача A14.
Даны двоичные слова: {‘0’,’10’,’110’,’1110’,’1111’}.
1) Является ли это префикс-кодом?
2) Модифицируйте один элемент, чтобы нарушить префиксное свойство, и объясните, почему.

Задача A15.
Для троичного кода конструктивно найдите все решения задачи:
буквы {A,B,C,D,E}, длины {1,2,2,3,3}, удовлетворяющие условию Фано.

Задача A16.
Частоты символов в тексте заданы списком fᵢ. Напишите формулу оценки Шеннона–Фано и проиллюстрируйте её для f=[500,300,200,100].

Задача A17.
Дан двоичный код: A→00, B→01, C→10, D→110, E→111.
1) Проверить Крафта: ∑2⁻ˡ ≤1?
2) Если неравенство строго, сколько свободного «кода» остаётся?

Задача A18.
Для букв {A,B,C,D} задан двоичный код A→0, B→10, C→110.
Найдите все возможные коды для D минимальной длины, чтобы осталось префиксным.

Задача A19.
Определите для алфавита мощности m=50, кодовой системе b=3 (троичный) минимальную ⌈log_b m⌉. Объясните отличие от бинарной системы.

Задача B11.
Исходное изображение 96″×54″ при 600 ppi, 24 bpp, весит 27 MB.
Уменьшили до 64″×36″, 12 bpp, 300 ppi.
Сколько сэкономили KБ? Проверьте оба варианта ppi.

Задача B12.
Сгенерировали 4K-видео (3840×2160, 16 M цветов) 60 fps на SSD 10¹² B.
SSD живёт 1000 циклов.
Сколько часов видео запишется до износа?

Задача B13.
Скан лунной поверхности (радиус 1737,1 км) в 255 оттенках с 10 cm/pixel.
Сколько TB потребуется? Округлите вверх.

Задача B14.
Сжатие BMP 2048×1536 без потерь в 4×, служебные 128 KB/фото → 32 фото заняли 16 MB.
1) Найдите исходный вес без служебного.
2) Определите палитру M.

Задача B15.
Канал 224 bit/s, сеансы 10+2 s, raw-изображения 1600×1200, M=2000.
Сколько полных изображений отправят за 100 s? С учётом перезапуска.

Задача B16.
За 40 s с тем же каналом B15 передаётся raw-поток.
Сколько успеют передать, если M изменится так, что bpp увеличится на 1 бит?

Задача B17.
WAV стерео 48 kHz×16 bit×30 s = V₁.
Если глубину удвоить и частоту уменьшить в 2 ×, найти V₂ и отношение V₂/V₁.

Задача B18.
Видео UltraHD+звук (B8).
1) Найдите общий объём исходный V₀.
2) После снижения до FullHD+новый звук V₁.
3) Во сколько раз V₁<V₀?

Задача B19.
По каналу 223 bit/s за ≤10 s приняли 20 картинок 1600×1200, M неизвестно.
Определите M, если передавалось без потерь и без повторений.

Задача B20.
Телефон 3840×2160, 20 bpp → мессенджер 1280×720, X bpp, 120 шт сэкономили 2 322 000 KB.
Определите X (целый).

Задача C11.
ID из 11 цифр + 4 hex‐символов (0–9,A–F).
1) Сколько байт займёт строка?
2) Если после каждых 8 байт вставлять выравнивание до 16 байт, как изменится?

Задача C12.
Дата (1–31), месяц, год(0…2³²−1), имя по 103, фамилия по N.
Вся база 1279 записей уместилась в 10 KB.
Найдите максимальное N.

Задача C13.
1347 записей, те же поля, имя=103, фамилия=733.
Сколько KB сэкономил Вася, перейдя к битовой строке?

Задача C14.
8 млрд записей: широта ±180°(сек), долгота ±90°(сек), timestamp (сек с ХХ в.), имя-ID L символов.
Всё заняло 240 GB.
Сколько байт осталось на имя?

Задача C15.
Пароль из 7 эмодзи (U+1F000–U+1FFFF) + 10 трехзначных чисел.
256 записей заняли X KB.
1) Найдите X.
2) Если увеличили длину эмодзи‐ID до 8, что станет с X?

Задача C16.
65 536 ID из цифр+1234 спецсимв за ≤2050 KB.
Найдите максимальную длину каждого ID.

Задача C17.
Переписали 32768 ID длины 163 симв в новый алфавит K.
Файл стал 3264 KB.
Найдите минимальное |K|.

Задача C18.
Пакет из 8192 серий по 50 значений (2000 уровней), записанных в байты.
Найдите объём в KB.

Задача C19.
RLE-сжатие числа 123000…555 (11 нулей).
1) Опишите код RLE.
2) Сколько байт займёт после 4-бит кодирования?

Задача C20.
Система отправила четыре 35-симв и пять 27-симв сообщений, алфавит 62 симв, + заголовок H байт.
Всего >320 B.
Найдите минимальный H.

Практикум. Часть 4. 5 задач олимпиадного уровня

Задача 1 (B-профиль).
Съёмка UltraHD‐видео (3840×2160, 10-bit color) идёт 24 fps.
Запись идёт на SSD с ресурсом 500 TB записи.
Через аппаратный компрессор каждый кадр сжимается в JPEG без потерь в среднем в 3 раза, но раз в 1000 кадров компрессор сбоит и пишет raw.
1) Сколько часов видео можно снять?
2) Какова дискретизация минимального размера буфера для 1 секунда событий (в байтах), чтобы не потерять ни кадра при пиковых сбоях?

Задача 2 (C-профиль).
В огромной БД 10⁹ записей: каждая запись – ID из K символов (алфавит мощности M) + числовое поле до N (целое).
Полное посимвольное кодирование дало 120 GB. Перевод в битовую строку позволил уместить всё в 95 GB.
Известно, что M и N – целые степени двойки. Найдите K и N.

13. Итоговый чек-лист с примерами

Заключение и дальнейшие рекомендации

Мы разобрали ключевые приёмы решения задач на кодирование, мультимедиа и базы данных. Чтобы закрепить материал и развиваться дальше, советуем:

• Практиковаться регулярно: решайте по одной–две задачи из каждого раздела каждый день.
• Писать небольшие скрипты на Python для автоматизации расчётов (ipaddress, struct, встроенные битовые операции).
• Изучить официальную документацию:
  • Модуль struct и codecs в Python.
  • Стандарт IEEE-754 для работы с float.
• Создать собственные чек-листы и шаблоны кода, постепенно расширяя их под новые задачи.
• Обсуждать решения в сообществе: форумы, чаты, профильные группы — это помогает увидеть альтернативные подходы.

Уверенный шаг за шагом — и даже самые сложные темы станут понятными. Удачи в учёбе и решении новых задач!