Question

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

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

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

Accepted Answer

2

Answer

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

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

Для каждого процесса время окончания вычисляется по формуле:
$$	ext{finish}(i) = 	ext{duration}(i) + \max(	ext{finish}(j) 	ext{ для всех предшественников } j)$$

Если предшественников нет, процесс начинается в момент 0.

Вычислим для каждого процесса:
- Процесс 1: независимый, finish(1) = 4
- Процесс 2: независимый, finish(2) = 6
- Процесс 3: зависит от 1, 2; finish(3) = 3 + max(4, 6) = 9
- Процесс 4: независимый, finish(4) = 7
- Процесс 5: зависит от 2, 3; finish(5) = 4 + max(6, 9) = 13
- Процесс 6: зависит от 4, 5; finish(6) = 9 + max(7, 13) = 22
- Процесс 7: независимый, finish(7) = 3
- Процесс 8: зависит от 7; finish(8) = 5 + 3 = 8
- Процесс 9: зависит от 6; finish(9) = 2 + 22 = 24
- Процесс 10: зависит от 4; finish(10) = 6 + 7 = 13
- Процесс 11: зависит от 5, 6; finish(11) = 2 + max(13, 22) = 24
- Процесс 12: зависит от 7, 8; finish(12) = 7 + max(3, 8) = 15
- Процесс 13: независимый, finish(13) = 8
- Процесс 14: зависит от 5; finish(14) = 3 + 13 = 16
- Процесс 15: зависит от 3, 4; finish(15) = 8 + max(9, 7) = 17

**Шаг 2. Определение интервалов выполнения**

Для каждого процесса найдём время начала:
$$	ext{start}(i) = 	ext{finish}(i) - 	ext{duration}(i)$$

| Процесс | Начало | Окончание | Длительность |
|---------|--------|-----------|--------------|
| 1       | 0      | 4         | 4            |
| 2       | 0      | 6         | 6            |
| 3       | 6      | 9         | 3            |
| 4       | 0      | 7         | 7            |
| 5       | 9      | 13        | 4            |
| 6       | 13     | 22        | 9            |
| 7       | 0      | 3         | 3            |
| 8       | 3      | 8         | 5            |
| 9       | 22     | 24        | 2            |
| 10      | 7      | 13        | 6            |
| 11      | 22     | 24        | 2            |
| 12      | 8      | 15        | 7            |
| 13      | 0      | 8         | 8            |
| 14      | 13     | 16        | 3            |
| 15      | 9      | 17        | 8            |

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

Проанализируем временные интервалы. Независимые процессы (1, 2, 4, 7, 13) можно сдвинуть, чтобы максимизировать одновременное выполнение.

Оптимальное расписание:
- Процессы 1, 4, 7, 13 сдвигаются так, чтобы выполняться в интервале [22, 24].
- В этом интервале одновременно выполняются процессы 9 и 11 (оба длительностью 2 мс).

Максимальное количество процессов, выполняемых одновременно в оптимальном расписании, составляет 2 миллисекунды.

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

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

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

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