Автор статьи: Андрей Рогов
Краткая теория
На выполнение этого задания обычно отводится около трёх минут. Если вы столкнулись с таким заданием впервые, процесс может занять больше времени, особенно из-за сложной или необычной формулировки. Главное — понять суть вопроса. Часто речь идёт о посимвольном кодировании или переводе между единицами измерения информации. На каждом этапе решения следите за тем, чтобы использовать правильные единицы: сначала обычно считают количество бит, затем переводят в байты, а при необходимости — в килобайты или мегабайты.
Ещё одна причина, по которой выполнение задания может занять больше времени, — встреча со сложными прототипами, требующими более эффективных методов решения. В таких случаях бывает полезно подключить программирование для автоматизации расчётов.
В информатике различают два способа кодирования: равномерное и неравномерное. При неравномерном кодировании кодовые слова могут иметь разную длину. Работа с таким кодом требуется в задании номер 4. А в задании номер 11 речь идёт о равномерном кодировании, когда все кодовые слова имеют равную длину.
Прежде всего необходимо разобраться с понятием мощности алфавита — это количество разных символов, которые используются для кодирования. Например, в русском алфавите $33$ буквы, а в десятичной системе счисления $10$ символов. Зная мощность алфавита, можно определить, сколько двоичных разрядов потребуется для кодирования одного символа. Поскольку мощность алфавита часто не совпадает с целой степенью двойки, для расчёта используйте формулу $N \leq 2^i$, где $N$ — мощность алфавита, $i$ — количество бит, требуемое для кодирования одного символа алфавита.
Сообщения составляются из символов выбранного алфавита. В заданиях это могут быть пароли, серийные номера или идентификаторы; каждый объект включает несколько символов. Чтобы рассчитать объём информации, необходимо умножить количество символов в сообщении на объём информации, приходящийся на один символ: $I = k \times i$.
Владение этими двумя формулами — ключ к самостоятельному решению заданий ЕГЭ по информатике, даже если вы только начинаете подготовку.
Задача 1
Определим мощность алфавита. Одна из распространённых ошибок — путать длину идентификатора с мощностью алфавита. Например, число семь обычно обозначает количество символов в идентификаторе, а не количество различных символов в используемом алфавите.
В задачах встречаются ситуации, когда символы составляют из десятичных цифр и дополнительных знаков специализированного алфавита, содержащего в нашем случае $8188$ символов. Важно правильно различать: длина идентификатора — это число его символов, а мощность алфавита — это общее количество различных символов, из которых эти идентификаторы формируются.
Получаем: $N = 10 + 8188 = 8198$.
Найдём степень двойки, способную закодировать $8198$ символов. $2^{13} = 8192$, что недостаточно. $2^{14} = 16 384$ — минимальная подходящая степень двойки. Значит, на кодирование одного символа потребуется $i = 14$ бит.
Теперь определим объём информации, необходимый для хранения одного идентификатора. Сначала важно посчитать объём именно одного идентификатора, а уже после переходить к общему количеству — это позволит избежать ошибок при округлении байтов. Поскольку в каждом идентификаторе содержится семь символов, рассчитаем объём следующим образом:
$I = 14 \times 7 = 98$ бит.
По условию задачи для хранения каждого идентификатора выделено минимально возможное целое число байт. Для перевода битов в байты разделим полученное число на $8$.
$I = 98 / 8 = 12.25$ байта
Полученный результат необходимо округлять в большую сторону, до $13$ байт. Если бы мы ограничились $12$ байтами, это дало бы только $96$ бит, а для хранения информации требуется $98$ бит.
Находим объём памяти под $20\,240$ идентификаторов:
$I = 13 \times 20\,240 = 263\,120 байт \approx 256.95$ Кбайта
Как и в случае с байтами, для того чтобы записать ответ, округлим число в большую сторону, поскольку $256$ Кбайт будет недостаточно.
Ответ: $257$ Кбайт.
Задача 2
Мощность алфавита $N = 10 + 26 = 36$, необходимо $6$ бит для кодирования одного символа. В пароле $11$ символов:
$I_{пароль} = 11 \times 6 = 66~бит$
Переведём в байты:
$66 / 8 = 8.25$ байта, округляем до $9$ байт.
Если сведения о тридцати пользователях заняли $750$ байт, тогда:
$I_{пользователь} = 750 / 30 = 25~байт.$
Помимо пароля, у пользователя есть дополнительные сведения:
$I_{доп} = 25 − 9 = 16~байт.$
Ответ: $16$ байт.
Задача 3
В этой задаче неизвестна длина серийного номера, сперва решим аналитически.
Мощность алфавита $N = 10 + 52 + 458 = 520$, минимальная подходящая степень двойки — $2^{10} = 1024$.
По условию $862$ серийных номера занимают не больше $276$ Кбайт.
Запишем формулу:
$k \times 10 / 8 = 276 \times 1024 / 862$\
$k = 276 \times 1024 / 862 \times 8 / 10$\
$k = 262.296$ символов
Это примерное значение, так как не учтено округление при переводе битов в байты. Проверим несколько значений $k$.
Для $k = 262$:
$I = 262 × 10 / 8 = 327.5$ байта $= 328$ байт.
Объём всех номеров $I = 862 \times 328 / 1024 \approx 276.11$ Кбайта — превышает лимит.
Для $k = 261$:
$I = 261 \times 10 / 8 = 326.25$ байта $= 327$ байт\
$862 \times 327 / 1024 \approx 275.27$ Кбайта — подходит.
Значит, максимальная длина серийного номера — $261$.
Альтернативный способ решения такого задания ЕГЭ по информатике — написать программу, которая перебирает возможные значения длины серийного номера и рассчитывает результат автоматически, аналогично тому, как это делалось на последнем этапе аналитического решения.
from math import ceil # функция для округления в большую сторону
for k in range(1, 1000): # перебираем значения длины
v = ceil(k * 10 / 8) # объём одного серийного номера
v = v * 862 / 1024 # объём всех номеров
if v <= 276: # подходит под условие
print(k)
Перед тем как приступить к написанию программы, нужно определить объём информации, приходящийся на один символ. Это можно сделать с помощью логарифмической формулы: $N = 2^{i}$, откуда получим, что $i = log_{2} N$, где $N$ — мощность алфавита, а $i$ — информационный вес одного символа в битах.
from math import ceil # функция для округления в большую сторону
from math import log # логарифм
for k in range(1, 1000): # перебираем значения длины
i = ceil(log(10+52+458, 2)) # вычисляем вес одного символа
v = ceil(k * i / 8) # объём одного серийного номера
v = v * 862 / 1024 # объём всех номеров
if v <= 276: # подходит под условие
print(k)
Максимальное значение, которое выводит программа, — $261$ символ.
Ответ: $261$.
Задача 4
Здесь неизвестна мощность алфавита. Находим вес одного символа, как в предыдущем примере:
$197 \times i / 8 = 25 \times 1024 \times 1024 / 178~080$\
$i ≈ 5.98$ бита
Пробуем два значения битов:
$i = 5:$\
$I = 197 × 5 / 8 = 123.125~байта = 124$ байта\
$124 × 178~080 / (1024 × 1024) = 21$ Мбайт\
$i = 6:$\
$I = 197 × 6 / 8 = 147.75~байта = 148$ байт\
$148 × 178~080 / (1024 × 1024) = 25.13$ Мбайта — подходит.
По формуле $N ⩽ 2^{i}$ одному значению $i$ может соответствовать несколько разных $N$. Например, если $i = 6$, то $2^{6} = 64$, значит, $N$ может быть любым числом от $1$ до $64$. Однако важно помнить, что, если для кодирования можно использовать меньше битов, такое значение $N$ нас не устраивает. В нашем случае при $i = 5$ (то есть $5$ битах) $2^{5} = 32$, поэтому для любого $N$ больше $32$ понадобится уже 6 бит.
Получаем неравенство $32 < N ⩽ 64$. Значит, все значения $N$ от $33$ до $64$ включительно требуют 6 бит для кодирования одного символа. Минимальное подходящее значение $N$ — это $33$.
Напишем программу для подбора нужного значения $N$. При подготовке к ЕГЭ по информатике такая техника часто практикуется для решения заданий этого типа:
from math import ceil # функция для округления в большую сторону
from math import log # логарифм
for n in range(1, 1000): # мощность алфавита
i = ceil(log(n, 2)) # вес одного символа в битах
v = ceil(197 * i / 8) # вес серийного номера в байтах
v = v * 178080 / 1024 / 1024 # вес всех серийных номеров
if v > 25:
print(n)
break
Программа выводит одно число, $33$, первое подходящее значение.
Ответ: $33$.
Заключение
Мы разобрали основную теорию и практику по задачам на кодирование информации в ЕГЭ по информатике. Чтобы решать такие задания уверенно и без ошибок, важно внимательно читать условия и разбираться, в каких единицах требуется дать ответ. Необходимо убедиться, что найденное число соответствует условию задачи: это объём всех идентификаторов, максимальное или минимальное значение мощности алфавита или длины информационного объекта.
Особое внимание стоит уделить величинам с одинаковыми единицами измерения информации: мощность алфавита и количество символов, вес одного символа и вес всего сообщения. Пригодятся базовые формулы для расчёта мощности алфавита и объёма информации. Не забудьте, при переводе бит в байты результат нужно правильно округлять.
Если задача кажется слишком запутанной, можно написать небольшую программу. Это не только ускорит решение, но и поможет лучше понять материал. Особое внимание стоит уделить умению переводить информационные единицы и применять нужные формулы в разных задачах. А теперь самое время закрепить новые знания на практике — попробуйте решить подборку заданий.