Демонстрационная версия ЕГЭ по информатике 2023 года содержит новые задания 6 и 22. Как сказано на официальном сайте Рособрнадзора, «задание 22 призвано привлечь внимание к параллельному программированию, технологиям организации многопроцессорных / ногопоточных вычислений». Для выполнения задания необходимо использовать файл - электронную таблицу.
- Уровень сложности - повышенный.
- Использование специализированного программного обеспеченья - да.
- Время выполнения задания - 7 минут.
- Максимальный балл за выполнения задания - 1.
- Средний процент выполнения: 51.9%.
- Ответом к заданию 22 по информатике может быть цифра (число) или слово.
У нас есть различные процессы. Для каждого процесса известно время его выполнения (столбец B), а также от каких процессов он зависит (столбец С).
Общее время выполнения процесса вычисляется следующим образом: процесс должен дождаться самый долгий процесс от которого он зависит, а потом выполнится сам.
Используем столбец D, чтобы вычислить окончательное время выполнения каждого процесса.
Важно помнить, что когда мы берём время процесса от которого зависит какой-то процесс, то мы должны взять это время из столбца D, т.е. уже окончательное время выполнения процесса.
Минимальное время, через которое завершится выполнение всей совокупности процессов будет равно времени самого медленного процесса.
Рассмотрим способы решения данного задания. В качестве примера возьмем задание одного из вариантов досрочной волны ЕГЭ за 2023 год.
1 способ: с помощью графа
Решим задачу, построив граф, вершинами которого будут ID процессов из первого столбца «ID процесса B», а рёбрами - связи процессов, заданные столбцами «ID процесса(ов) A» и «ID процесса B». Поскольку для выполнения процесса B иногда необходимы результаты выполнения процесса А, рёбра графа будут дугами (в теории графов ребро, имеющее направление, называется ориентированным ребром или дугой), а сам граф - ориентированным графом или орграфом. В столбце «ID процесса(ов) A» содержатся номера вершин графа, являющихся началом дуги, в столбце «ID процесса B» задан конец для каждой дуги.
Процессы с ID 1, 2, 4 - независимые, не имеют предшествующих процессов и поэтому отображаются на графе как корневые вершины. Процесс No 3 может начаться только по окончании выполнения процессов No 1 и 2, поэтому на графе отображены дуги P1 → P3, P2 → P3. Процесс 6 зависит от результатов работы процессов No 3 и 2, чему соответствуют дуги P3 → P6 и P2 → P6. Таким образом, для решения задачи следует изменить форму представления информации с табличной на графическую, данные о дугах для вершин P1, P2, P3, P4, P5 получены из следующих строк таблицы:
Обозначим рядом с каждой вершиной графа время выполнения процесса из второго столбца таблицы «Время выполнения процесса B (мс)» - вес вершины. Получим граф со взвешенными вершинами (рис. 2). Поскольку необходимо завершение выполнения всех процессов, для нахождения минимального времени выполнения всей совокупности процессов требуется найти путь от корневых до концевых вершин, имеющий наибольшую сумму весов вершин графа, и сложить веса каждой вершины на найденном пути. В данном случае это путь P1-P3-P5-P7-P8-P12.
Обратите внимание, что граф для решения задачи состоит из трёх изолированных подграфов, и для корректного решения задачи наибольшую сумму весов следует найти для каждого из изолированных подграфов, после чего следует выбрать наибольшую из найденных сумм, поскольку все процессы должны быть выполнены по условию задачи (рис. 3). Путь с наибольшей суммой и будет ответом к заданию. Таким образом, ответом на задание КЕГЭ No 22 будет число 79.
Ответ 79.
2 способ: вручную, перебором
Для выполнения задания последовательно внесём в столбец D время окончания выполнения процессов, назвав столбец D «Время окончания процесса B (мс)». Время окончания для каждого процесса будем отсчитывать с момента запуска первых (всех независимых) роцессов.
Если процесс не зависит от других процессов, он сразу же начинает своё выполнение. Для независимых процессов B, т.е. тех, для которых в столбце «ID процесса(ов) A» указано значение 0, в новый столбец D внесём значения, равные времени выполнения процессов (табл. 2). Далее заполним столбец D «Время окончания процесса B (мс)» таблицы для тех процессов B, которые зависят от процессов, время окончания работы которых уже известно. Это процессы No 1,2,4, числовые обозначения которых содержатся в столбце A «ID процесса B». Процесс No 3 начнёт выполнение после окончания работы каждого из процессов 1 и 2, следовательно, для вычисления времени окончания процесса 3 нужно вычислить сумму максимального из полученных значений для процессов 1 и 2 и времени выполнения процесса 3: МАКС(14, 3) + 14 = 28.
Аналогично вычисляется время окончания работы остальных процессов.
Таким образом, время окончания каждого процесса является суммой его времени выполнения и большего из времён окончания процессов, от которых зависит данный процесс.
Продолжая вычисления, получим значения для остальных процессов.
Система завершит работу, когда завершится самый медленный процесс. Таким образом нам нужно выбрать максимум из последнего столбца.
Ответ: 79.
3 способ: с помощью электронных таблиц, «подсвечиванием»
Растягиваем милисекунды сверху и выделяем время для всех процессов. Смотрим от каких процессов зависит данный процесс, выбираем самое позднее время завершения и от него начинаем красить количество ячеек по времени текущего процесса.
4 способ: в электронных таблицах, с помощью функции ВПР
Данный способ полезен при большом объеме данных в таблице.
Решим данную задачу с использованием средств электронных таблиц LibreOffice Calc.
Рассмотрим синтаксис функции ВПР.
ВПР (Vlookup, или вертикальный просмотр) - поисковая функция в электронных таблицах. Функция ВПР нужна, чтобы работать с большими объёмами данных - не нужно самостоятельно сопоставлять и переносить сотни наименований, функция делает это автоматически.
ВПР(искомое_значение;таблица;номер_столбца;[интервальный_просмотр])
1 Искомое_значение - значение, которое нужно искать.Это может быть значение (число, дата, текст) или ссылка на ячейку (содержащую искомое значение), или значение, возвращаемое какой-либо другой функцией Excel.
2 Таблица - два или более столбца с данными. Диапозон где мы будем искать нужные нам значения. Следует запомнить, функция ВПР всегда ищет значение в первом столбце диапазона, заданного в аргументе таблицы. В просматриваемом диапазоне могут быть различные данные, например, текст, даты, числа, логические значения. Регистр символов не учитывается функцией, то есть символы верхнего и нижнего регистра считаются одинаковыми.
3 Номер_столбца - номер столбца в заданном диапазоне, из которого будет возвращено значение, находящееся в найденной строке. Крайний левый столбец в заданном диапазоне - это 1, второй столбец - это 2, третий столбец - это 3 и так далее.
4 Интервальный_просмотр - условное значение, которое настроит, насколько точно сработает функция:
- Если нужно точное совпадение при поиске ВПР, вводим 0.
- Если нужно приближённое соответствие при поиске ВПР, вводим 1.
Вернемся к нашей задаче и рассмотрим ее решение в соответствии со следующим алгоритмом:
Разобьем последний столбец по разным столбцам: выделяем столбец С, данные, текст по столбцам, выбираем разделитель и ставим галочку - точка с запятой.
Добавляем строчку с нулевым процессом и заполняем в пустые ячейки в столбце D нулями (Если в Excel в качестве результата ссылки на пустую ячейку всегда возвращается число, то LibreOffice Calc может обрабатывать пустые ячейки иначе, что приводит к появлению значений #Н/Д в столбцах E-G).
Используем функцию ВПР(вертикальный просмотр) и прибавляем время выполнения процесса.
Тянем до последнего процесса, НО это мы получили данные только для процессов из столбца С, поэтому изменяем формулу и выбираем максимум из столбцов С и D:
Выбираем максимум в столбце Е, это и есть ответ.
5 способ (с помощью программы на Python)
Подходит для работы с очень большими массивами данных.
Создаем текстовый документ и копируем из электронных таблиц данные соблюдая табуляцию, то есть, между числами должно быть по 4 пробела. Далее используем шаблонный код на Python.
Выводы: Задание 22 посвящено параллельному программированию, технологиям организации многопроцессорных/многопоточных вычислений. Его нужно выполнять с использованием файла с информацией, необходимой для решения. Считаю, что в этом задании оптимально использовать электронные таблицы. Мне и моим ученикам наиболее близок способ 4 с использованием функции ВПР. Если разобраться как она работает, то этот способ решения занимает наименьшее время, что так актуально при решении ЕГЭ. Кроме того способ достаточно автоматизирован, что дает наименьшую вероятность ошибки.