Задание 22 ЕГЭ по информатике: параллельные процессы
В двадцать втором задании ЕГЭ по информатике дана таблица процессов: у каждого длительность и список процессов, от которых он зависит. Процессы могут идти параллельно. Нужно найти минимальное время, за которое завершатся все. Решение: считаем для каждого процесса самое раннее время окончания.
Для 10–11 классов. Нумерация по проекту демоверсии ФИПИ на 2027 год.
Разбор примера
| Процесс | Длительность, мс | Зависит от |
|---|---|---|
| A | 3 | нет |
| B | 2 | A |
| C | 4 | A |
| D | 1 | B, C |
| E | 5 | нет |
| F | 2 | D, E |
Минимальное время
Найдите минимальное время выполнения всех процессов.
A заканчивается в 3, E в 5. B: 3 + 2 = 5, C: 3 + 4 = 7.
D начинается после B и C, то есть в 7, заканчивается в 8.
F начинается после D и E: max(8, 5) = 8, заканчивается в 10.
Ответ: 10
Код на Python
t = {'A': 3, 'B': 2, 'C': 4, 'D': 1, 'E': 5, 'F': 2} dep = {'A': [], 'B': ['A'], 'C': ['A'], 'D': ['B', 'C'], 'E': [], 'F': ['D', 'E']} end = {} def finish(p): if p not in end: end[p] = max([finish(q) for q in dep[p]], default=0) + t[p] return end[p] print(max(finish(p) for p in t))
На экзамене таблица дана в файле электронной таблицы, процессов десятки. Тот же расчёт можно сделать и формулами в самой таблице: столбец «окончание» равен максимуму окончаний зависимостей плюс длительность.
Проверь себя
- В примере выше: в какой момент может начаться процесс D? Ответ: 7.
- Если длительность E увеличить до 9, каким станет общее время? Ответ: 11.
Где теряют балл
- Сумма вместо максимума. Процесс ждёт самую позднюю из зависимостей, а не их сумму.
- Независимые процессы. Процесс без зависимостей начинается в момент 0, он тоже может определить общее время.
Как тренироваться
Похожая логика «пройти по зависимостям» в новом задании 23 на графы: задание 23. Все номера экзамена в статье ЕГЭ по информатике по номерам.
Разберём на занятии
Готовим к ОГЭ и ЕГЭ на живых занятиях в мини-группе до шести человек или один на один, с пробниками в формате экзамена и разбором каждой ошибки.
Первое занятие бесплатное: можно посмотреть формат вместе с ребёнком и решить, подходит ли он.
Частые вопросы
Бывает ли вопрос не про общее время?
Да, например, «какое наибольшее число процессов выполняется одновременно» или «на сколько можно задержать процесс без увеличения общего времени». Основа расчёта та же.
Сколько баллов?
Один первичный балл.