6 Шпаргалка по заданию 22

Шпаргалка по заданию 22

Модель (одна на все вопросы)

1. Начало процесса = МАКС(концы зависимостей); у независимого — 0.

2. Конец процесса = начало + время выполнения.

3. Процесс с началом s и временем d занимает мс (s+1) … (s+d), конец = s+d.

Формулы электронных таблиц

=ВПР(C2; $A:$G; 7; 0) # подтянуть конец процесса-зависимости

=МАКС(E2:F2) + B2              # конец процесса = макс(концы зависимостей) + время

=МАКС(G:G) # минимальное время всей совокупности

=СЧЁТЕСЛИ(G:G; "<=17") # сколько завершится за первые 17 мс

=СЧЁТЕСЛИ(H:H; ">=8")          # сколько стартует не ранее 8-й мс (H — номер мс начала)

Python (рекурсия с кэшем)

@lru_cache(None)
def finish(p):
    if not deps[p]: return dur[p]
    return max(finish(a) for a in deps[p]) + dur[p]
# начало = finish(p) - dur[p]

Вопрос → что считать

Мин. время совокупности → МАКС(концы)

Завершится за первые T мс → сколько концов <= T

Стартует не ранее T-й мс → сколько (начало + 1) >= T

Идёт параллельно на T-й мс → сколько процессов: начало < T <= конец

Макс. отрезок с N одновременными →  лента по мс, самый длинный ряд, где работающих >= N

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

1. Забыл про несколько зависимостей. Начало — это МАКС по ВСЕМ зависимостям, а не по первой.

2. Не включил итеративные вычисления в Calc — и ВПР не сработал для процесса, зависящего от процесса с бóльшим номером.

3. Перепутал «начало» и «конец». Зависимость ждёт конца предшественника, а не его начала.

4. Ошибся на единицу с номером мс. Процесс с началом s идёт с (s+1)-й мс; «стартует не ранее T-й мс» — это начало + 1 >= T.

5. В вопросе про одновременность посчитал процесс работающим в мс своего начала. Работает он с следующей мс: условие начало < t <= конец.

6. Взял не тот итог: для «минимального времени» нужен максимум концов (самая длинная цепочка), а не сумма и не минимум.

💡 Последнее напутствие

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

В таблице держи под рукой связку ВПР + МАКС, а если любишь код — рекурсия с lru_cache решает всё за пару строк. Удачи на экзамене — Профиматика с тобой!

Шпаргалка по заданию 22 — Задание 22 ЕГЭ 2027 | Методички — Профиматика