Question

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

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

Типовой пример:

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

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

Accepted Answer

17

Answer

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

Рассмотрим логику на примере из условия:

- Процессы 1 и 2 независимые, завершаются на 4 и 3 мс соответственно.
- Процесс 3 зависит от 1 и 2, поэтому может начаться только после завершения обоих: $\max(4, 3) + 1 = 5$ мс.
- Процесс 4 зависит от 3: $5 + 7 = 12$ мс.

Применим этот подход к данным из файла:

| ID | Время (мс) | Предшественники | Завершение (мс) |
|---|---|---|---|
| 1 | 4 | 0 | 4 |
| 2 | 3 | 0 | 3 |
| 9 | 7 | 0 | 7 |
| 10 | 8 | 0 | 8 |
| 3 | 1 | 1; 2 | $\max(4, 3) + 1 = 5$ |
| 5 | 6 | 3 | $5 + 6 = 11$ |
| 4 | 7 | 3 | $5 + 7 = 12$ |
| 11 | 6 | 9 | $7 + 6 = 13$ |
| 12 | 6 | 10 | $8 + 6 = 14$ |
| 6 | 3 | 5 | $11 + 3 = 14$ |
| 7 | 1 | 4; 6 | $\max(12, 14) + 1 = 15$ |
| 8 | 2 | 7 | $15 + 2 = 17$ |

Максимальное время завершения среди всех процессов — 17 мс.

Реализация на Python:

```python
f = open("22.txt").read().split("
")
m = {}

for i in f:
    s = i.split()
    if s[2] == '0':
        m[s[0]] = int(s[1])
    else:
        w = s[2].split(";")
        sp = []
        for j in w:
            j = j.replace(" ", "")
            sp.append(int(m[j]))
        m[s[0]] = int(s[1]) + max(sp)

print(max(m.values()))
```

Программа читает данные из файла, для каждого процесса определяет время завершения и выводит максимальное значение.

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