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

Задания

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

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

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

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

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

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

Задание 22

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

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

f(104)  =  4 + f(103)  =  4 + 14  =  18;

f(105)  =  18 + f(103)  =  18 + 14  =  32;

f(106)  =  1 + f(104)  =  1 + 18  =  19;

f(108)  =  3 + f(107)  =  3 + 33  =  36;

f(110)  =  14 + f(109)  =  14 + 8  =  22;

f(111)  =  6 + f(109)  =  6 + 8  =  14;

f(113)  =  11 + f(111)  =  11 + 14  =  25;

f(103)  =  2 + max(f(101), f(102))  =  2 + 12  =  14;

f(107)  =  1 + max(f(105), f(106))  =  1 + 32  =  33;

#f(1112)  =  15 + max(f(110), f(111))  =  15 + 22  =  37.

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

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

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

Ответ: 5.

№ п/п	№ задания	Ответ
1	70549	5

Ключ