вентилятор
Удачи на экзаменах!

ЕГЭ по информатике 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



Задача (ДЕМО 2024)

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

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



ЕГЭ по информатике ДЕМО 2024 - задание 22

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


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


Скачать файл




Решение:

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


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


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


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


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


ЕГЭ по информатике ДЕМО 2024 - задание 22 (решение)

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


=СУММ(E2:E13)

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


ЕГЭ по информатике ДЕМО 2024 - задание 22 (решение 2)




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


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


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


ЕГЭ по информатике ДЕМО 2024 - задание 22 (решение 3)

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


Ответ: 7





31-12-2022 в 13:00:03






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


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

ОГЭ по информатике - Задание 15 (нестандартные задачи, часть 2)

Сегодня порешаем новую подборку нестандартных задач из 15 задания ОГЭ ...

Категория: Информатика  Подкатегория: ОГЭ
Дата: 01-05-2023 в 23:10:04 0


Комментарии:

Добрый день, а почему во втором задании в 12 процессе 20, а не 22, просто мы же вроде среди процессов 3;8 выбираем самый долгий(и это 15, а не 13) можете пояснить, пожалуйста.
Figh 13-03-2023 в 11:16:10

У 8-ого процесса 13, а не 15.
Калужский Александр 13-03-2023 в 11:25:52

Дошло, что мы берём только 3 и 8 процессы, а не промежуток между ними, спасибо.
Figh 13-03-2023 в 11:31:10

Спасибо большое за разбор! У меня несколько вопросов: 1) Минимальное время, через которое завершится выполнение всей совокупности процессов будет равно времени самого медленного процесса. Почему так? 2) Мы можем смещать процессы по времени, если это возможно. Как именно мы их смещаем и почему мы можем это делать?
Илья 10-01-2024 в 08:57:32

1) Представьте, что есть в гонке участвуют спортсмены. Вам нужно узнать минимальное время, через которое завершится гонка. Минимальное время будет определятся, когда мы дождёмся самого медленного участника. 2) Мы можем смещать процессы, т.к. не сказано, что все процессы начинают выполнятся одновременно. Как именно смещать, посмотрите видео в конце статьи.
Калужский Александр 10-01-2024 в 11:43:06

здравствуйте. Задание из демоверсии 2024. Почему, если его решать способом, как в двух предыдущих заданиях, то ответ получается 24?
эл 20-04-2024 в 01:29:52

В этой задаче другой вопрос)
Калужский Александр 20-04-2024 в 07:05:38



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



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


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




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