+Оглавление
Разбираем задачу №9 в ЕГЭ по информатике.
Обратите внимание, здесь будет не только пример решения, но и разбор задания по существу.
Для примера я беру демоверсию 2020 года (актуальная на момент написания статьи) с сайта fipi.ru.
Прежде чем приступать к решению этого примера, посмотрим в спецификацию к демоверсии.
На задание отводится 5 минут - это немного больше, чем на другие задания базового уровня сложности (ещё на 11е задание даётся 5 минут)
С нас просят уметь определять объёмы памяти. По сути дела, мы должны без компьютера уметь измерять информационный объём файлов разных типов. В этом году звукового или графического. Кроме того, тут может попасться задание на скорость передачи данных. Посмотрим, что в кодификаторе:
Из необычного - форматы графических и звуковых объектов. Ничего страшного в этой формулировке нет. Форматы - значит способы кодирования. Их довольно много разных, однако есть пара стандартных, и за их рамки выходить авторы ЕГЭ не намерены.
Немного об информационном объёме (количестве информации)
Обычно эта тема идёт в первых строках учебных программ, но в ЕГЭ она попала лишь на девятую строчку. Авторы справедливо считают, что прежде чем требовать сосчитать его, надо сначала проверить все вспомогательные темы. А именно, системы счисления.
Определение количества информации (в нашем случае - синоним информационного объёма) довольно сложное, особенно, если рассматривать подход Колмогорова. Давайте пока Андрея Николаевича трогать не будем, а ограничимся алфавитным подходом.
Любое измерение - это всегда подсчёт чего-либо, как, например, подсчёт попугаев, которые поместятся в удава. При алфавитном подходе:
Измерение количества информации - подсчёт количества символов, которое требуется для записи всей информации.
Единица измерения здесь определяется тоже с трудом. Вот для определения длин используется палка (метр). Можно брать единицу длиннее (аршин) или короче (фут). От этого будет меняться число, которое мы намеряем. Символы для записи, казалось бы, все одинаковые при подсчёте штук. Одинаковые да не совсем. Их "вес" зависит от того, сколько их разных существует.
Например, в русском алфавите 33 буквы, и слово из 5 букв будет "весить" больше, чем слово из 5 английских букв, коих всего 26 штук.
Самым "лёгким" будет слово, составленное из букв алфавита, в котором всего 2 разные буквы. А самый распространённый вариант - это двоичный набор из "0" и "1". Именно такой вариант общепринят за единицу измерения информации. И такая единица называется бит.
Информационным объёмом (Количеством информации) смело можно назвать количество двоичных символов, которые требуются для записи информации
Кстати, если бы мы брали десятичный алфавит (цифры 0-9), то единица называлась бы "дит". А если троичный - "трит". Ну, вы поняли?
Слово "бит" используется и в других смыслах. Так называют место, куда можно записать только 0 или 1 (даже пустым нельзя оставить).
Об изображениях
Более подробно читайте в теме "кодирование изображений"
Наша задача загнать изображение в "нолики" и "единички", а потом посчитать, сколько их получилось. Сделать это можно, например, так (для ЕГЭ - именно так):
Картинка очень наглядно иллюстрирует, как производится кодирование изображения: каждый пиксель (точка на изображении) записывается в память машины как последовательность "нулей" и "единиц". Чтобы записать нашего Пикачу, потребуется 2664 цифры (читай - бита). Подсчёт довольно прост:
Всего в изображении 36 рядов по 37 пикачуселей. Называются эти два числа "разрешением изображения". Это 1332 штуки. И в каждом из них по 2 цифры. 37*36*2=1332*2=2664.
Как я решил, что в каждом пикселе по 2 бита?
О цветах
Есть формула, но её вечно все забывают (я, в том числе). Поэтому я всегда рекомендую использовать таблицу. Её не надо помнить, можно писать по смыслу: Если у нас есть 1 бит, то мы сможем закодировать только 2 цвета. 2 бита - 4 цвета (00,01,10 и 11), 3 бита - 8 цветов (000 , 001, 010, 011, 100, 101, 110, 111).... и так далее.
У Пикачу 4 цвета, поэтому ему подойдёт второй столбик с двумя битами на пиксель. Если захотите поиграть в Гоблинов или СпайсКвест, то придётся раскошелиться на 8 бит на пиксель, потому что там надо 256 цветов. Формула
К решению задачи
Наша задача - обратная. Это значит, что у нас есть предел памяти, который мы можем использовать, и задано разрешение изображения. 128x320 это всего 40960 пикселей.
Мы не знаем, сколько цветов, поэтому не знаем, сколько бит на каждый пиксель пойдёт. Но мы знаем, сколько бит может получиться всего:
Итак, нам нужно 40960 пикселей упихнуть в 327680 бит. Тут не надо иметь семи пядей во лбу, чтобы догадаться, что на каждый пиксель у нас приходится всего по 8 бит. Для самых дотошных, 8 получилось как результат деления 327680/40960. Или, если хотите, x*40960=327680
Осталось лишь с цветами разобраться. Надо продлить табличку до 8 бит:
Сразу виден ответ - 256 цветов. Если мы возьмём 256 цветов, то каждый пиксель придётся кодировать по 8 бит, а значит, 40960 пикселей займут у нас 327680 бит.
Маленькая ремарка. Дело в том, что вычисления получаются довольно громоздкими. Можно сэкономить усилия, используя свойство дроби:
О других типах задач
В задачах на кодирование изображения могут попасться довольно хитрые. Например, памяти могут дать столько, что у нас получится дробное число бит/px. Мы должны понимать, что память ограничена, и простым округлением тут не обойдёшься. Хорошая модель - распихивать яйца в коробки. Какого размера (вместимости) коробки надо брать, чтобы в 3 коробки разложить 16 яиц? При прямом делении получится 5,33. Ну, вы где-нибудь видели коробки на 5,33 яиц? Округление даст 5. Сможем мы упихнуть в три коробки по 5 яиц 16 штук? Ногами, разве что... Надо брать коробки по 6. И тогда у нас будет заполненность: 6,6,4.
Важно (и в аналитическом отчёте ФИПИ это есть) не путать количество цветов и количество бит, нужных для кодирования одного цвета.
Может быть в задании многостраничное изображение. Например, gif-анимация. По методике мы высчитаем память, необходимую для записи только одной страницы.
Задачи на звукозапись так же возможны. Про них я напишу отдельную статью.
Может попасться задача, в которой требуется вычислить время/скорость передачи графического файла. Такая задача актуальна, например, для онлайн-трансляции (будет ли успевать передаваться изображение по "узкому" каналу связи). Про скорость передачи тоже напишу отдельную статью.
Заключение
Я рассмотрел не все, а только некоторые возможные задачи (подробно про изображения), поэтому ждите ещё стаей на эту тему. "Графические" задачи наиболее вероятны, поэтому начал именно с них. К тому же, они более наглядны.
Подписывайтесь на канал, делитесь в соцсетях, будут новые разборы