Задание 22 ЕГЭ по информатике 2023 года — задача повышенного уровня сложности, на решение которой отводится около 7 минут. В отличие от аналогичного задания 2022 года, основанного на анализе алгоритмов, задание 2023 года полностью переработано и посвящено построению математических моделей для решения практических задач. Несмотря на сложную формулировку, задание решается достаточно просто.
Условие задачи
Файл содержит информацию о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Процесс B зависит от процесса A, если для выполнения B необходимы результаты выполнения A. В этом случае процессы выполняются последовательно. Информация о процессах представлена в виде таблицы:
| ID процесса | Время выполнения (мс) | Зависимые процессы |
|---|---|---|
| 1 | 4 | |
| 2 | 3 | |
| 3 | 1 | 1; 2 |
Первый столбец таблицы содержит идентификатор процесса (ID). Второй столбец — время выполнения процесса в миллисекундах. Третий столбец — список ID процессов, от которых зависит данный процесс (через точку с запятой). Если процесс независим, указано пустое значение.
Задача: определить минимальное время завершения выполнения всей совокупности процессов при условии, что независимые процессы могут выполняться параллельно.
Решение задачи
Рассмотрим процессы:
- Процесс 1 выполняется за 4 миллисекунды и не зависит от других процессов.
- Процесс 2 выполняется за 3 миллисекунды и не зависит от других процессов.
- Процесс 3 выполняется за 1 миллисекунду и зависит от процессов 1 и 2.
Так как процессы 1 и 2 независимы, они выполняются параллельно. Время выполнения параллельных процессов определяется максимальным временем выполнения одного из них. В данном случае, максимальное время — 4 миллисекунды.
Время выполнения процесса 3 равно сумме его собственного времени выполнения (1 мс) и времени выполнения зависимых процессов (4 мс). Итоговое время для процесса 3: 1 + 4 = 5 мс.
Для решения задачи с большим количеством строк вручную необходимо разработать универсальный алгоритм.
Обработка данных в Excel
Для удобства обработки данных в Excel необходимо разделить значения в столбце «Зависимые процессы» на отдельные ячейки. Это можно сделать, используя функцию «Текст по столбцам» с разделителем «Точка с запятой».
Формула для расчета времени выполнения
Для автоматического расчета времени выполнения каждого процесса воспользуемся формулой в Excel, используя функции ЕСЛИ, ВПР и МАКС:
=ЕСЛИ(C2=0;B2;ЕСЛИ(D2="";B2+ВПР(C2;$A$2:$E$4;5;0);МАКС(B2+ВПР(C2;$A$2:$E$4;5;0);B2+ВПР(D2;$A$2:$E$4;5;0))))
- ЕСЛИ(C2=0;B2; …): Если процесс независим (C2 пусто), время выполнения равно времени из столбца B.
- ЕСЛИ(D2="";B2+ВПР(…);МАКС(…)): Если зависимость от одного процесса (D2 пусто), время выполнения — сумма собственного времени и времени зависимого процесса (ВПР). Если зависимость от двух процессов, время выполнения — максимум из двух сумм.
- ВПР(C2;$A$2:$E$4;5;0): Функция ВПР находит время выполнения зависимого процесса.
После применения формулы и растягивания на все строки, максимальное значение в полученном столбце будет определять минимальное время завершения всех процессов. Для удобства можно использовать функцию МАКС для определения этого максимального значения.
Задание 22 ЕГЭ по информатике 2023 года, несмотря на кажущуюся сложность, решается с помощью построения математической модели и использования возможностей табличного процессора Excel. Предложенная формула позволяет автоматизировать расчет времени выполнения процессов, что особенно полезно при большом количестве данных. Правильный ответ в демо-версии — 5. (Исправлено предполагаемое значение ответа)