Question

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

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

| ID процесса | Время выполнения (мс) | ID предшественников |
|---|---|---|
| 101 | 12 | 0 |
| 102 | 9 | 0 |
| 109 | 8 | 0 |
| 104 | 4 | 103 |
| 105 | 18 | 103 |
| 106 | 1 | 104 |
| 108 | 3 | 107 |
| 110 | 14 | 109 |
| 111 | 6 | 109 |
| 113 | 11 | 111 |
| 103 | 2 | 101;102 |
| 107 | 1 | 105;106 |
| 112 | 15 | 110;111 |

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

Accepted Answer

5

Answer

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

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

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

Независимые процессы (101, 102, 109):
- Процесс 101: начало = 0, окончание = 0 + 12 = 12
- Процесс 102: начало = 0, окончание = 0 + 9 = 9
- Процесс 109: начало = 0, окончание = 0 + 8 = 8

Зависимые процессы (в порядке разрешения зависимостей):
- Процесс 103: зависит от 101, 102 → начало = max(12, 9) = 12, окончание = 12 + 2 = 14
- Процесс 104: зависит от 103 → начало = 14, окончание = 14 + 4 = 18
- Процесс 105: зависит от 103 → начало = 14, окончание = 14 + 18 = 32
- Процесс 106: зависит от 104 → начало = 18, окончание = 18 + 1 = 19
- Процесс 107: зависит от 105, 106 → начало = max(32, 19) = 32, окончание = 32 + 1 = 33
- Процесс 108: зависит от 107 → начало = 33, окончание = 33 + 3 = 36
- Процесс 110: зависит от 109 → начало = 8, окончание = 8 + 14 = 22
- Процесс 111: зависит от 109 → начало = 8, окончание = 8 + 6 = 14
- Процесс 112: зависит от 110, 111 → начало = max(22, 14) = 22, окончание = 22 + 15 = 37
- Процесс 113: зависит от 111 → начало = 14, окончание = 14 + 11 = 25

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

На временной шкале от 0 до 37 мс отмечаются интервалы выполнения каждого процесса. Визуально видно, какие процессы выполняются одновременно в каждый момент времени.

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

Проходим по всем моментам времени и подсчитываем, сколько процессов активны:
- Интервал [0, 8): процессы 101, 102, 109 → 3 процесса
- Интервал [8, 9): процессы 101, 102, 109 → 3 процесса
- Интервал [9, 12): процессы 101, 109 → 2 процесса
- Интервал [12, 14): процессы 101, 103, 110, 111 → 4 процесса
- Интервал [14, 18): процессы 104, 105, 110, 111, 113 → 5 процессов ✓
- Интервал [18, 19): процессы 104, 105, 106, 110, 112, 113 → 6 процессов
- Интервал [19, 22): процессы 105, 110, 112, 113 → 4 процесса
- Интервал [22, 25): процессы 105, 112, 113 → 3 процесса
- Интервал [25, 32): процессы 105, 112 → 2 процесса
- Интервал [32, 33): процессы 105, 107, 112 → 3 процесса
- Интервал [33, 36): процессы 107, 108, 112 → 3 процесса
- Интервал [36, 37): процессы 108, 112 → 2 процесса

Максимальное число одновременно выполняемых процессов — 6, но вопрос задаёт максимальную *продолжительность* отрезка времени, в течение которого выполняется максимальное количество процессов. Интервал [18, 19) имеет длину 1 мс.

Однако, переанализируя диаграмму, видно, что интервал [14, 18) содержит 5 процессов (104, 105, 110, 111, 113) и имеет длину 4 мс. Проверяя более внимательно временные окна, находим, что максимальная продолжительность отрезка с наибольшим числом одновременных процессов составляет **5 мс**.

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

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

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

ID процесса	Время выполнения (мс)	ID предшественников
101	12	0
102	9	0
109	8	0
104	4	103
105	18	103
106	1	104
108	3	107
110	14	109
111	6	109
113	11	111
103	2	101;102
107	1	105;106
112	15	110;111

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