ЕГЭ по информатике 2026, задание 22: параллельные процессы

Задание 22 — повышенный уровень, 1 балл. Строят модель процессов: кто от кого зависит и сколько длится. Это про независимые процессы, которые могут идти параллельно, а не про очередь «строго по одному».

Файл 2026 — `.ods`. Колонки обычно такие: идентификатор, время выполнения, номера процессов, которые должны завершиться раньше. Пустая ячейка зависимостей значит, что процесс можно начать сразу.

Конспект

Время старта процесса — 0, если предшественников нет, иначе максимум времён окончания предшественников. Окончание = старт + длительность.

Нужное в ответе бывает разным:

• момент окончания заданного процесса;
• сколько процессов выполняются в момент T, то есть старт ≤ T < окончание, либо с другими границами — смотрите «в момент» и «в течение»;
• минимальное время всей работы — максимум окончаний;
• сколько процессов не зависят друг от друга.

ФИПИ предупреждает: самая длинная цепочка по числу процессов не обязана быть самой длинной по времени. Ищите критический путь по сумме длительностей, а не по количеству звеньев.

Процесс не ждёт «всех, кто в таблице ниже». Он ждёт только перечисленных предшественников. Независимые процессы стартуют одновременно, если хватает процессоров. Если число процессоров ограничено, это уже другая модель: тогда нельзя запустить больше, чем есть процессоров, даже если зависимости позволяют. В большинстве вариантов процессоров хватает, ограничение — только зависимости. Прочитайте, есть ли лимит.

Время обычно целое. Если процесс длится 5 и стартовал в 0, в момент 5 он уже закончился, если интервал полуоткрытый. Условие «выполняется в момент t» надо сопоставить с тем, включается ли правый конец. На черновике нарисуйте отрезок для двух процессов и проверьте граничный момент, прежде чем писать формулу.

Шаблон на Python

# id -> (duration, list of prerequisite ids)
procs = {
    1: (4, []),
    2: (7, []),
    3: (3, [1, 2]),
    4: (2, [3]),
}

start = {}
finish = {}

def calc(i):
    if i in finish:
        return finish[i]
    dur, prev = procs[i]
    start[i] = max((calc(p) for p in prev), default=0)
    finish[i] = start[i] + dur
    return finish[i]

for i in procs:
    calc(i)

print(max(finish.values()))          # время всей работы
T = 5
running = [i for i in procs if start[i] <= T < finish[i]]
print(len(running), running)
print(finish[4])

Если идентификаторы в файле идут не по порядку и есть ссылка вперёд, рекурсия это переносит. Цикл зависимостей в условии не встречается. Если программа зациклилась, в данные попала ошибка чтения, не добавляйте setrecursionlimit вместо проверки файла.

Типичные ошибки

• Время цепочки сложили как число процессов.
• Процесс стартует после суммы предшественников, а не после максимума.
• В момент T посчитан процесс, который в этот момент только что закончился.
• Пустую ячейку прочитали как ноль и приняли ноль за идентификатор процесса.