Информационный объём сообщения

В задании 11 считают, сколько памяти занимают пароли, номера и другие сведения, — или, наоборот, по объёму памяти находят длину, алфавит или размер части. Вот задача, которую мы будем решать всю тему:

«Каждому пользователю компьютерной системы выдаётся пароль из 15 символов. Пароль может содержать десятичные цифры и латинские буквы, заглавные и строчные. Для каждого пароля отведено одинаковое и минимально возможное целое число байт, используется посимвольное кодирование, все символы кодируются одинаковым и минимально возможным количеством бит. Кроме пароля, для каждого пользователя хранятся дополнительные сведения, для которых отведено одинаковое целое число байт. Для хранения сведений о 40 пользователях потребовалось 1200 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе?»

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

Тема состоит из шести подтем — у каждой своя страница. Идём по ним по порядку:

1. Пароль в байтах — ты сейчас здесь.
2. Дополнительные сведения — ответ задачи темы: 18.
3. Наибольшее значение: «не более» — наибольшие длина и алфавит, когда памяти не больше заданной.
4. Наименьшее значение: «более» и «не менее» — наименьшие длина и алфавит.
5. Составной код — пароль вместе с номером и другие коды из частей.
6. Служебные данные, зависящие от размера — дополнительный урок для редких задач.

Почти везде задачу можно решить и вручную, и программой — выбирай вкладку «Вручную» или «Python». На экзамене подойдёт любой способ, а второй пригодится для проверки.

Из скольких разных символов составляют пароль задачи темы?

Мощность алфавита N — сколько разных символов разрешено использовать. Наборы символов складываются. Цифр 10, заглавных латинских букв 26, строчных ещё 26: N = 10 + 26 + 26 = 62. Каждый символ пароля — один из этих 62.

Длина пароля K = 15 — другая величина: это число позиций в пароле. Пароль aaaaaaaaaaaaaaa тоже имеет длину 15, и алфавит у него по-прежнему 62 символа. Выбери набор, чтобы увидеть его мощность:

цифры

десятичные цифры от 0 до 910

заглавные

заглавные латинские буквы26

заглавные и цифры

заглавные латинские буквы и десятичные цифры26 + 10 = 36

задача темы

цифры и латинские буквы обоих регистров10 + 26 + 26 = 62

16-ричные цифры

цифры шестнадцатеричной системы16: от 0 до 9 и от A до F

цифры и 2000 знаков

десятичные цифры и специальный алфавит из 2000 знаков10 + 2000 = 2010

Сколько битов нужно на один символ из 62?

Число битов на символ i — наименьшее, при котором 2ⁱ ≥ N: i битов дают 2ⁱ разных кодов, и их должно хватить на все символы. Это правило подробно разобрано в теме 7. «Одинаковое и минимально возможное количество бит» в условии означает именно его.

def bits(n):    i = 0    while 2 ** i < n:        i += 1    return i  print(bits(62), bits(64), bits(65))

Число битов меняется только при переходе через степень двойки: и 33, и 62, и 64 символа — по 6 битов, а 65 — уже 7.

Сколько байт отведено на один пароль?

Код пароля — K · i бит. Целое число байт получают делением на 8 с округлением вверх. 15 символов по 6 бит — 90 бит. 90 / 8 = 11,25: одиннадцати байт мало (88 бит), поэтому пароль занимает 12 байт.

from math import ceil  def bits(n):    i = 0    while 2 ** i < n:        i += 1    return i  i = bits(10 + 26 + 26)password = ceil(15 * i / 8)print(i, 15 * i, password)

Округляют только вверх, даже если дробная часть мала: 11,25 байта — это 12. Если же биты делятся на 8 нацело, ничего не прибавляют: пароль из 16 символов — 96 бит, ровно 12 байт.

Сколько байт займут пароли 40 пользователей?

Сначала округляют один пароль — ему выделены целые байты, — потом умножают на число паролей. 40 · 12 = 480 байт. Расчёт 40 · 90 / 8 = 450 байт неверен: он складывает пустые хвосты паролей в общие байты, а у каждого пароля байты свои.

С 2021 года числа в задачах крупные, а ответ просят в Кбайт или Мбайт: 1 Кбайт = 1024 байта, 1 Мбайт = 1024 Кбайт. Пусть идентификатор — 180 символов из 10 цифр и 2000 специальных знаков, а хранить нужно 50 000 идентификаторов. Сколько Кбайт потребуется?

from math import ceilone = ceil(180 * bits(10 + 2000) / 8)total = 50000 * oneprint(one, total, total / 1024)

Как округлять ответ, решает вопрос: «сколько Кбайт потребуется» — вверх, иначе данные не поместятся; «запиши целую часть» — просто отбрось дробь.

• Алфавит Nчисло разных символов; наборы складываются
• Длина Kчисло позиций в пароле, не алфавит
• Биты iнаименьшее i, при котором 2ⁱ ≥ N
• ПарольK · i бит, делить на 8 и округлить вверх
• n паролейn · байты одного пароля
• Pythonceil(K * bits(N) / 8)