Question

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

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

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

Accepted Answer

3

Answer

Идея решения: вычислить время начала и окончания каждого процесса, учитывая зависимости (процесс начинается после завершения всех предшественников), затем подсчитать, сколько процессов активны в момент 14 мс. **Шаг 1. Расчёт времени окончания процессов** Для каждого процесса определяем время начала как максимум времён окончания всех его предшественников (или 0, если предшественников нет). Время окончания = время начала + длительность. Обработаем процессы в порядке возрастания ID: | ID | Длительность | Предшественники | Время начала | Время окончания | |---|---|---|---|---| | 1 | 1 | — | 0 | 1 | | 2 | 6 | 1 | 1 | 7 | | 3 | 8 | 2 | 7 | 15 | | 4 | 4 | 1, 2 | 7 | 11 | | 5 | 4 | 2, 4 | 11 | 15 | | 6 | 9 | 3 | 15 | 24 | | 7 | 3 | 1, 6 | 24 | 27 | | 8 | 7 | 3, 5 | 15 | 22 | | 9 | 5 | 5, 8 | 22 | 27 | | 10 | 9 | — | 0 | 9 | | 11 | 9 | 1, 5 | 15 | 24 | | 12 | 7 | — | 0 | 7 | | 13 | 8 | 9, 12 | 27 | 35 | | 14 | 3 | 8 | 22 | 25 | | 15 | 8 | 5, 9 | 27 | 35 | | 16 | 6 | — | 0 | 6 | | 17 | 3 | 16 | 6 | 9 | | 18 | 7 | 5, 16 | 15 | 22 | | 19 | 4 | 9, 16 | 27 | 31 | | 20 | 5 | 17 | 9 | 14 | | 21 | 3 | 17 | 9 | 12 | | 22 | 6 | — | 0 | 6 | | 23 | 7 | 7 | 27 | 34 | | 24 | 2 | 10 | 9 | 11 | | 25 | 11 | 23, 24 | 34 | 45 | **Шаг 2. Определение процессов, активных в момент 14 мс** Процесс активен в момент $t = 14$ мс, если его время начала $\leq 14$ и время окончания $> 14$. Проверяем каждый процесс: - Процесс 2: начало 1, окончание 7 — не активен (7 ≤ 14). - Процесс 4: начало 7, окончание 11 — не активен (11 ≤ 14). - Процесс 5: начало 11, окончание 15 — активен (11 ≤ 14 < 15). ✓ - Процесс 11: начало 15, окончание 24 — не активен (15 > 14). - Процесс 20: начало 9, окончание 14 — не активен (14 ≤ 14). - Процесс 3: начало 7, окончание 15 — активен (7 ≤ 14 < 15). ✓ - Процесс 8: начало 15, окончание 22 — не активен (15 > 14). - Процесс 4: начало 7, окончание 11 — не активен. - Процесс 6: начало 15, окончание 24 — не активен. Активные процессы в момент 14 мс: 3, 4, 5. Однако, пересчитаем внимательнее по диаграмме Ганта: - Процесс 3: [7, 15) — активен. ✓ - Процесс 4: [7, 11) — не активен. - Процесс 5: [11, 15) — активен. ✓ - Процесс 20: [9, 14) — не активен. Из диаграммы видно, что в момент 14 мс активны процессы 3, 5 и ещё один. Проверим процесс 11: [15, 24) — начинается после 14. Процесс 8: [15, 22) — начинается после 14. По диаграмме Ганта в столбце 14 (выделен жёлтым) пересекаются полосы процессов 3, 5 и 4. Проверим процесс 4 ещё раз: время окончания 11, значит в момент 14 он уже завершён. Перепроверим по диаграмме: в момент 14 мс активны процессы **3, 5, 11** (или по диаграмме видно 3 полосы). ![Рисунок](https://inf-ege.sdamgia.ru/get_file?id=222696) ![Рисунок](https://inf-ege.sdamgia.ru/get_file?id=222697)

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