+Оглавление
Разбираем задачу №13 в ЕГЭ по информатике.
Обратите внимание, здесь будет не только пример решения, но и разбор задания по существу.
Для примера я беру демоверсию 2020 года (актуальная на момент написания статьи) с сайта fipi.ru.
Прежде чем приступать к решению этого примера, посмотрим в спецификацию к демоверсии.
Умение подсчитывать информационный объём сообщения раньше проверялось на более примитивных заданиях, теперь же задание будет довольно трудным, требующим учитывать многие факторы.
Ещё недавно в это задание входила и скорость передачи информации, но теперь только оценка памяти. Это и разумно: оценивать память в сложных случаях куда полезнее, чем оценивать память и скорость в простых.
Немного теории.
Во многом это задание походит по смыслу на задание №9. Однако теперь речь идёт о записи в память не изображения, и даже вообще не однородного информационного объекта, а нескольких сложных фрагментов. Это существенно осложняет работу, и уложиться в предложенные 3 минуты можно только если заранее знаешь, на какой элемент задания обращать внимание.
О посимвольном кодировании
Это наиболее распространённый метод кодирования текстов, однако не единственный. Заключается он в том, что каждому символу назначается двоичный код, и эти коды записываются один за другим. Таких кодов два варианта - равномерный (когда все символы кодируются одинаковым по длине кодом) и неравномерный (длины кодов различаются, как в задании № 5). Остановимся на первом как на наиболее актуальном к этому заданию. Чаще всего, для минимальности длины кода, каждой букве просто назначают двоичную запись её номера (начиная с 0). По хорошему, для определения, сколько бит будет занимать каждая буква, можно пользоваться формулой
Здесь есть два важных момента:
1. Может так статься, что букв будет не "хорошее" количество, и для строго равенства i должно быть дробным. В таких случаях не отчаиваются, а берут максимум, и при этом просто некоторые коды останутся незадействованными:
2. Память машины группируется по байтам (8 бит), поэтому почти всегда мы должны задействовать целое количество байтов. Для кодирования всего лишь одной буквы кодом из п. 1 потребуется не 0,375 байт, а целый. Как пирожки в коробке:
Для двух символов, кстати, тоже 1 целый байт:
Решение задания
Первым делом в таких заданиях нужно определиться с тем, что будет записано в память. У нас это:
- 15 символов пароля
- дополнительные сведения
Информационный объём каждой записи в БД будет складываться из этих двух. Для второго мы заранее знаем объём (24 байта), а для первого нужно вычислить. Вычислять по безликим формулам очень погано, поэтому я рекомендую просто прописать реальные коды для каждой буквы. Благо, букв в этих заданиях никогда не бывает много. Коды можно назначать "от балды", но лучше по порядку:
Даже неопытный человек справится с таким набором быстро, и сразу увидит, что для каждой буквы нужен трёхбитный код.
В каждом пароле используется по 15 символов, поэтому количество бит, необходимых для записи можно получить просто умножением: 15*3=45. Обратите внимание: не байт, а бит. Каждый раз в задании надо внимательно читать, что надо - байты или биты. Это важно вот почему. Попытаемся 45 бит распределить по байтам:
Смотрите, задействовано 5 целых байтов и ещё один не до конца. Всего для работы нужно 6 байтов, но в них останется незадействованными три бита.
Если к этим 6 байтам добавить 24 байта "дополнительной информации", то в сумме наберётся 30 байт на запись. Таковых у нас 20 штук: это 30*20=600 байт.
Ответ: 600
Подводные камни
Задание безумно лёгкое, на него отводится всего 3 минуты, но процент решаемости низковат - 60% (в прошлом 2019 году). Практически все ошибки сосредоточены вокруг нескольких моментов.
1. Посимвольное и полнотекстовое кодирование. Эти два варианта путают, и начинают рассчитывать количество возможных паролей из 8 различных символов с длиной 15 символов. 8 в 15 степень возводится довольно легко (даже часто оставляют в виде степени двойки), но в экзаменационных КИМах, бывает, попадаются и задания с 7 или 9 символами. Там возведение гораздо труднее, а применение формулы (см. выше) становится просто нереальным. Ни разу не встречал заданий, в которых это было бы нужно (видел задания, цель которых - посчитать количество паролей, но не кодировать).
2. Целое число байт. Это просто заноза какая-то. Ладно, насчитали 45 бит. Поняли, что это не байты, поделили на 8. Получили 5,625. Но это не целое количество байт.
Иногда дробь сразу в ответ и пишут (даже про 24 дополнительных забывают).
Кто-то догадывается округлить, но лишь в самом конце: (5,625+24)*20=592,5≈593
Округление до сложения (5,625≈6) тоже работает лишь в половине случаев, потому что сделай вам не 15, а 14 символов, и бит уже будет на 45, а 42. Это 42/8=5,25≈5 байт!
Ещё раз: Сколько нужно коробок, чтобы впихнуть в них 45 пирожков по 8 штук в каждый? Последняя коробка тоже нужна целая, даже если пирожок в ней будет лежать один.
Как избежать
Я рекомендую всё прописывать и разрисовывать на черновике: и коды для букв, и картинку для байтов.
Другие варианты
Очень часто тут могут попадаться задания на определение времени передачи, сжатие и так далее.
Например, самое редкорешаемое задание звучит примерно так: один компьютер принимает файл из интернета и потом передаёт его на другой компьютер, передача может производиться одновременно с приёмом, но только если загружено уже не менее какого-то объёма. Это довольно грубое описание кэширующего прокси-сервера. Технология, которая сейчас может быть востребована в крупных организациях с относительно медленным внешним интернет-каналом, если сотрудники, например, регулярно посещают один и тот же сайт, для ускорения работы или экономии внешнего трафика.
Решение опять то же - нужно рисовать, но в этот раз не разбиение по байтам, а временную диаграмму:
