ЕГЭ по информатике · задание 11

Количество информации: номера и пароли

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

Формулы

  • Алфавит из k символов → i бит на символ, где 2i ≥ k (наименьшее такое i).
  • Строка из L символов → L·i бит → ⌈L·i / 8⌉ байт, если запись занимает целое число байт.
  • N записей → N·(байт на запись).

Единицы

  • 1 Кбайт = 210 байт, 1 Мбайт = 220 байт, 1 Гбайт = 230 байт.
  • Округление: байты на запись — вверх, допустимая длина — вниз.

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

  • Сначала умножить на N, а потом округлять до байт — округлять нужно каждую запись.
  • Взять i бит при k = 2i + 1 — нужно на один бит больше.
  • Перепутать «минимальную мощность алфавита» и «число бит».

Разобранные варианты

Сначала посчитай сам, потом открой разбор. В разборе — вычисления по шагам и программа.

Вариант 1

минимальная мощность алфавита

На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 1907 символов. В базе данных каждый серийный номер занимает одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным целым числом бит. Известно, что для хранения 3 572 608 серийных номеров требуется не менее 6 Гбайт памяти. Определите минимально возможную мощность алфавита, используемого для записи серийных номеров. В ответе запишите только целое число.

Разбор

Шаг 1. Сколько байт как минимум на один номер. 6 Гбайт = 6 442 450 944 байт. На один номер приходится не меньше 6 442 450 944 / 3 572 608 ≈ 1803.29 байт, а так как номер занимает целое число байт — не меньше 1804 байт.

Шаг 2. Бит на символ. Если на символ отвести i бит, номер займёт ⌈1907·i / 8⌉ байт. При i = 7: ⌈13349 / 8⌉ = 1669 байт — мало; при i = 8: ⌈15256 / 8⌉ = 1907 байт — достаточно. Значит, на символ нужно не меньше 8 бит.

Шаг 3. Мощность алфавита. 8 бит на символ используется, когда в алфавите больше 27 = 128 символов. Минимальная мощность — 128 + 1 = 129.

Ответ: 129

Решение на Python.

from math import ceil, log2

L, N, need = 1907, 3572608, 6 * 2 ** 30   # символов, номеров, байт
for k in range(2, 10000):            # мощность алфавита
    i = ceil(log2(k))                # бит на символ
    size = ceil(L * i / 8)           # байт на номер
    if N * size >= need:
        print(k)
        break

Вариант 2

объём памяти для N записей

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 12 символов; в пароле используются только 26 строчных латинских букв. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего отведено 8 байт на одного пользователя. Определите объём памяти (в байт), необходимый для хранения сведений о 500 пользователях. В ответе запишите только целое число — количество байт.

Разбор

Шаг 1. Алфавит — 26 символов, нужно 5 бит на символ (25 = 32 ≥ 26).

Шаг 2. Пароль: 12·5 = 60 бит → ⌈60 / 8⌉ = 8 байт.

Шаг 3. На пользователя: 8 + 8 = 16 байт; на 500 пользователей: 500·16 = 8000 байт.

Ответ: 8000

Решение на Python.

from math import ceil, log2

i = ceil(log2(26))             # бит на символ
password = ceil(12 * i / 8)        # байт на пароль
total = 500 * (password + 8)
print(total)

Вариант 3

дополнительные сведения

Каждый сотрудник предприятия получает электронную карту, на которой записаны личный код сотрудника, код подразделения и некоторая дополнительная информация. Личный код состоит из 15 символов, каждый из которых может быть одним из 250 допустимых символов. Для записи кода на карте отведено минимально возможное целое число байт, при этом используют посимвольное кодирование, все символы кодируют одинаковым минимально возможным количеством бит. Код подразделения и дополнительная информация вместе занимают целое число байт, одинаковое для всех сотрудников. Для хранения данных о 128 сотрудниках потребовалось 6016 байт. Сколько байт выделено для хранения кода подразделения и дополнительной информации об одном сотруднике? В ответе запишите только целое число — количество байт.

Разбор

Шаг 1. 250 символов → 8 бит на символ; код: 15·8 = 120 бит → 15 байт.

Шаг 2. На одного сотрудника: 6016 байт / 128 = 6016 / 128 = 47 байт.

Шаг 3. Дополнительная информация: 47 − 15 = 32 байт.

Ответ: 32

Решение на Python.

from math import ceil, log2

code = ceil(15 * ceil(log2(250)) / 8)   # байт на личный код
per = 6016 * 1 // 128            # байт на сотрудника
print(per - code)

Вариант 4

наибольшая длина номера

В автоматизированной системе каждой посылке присваивают трек-номер одинаковой длины, составленный из 33 различных символов. Каждый номер хранится в памяти как минимально возможное целое число байт, при этом используется посимвольное кодирование и все символы кодируются одинаковым минимально возможным количеством бит. Для хранения 100 000 трек-номеров отведено 625 Кбайт памяти. Какова наибольшая возможная длина трек-номера? В ответе запишите только целое число.

