Задание 22 ЕГЭ информатика

1. Введение

В задании 22 нужно работать с набором процессов: для каждого известны его ID, длительность и процессы-предшественники. Главная идея — правильно учесть зависимости и определить, когда каждый процесс может начаться и закончиться.

Решать задачу удобно в электронной таблице. В этой методичке используем LibreOffice Calc: он позволяет быстро разбить список зависимостей по столбцам, автоматически считать время окончания через ВПР и МАКС, а при необходимости — отрисовать процессы на временной шкале.

2. Суть задачи

Независимый процесс не ждёт других процессов и может стартовать сразу. Зависимый процесс может стартовать только после завершения всех процессов, от которых он зависит. Независимые друг от друга процессы могут выполняться параллельно.

2.1. Как считать время окончания

Если обозначить длительность текущего процесса как d, а время окончания его предшественников как T, получаем три простых случая:

• Независимый процесс: конец = d.
• Зависимость от одного процесса: конец = d + конец предшественника.
• Зависимость от нескольких процессов: конец = d + МАКС(время окончания всех предшественников).

Почему берём МАКС? Если процесс ждёт несколько поставщиков данных, он не может стартовать после первого завершившегося — нужно дождаться самого позднего из них.

Что обычно спрашивают: минимальное время завершения n процессов; сколько процессов выполнялось на конкретной миллисекунде; сколько процессов завершилось к моменту t; максимальную длительность одновременного выполнения максимального числа процессов.

2.2. Важное уточнение про сдвиги процессов

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

Если такой фразы нет, сдвиги могут быть допустимы. При условии «время окончания работы всех процессов минимально» можно двигать процессы только внутри их запаса времени — так, чтобы общий момент завершения всей совокупности не увеличился. Если ограничения на минимальное общее время нет, допустимый сдвиг может быть больше, но зависимости всё равно нарушать нельзя.

3. Пошаговое автоматическое решение

Шаг 1. Разбиваем зависимости по столбцам

Выделяем столбец, где несколько ID записаны через «;», затем открываем: Данные → Текст по столбцам. В качестве разделителя выбираем точку с запятой.

Шаг 2. Добавляем нулевой процесс и заполняем пустые зависимости нулями

В первой строке создаём технический процесс с ID = 0 и длительностью 0. В столбцах зависимостей все пустые ячейки также заменяем на 0. Тогда любой отсутствующий предшественник будет ссылаться на нулевой процесс, время окончания которого равно 0.

Это особенно удобно в LibreOffice Calc: ВПР по пустой ячейке может вернуть ошибку #Н/Д, а поиск ID 0 корректно вернёт 0.

Шаг 3. Считаем время окончания через МАКС и ВПР

Пусть A — ID процесса, B — его длительность, C:F — до четырёх предшественников, G — время окончания. В G2 записываем:

=МАКС(ВПР(C2;$A:$G;7;0);ВПР(D2;$A:$G;7;0);ВПР(E2;$A:$G;7;0);ВПР(F2;$A:$G;7;0))+B2

После этого растягиваем формулу вниз на все процессы.

Важно: последний аргумент 0 в ВПР означает точное совпадение ID. Он не «защищает от вылета». Ошибки из-за пустых зависимостей мы убрали на предыдущем шаге с помощью нулевого процесса.

Шаг 4. Если нужно найти минимальное время, за которое завершатся n процессов

Столбец G уже содержит момент окончания каждого процесса. Считаем, сколько процессов завершилось к моменту t:

=СЧЕТЕСЛИ(G2:G100;"<="&J1)

Здесь J1 — ячейка, в которой находится выбранное t. Подбираем t, пока результат не станет равен n или больше. Минимальное подходящее t и будет ответом.

Быстрее: если удобно, можно отсортировать времена окончания по возрастанию и посмотреть время n-го завершившегося процесса. СЧЕТЕСЛИ полезнее, когда нужно быстро проверять разные t.

Шаг 5. Если нужно узнать, сколько процессов выполнялось на n-й миллисекунде

Одного времени окончания недостаточно — считаем ещё и начало процесса. Если миллисекунды учитываются включительно:

начало = конец - длительность + 1

Например, процесс длится 4 мс и заканчивается на 8-й мс. Значит, он выполнялся на 5-й, 6-й, 7-й и 8-й мс, поэтому начало равно 8 − 4 + 1 = 5.

Теперь проверяем, попадает ли n внутрь отрезка [начало; конец]:

=ЕСЛИ(И(ячейка_конца>=n;ячейка_начала<=n);1;0)

Растягиваем формулу вниз и суммируем единицы — получаем количество процессов, которые выполнялись на n-й миллисекунде.

Исправление важной ошибки: условия должны быть конец ≥ n и начало ≤ n. Если развернуть первый знак в другую сторону, проверка будет неверной.

Шаг 6. Если процессы можно сдвигать

Для задач со сдвигами удобнее отрисовать расписание прямо в Calc: одна клетка по горизонтали = одна миллисекунда. Закрашиваем клетки длительности каждого процесса и подписываем его ID.

Главное правило сдвига: если мы двигаем процесс, все процессы, которые зависят от него и из-за этого больше не могут стартовать в прежний момент, тоже должны сдвинуться. Связи между процессами всегда сохраняются.

В Calc можно просто выделить закрашенный диапазон процесса или целую связанную группу и сдвигать её вправо, отслеживая, где одновременно пересекается максимальное количество процессов и как долго длится это пересечение.

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

Короткий алгоритм

• Разбить столбец зависимостей по «;».
• Добавить строку нулевого процесса и заменить пустые зависимости на 0.
• Через ВПР получить время окончания предшественников и через МАКС + длительность посчитать конец каждого процесса.
• По формулировке задачи выбрать нужную проверку: СЧЕТЕСЛИ для завершившихся к t; начало/конец + ЕСЛИ для выполняющихся в n; диаграмму для задач со сдвигами.
• Перед ответом ещё раз проверить, разрешены ли сдвиги и требуется ли минимальное время окончания всей совокупности.

Видео разбор