Типы заданий № 11
В этой статье будет разобрано задание 11.
Рассмотрим типовые задачи из одиннадцатого задания ЕГЭ по информатике.
Данное задание относится к повышенному уровню сложности.
Время выполнения задания ≈ 3 минуты.
Для того чтобы решать задания № 11 ЕГЭ — нужно знать теорию на определение количества информации с помощью вероятностного и алфавитного подхода. А также нюансы при решении данных задач описаны в статье(ссылка ниже):
Ссылка на статью: Измерение количества информации.
Задача 1 (Классическая)
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 10 символов. В качестве символов используют прописные буквы латинского алфавита, т.е. 26 различных символов. В базе данных для хранения каждого пароля отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Определите объём памяти (в байтах), необходимый для хранения данных о 50 пользователях. В ответе запишите только целое число – количество байт.
Решение:
У каждого пользователя есть пароль, состоящий из 10 символов. Это значит, длина пароля 10 символов!
И в каждую ячейку можно выбрать символ из 26 букв! Важно различать длину пароля и количество символов из которых пользователь выбирает для каждой ячейки пароля.
Теперь нужно определить: сколько бит занимает одна ячейка (1 символ пароля!).
Когда речь идёт о количестве бит, применяем формулу, которую мы использовали в 7 задании из ЕГЭ по информатике(формула Хартли). Там мы кодировали цвета для одного пикселя, а здесь нужно закодировать 26 букв для одного поля пароля.
Целого числа нет для i (количества бит), чтобы равенство было верным. Значит берём столько количество бит, сколько точно будет достаточно, чтобы закодировать 26 букв (символов):
Получаем, что одна ячейка (одно поле) пароля занимаем 5 бит! А в пароле их 10! Значит, весь пароль будет занимать: 5 * 10 = 50 бит(весит один пароль).
В условии сказано: для хранения каждого пароля отведено одинаковое и минимально возможное целое число байт. Это означает, что мы не может выделять память по одному биту. Память выделяется блоками по 8 бит (по одному байту).
Если взять 7 блоков по 8 бит (1 байту), то нам хватит этого на один пароль: 50 бит / 8 = 6,25 = 7 байт (округляем в большую сторону).
Таким образом, на 1 пароль потребуется 7 байт! Мы округлили в большую сторону, т.к. нужно выделить столько памяти, чтобы точно хватило на 1 пароль.
Тогда на 50 пользователей потребуется: 50 пользователей * 7 байт = 350 байт (для 50 пользователей).
Ответ: 350
Задача 2 (Дополнительные сведения)
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 11 символов. В качестве символов используют 26 прописных букв из латинского алфавита и десять цифр. В базе данных для хранения каждого пароля отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля для каждого пользователя в системе хранятся дополнительные сведения. Для кодирования данных о 30 сотрудниках было выделено 750 байт. Сколько памяти(в байтах) выделено для хранения дополнительных сведений об одном пользователе. В ответ запишите только целое число - количество байт.
Решение:
Здесь длина пароля составляет 11 символов.
Найдём сколько бит занимает одна ячейка пароля:
Значит, 6 бит - минимальное количество бит, которое нужно, чтобы была возможность разместить любой из 36 символов в одной ячейке пароля. Найдём сколько бит нужно на весь пароль: Vпароля = 6 бит * 11 символов = 66 бит (на один пароль).
Теперь найдём, а сколько байт нужно на 1 пароль: 66 бит / 8 = 8,25 ≈ 9 байт
Следовательно, 9 байт достаточно, чтобы покрыть 66 бит на 1 пароль.
Сказано, что для 30 сотрудников выделено 750 байт. Подсчитаем, сколько байт будет выделено на одного сотрудника: Vпользователя = 750 байт / 30 = 25 байт (приходится на одного пользователя).
Мы выяснили, что на пароль из этих 25 байт потребуется 9 байт. Тогда на дополнительную информацию о каждом пользователе потребуется: Vдоп.инф. = 25 байт - 9 байт = 16 байт.
Ответ: 16
Задача 3 (Автомобильный номер)
В некоторой стране автомобильный номер состоит из 7 символов: сначала 2 буквы, затем 3 цифры, затем ещё 2 буквы. При этом буквы могут быть выбраны только из 12 строчных букв местного алфавита. Среди цифр не используются цифры 6 и 9. Автоматизированная система хранит номера автомобилей следующим образом. Используется посимвольное кодирование. В памяти системы для кодирования каждого символа используется минимально возможное и одинаковое целое количество бит (для букв и цифр отдельно). А для номера используется минимально возможное целое количество байт. Какое количество информации (в байтах) требуется для хранения номеров 160 автомобилей?
Решение:
Найдём сколько бит потребуется для кодирования 4-х букв:
4 бита хватит для кодирования 12 букв. Всего таких ячейки 4! Поэтому в одном номере на все буквы уйдёт 4 * 4 бита = 16 бит.
Найдём сколько бит потребуется на кодирование 3 ячеек, где находятся цифры:
Для кодирования одной ячейки, где находится цифра, потребуется 3 бита. Все цифры в одном номере будут закодированы 3 бита * 3 = 9 битами. Всего на один номер уйдёт 16 бит + 9 бит = 25 бит.
Найдём сколько байт потребуется для кодирования одного номера: 25 бит / 8 = 3,125 ≈ 4 байта.
4-х байт достаточно для 25 бит. Если взять 3 байта, то 3 * 8 бит (1 байт) = 24 бита. Этого будет не достаточно.
Найдём количество байт, которое нужно для кодирования 160 автомобилей: 160 автомобилей * 4 байта = 640 байт.
Ответ: 640
Задача 4 (Номера спортсменов)
В велокроссе участвуют 48 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Какой объём памяти будет использован устройством, когда все спортсмены прошли промежуточный финиш? (Ответ дайте в байтах.)
Решение:
Узнаем сколько бит потребуется выделить на каждого спортсмена, чтобы была возможность записать любой номер от 1 до 48.
Здесь работает логика, как и в прошлых задачах:
Получается 6 бит потребуется для того, чтобы была возможность записать любой номер от 1 до 48 для каждого спортсмена. Если взять пять бит, то мы будем иметь возможность записать номера только от 1 до 25 = 32 для каждого спортсмена (этого не хватает).
Т.к. все участники пересекли финиш, а на каждого участника выделено по 6 бит, то получается: 6 бит * 48 = 288 бит = 36 байт.
Ответ: 36
Задача 5 (Метеорологическая станция)
Метеорологическая станция ведет наблюдение за влажностью воздуха. Результатом одного наблюдения является целое число от 0 до 100%, записываемое при помощи минимально возможного количества бит. Станция сделала 800 измерений. Определите информационный объем результатов наблюдений. (Ответ дайте в байтах.)
Решение:
Здесь, нужно закодировать сто одно число (от 0 до 100). Ситуация похоже на ту, где мы кодировали номера спортсменов.
Получается, что 7 бит потребуется, чтобы полностью закодировать 101 число. Всего было сделано 800 таких измерений: 800 * 7 бит = 5600 бит = 700 байт.
Ответ: 700
Задача 6 (ЕГЭ по информатике 7.06.24, длина номера)
На предприятии каждой изготовленной детали присваивают серийный номер, содержащий десятичные цифры, 52 латинские буквы (с учётом регистра) и символы из 458-символьного специального алфавита. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 862 серийных номеров отведено не более 276 Кбайт памяти. Определите максимально возможную длину серийного номера. В ответе запишите только целое число.
Решение:
В этой задаче нам неизвестна длина серийного номера. Обозначим её за x. Найдём сколько весит один символ серийного номера.
Получается, что 10 бит весит 1 символ серийного номера. Тогда 10*x бит - будет весить весь серийный номер. Латинские буквы можно использовать с учётом регистра, это значит, допускаются как большие буквы, так и маленькие.
Найдём, сколько памяти отведено на 1 серийный номер: 276 Кбайт / 862 = 276*1024 байт / 862 ≈ 327,87 ≈ 327 байт
Здесь округлили в меньшую сторону. Если бы мы округлили в большую сторону, то в итоге бы превысили 276 Кбайт памяти. А в задаче сказано, что выделено не более 276 Кбайт. В виде дробного числа тоже нельзя оставлять, т.к. сказано, что для номера отведено целое число байт.
Переведём 10*x в байты и получим уравнение:
10 * x / 8 = 327 байт
10 * x = 327 * 8
x = 327 * 8 / 10 = 261,6 ≈ 261
Здесь мы опять округлили в меньшую сторону, т.к. если длина номера будет больше, чем положено, для номера опять придётся выделять больше памяти, чем 327 байт, и в итоге мы превысим 276 Кбайт для всех номеров.
В подобных задачах лучше делать проверку. Например, если бы мы округлили в большую сторону, т.е. взяли 262 символа, то на один номер приходится 10 бит * 262 = 2620 бит. Номер хранится в байтах, значит, 2620 бит / 8 = 327,5. Т.е. для хранения одного номера нужно выделить 328 байт. Это превышает допустимое значение 327 байт. Следовательно, ответ получается равен 261.
Ответ: 261
Задача 7 (ЕГЭ по информатике 8.06.24, мощность алфавита)
На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 261 символов. Для его хранения отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 252 500 серийных номеров отведено более 31 Мбайт памяти. Определите минимально возможную мощность алфавита, из которого составляются серийные номера. В ответе запишите только число.
Решение:
Мощность алфавита - это то количество символов, которые претендуют в одну ячейку серийного номера. Обозначим за x сразу вес одного символа серийного номера в битах. Тогда вес всего номера будет равен 261 * x.
Узнаем, сколько памяти выделили на один серийный номер:
31 Мб / 252500 = 31 * 1024 * 1024 / 252500 ≈ 128,74 ≈ 129 байт
Здесь мы округлили в большую сторону, т.к. в задачке сказано, что выделено более 31 Мб.
Найдём x. Переведём значение 261 * x в биты:
261 * x / 8 = 129
261 * x = 1032
x = 1032 / 261 ≈ 3,9 ≈ 4 бит
Мы округлили в большую сторону, иначе опять бы нарушилось условие, что выделено более 31 Мб на все номера.
Получается 4 бита выделено на один символ серийного номера.
Минимальная возможная мощность алфавита при 4 битах будет равна 9.
Но ещё меньше взять нельзя, т.к. если мощность алфавита будет равна 8, то для этого достаточно 3 бита, а нам нужно, чтобы 1 символ весил 4 бита.
Ответ: 9
Задача 8 (ЕГЭ по информатике 19.06.24, длина номера)
На предприятии каждой изготовленной детали присваивается серийный номер, содержащий десятичные цифры, 26 латинских букв (без учёта регистра) и символы из 450-символьного специального алфавита. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 708 серийных номеров отведено более 213 Кбайт памяти. Определите минимально возможную длину серийного номера. В ответе запишите только целое число.
Решение:
В этой задаче так же неизвестна длина серийного номера. Обозначим её за x. Найдём сколько весит один символ серийного номера:
Значит, 9 бит весит 1 символ серийного номера. Тогда 9 * x бит - будет весить весь серийный номер. Здесь латинские буквы используют без учёта регистра, следовательно, и большая, и маленькая буква - это одно и тоже. Но разнообразных букв получается 26, т.е. здесь на 2 умножать не нужно количество латинских букв.
Найдём, сколько памяти отведено на 1 серийный номер:
213 Кбайт / 708 = 213 * 1024 байт/ 708 ≈ 308,06 байт ≈ 309 байт
Здесь мы округлили в большую сторону, т.к., если округлим в меньшую сторону, в итоге получится меньше, чем 213 Кб для всех номеров, а нам сказали должно более 213 Кб.
Переведём 9 * x в байты и получим уравнение:
9 * x / 8 = 309
x = 309 * 8 / 9 ≈ 274,66 байт
В какую строну округлить ? В подобных задачах лучше всего сделать проверку.
Попробуем округлить в большую сторону, т.е. возьмём 275 символов:
9 бит * 275 / 8 = 309,375 байт ≈ 310 байт.
Здесь мы округлили в большую сторону, ведь номер занимает целое количество байт. Мы не имеем право отбросить дробную часть номера - действуем классически, как это делали в самой первой задаче.
Это число нам подходит, ведь в итоге получится для всех номеров более 213 Кб. Но нам нужно найти число как можно меньше. Проверим число 274 (округлим в меньшую сторону).
9 бит * 274 / 8 = 308,25 байт ≈ 309 байт
Это число так же подходит, т.к. получилось вычисленное ранее значение 309 байт.
На всякий случай проверим число 273.
9 бит * 273 / 8 = 307,125 байт ≈ 308 байт < 309 байт
Уже мы получаем меньше для всех номеров, чем 213 Кб.
Ответ: 274
Задача 9 (Демоверсия ЕГЭ 2024 года)
При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 60 символов и содержащий только десятичные цифры и символы из 250-символьного специального алфавита.
В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт.
При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным количеством бит.
Определите объём памяти (в Кбайт), необходимый для хранения 65536 идентификаторов.
В ответе запишите только целое число – количество Кбайт.
Решение:
Из задачи посчитаем N = 250(символов) + 10(цифр) = 260. Тогда по формуле Хартли:
т.е. 9 бит точно хватит, чтобы закодировать алфавит любого идентификатора.
В одном идентификаторе всего 60 символов. Найдём сколько будет "весить" один идентификатор: 60 * 9 = 540 бит.
Переведём в байты: 540 / 8 ≈ 67,5 байт ≈ 68 байт (округляем в большую сторону, чтобы точно хватило).
У нас всего 65536 идентификаторов. Тогда нам потребуется 65536 * 68 = 4456448 байт. Переведём в Кб: 716800 / 1024 = 4352 Кб.
Ответ: 4352
Задача 10 (Демоверсия ЕГЭ 2025 года)
На предприятии каждой изготовленной детали присваивают серийный номер, содержащий десятичные цифры, 52 латинские буквы (с учётом регистра) и символы из 963-символьного специального алфавита. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 2000 серийных номеров отведено не более 693 Кбайт памяти. Определите максимально возможную длину серийного номера. В ответе запишите только целое число.
Решение:
Воспользуемся формулой Хартли для вычисления мощности алфавита:
где N - количество символов алфавита, i - количество бит для одного символа идентификатора.
Из задачи посчитаем N = 963символов) + 10(цифр) + 52(буквы) = 1025. Тогда:
т.е. 11 бит точно хватит, чтобы закодировать 1 символ любого серийного номера.
Найдём сколько будет "весить" один серийный номер в байтах: (693(Кб) * 1024) байт / 2000 = 709632(байт общий вес всех 2000 серийных номеров не должен превышать это число) / 2000 ≈ 354,816 ≈ 354 байт (округляем т.к. в задаче сказано, что для хранения серийного номера отведено минимально возможное целое число байт. В большую сторону округлить нельзя - превысим порог в 693Кб).
Осталось найти сколько всего в серийном номере может быть символов. Вес одного символа 11 бит. Всего весит серийный номер 354 байт. Переводим байты в биты и делим общий вес серийного номера в битах на вес одного символа, чтобы получить количество символов всех символов в серийном номере: 354 * 8 / 11 ≈ 257.454545455 ≈ 257 (округляем т.к. 0.45 символа невозможно сохранить, также даже если бы получилось .9999999 в остатке от деления).
Ответ: 257
Задача 11 (Джобс Е.)
В базе данных регистрационных данных о каждом пользователе хранятся следующие данные: дата рождения, номер паспорта и адрес проживания.
Дата рождения состоит из дня (1-31), месяца (1-12) и года (1900-2500), при этом для хранения даты отводится битовая последовательность одинаковой минимальной длины для всех пользователей, которая представляет собой одно двоичное число. Номер паспорта представлен как строка из 12 цифр от 0 до 9, каждая из которых кодируется одинаковым и минимально возможным количеством бит. Известно, что для кодирования информации об одном пользователе выделяется целое, одинаковое для всех пользователей минимальное количество байт. Известно, что адрес проживания содержит символы из алфавита мощностью 32, при этом используется посимвольное кодирование, и каждый символ кодируется одинаковым и минимально возможным количеством бит.
Известно, что для хранения данных о 1316 пользователях понадобилось 27 Кбайт памяти. Найдите максимальную длину строки, которая может быть адресом пользователя.
Решение:
Найдём сколько весит информация по дню рождения, адресу и номеру паспорта для одного пользователя: День рождение: 31 * 12 * (2500-1900 + 1) = log2(31 * 12 * 601) = log2(223572) = 17.77 = 18 бит занимает 1 запись о дне рожденья (округляем логарифм двойки вверх, т.к. количество бит не может быть дробным числом по количеству состояний берётся с запасом всегда или строго равно).
Адрес: N = 32 = 2^5; i = 5 бит (на 1 символ адреса). Весь адрес будет "весить": 5 * X(количество символов у всего адреса и есть вопрос задачи).
№ паспорта: N = 10(0..9) i = 2^4. 4 * 12 = 48 бит (объём одного № паспорта)
Составим уравнение для решения всей задачи: (18 + 48 + 5*x) * 1316 <= 27 Кбайт / 1316
Выразим x:
Можно прописать выражение на Python: (-66 * 1316 + 27*2**13) // (1316 * 5) и сразу получим ответ.
Ответ: 20