Разбор

Шаг 1. 625 Кбайт = 640 000 байт; на один номер — не больше ⌊640 000 / 100 000⌋ = 6 байт = 48 бит.

Шаг 2. 33 символов → 6 бит на символ. Длина не больше ⌊48 / 6⌋ = 8 символов.

Проверка: 8 символов занимают ⌈48 / 8⌉ = 6 байт ≤ 6, а 9 — уже 7 байт.

Ответ: 8

Решение на Python.

from math import ceil, log2

i = ceil(log2(33))
cap = 625 * 1024                  # байт памяти
L = 1
while 100000 * ceil((L + 1) * i / 8) <= cap:
    L += 1
print(L)

Вариант 5

автомобильные номера

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

Разбор

Шаг 1. Алфавит: 30 букв + 10 цифр = 40 символов → 6 бит на символ.

Шаг 2. Номер: 8·6 = 48 бит → 6 байт.

Шаг 3. 256·6 = 1536 байт.

Ответ: 1536

Решение на Python.

from math import ceil, log2

i = ceil(log2(30 + 10))
print(256 * ceil(8 * i / 8))

Вариант 6

минимальная мощность алфавита

На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 1830 символов. В базе данных каждый серийный номер занимает одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным целым числом бит. Известно, что для хранения 1 284 191 серийных номеров требуется не менее 1681 Мбайт памяти. Определите минимально возможную мощность алфавита, используемого для записи серийных номеров. В ответе запишите только целое число.

Разбор

Шаг 1. Сколько байт как минимум на один номер. 1681 Мбайт = 1 762 656 256 байт. На один номер приходится не меньше 1 762 656 256 / 1 284 191 ≈ 1372.58 байт, а так как номер занимает целое число байт — не меньше 1373 байт.

Шаг 2. Бит на символ. Если на символ отвести i бит, номер займёт ⌈1830·i / 8⌉ байт. При i = 5: ⌈9150 / 8⌉ = 1144 байт — мало; при i = 6: ⌈10980 / 8⌉ = 1373 байт — достаточно. Значит, на символ нужно не меньше 6 бит.

Шаг 3. Мощность алфавита. 6 бит на символ используется, когда в алфавите больше 25 = 32 символов. Минимальная мощность — 32 + 1 = 33.

Ответ: 33

Решение на Python.

from math import ceil, log2

L, N, need = 1830, 1284191, 1681 * 2 ** 20   # символов, номеров, байт
for k in range(2, 10000):            # мощность алфавита
    i = ceil(log2(k))                # бит на символ
    size = ceil(L * i / 8)           # байт на номер
    if N * size >= need:
        print(k)
        break

Вариант 7

объём памяти для N записей

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 38 символов; в пароле используются символы из 12-символьного набора. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего отведено 54 байт на одного пользователя. Определите объём памяти (в байт), необходимый для хранения сведений о 100 пользователях. В ответе запишите только целое число — количество байт.

Разбор

Шаг 1. Алфавит — 12 символов, нужно 4 бит на символ (24 = 16 ≥ 12).

Шаг 2. Пароль: 38·4 = 152 бит → ⌈152 / 8⌉ = 19 байт.

Шаг 3. На пользователя: 19 + 54 = 73 байт; на 100 пользователей: 100·73 = 7300 байт.

Ответ: 7300

Решение на Python.

from math import ceil, log2

i = ceil(log2(12))             # бит на символ
password = ceil(38 * i / 8)        # байт на пароль
total = 100 * (password + 54)
print(total)

Вариант 8

наибольшая длина номера

В автоматизированной системе каждой посылке присваивают трек-номер одинаковой длины, составленный из 20 различных символов. Каждый номер хранится в памяти как минимально возможное целое число байт, при этом используется посимвольное кодирование и все символы кодируются одинаковым минимально возможным количеством бит. Для хранения 100 000 трек-номеров отведено 393 Кбайт памяти. Какова наибольшая возможная длина трек-номера? В ответе запишите только целое число.

Разбор

Шаг 1. 393 Кбайт = 402 432 байт; на один номер — не больше ⌊402 432 / 100 000⌋ = 4 байт = 32 бит.

Шаг 2. 20 символов → 5 бит на символ. Длина не больше ⌊32 / 5⌋ = 6 символов.

Проверка: 6 символов занимают ⌈30 / 8⌉ = 4 байт ≤ 4, а 7 — уже 5 байт.

Ответ: 6

Решение на Python.

from math import ceil, log2

i = ceil(log2(20))
cap = 393 * 1024                  # байт памяти
L = 1
while 100000 * ceil((L + 1) * i / 8) <= cap:
    L += 1
