Задания № 13, 16 · ЕГЭ

Зависимости между задачами

Как зависимости задают допустимый порядок выполнения работ

2 мин чтенияСложность: Обновлено 29 сентября 2026

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

Зависимость между задачами

Зависимость между задачами — это отношение, при котором одна задача не может начаться или завершиться, пока не выполнено условие, связанное с другой задачей. Обычно зависимость записывают как направленную связь: если задача \(A\) должна быть выполнена раньше задачи \(B\), пишут \(A \rightarrow B\). Задача \(A\) называется предшественником, а задача \(B\) — последующей.

В параллельных задачах часть работ может выполняться одновременно, но только если между ними нет зависимости. Например, чтение двух независимых файлов можно начать одновременно, а вычисление суммы результатов — только после завершения обоих чтений.

Как представить зависимости

Удобно изображать задачи вершинами ориентированного графа, а зависимости — стрелками. Такая схема является частью параллельных вычислений. Если есть путь \(A \rightarrow B \rightarrow C\), то \(A\) должна закончиться раньше \(B\), а \(B\) — раньше \(C\). Следовательно, \(A\) также предшествует \(C\).

\[A \rightarrow B \quad \Longrightarrow \quad t_{\text{start}}(B) \ge t_{\text{finish}}(A)\]

Если у задачи несколько предшественников, она начинается только после завершения всех обязательных предшественников. Если у двух задач нет пути друг к другу, их обычно можно выполнять параллельно, если хватает вычислительных ресурсов.

№

Пример

Пусть нужно: \(A\) — скачать данные, \(B\) — обработать данные, \(C\) — подготовить отчёт, \(D\) — отправить отчёт. Зависимости таковы: \(A \rightarrow B\), \(B \rightarrow D\), \(C \rightarrow D\). Задачи \(A\) и \(C\) можно выполнять одновременно. Задача \(D\) начнётся только после завершения \(B\) и \(C\).

Не путайте

Зависимость не означает, что задачи обязательно выполняются сразу одна за другой. Между ними может быть ожидание или другие независимые работы. Кроме того, зависимость отличается от расписания параллельных вычислений: зависимость задаёт ограничения, а расписание выбирает конкретные моменты запуска.

Проверка

Есть зависимости \(A \rightarrow C\) и \(B \rightarrow C\). Какие задачи можно начать одновременно в самом начале?

Главное за минуту

Главное

Зависимость \(A \rightarrow B\) означает, что задача \(A\) должна завершиться до начала задачи \(B\).
Независимые задачи можно выполнять параллельно, а задача с несколькими предшественниками ждёт завершения всех обязательных работ.
Зависимости задают допустимые ограничения, а конкретный порядок и время запуска определяет расписание.