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

Что проверяет задание

Задание 22 проверяет умение работать с моделью параллельных вычислений: по описанию совокупности процессов и их зависимостей нужно построить граф выполнения и найти минимальное время, за которое завершится вся работа. По сути это классическая задача сетевого планирования (метод критического пути), только оформленная в виде таблицы процессов. Проверяются три навыка: понимание понятия зависимости между процессами, умение правильно определить порядок вычислений (кто может стартовать сразу, а кто должен ждать) и умение аккуратно посчитать время начала и окончания каждого процесса без арифметических ошибок.

Важная особенность: задание работает с файлом данных (в реальном экзамене — приложенный файл, в тренировочных версиях — таблица в тексте). Поэтому дополнительно проверяется умение читать структурированные данные: таблицу с идентификаторами процессов, временем выполнения и списком зависимостей, разделённых знаком «;».

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

Типовая формулировка звучит так: дана совокупность из $N$ процессов, каждый из которых характеризуется идентификатором, временем выполнения в миллисекундах и списком идентификаторов процессов, от которых он зависит. Если список пуст (стоит значение 0), процесс независим и может стартовать в любой момент. Процесс B зависит от процесса A означает, что B не может начаться, пока не завершится A. Все независимые друг от друга процессы могут выполняться параллельно (предполагается неограниченное число процессоров). Требуется найти минимальное время, через которое завершится выполнение всей совокупности процессов.

Задание относится к практической части экзамена, оценивается в 1 первичный балл, уровень сложности — повышенный. Ответ — целое число (миллисекунды), вводится без единиц измерения. Ошибка в вычислении хотя бы на одном шаге даёт неверный итоговый ответ, поэтому здесь важна не скорость, а аккуратность.

Что нужно знать

• Процесс — задача с фиксированным временем выполнения $t$, которая может зависеть от других процессов.
• Зависимость: если B зависит от A, то A должен полностью завершиться до старта B. Такие процессы выполняются строго последовательно.
• Независимые процессы (без общих зависимостей друг от друга) выполняются параллельно — их времена не складываются, а идут «одновременно».
• Время начала процесса определяется формулой: $$T_{start}(B) = \max_{A \in \text{Dep}(B)} T_{finish}(A)$$ где $\text{Dep}(B)$ — множество процессов, от которых зависит B. Если B независим, $T_{start}(B) = 0$.
• Время завершения процесса: $$T_{finish}(B) = T_{start}(B) + t(B)$$
• Итоговый ответ задачи — максимальное время завершения среди всех процессов: $$T_{answer} = \max_{B} T_{finish}(B)$$
• Граф зависимостей процессов — это ориентированный ациклический граф (DAG): вершины — процессы, рёбра идут от A к B, если B зависит от A. Обрабатывать вершины нужно в порядке топологической сортировки: сначала процессы без зависимостей, затем те, чьи «родители» уже обработаны.
• Критический путь — самая длинная по суммарному времени цепочка последовательных зависимых процессов. Именно длина критического пути и есть минимальное время выполнения всей системы.

Методы решения

1. Метод построения графа и обхода по уровням. Строится граф: вершины — процессы, стрелки — зависимости. Сначала выделяются процессы без зависимостей (уровень 0), затем те, у кого все зависимости лежат в уже обработанных уровнях, и так далее. Пример: если процесс 3 зависит от 1 и 2, а 1 и 2 независимы, то 1 и 2 — уровень 0, а 3 — уровень 1. Это гарантирует, что при расчёте времени процесса все нужные значения уже известны.

2. Метод критического пути (аналог CPM). Для каждого процесса вычисляется самое раннее время старта и финиша, как в сетевом планировании. Итоговый ответ — время финиша самого «позднего» процесса. Мини-пример: пусть A(2 мс, независим) → B(3 мс, зависит от A) → C(1 мс, зависит от B). Тогда $T_{finish}(A)=2$, $T_{start}(B)=2$, $T_{finish}(B)=5$, $T_{start}(C)=5$, $T_{finish}(C)=6$. Ответ: 6 мс.

