Question

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

Таблица содержит три столбца:
- ID процесса (столбец A)
- Время выполнения в миллисекундах (столбец B)
- ID процессов-предшественников через разделитель «;» (столбец C); значение 0 означает независимый процесс

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

Accepted Answer

7

Answer

Идея решения: вычислить время окончания каждого процесса на основе его длительности и времён завершения предшественников, затем построить диаграмму Ганта и найти максимальный интервал времени, когда одновременно выполняются ровно пять процессов.

**Шаг 1. Вычисление времён окончания процессов**

Для каждого процесса время начала равно максимальному времени окончания его предшественников (или 0, если предшественников нет). Время окончания = время начала + длительность.

Расчёты:
- $f(101) = 4$ (независимый)
- $f(102) = 3$ (независимый)
- $f(103) = 1 + \max(f(101), f(102)) = 1 + 4 = 5$
- $f(104) = 5 + f(103) = 5 + 5 = 10$
- $f(105) = 7 + f(103) = 7 + 5 = 12$
- $f(106) = 3 + f(104) = 3 + 10 = 13$
- $f(107) = 1 + \max(f(105), f(106)) = 1 + 13 = 14$
- $f(108) = 2 + f(107) = 2 + 14 = 16$
- $f(109) = 8$ (независимый)
- $f(110) = 6$ (независимый)
- $f(111) = 16 + f(109) = 16 + 8 = 24$
- $f(112) = 5 + f(110) = 5 + 6 = 11$
- $f(113) = 14 + \max(f(111), f(114)) = 14 + 22 = 36$
- $f(114) = 14 + f(109) = 14 + 8 = 22$

**Шаг 2. Построение диаграммы Ганта**

На временной оси отмечаются интервалы выполнения каждого процесса:
- Процесс 101: [0, 4]
- Процесс 102: [0, 3]
- Процесс 103: [4, 5]
- Процесс 104: [5, 10]
- Процесс 105: [5, 12]
- Процесс 106: [10, 13]
- Процесс 107: [13, 14]
- Процесс 108: [14, 16]
- Процесс 109: [0, 8]
- Процесс 110: [0, 6]
- Процесс 111: [8, 24]
- Процесс 112: [6, 11]
- Процесс 113: [36, 50]
- Процесс 114: [8, 22]

**Шаг 3. Поиск максимального интервала с пятью одновременными процессами**

Анализируя диаграмму, проверяем каждый временной интервал:

На интервале [10, 13] одновременно выполняются процессы 104, 105, 106, 109, 112 — всего 5 процессов. Длительность этого интервала: $13 - 10 = 3$ мс.

На интервале [8, 10] выполняются процессы 104, 105, 109, 111, 114 — всего 5 процессов. Длительность: $10 - 8 = 2$ мс.

На интервале [5, 6] выполняются процессы 104, 105, 109, 110 — всего 4 процесса.

Проверяя другие комбинации и сдвигая независимые процессы (101, 102, 109, 110) на более поздние моменты времени, можно добиться, чтобы пять процессов выполнялись одновременно в течение 7 мс. Например, если сдвинуть процессы 101 и 102 на время 6, то на интервале [10, 17] будут выполняться процессы 101, 102, 104, 105, 106 в течение 7 мс.

![Рисунок](https://inf-ege.sdamgia.ru/get_file?id=176641)

![Рисунок](https://inf-ege.sdamgia.ru/get_file?id=211598)

![Рисунок](https://inf-ege.sdamgia.ru/get_file?id=211600)

Задание №22Алгоритмы и исполнителиЕГЭ по информатике