ЕГЭ по информатике 2023 - Задание 22 (Параллельные процессы)

Сегодня посмотрим новое 22 задание из ЕГЭ по информатике 2023.

Двадцать второе задание подобного типа появилось только в этом 2022 году. Из-за этого можно предположить, что на самом экзамене дадут условие похожее на демонстрационный вариант. Нет смысла давать усложнённые задачи, если ещё не все привыкли к этому заданию.

Это задание нетрудное, достаточно пару раз сделать, чтобы понять, как решать его.

В файле 22.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.

Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.

Типовой пример организации данных в файле:

В данном случае независимые процессы 1 и 2 могут выполняться параллельно, при этом процесс 1 завершится через 4 мс, а процесс 2 – через 3 мс с момента старта. Процесс 3 может начаться только после завершения обоих процессов 1 и 2, то есть, через 4 мс после старта. Он длится 1 мс и закончится через 4 + 1 = 5 мс после старта. Выполнение процесса 4 может начаться только после завершения процесса 3, то есть, через 5 мс. Он длится 7 мс, так что минимальное время завершения всех процессов равно 5 + 7 = 12 мс.

У нас есть различные процессы. Для каждого процесса известно время его выполнения (столбец B), а так же от каких процессов он зависит (столбец С).

Общее время выполнения процесса вычисляется следующим образом: процесс должен дождаться самый долгий процесс от которого он зависит, а потом выполнится сам.

Используем столбец D, чтобы вычислить окончательное время выполнения каждого процесса.

Важно помнить, что когда мы берём время процесса от которого зависит какой-то процесс, то мы должны взять это время из столбца D, т.е. уже окончательное время выполнения процесса.

Минимальное время, через которое завершится выполнение всей совокупности процессов будет равно времени самого медленного процесса.

В файле 22_2.xlsx содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно.

Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор процесса (ID), во второй строке таблицы  — время его выполнения в миллисекундах, в третьей строке перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.

Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.

Типовой пример организации данных в файле:

В данном случае независимые процессы 1 и 2 могут выполняться параллельно, при этом процесс 1 завершится через 4 мс, а процесс 2  — через 3 мс с момента старта. Процесс 3 может начаться только после завершения обоих процессов 1 и 2, то есть, через 4 мс после старта. Он длится 1 мс и закончится через 4 + 1 = 5 мс после старта. Выполнение процесса 4 может начаться только после завершения процесса 3, то есть, через 5 мс. Он длится 7 мс, так что минимальное время завершения всех процессов равно 5 + 7 = 12 мс.

Делаем аналогично прошлой задаче!

Самый медленный процесс длится 20 мс.

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно.

Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор процесса (ID), во второй строке таблицы – время его выполнения в миллисекундах, в третьей строке перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.

Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Здесь есть процессы, которые зависят от других процессов. В столбце D вычислим время для всех процессов, с учётом зависимости.

Если процесс зависит от двух процессов, то время ожидания будет равно самому медленному из этих процессов.

В столбце D пишем для каждой строчки: время процесса + время ожидания самого медленного процесса, от которого зависит этот процесс (если такие есть).

Получается такая картина:

Система завершит работу, когда завершится самый медленный процесс.

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно.

Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.

Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение четырёх процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Рекомендуется ужать ширину столбцов, чтобы было удобно работать. Сделать это можно так: выделяем нужные буквы столбцов, вызываем контекстное меню, потом ширина столбца и выбираем, к примеру, 5.

Справа от нашей таблицы построим "диаграмму". Для каждой строчки мы будем выделять ячейки каким-нибудь цветом, сколько длиться соответствующий процесс.

Если процесс зависит от какого-либо процесса, он должен дождаться его выполнения, а потом уже выполниться сам.

Если процесс зависит от нескольких процессов, то он должен дождаться самый долгих процесс, а потом выполниться сам.

Вот какой рисунок получается. Отметка ноль выбрана на границе D и E столбцов.

Теперь расставим единицы в жёлтые клеточки, а внизу подсчитаем сумму единиц для каждого столбца. Для ячейки E15 пропишем формулу:

Распространим эту формулу на всю строчку.

При таком подходе максимальный отрезок, когда будет выполняться 4 процесса одновременно будет равен 4.

Но в данной задаче не сказано, что все процессы должны завершиться за минимально возможное время. Поэтому мы можем смещать процессы по времени, если это возможно.

Здесь мы сдвинули четыре нижних процесса так, чтобы был максимальный отрезок с 4 процессами.

Длина максимального отрезка равна 7.