Задача к ЕГЭ по информатике на тему «задачи под вебы» №55

Задача из ДЕМО-2024

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

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

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


ID процесса $B$	Время выполнения процесса $B$	ID процесса(ов) А

1	4	0

2	3	0

3	1	1;2

4	7	3

Решение (способ 1):

Решим задачу в файле 22-0.xls.

Построим диаграмму Ганта: все независимые процессы начинаем с 1 мс, зависимые процессы начинаем после выполнения процессов, от которых они зависят.

Чтобы ячейки подсвечивались, перейдем в Условное форматирование, Правила выделения ячеек, Равно 1.

В ячейку $E14$ запишем формулу

= СУ ММ (E2 : E13)

и растянем ее вправо до столбца $U$ .

Выделим строку 14, снова перейдем в Условное форматирование, Правила выделения ячеек, Равно 4.

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

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

Решение (способ 2):

Вернемся на лист с решением примера 1. Теперь в столбце $H$ будем записывать время начала выполнения процесса с помощью формулы

= М АК С(E2 : F2)+ 1

А в столбце $I$ – время окончания процесса:

= H2 + B2 − 1

Далее в ячейке $J1$ пишем заголовок «Сдвиг», а с ячейки $K1$ проставляем цифры от одного, по порядку.

В ячейке $K2$ пишем формулу

= ЕСЛ И(И (K$1 >= $H2;K$1 <= $I2);1;” ”)

растягиваем до 13й строки и вправо. Получили диаграмму Ганта:

В ячейке $K14$ найдем сумму по формуле

= СУ ММ (K2 : K13 )

и растянем формулу вправо.

Изменим формулу для общего времени, добавив сдвиг:

= М АК С(E2 : F2)+ B2 + J2

Теперь, если в столбец $J$ написать время сдвига, все процессы автоматически подвинутся.

Ответ: 7