РЕШУ ЕГЭ — информатика

Задания

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

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

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

ID процесса B	Время выполнения процесса B (мс)	ID процесса(ов) A
1	4	0
2	3	0
3	1	1; 2
4	7	3

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

Выполните задания, используя данные из файла ниже:

Задание 22

Решение. Отсортируем данные в таблице так, чтобы все независимые процессы оказались в начале таблицы и любой процесс был расположен после всех процессов, от которых он зависит. Также в таблицу добавим столбец «Время окончания процесса» и запишем туда длительности независимых процессов.

A	B	C	D
ID процесса B	Время выполнения процесса B (мс)	ID процессов A	Время окончания процесса
1	4	0	4
2	3	0	3
9	7	0	7
10	8	0	8
4	7	3
5	6	3
6	2	5
8	2	7
11	6	9
12	6	10
3	5	1;2
7	5	4;6

Далее рассчитаем время выполнения оставшихся процессов:

f(4)  =  7 + f(3)  =  7 + 9  =  16;

f(5)  =  6 + f(3)  =  6 + 9  =  15;

f(6)  =  2 + f(5)  =  2 + 15  =  17;

f(8)  =  2 + f(7)  =  2 + 22  =  24;

f(11)  =  6 + f(9)  =  6 + 7  =  13;

f(12)  =  6 + f(10)  =  6 + 8  =  14;

f(3)  =  5 + max(f(1), f(2))  =  5 + 4  =  9;

f(7)  =  5 + max(f(4), f(6))  =  5 + 17  =  22.

A	B	C	D
ID процесса B	Время выполнения процесса B (мс)	ID процессов A	Время окончания процесса
1	4	0	4
2	3	0	3
9	7	0	7
10	8	0	8
4	7	3	16
5	6	3	15
6	2	5	17
8	2	7	24
11	6	9	13
12	6	10	14
3	5	1;2	9
7	5	4;6	22

Построим диаграмму выполнения каждого процесса и рассмотрим когда могут выполняться одновременно 4 процесса.

Заметим, что первые четыре процесса можно начинать в любой промежуток времени, так как они независимы. Тогда, если сдвинуть время начала процессов 9 и 10 (новое время обозначено красным), можно получить максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение четырёх процессов:

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

Ответ: 7.

№ п/п	№ задания	Ответ
1	60264	7

Ключ