Question

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

Информация представлена в виде таблицы:
- первый столбец — идентификатор процесса (ID);
- второй столбец — время выполнения в миллисекундах;
- третий столбец — ID процессов-предшественников, разделённые «;» (если процесс независимый, указано 0).

| ID процесса | Время выполнения (мс) | ID предшественников |
|---|---|---|
| 1 | 3 | 0 |
| 2 | 4 | 1 |
| 3 | 2 | 2; 4 |
| 4 | 5 | 0 |
| 5 | 8 | 1; 4 |
| 6 | 3 | 1 |

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

Accepted Answer

34

Answer

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

**Шаг 1.** Разделяем столбец с предшественниками по разделителю «;» в отдельные столбцы (D, E и т. д.).

**Шаг 2.** Добавляем нулевой процесс (строка 2) с нулевой длительностью и нулевыми предшественниками. Это упрощает вычисления формул.

**Шаг 3.** Создаём два вспомогательных столбца:
- столбец F — «начало» (время начала процесса);
- столбец G — «конец» (время завершения процесса).

**Шаг 4.** В ячейку G3 вводим формулу для времени завершения:

```
=F3+B3
```

Копируем формулу вниз до конца списка. Время завершения = время начала + длительность.

**Шаг 5.** В ячейку F3 вводим формулу для времени начала:

```
=МАКС(ВПР(C3;A:G;7;0);ВПР(D3;A:G;7;0);ВПР(E3;A:G;7;0))
```

Эта формула ищет время завершения (столбец G, 7-й столбец в диапазоне A:G) каждого предшественника и берёт максимум. Копируем формулу вниз.

**Шаг 6.** Находим максимальное значение в столбце G — это минимальное время завершения всех процессов.

Из таблицы видно, что максимальное значение в столбце «конец» равно 34 мс.

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

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

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

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

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