Логотип
вентилятор
Волк

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



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


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


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





Задача (Классическая)

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


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


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


ЕГЭ по информатике - Задание 22

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





Решение:

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


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


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


ЕГЭ по информатике - Задание 22 (Решение)

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


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


Ответ: 44



Задача (Закрепление)

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


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


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


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


ЕГЭ по информатике - Задание 22 (Закрепление)

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




Решение:

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


ЕГЭ по информатике - Задание 22 (Закрепление, Решение)

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


Ответ: 20



Задание 22 (Демо 2022)

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

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


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

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

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


Скачать файлы




Решение:

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


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


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


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


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

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


Ответ: 17




31-12-2022 в 13:00:03







Поддержать сайт:

Похожая статья:

ЕГЭ по информатике 2021 - Задание 12 (Укрощение Робота)

Продолжаем подготовку к ЕГЭ по информатике нового формата 2021, и сего...

Категория: ЕГЭ  Подкатегория: -
Дата: 04-10-2020 в 15:31:54 1



Оставить коментарий:



Напишите email, чтобы получать сообщения о новых комментариях (необязательно):


Задача против робота. Расположите картинки горизонтально: