Задание 22 ЕГЭ по информатике: критический путь в графе процессов

Задание 22 ЕГЭ по информатике (КЕГЭ) — это файл с таблицей вычислительных процессов: у каждого процесса есть длительность и список процессов, от которых он зависит. Нужно определить время выполнения всей совокупности процессов, если независимые процессы разрешено запускать параллельно, а приостанавливать уже начатый процесс нельзя. Это повышенный уровень сложности, за верный ответ дают 1 первичный балл, а по обобщённому плану ФИПИ на задание отводится примерно 7 минут. Проверяемый элемент содержания — 1.1, формулировка в кодификаторе звучит так: «Построение математических моделей для решения практических задач. Архитектура современных компьютеров. Многопроцессорные системы». За формулировкой прячется простая математическая модель — граф зависимостей (DAG) и поиск в нём критического пути, а весь расчёт укладывается в одну формулу и десяток строк кода. В статье — теория, формула для электронной таблицы, рабочий код на Python и разбор двух реальных заданий из открытого банка ФИПИ с проверенными ответами. Потренироваться можно на реальных заданиях 22 ЕГЭ по информатике онлайн — с мгновенной проверкой ответа.

Что проверяет задание 22 ЕГЭ по информатике

По спецификации ЕГЭ 2026 года задание 22 проверяет умение строить математическую модель практической задачи, связанной с архитектурой компьютеров, а именно — с работой многопроцессорных систем. В кодификаторе (КЭС 1.1, код требования 1.1) это записано так: «Построение математических моделей для решения практических задач. Архитектура современных компьютеров. Многопроцессорные системы». За формулировкой стоит конкретный набор проверяемых умений:

Проекты КИМ ЕГЭ-2027 ФИПИ публикует в конце августа 2026 года, финальные версии — в ноябре. Все цифры в статье приведены по действующей спецификации ФИПИ 2026 года: структура работы не менялась с 2025 года. Когда выйдут документы 2027 года, их стоит свериться, но резких изменений в задании 22 никто не анонсировал.

Как выглядит формулировка

Условие задания 22 почти всегда описывает одну и ту же ситуацию: есть $N$ вычислительных процессов, каждый процесс $B$ может зависеть от одного или нескольких процессов $A$, а зависимые процессы обязаны выполняться строго последовательно после завершения всех процессов, от которых зависят. Вот реальная формулировка из открытого банка ФИПИ — в задании она приведена как «типовой пример организации данных в файле»:

Сам вопрос в конце формулировки — вот где начинаются варианты. Встречаются минимум три:

Как записывается ответ. Ответ на задание 22 — одно целое число (миллисекунды или значение t). Ответы на задания КЕГЭ вводятся в специальную форму на компьютере, без пробелов и лишних символов: только число, никаких единиц измерения и слова «мс». Файл с исходными данными нужно открывать в редакторе электронных таблиц — писать формулу для 10–20 процессов вручную на черновике долго и ненадёжно, а сам редактор считает мгновенно и без арифметических ошибок.

Теория: всё, что нужно для задания 22

=МАКС(D4) + B5

def parse_deps(cell):
    cell = cell.strip()
    if cell == "0" or cell == "":
        return []
    return [int(x) for x in cell.split(";")]

print(parse_deps("0"))          # []
print(parse_deps("101; 102"))   # [101, 102]

data = {
    1: (2, []),
    2: (5, [1]),
    3: (3, []),
    4: (2, [3]),
    5: (4, [2, 4]),
    6: (1, []),
    7: (1, [6]),
    8: (4, [7]),
    9: (2, [6]),
    10: (3, []),
    11: (5, []),
    12: (8, [8, 9, 10, 11]),
}

finish = {}

def calc(i):
    if i not in finish:
        deps_finish = [calc(j) for j in data[i][1]]
        start = max(deps_finish, default=0)
        finish[i] = start + data[i][0]
    return finish[i]

for i in data:
    calc(i)

print(max(finish.values()))

finish = {}
for i in sorted(data):
    dur, deps = data[i]
    finish[i] = max([finish[d] for d in deps], default=0) + dur

print(max(finish.values()))   # 14

order = []
visited = set()

def visit(i):
    if i not in visited:
        visited.add(i)
        for d in data[i][1]:
            visit(d)
        order.append(i)

for i in data:
    visit(i)

finish = {}
for i in order:
    dur, deps = data[i]
    finish[i] = max([finish[d] for d in deps], default=0) + dur

print(max(finish.values()))   # 14

Алгоритм решения задания 22

1. Откройте приложенный файл (*.ods) в редакторе электронных таблиц. Убедитесь, что видите три столбца: ID процесса, время выполнения, список зависимостей.
2. Дочитайте вопрос до конца. Проверьте, какой именно вариант вопроса: «минимальное время выполнения всей совокупности», «максимальное t при ограничении на общее время» или «максимальная продолжительность одновременной работы N процессов» — от этого зависит, что именно вы будете искать в итоговом столбце.
3. Добавьте столбец «Время завершения» рядом с данными и заполните первую строку формулой с функцией МАКС по ячейкам зависимостей плюс собственная длительность (для независимых процессов — просто длительность).
4. Протяните формулу вниз, убедившись, что зависимости в третьем столбце всегда ссылаются на уже заполненные строки. Если формула в какой-то строке выдаёт ошибку или подозрительно маленькое число — скорее всего, зависимость указывает на процесс ниже по таблице, и порядок нужно поправить.
5. Найдите максимум по всему столбцу «Время завершения» — отдельной ячейкой с формулой $\text{=МАКС(...)}$. Это и есть минимальное время выполнения всей совокупности процессов.
6. Если в задаче есть неизвестное t — переберите целые значения t (можно прямо в отдельном столбце или через подбор параметра), пока итоговый максимум не станет равен или меньше заданного порога, и возьмите наибольшее подходящее t.
7. Проверьте результат прикидкой: ответ не может быть меньше длительности самого длинного одиночного процесса и не может быть больше суммы длительностей всех процессов подряд. Запишите в форму ответа только число, без единиц измерения.

Примеры с разбором

Пример 1. Минимальное время выполнения всей совокупности процессов

F(1)  = 2                          (независимый)
F(2)  = F(1) + 5             = 2 + 5   = 7
F(3)  = 3                          (независимый)
F(4)  = F(3) + 2             = 3 + 2   = 5
F(5)  = max(F(2), F(4)) + 4  = max(7, 5) + 4 = 11
F(6)  = 1                          (независимый)
F(7)  = F(6) + 1             = 1 + 1   = 2
F(8)  = F(7) + 4             = 2 + 4   = 6
F(9)  = F(6) + 2             = 1 + 2   = 3
F(10) = 3                          (независимый)
F(11) = 5                          (независимый)
F(12) = max(F(8), F(9), F(10), F(11)) + 8
      = max(6, 3, 3, 5) + 8   = 6 + 8  = 14

data = {
    1: (2, []), 2: (5, [1]), 3: (3, []), 4: (2, [3]),
    5: (4, [2, 4]), 6: (1, []), 7: (1, [6]), 8: (4, [7]),
    9: (2, [6]), 10: (3, []), 11: (5, []), 12: (8, [8, 9, 10, 11]),
}
finish = {}
for i in sorted(data):
    dur, deps = data[i]
    finish[i] = max([finish[d] for d in deps], default=0) + dur
print(max(finish.values()))   # 14

Пример 2. Неизвестная длительность одного процесса

F(1)  = 4                          (независимый)
F(2)  = 3                          (независимый)
F(3)  = max(F(1), F(2)) + 2  = max(4, 3) + 2 = 6
F(4)  = F(3) + 3             = 6 + 3   = 9
F(5)  = t                    = 9                (неизвестный процесс)
F(6)  = max(F(4), F(5)) + 5  = max(9, 9) + 5 = 14
F(7)  = 5                          (независимый)
F(8)  = F(7) + 6             = 5 + 6   = 11
F(9)  = max(F(6), F(8)) + 5  = max(14, 11) + 5 = 19
F(10) = 12                         (независимый)
F(11) = F(10) + 2            = 12 + 2  = 14
F(12) = F(11) + 2            = 14 + 2  = 16

data = {
    1: (4, []), 2: (3, []), 3: (2, [1, 2]), 4: (3, [3]),
    5: (None, []), 6: (5, [4, 5]), 7: (5, []), 8: (6, [7]),
    9: (5, [6, 8]), 10: (12, []), 11: (2, [10]), 12: (2, [11]),
}

def total_time(t):
    finish = {}
    for i in sorted(data):
        dur, deps = data[i]
        dur = t if dur is None else dur
        finish[i] = max([finish[d] for d in deps], default=0) + dur
    return max(finish.values())

print(max(t for t in range(1, 100) if total_time(t) <= 19))   # 9

Типичные ошибки и ловушки

Как задание 22 связано с остальным экзаменом

КЕГЭ по информатике состоит из 27 заданий, все с кратким ответом, частей и развёрнутых ответов нет. Максимальный первичный балл — 29, на всю работу отводится 235 минут. Уровни сложности распределены так: базовый — 11 заданий, повышенный — 11, высокий — 5. Задание 22 занимает в этой структуре особое место:

• оно относится к разделу «Цифровая грамотность» кодификатора (КЭС 1.1) — вместе с заданием 13 (маска подсети) это всего 2 задания и 2 первичных балла в этом разделе;
• вместе с заданиями 3, 9 и 18 входит в четвёрку заданий, где приложен файл *.ods и требуется редактор электронных таблиц — готовить их удобно вместе, отрабатывая один и тот же навык работы с формулами;
• модель «граф зависимостей → критический путь» на КЕГЭ встречается только здесь: по графу ищут не количество путей и не сумму, а самый длинный путь по сумме весов;
• задание относится к повышенному уровню сложности — таких заданий 11 из 27, и задание 22 одно из самых «формульных» среди них: правильная формула сразу даёт верный ответ, в отличие от заданий с перебором вариантов.

План подготовки на 2 недели

Неделя 1 — ставим модель и формулу

День 1–2: разберите формулу $F(B) = \max(F(A_i)) + t(B)$ на маленьком наборе из 4–6 процессов (можно взять «типовой пример» из условия задания) и убедитесь, что понимаете, почему берётся именно максимум, а не сумма. День 3–5: решайте задания на 12–16 процессов, каждый раз выписывая столбец $F$ вручную на черновике, прежде чем переносить формулу в электронную таблицу. День 6–7: откройте реальные *.ods-файлы из тренажёра и потренируйтесь строить формулу МАКС именно в редакторе таблиц, а не на бумаге — это то умение, которое проверяется на экзамене.

Неделя 2 — варианты вопроса и скорость

День 1–3: отработайте вариант с неизвестным t — подстановка целых значений и проверка условия «не более […] мс». День 4–5: если встретится вариант «максимальная продолжительность одновременной работы N процессов», потренируйтесь сначала находить интервалы работы каждого процесса (старт и финиш), а затем считать, на каком отрезке одновременно активны ровно N из них. День 6–7: работайте на время — норматив ФИПИ 7 минут, из них большую часть должно занимать построение формулы, а не устный счёт. Проверьте себя в тренажёре на заданиях из банка ФИПИ.