В файле 11.ods содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно.
Реши задание на изображении
Сверь числа и знаки с фото.
Задание № 7 В файле 11.ods содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0. Определите максимально возможное целочисленное неизвестное время выполнения процесса \(t\), при котором выполнение всей совокупности процессов может завершиться не более чем за 96 мс. Типовой пример организации данных в файле: [Таблица типового примера обрезана]
11.ods ID процесса B | Время выполнения процесса B (мс) | ID процесса (ов) A 1 | 37 | 4;9 2 | 38 | 4;14;15 3 | 18 | 15 4 | 17 | 14;15 5 | 11 | 15;17 6 | 19 | 0 7 | 16 | 9 8 | 4 | 6 9 | 4 | 13;19 10 | 16 | 0 11 | 24 | 6;15 12 | 6 | 10;13;18 13 | \(t\) | 10;14;15 14 | 31 | 0 15 | 27 | 0 16 | 33 | 6;15 17 | 27 | 10;14;15 18 | 24 | 6 19 | 10 | 10;15 20 | 3 | 10;15
Краткий ответ: \(t_{\max}=24\) мс.
Как рассуждать
Процессы могут идти параллельно, поэтому время нельзя просто складывать. Для каждого процесса считаем самое раннее время окончания: \[ F_B=d_B+\max F_A, \] где \(d_B\) — время выполнения процесса \(B\), а максимум берётся по всем процессам \(A\), от которых \(B\) зависит. Если зависимостей нет, процесс начинается с нуля.
Ключевые расчёты: \[ F_{13}=t+\max(16,31,27)=t+31. \] \[ F_{19}=27+10=37, \] \[ F_9=\max(F_{13},F_{19})+4. \] Процесс 4 зависит от 14 и 15: \[ F_4=31+17=48. \] Процесс 1 зависит от 4 и 9: \[ F_1=\max(F_4,F_9)+37. \]
Для максимального \(t\) важна цепочка \[ 14\to13\to9\to1. \] Её длина: \[ 31+t+4+37=t+72. \] Она не должна превышать 96 мс: \[ t+72\le 96, \] \[ t\le 24. \]
Проверка при \(t=24\): \[ F_{13}=55,\qquad F_9=59,\qquad F_1=59+37=96. \] Остальные процессы завершаются не позже 96 мс: например, процесс 2 — за 86 мс, процесс 7 — за 75 мс, процесс 5 — за 69 мс.
Если взять \(t=25\), то процесс 1 закончится за \[ 25+72=97\text{ мс}>96. \] Значит, максимальное целое значение: \[ \boxed{t=24\text{ мс}}. \]