3. Табличный метод. Составляется рабочая таблица с колонками: ID, время выполнения, зависимости, $T_{start}$, $T_{finish}$. Строки заполняются построчно в порядке топологической сортировки. Такой способ снижает число ошибок при большом числе процессов (5 и более), так как все промежуточные значения видны наглядно.

4. Метод разбиения на независимые ветви. Если граф распадается на несколько независимых цепочек (нет общих процессов), можно посчитать время каждой ветви отдельно, а итоговый ответ — максимум среди ветвей. Пример: ветвь 1: A(4 мс) → B(2 мс) = 6 мс; ветвь 2: C(5 мс) — независимая, без продолжения. Ответ: $\max(6, 5) = 6$ мс.

5. Метод рекурсивного вычисления с «запоминанием» (мемоизация). При большом количестве зависимостей полезно считать время каждого процесса рекурсивно: чтобы найти $T_{finish}(B)$, сначала находим $T_{finish}$ всех процессов из списка зависимостей B, при этом уже посчитанные значения не пересчитываются повторно. Это удобно, если один и тот же процесс входит в зависимости нескольких других.

Алгоритм решения по шагам

1. Выписать из таблицы/файла для каждого процесса: ID, время выполнения $t$, список зависимостей (или 0, если процесс независим).
2. Найти все процессы без зависимостей — для них $T_{start} = 0$, $T_{finish} = t$.
3. Определить порядок обработки оставшихся процессов так, чтобы к моменту расчёта процесса B все процессы из его списка зависимостей уже были обработаны (топологическая сортировка).
4. Для каждого следующего процесса B вычислить: $$T_{start}(B) = \max_{A \in \text{Dep}(B)} T_{finish}(A), \qquad T_{finish}(B) = T_{start}(B) + t(B)$$
5. Повторять шаг 4, пока не будут обработаны все процессы.
6. Найти максимум среди всех $T_{finish}$ — это и есть минимальное время выполнения всей совокупности процессов.
7. Записать ответ как целое число миллисекунд.

Разбор примеров

Во всех трёх заданиях структура одинаковая: таблица с ID процесса, временем выполнения и списком зависимостей, разделённых «;». Разберём подробно опорный (типовой) пример, который используется как образец формата данных, а затем покажем, как тот же алгоритм применяется к более крупным файлам, дающим итоговые ответы 17, 24 и 34 мс.

Опорный пример. Таблица содержит четыре процесса:

• Процесс 1: время 4 мс, зависимостей нет (0).
• Процесс 2: время 3 мс, зависимостей нет (0).
• Процесс 3: время 1 мс, зависит от процессов 1 и 2.
• Процесс 4: время 7 мс, зависит от процесса 3.

Шаг 1. Процессы 1 и 2 независимы, поэтому выполняются параллельно, начиная с момента 0. $$T_{finish}(1) = 0 + 4 = 4, \qquad T_{finish}(2) = 0 + 3 = 3$$

Шаг 2. Процесс 3 зависит от обоих — 1 и 2. Он может начаться только после завершения самого долгого из них: $$T_{start}(3) = \max(4, 3) = 4$$ $$T_{finish}(3) = 4 + 1 = 5$$

Шаг 3. Процесс 4 зависит только от процесса 3: $$T_{start}(4) = T_{finish}(3) = 5$$ $$T_{finish}(4) = 5 + 7 = 12$$

Шаг 4. Итоговое время — максимум среди всех $T_{finish}$: $\max(4, 3, 5, 12) = 12$. Минимальное время выполнения всей совокупности процессов равно 12 мс.

Этот пример показывает главную идею: параллельные ветви не складываются, а «сливаются» в точке, где начинается зависимый процесс, причём время старта такого процесса определяется самой долгой из предшествующих веток.

Пример с большим числом процессов (ответ 17 мс). В реальном файле экзаменационного варианта количество процессов больше — обычно от 8 до 15. Алгоритм не меняется: сначала выделяются все независимые процессы (у них зависимость «0»), для них время финиша равно времени выполнения. Затем в порядке топологической сортировки обрабатываются процессы с одной или несколькими зависимостями — для каждого берётся максимум времени финиша среди «родителей» и добавляется собственное время выполнения. Из-за большего числа веток и более длинных цепочек критический путь получается длиннее — в данном случае он составляет 17 мс. Ключевой момент решения — не ошибиться, определяя, какие процессы уже полностью «готовы» к обработке (все их зависимости уже посчитаны).

Пример с ответом 24 мс. Здесь граф зависимостей содержит более длинную цепочку последовательных процессов либо несколько уровней ветвления, где итоговый критический путь проходит не через самую «тяжёлую» по времени отдельную задачу, а через цепочку из нескольких процессов среднего времени выполнения, суммарно превышающую другие пути. При решении важно построить таблицу $T_{start}/T_{finish}$ для каждого процесса и не забыть, что путь с наибольшим числом звеньев не всегда самый длинный по времени — нужно именно сравнивать суммарное время, а не количество процессов в цепочке.

Пример с ответом 34 мс. Аналогичная структура, но с процессами большего времени выполнения на критическом пути. Решение выполняется тем же алгоритмом: выписываются все зависимости, определяется топологический порядок, последовательно вычисляются $T_{start}$ и $T_{finish}$, а итоговый ответ — максимум по всем процессам. Такой пример хорошо иллюстрирует, что рост числа процессов в файле не меняет метод решения — меняется только объём вычислений, поэтому здесь особенно важно использовать табличную форму записи, чтобы не потерять промежуточные значения.

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

• Сложение времени независимых процессов вместо взятия максимума — частая ошибка, приводящая к завышенному ответу.
• Неверное направление зависимости: если B зависит от A, то именно A выполняется первым, а не наоборот.
• Учёт только одной зависимости из списка, когда их несколько (нужно брать максимум времени финиша среди всех процессов из списка, а не первого по порядку).
• Нарушение порядка обработки: попытка посчитать время процесса раньше, чем найдены значения всех его предшественников, из-за чего используются нулевые или неверные промежуточные данные.
• Итоговый ответ берётся не как максимум по всем процессам, а как время финиша последнего процесса в таблице — это неверно, если граф ветвится и есть несколько «конечных» процессов.
• Ошибки при разборе данных из файла: перепутаны столбцы (время и ID), неправильно разделены значения по «;», не учтён случай «0» как признак отсутствия зависимостей.
• Арифметические ошибки при большом количестве процессов из-за отсутствия промежуточной таблицы — рекомендуется всегда фиксировать $T_{start}$ и $T_{finish}$ для каждого процесса письменно.

Как готовиться

Основной способ подготовки — набить руку на нескольких вариантах с разным количеством процессов и разной структурой графа (цепочки, ветвления, слияния нескольких веток в одну точку). Полезно всегда строить промежуточную таблицу с колонками ID, время, зависимости, $T_{start}$, $T_{finish}$ — это исключает пропуск шагов и путаницу в порядке обработки. Стоит потренироваться определять топологический порядок «на глаз»: сначала находить все процессы с зависимостью 0, затем те, чьи зависимости уже отмечены как обработанные, и так далее, пока не закончится список. При работе с реальными файлами формата ЕГЭ полезно освоить работу с электронными таблицами (Excel, LibreOffice Calc) — можно автоматизировать вычисление $T_{start}$ и $T_{finish}$ формулами, что резко снижает число ошибок и экономит время на экзамене. Рекомендуется решить не менее 10–15 вариантов такого задания с разным числом процессов, чтобы отработать аккуратность и скорость построения графа зависимостей.