На ЕГЭ 2025 задание 22 на параллельные процессы стало самым нерешаемым заданием из 1 части экзамена.
Но сегодня я покажу вам секрет, который превратит эту задачу из ужаса в простую таблицу в LibreOffice Calc.
📚 Теория: что такое диаграмма Ганта и как работает формула ВПР?
1️⃣ Формула ВПР — когда нужно быстро найти время окончания каждого процесса.
2️⃣ Диаграмма Ганта (граф зависимостей) — когда важно видеть, какие процессы выполняются одновременно и в какой момент времени.
Что такое диаграмма Ганта?
Это график, показывающий сроки выполнения задач. Каждая строка — один процесс, а столбцы — время (в миллисекундах, секундах, днях).
В нашем случае — время в миллисекундах (мс).
Столбец A — ID процесса
- Столбец B — время выполнения
- Столбец C и D — ID процессов, от которых зависит текущий
- Столбец E — время окончания (вычисляется по формуле)
- Столбец F — время начала (вычисляется как окончание - выполнение)
Что такое формула ВПР?
В LibreOffice Calc она называется ВПР (по аналогии с Excel), но на самом деле — это VLOOKUP.
Формула:
=ВПР(значение; диапазон; номер_столбца; 0)
значение — что ищем (например, ID процесса)
- диапазон — где ищем (обычно весь массив данных)
- номер_столбца — какой столбец возвращаем (например, 5 — это столбец E — время окончания)
- 0 — точное совпадение
💡 Почему важно использовать 0? Потому что нам нужно точное совпадение ID, а не приближенное.
🧩 Два типа задач: два подхода
В задании 22 есть два основных типа.
🔹 Тип 1: Решение через формулу ВПР
🎯 Когда использовать?
Когда в задаче спрашивают:
- Сколько процессов завершится за первые X мс?
- Какое минимальное время, чтобы завершились N процессов?
- Когда завершится последний процесс?
→ Нам не нужно знать, кто и когда выполнялся параллельно — только время окончания каждого процесса.
🧮 Как работает формула?
В столбце E («Время окончания») пишем:
=МАКС(ВПР(C2;A1:E1048576;5;0); ВПР(D2;A1:E1048576;5;0)) + B2
Что делает эта формула?
- ВПР(C2;A$1:E$1048576;5;0) — ищет в столбце A значение из C2 и возвращает время окончания этого процесса (столбец E = 5-й).
- То же самое для D2.
- МАКС(...) — выбирает последнее завершение из зависимых процессов.
- + B2 — добавляет время выполнения текущего процесса.
✅ Тип 1: Сколько процессов завершится за первые 16 мс
Условие:
Даны процессы с ID, временем выполнения и зависимостями.
Найти максимальное количество процессов, которые могут быть завершены за первые 16 мс.
Задание.
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.
Вопрос
Определите максимальное количество процессов, которые могут быть завершены за первые 16 мс. Считать, что каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с 1.
🔍 Шаг 1: Разбиваем процессы в столбце С
Необходимо обеспечить, чтобы каждый процесс был в отдельной ячейке, а пустые ячейки были заполнены нулями (их проставляем вручную).
💡 На забудьте добавить в столбец А процесс с номером 0
🔍 Шаг 2: Вычисляем время окончания
Для каждого процесса время окончания = максимум времени окончания всех зависимых процессов + время выполнения.
Формула в ячейке E2:
=МАКС(ВПР(C2;A$1:E$1048576;5;0);ВПР(D2;A$1:E$1048576;5;0)) + B2
Что делает эта формула?
- ВПР(C2;A$1:E$1048576;5;0) — ищет в столбце A значение из C2 (ID процесса A), и возвращает значение из 5-го столбца (E — время окончания).
- ВПР(D2;A$1:E$1048576;5;0) — то же самое для D2 (ID процесса B).
- МАКС(...) — берёт максимальное из двух значений (потому что процесс может начаться только после завершения последнего зависимого процесса).
- + B2 — добавляет время выполнения текущего процесса.
🔍 Шаг 3: Вычисляем время начала
Формула в ячейке F2:
=E2-B2+1
💡 Почему +1? Потому что процесс начинается в следующую миллисекунду после завершения зависимых процессов.
🔍 Шаг 4: Считаем количество процессов, завершившихся до 16 мс
В ячейке G2:
=ЕСЛИ(E2<=16;1;0)
Затем суммируем все единицы:
=СУММ(G2:G1048576)
Итоговая таблица (ответ 13).
✅ Тип 2: Минимальное время, чтобы завершились 14 процессов
Определите минимальное время (в мс), за которое завершатся 14 процессов. Считать, что каждый процесс начинается в самое раннее допустимое время. Минимальное время отсчитывается непрерывно с первой миллисекунды. В ответе укажите только число - количество мс.
🔍 Шаг 1: Вычисляем время окончания для всех процессов
Используем ту же формулу, что и в типе 1:
🔍 Шаг 2: Сортируем процессы по времени окончания
Выбираем весь диапазон A1:F1048576 → меню "Данные" → "Сортировка" → сортируем по столбцу E (по возрастанию).
🔍 Шаг 3: Находим 14-й процесс
После сортировки 14-й процесс будет в строке 14 (если считать заголовок).
Время окончания этого процесса — и есть ответ.
Ответ: 14
✅ Тип 3: Минимальное время, чтобы завершились все процессы
Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.
🔍 Шаг 1: Вычисляем время окончания для всех процессов
Используем ту же формулу:
🔍 Шаг 2: Находим максимальное время окончания
=МАКС(E2:E1048576)
Ответ: 17
✅ Тип 4: Максимальное количество процессов, выполняющихся параллельно на 15-й мс
Определите максимальное количество процессов, которые параллельно выполняются на 15-й мс. Считать, что каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с 1.
🔍 Шаг 1: Разбиваем процессы в столбце С
Также как в типе 1. Через меню Данные - текст по столбцам
🔍 Шаг 2: Находим время окончания каждого процесса и время начала каждого процесса
🔍 Шаг 3: Считаем количество активных процессов на 15-й мс
🔸 Тип 2: Решение через диаграмму Ганта (граф зависимостей)
🎯 Когда использовать?
Когда в задаче спрашивают:
- Максимальную продолжительность отрезка, на котором выполняется ровно K процессов
- Максимальное число процессов, выполняющихся одновременно
→ Здесь недостаточно знать только время окончания — нужно видеть динамику выполнения во времени.
🧩 Как строить диаграмму?
В ячейках D1:AV1 цифры от 1 до 45. Каждый столбец будет обозначать одну миллисекунду.
Раскрашиваем столбцы для каждого процесса, учитывая зависимости. Зависимые процессы должны идти после тех от кого они зависят.
Задача 1
«Максимальная продолжительность отрезка с максимальным числом процессов при условии, что время окончания всех процессов минимально»
Задание
Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение максимального количества процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно, а время окончания работы всех процессов минимально.
→ Это усложнённая версия.
Сначала строится диаграмма,
- Затем анализируются отрезки. Важно заметить, что никто не зависит от процесса 104. Поэтому он спокойно может переместиться вправо и стать пятым параллельным процессом.
- И выбирается тот, где одновременно выполняется максимум процессов (5 штук, не 4!)
- Условие "время окончания работы всех процессов минимально" означает, что процессам в своём движении вправо нельзя выходить за начальное время окончания процессов (32 секунда). До этого времени они могут двигаться (с соблюдением зависимостей).
Ответ: 7 (участок с 16 по 22 мс)
Задача 2
«Максимальная продолжительность отрезка с максимальным числом процессов при условии, что время окончания каждого процессов минимально»
Задание
Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение максимального количества процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно, а время завершения каждого процесса минимально.
Сначала строится диаграмма,
- Затем анализируются отрезки.
- И выбирается тот, где одновременно выполняется максимум процессов (4 процесса)
- Условие "время окончания работы каждого процесса минимально" означает, что процессы НЕЛЬЗЯ никуда передвигать, т.к. если процесс сдвинуть хоть на 1 мс, то его время окончания перестанет быть минимальным
Получается, что можно максимум 4 процесса на участке 9-14 мс и на 16-18 мс. Участок 9-14 мс выгоднее. Ответ 6.
💬 Заключение
Задание 22 про понимание модели выполнения процессов.
Если вы умеете:
- писать формулу ВПР для расчёта времён,
- и строить диаграмму Ганта для анализа параллелизма,
— вы гарантированно получите 1 балл.
А если хотите — напишите в комментариях, какой тип задач вызывает больше сложностей: ВПР или диаграмма?
⚠️ Главные ловушки
Подпишитесь на мой канал и научитесь решать все задания ЕГЭ по информатике!
Удачи на экзамене!
Записаться ко мне на занятия можно тут https://vk.com/nebolsink