"В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что…
"В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0. Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно. Выполните задания, используя данные из файла ниже: №22_4.xlsx ЛИСТ 1 (переключение между листами находится внизу Excel)"
Класс, давай разберёмся по шагам. Это поможет и в твоём файле, и в ЕГЭ.
Подсказка (ключ к решению):
- Для каждого процесса i введи f(i) — время, к которому завершится этот процесс при оптимальном параллельном исполнении (то есть время его полного завершения).
- Правило: если у i есть зависимости D(i) = {j1, j2, ...}, то i может завершиться только после того, как завершатся все зависимости. Значит f(i) = t(i) + max{ f(j) | j ∈ D(i) }.
- Если зависимостей нет (D(i) = 0), то f(i) = t(i).
- Всё множество можно считать параллельно, поэтому итоговое время завершения всей совокупности — это max_i f(i).
Пример использования этой идеи на твоем примере (из правильного решения):
- для узла с несколькими зависимостями берём максимум времен завершения зависимостей, а не сумму.
- после того как посчитаешь f(i) для всех, ответ будет равен max_i f(i) (у тебя это и есть 43).
Если хочешь, могу пройтись по твоим данным из файла (№22_4.xlsx) и посчитать по шагам вместе. Скажи, хочешь пошаговый разбор по твоим зависимостям или примеры расчётов на нескольких узлах?
Пожалуйста, оцените мой ответ лайком или дизлайком.