print(L)

Вариант 9

дополнительные сведения

Каждый сотрудник предприятия получает электронную карту, на которой записаны личный код сотрудника, код подразделения и некоторая дополнительная информация. Личный код состоит из 12 символов, каждый из которых может быть одним из 100 допустимых символов. Для записи кода на карте отведено минимально возможное целое число байт, при этом используют посимвольное кодирование, все символы кодируют одинаковым минимально возможным количеством бит. Код подразделения и дополнительная информация вместе занимают целое число байт, одинаковое для всех сотрудников. Для хранения данных о 60 сотрудниках потребовалось 2280 байт. Сколько байт выделено для хранения кода подразделения и дополнительной информации об одном сотруднике? В ответе запишите только целое число — количество байт.

Разбор

Шаг 1. 100 символов → 7 бит на символ; код: 12·7 = 84 бит → 11 байт.

Шаг 2. На одного сотрудника: 2280 байт / 60 = 2280 / 60 = 38 байт.

Шаг 3. Дополнительная информация: 38 − 11 = 27 байт.

Ответ: 27

Решение на Python.

from math import ceil, log2

code = ceil(12 * ceil(log2(100)) / 8)   # байт на личный код
per = 2280 * 1 // 60            # байт на сотрудника
print(per - code)

Вариант 10

минимальная мощность алфавита

На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 2236 символов. В базе данных каждый серийный номер занимает одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным целым числом бит. Известно, что для хранения 4 851 248 серийных номеров требуется не менее 5172 Мбайт памяти. Определите минимально возможную мощность алфавита, используемого для записи серийных номеров. В ответе запишите только целое число.

Разбор

Шаг 1. Сколько байт как минимум на один номер. 5172 Мбайт = 5 423 235 072 байт. На один номер приходится не меньше 5 423 235 072 / 4 851 248 ≈ 1117.91 байт, а так как номер занимает целое число байт — не меньше 1118 байт.

Шаг 2. Бит на символ. Если на символ отвести i бит, номер займёт ⌈2236·i / 8⌉ байт. При i = 3: ⌈6708 / 8⌉ = 839 байт — мало; при i = 4: ⌈8944 / 8⌉ = 1118 байт — достаточно. Значит, на символ нужно не меньше 4 бит.

Шаг 3. Мощность алфавита. 4 бит на символ используется, когда в алфавите больше 23 = 8 символов. Минимальная мощность — 8 + 1 = 9.

Ответ: 9

Решение на Python.

from math import ceil, log2

L, N, need = 2236, 4851248, 5172 * 2 ** 20   # символов, номеров, байт
for k in range(2, 10000):            # мощность алфавита
    i = ceil(log2(k))                # бит на символ
    size = ceil(L * i / 8)           # байт на номер
    if N * size >= need:
        print(k)
        break

Для самостоятельного решения

Варианты 11–15 без разборов. Ответ можно проверить кнопкой.

Вариант 11

минимальная мощность алфавита

На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 3702 символов. В базе данных каждый серийный номер занимает одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным целым числом бит. Известно, что для хранения 4 685 116 серийных номеров требуется не менее 12 Гбайт памяти. Определите минимально возможную мощность алфавита, используемого для записи серийных номеров. В ответе запишите только целое число.

Вариант 12

дополнительные сведения

Каждый сотрудник предприятия получает электронную карту, на которой записаны личный код сотрудника, код подразделения и некоторая дополнительная информация. Личный код состоит из 30 символов, каждый из которых может быть одним из 250 допустимых символов. Для записи кода на карте отведено минимально возможное целое число байт, при этом используют посимвольное кодирование, все символы кодируют одинаковым минимально возможным количеством бит. Код подразделения и дополнительная информация вместе занимают целое число байт, одинаковое для всех сотрудников. Для хранения данных о 50 сотрудниках потребовалось 2400 байт. Сколько байт выделено для хранения кода подразделения и дополнительной информации об одном сотруднике? В ответе запишите только целое число — количество байт.

Вариант 13

наибольшая длина номера

В автоматизированной системе каждой посылке присваивают трек-номер одинаковой длины, составленный из 150 различных символов. Каждый номер хранится в памяти как минимально возможное целое число байт, при этом используется посимвольное кодирование и все символы кодируются одинаковым минимально возможным количеством бит. Для хранения 4 096 трек-номеров отведено 5 Мбайт памяти. Какова наибольшая возможная длина трек-номера? В ответе запишите только целое число.

Вариант 14

объём памяти для N записей

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов; в пароле используются десятичные цифры и 26 заглавных латинских букв. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего отведено 46 байт на одного пользователя. Определите объём памяти (в байт), необходимый для хранения сведений о 64 пользователях. В ответе запишите только целое число — количество байт.

Вариант 15

автомобильные номера

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