2 Краткая информация о задании 22

Краткая информация о задании 22

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

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

Проверяемые требования

Умение строить и анализировать модель вычислительного процесса; умение обрабатывать информацию в электронных таблицах (поиск, условные вычисления).

Средний процент выполнения по РФ

Год

% по РФ

2024

19 %

2025

34 %

2026

41,3 %

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

Уровень сложности: повышенный.

Примерное время выполнения: 10 минут.

💡 Важный момент про способ решения

Файл приходит в формате .ods, и задание 22 — из тех, где удобны электронные таблицы: время конца каждого процесса легко посчитать формулой ВПР + МАКС. Но есть тонкость: процессы могут зависеть от процессов с бóльшим номером, поэтому в Calc нужно либо включить итеративные вычисления, либо аккуратно расставить формулы.

Python решает эту проблему элегантно: рекурсивная функция с кэшированием сама посчитает время конца в любом порядке зависимостей. Поэтому дадим оба способа — таблицу как основной, Python как быстрый и надёжный.