Задание 22 ЕГЭ по информатике. Параллельные процессы

Содержание

Теория

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

Процессы в современных компьютерах могут выполняться параллельно, если являются независимыми. Формула «процесс B зависит от процесса A» означает, что выполнение процесса B не может начаться раньше, чем выполнение процесса A (в таком случае A и B можно выполнять только последовательно).

Задание

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты A; тогда процессы выполняются только последовательно. В первой строке таблицы указан идентификатор процесса (ID), во второй — время его выполнения (мс), в третьей — через «;» перечислены ID зависимостей (или 0 для независимого процесса). Требуется определить минимальное время, через которое завершится выполнение всей совокупности процессов, если все независимые процессы могут выполняться параллельно.

Подготовка таблицы

Добавляем столбец «общее время» (С): ПКМ по C1 → «Вставить».
Разбиваем столбец зависимостей на два (D и E) по максимальному числу зависимостей: «Данные → Текст по столбцам → С разделителями → Точка с запятой».
Промежуточный результат: получаем таблицу с ID (A), длительностью (B), зависимостями D/E и пустым столбцом «Общее время» (C).

Это слайд-шоу требует JavaScript.

Идея расчёта «общего времени» (критический путь)

Для независимых процессов (D=0) «общее время» на этапе их завершения равно их собственной длительности: C = B.
Для зависимых процессов (D≠0) «общее время» равно времени самого длинного предыдущего пути плюс длительность текущего процесса: C = B + max(C<sub>пред1</sub>, C<sub>пред2</sub>).
Чтобы взять «общее время» предшественников по их ID, используем ВПР; чтобы на пустых/нулевых зависимостях не было #Н/Д, оборачиваем в ЕСЛИОШИБКА и подставляем 0.

Формулы (LibreOffice Calc, RU)

Пусть заголовки в строке 1; с 2-й строки идут данные. Тогда в C2:
```
=B2 + МАКС(
  ЕСЛИОШИБКА(ВПР(D2; $A$2:$C$9999; 3; 0); 0);
  ЕСЛИОШИБКА(ВПР(E2; $A$2:$C$9999; 3; 0); 0)
)
```
Эта одна формула корректно считает и независимые процессы (когда D=0/E пустые, оба ВПР дают 0), и зависимые (берём максимум из «общих времён» предшественников). Протягиваем вниз по всем строкам.
Ответ по заданию «минимальное время завершения» — это МАКС($C$2:$C$9999).

Общее решение

После протяжки формул по столбцу C достаточно взять максимум: это и есть время завершения всей совокупности (критический путь).

Диаграмма Ганта (визуальный контроль и альтернативный способ)

Строим Гант: по строкам — процессы, по оси X — миллисекунды; для каждого процесса рисуем «старт в самое раннее допустимое время» и длительность B. Для независимых — старт с 1-й мс; для зависимых — старт = максимум окончаний предков + 0. По диаграмме легко видеть параллельность и пересечения интервалов.

Примеры решений заданий

1) «Сколько процессов могут начаться не ранее чем с T-й мс?» (ASAP-план)

Постановка (пример из вопроса): для таблицы вида

«ID | Время (B) | Зависимости (D;E)» нужно определить максимальное количество процессов, которые начнутся не ранее чем с 8-й мс, при условии, что каждый процесс стартует в самое раннее допустимое время (ASAP) и приостановок нет. Нумерация мс — с 1-й.

Шаг 1. Ранние начала/окончания

Раннее окончание (RO) процесса: это «общее время» из столбца C.
Раннее начало (RN) процесса: RN = RO - B + 1 (с учётом, что считаем миллисекунды с 1-й). В Calc:
```
=C2 - B2 + 1
```

Шаг 2. Считаем, сколько RN ≥ T

Заводим столбец F = RN. Затем:
```
=СЧЁТЕСЛИ($F$2:$F$9999; ">=8")
```
— это и есть требуемое количество процессов, которые могут начаться не ранее чем с 8-й мс.

