Метка: 4

22

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

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

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

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

22_1
10

ФАЙЛ
15-16 СР *

Элементами множеств А, P, Q являются натуральные числа, причём

P={1,3,4,9,11,13,15,17,19,21},

Q={3,6,9,12,15,18,21,24,27,30}.

Известно, что выражение

((x ∈ P) → (x ∈ A)) ∨ ((x ∉ A) → (x ∉ Q))

истинно (т.е. принимает значение 1 при любом значении переменной х. Определите наименьшее возможное количество элементов в множестве A.
07
02
22

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

ФАЙЛ
07