Задание 11: вычисление количества информации

Считаем, сколько бит нужно на символ и сколько памяти займёт сообщение, через мощность алфавита и логарифм.

Мощность алфавита N — число различных символов. Минимальная длина кода одного символа в битах: i = ⌈log₂ N⌉ (округление вверх).

Что проверяет задание 11

Задание 11 — базовый уровень, 1 балл. Дано множество объектов, которые надо закодировать (символы, пароли, номера, идентификаторы), известны мощность алфавита и/или длина. Нужно вычислить количество информации: сколько бит на символ, сколько на всё сообщение, сколько памяти займёт хранение нескольких таких объектов. Часто требуется округление длины кода до целого числа бит или байт.

Теория: ключевые формулы

Главная тонкость — округление вверх. Если N = 33 (русский алфавит), то log₂ 33 ≈ 5,04, но дробных бит не бывает, поэтому берём 6 бит на символ. Иногда требуют выравнивание на целое число байт — тогда округляют до ближайшего сверху кратного 8.

Метод решения

1. Определите мощность алфавита N (сколько разных символов используется).
2. Найдите длину кода одного символа: i = ⌈log₂ N⌉.
3. Если просят «в целых байтах на символ» — округлите i вверх до кратного 8.
4. Умножьте на длину сообщения и на количество сообщений, если нужно.

Разбор примера

Пароль состоит из 10 символов. Допустимы 26 латинских букв (один регистр) и 10 цифр — всего N = 36 символов. Каждый символ кодируется минимальным целым числом бит, одинаковым для всех. Сколько байт нужно на хранение одного пароля, если число бит на пароль округляют вверх до целого числа байт? Сколько на 50 паролей?

Решаем по шагам: log₂ 36 ≈ 5,17 → i = 6 бит на символ. Пароль: 10·6 = 60 бит. В байтах: ⌈60/8⌉ = 8 байт. На 50 паролей: 50·8 = 400 байт.

Решение на Python

import math

# Мощность алфавита: 26 латинских букв + 10 цифр
N = 36
bits_per_symbol = math.ceil(math.log2(N))      # округление ВВЕРХ
print("Бит на символ:", bits_per_symbol)

length = 10                                     # длина пароля
total_bits = length * bits_per_symbol
print("Бит на пароль:", total_bits)

bytes_per_password = math.ceil(total_bits / 8)  # выравнивание на целые байты
print("Байт на пароль:", bytes_per_password)

count = 50
print("Память на 50 паролей (байт):", count * bytes_per_password)

Вывод:

Бит на символ: 6
Бит на пароль: 60
Байт на пароль: 8
Память на 50 паролей (байт): 400

Обратная задача: подобрать длину или мощность

Иногда дано количество объектов и спрашивают минимальную длину кода. Например: закодировать 1000 различных идентификаторов двоичным кодом фиксированной длины — сколько бит минимум? Нужно наименьшее i, при котором 2ⁱ ≥ 1000.

import math

objects = 1000
i = math.ceil(math.log2(objects))   # минимальная длина кода в битах
print("Минимальная длина кода:", i, "бит")
print("Различимых кодов:", 2 ** i)  # проверяем, что хватает

Вывод:

Минимальная длина кода: 10 бит
Различимых кодов: 1024

2¹⁰ = 1024 ≥ 1000 — хватает; 2⁹ = 512 — мало. Поэтому ровно 10 бит.

Объём текста и единицы хранения

Иногда задание просит объём целого текста в килобайтах: дано число символов и кодировка. Помните соотношения: 1 Кбайт = 1024 байт, 1 Мбайт = 1024 Кбайт. В кодировке КОИ-8 один символ — 1 байт (8 бит), в Unicode UTF-32 — 4 байта, в распространённой двухбайтовой кодировке — 2 байта на символ.

import math

chars = 4096           # символов в тексте
bytes_per_char = 2     # двухбайтовая кодировка
total_bytes = chars * bytes_per_char

print("Объём текста (байт):", total_bytes)
print("Объём текста (Кбайт):", total_bytes / 1024)

# Сколько таких текстов поместится на носитель 1 Мбайт
disk_bytes = 1 * 1024 * 1024
print("Текстов на 1 Мбайт:", disk_bytes // total_bytes)

Вывод:

Объём текста (байт): 8192
Объём текста (Кбайт): 8.0
Текстов на 1 Мбайт: 128

4096 символов по 2 байта — это ровно 8 Кбайт; на мегабайт (1024 Кбайт) поместится 128 таких текстов. Здесь нет логарифма: кодировка прямо задаёт число байт на символ, остаётся аккуратно перевести единицы по степеням двойки.

Типичные ошибки

• Округляют вниз. log₂ 33 ≈ 5,04 — это НЕ 5 бит, а 6: 2⁵ = 32 < 33. Всегда округляйте длину кода вверх.
• Путают бит и байт. 1 байт = 8 бит; следите за единицами в вопросе.
• Делят на 1000 вместо 1024. 1 Кбайт = 1024 байт, 1 Мбайт = 1024 Кбайт — степени двойки, не десятки.
• Забывают про выравнивание на байты, когда оно требуется в условии (или, наоборот, выравнивают, когда не просят).
• Неверно считают мощность алфавита. «Буквы и цифры» — это 26+10 или 33+10, в зависимости от алфавита; «два регистра» удваивают буквы.

Итог

• Бит на символ: i = ⌈log₂ N⌉, всегда округляем ВВЕРХ.
• Объём сообщения: I = L · i; при необходимости выравниваем на целые байты.
• Обратная задача (минимальная длина под K объектов): наименьшее i с 2ⁱ ≥ K, то есть ⌈log₂ K⌉.