Замечание по примеру из условия

В типовом примере из задания (для T=6 мс) ответ 2 (процессы 3 и 5). Наш расчёт даёт то же самое: RN(3)=8, RN(5)=6 — оба удовлетворяют условию «не ранее 6». Всё определяется формулами RN/RO, без ручного перебора.

2) «Максимальная продолжительность интервала, в течение которого параллельно идут как минимум K процессов» (диаграмма Ганта)

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

Подход 2А. Через диаграмму Ганта (Calc, наглядно)

Сначала посчитайте ASAP-расписание (RN/RO) по формулам из «Теории» (это даст нижнюю границу старта для зависимых процессов).
Для независимых процессов допускается «сдвиг вправо» (они не обязаны стартовать в 1-ю мс, если задача это разрешает). Чтобы нарастить «плато» из 5 параллельных, разносим независимые и зависимые с учётом их длительностей, создавая полосу максимальной высоты ≥5.
Построение: в отдельном листе создайте шкалу времени по столбцам (1…Tmax=МАКС(C)) и условным форматированием/формулами залейте клетки [RN … RO] для каждого процесса. Далее в строке «Сумма по столбцу t» посчитайте:
```
=СУММПРОИЗВ( (t>=RN_i) * (t<=RO_i) )
```
(через массивные формулы/ПОИСКПОЗ/СЧЁТЕСЛИ.МН). Максимальная длина непрерывного участка, где сумма ≥5, и будет ответом.

Подход 2Б. «Сканирующая линия» (быстро и без рисунка)

Сформируйте таблицу событий: для каждого процесса две строки — (RN; +1) и (RO+1; −1).
Отсортируйте по времени, ведите префиксную сумму cnt(t) — это число одновременно работающих процессов.
Перебирая события, отмечайте самые длинные промежутки, где cnt ≥ 5. Это даёт ту же величину, что и Гант, но без отрисовки.

Почему здесь лучше Гант, а не только ВПР

Способ с ВПР идеален, когда процессов много и все запускаются «как можно раньше» (ASAP). Если же независимые процессы можно «передвигать», задача превращается в отыскание максимального перекрытия интервалов — визуально и логически это проще довести до ответа через Гант/сканирующую линию (мы контролируем реальные перекрытия, а не только ранние старты).

3) «Минимальное время завершения всех процессов»

Это основное задание со слайдов. Алгоритм целиком совпадает с «Теорией»: один столбец «общее время» (C) по формуле с ВПР/ЕСЛИОШИБКА/МАКС, ответ — МАКС(C). :contentReference[oaicite:12]{index=12}

Готовые шаблоны формул (скопируйте в Calc, RU локаль)

Общее время (C2):

=B2 + МАКС(
  ЕСЛИОШИБКА(ВПР(D2; $A$2:$C$9999; 3; 0); 0);
  ЕСЛИОШИБКА(ВПР(E2; $A$2:$C$9999; 3; 0); 0)
)

Раннее начало (F2):
```
=C2 - B2 + 1
```
Сколько процессов начнутся не ранее T (например, 8):
```
=СЧЁТЕСЛИ($F$2:$F$9999; ">=8")
```
Минимальное время завершения всех процессов:
```
=МАКС($C$2:$C$9999)
```

4) Мини-чек-лист по типовым заданиям

ASAP-план (все стартуют как можно раньше): считайте общее время (C) и RN=RO−B+1; далее любые вопросы по «кто позже/раньше T» решаются через RN.
Если можно сдвигать независимые группы во времени — используйте диаграмму Ганта или «сканирующую линию» для подсчёта максимального перекрытия K процессов.
Не допускается приостановка процесса: интервалы целые и непрерывные.
Зависимости «A;B;…» означают: старт B возможен только после завершения всех указанных предков (берём максимум их RO).