О задании
Ранее мы уже познакомились с таким важным и полезным инструментом, как диаграмма Ганта, а также научились строить её в редакторе электронных таблиц LibreOffice Calc.
Теперь перейдём к прикладному применению диаграмм Ганта в ЕГЭ по информатике. А именно, научимся решать 22 задания.
Эти задания по подходам к решению можно разделить на два основных типа:
- Задания «новые», в которых не требуется строить саму диаграмму, а можно обойтись только таблицей к ней;
- Задания «старые», в которых придётся и диаграмму построить, и проанализировать её.
Как обычно, каждому типу отведена своя статья. Сегодня же начнём с самого простого, первого типа 22 заданий. Узнать его можно по фразе «каждый процесс начинается в самое раннее допустимое время» в условии. Это нам буквально говорит следующее: «как процессы изначально располагаются, так они и должны идти, сдвигать никакой процесс нельзя».
В 22 заданиях первого типа обычно требуется найти количество процессов, которые начнутся или завершатся в какое-то время, либо же минимальное время, за которое завершится столько-то процессов.
Соответственно, строить саму диаграмму и смотреть, как же там расположены сами процессы, не требуется. Для ответа на поставленный в задании вопрос достаточно будет таблицы, в которой написано время начала и конца каждого процесса. А дальше все решается обычной фильтрацией или сортировкой.
В целом, с подготовительной частью закончили, давайте переходить к разбору алгоритма решения. Сразу отметим, что останавливаться на этапах построения диаграммы Ганта и разбирать работу каждой формулы мы не будем. Этим темам посвящена предыдущая статья, так что настоятельно рекомендуем с ней ознакомиться, прежде чем переходить к решениям 22 заданий.
Алгоритм решения
Начнём разбор алгоритма с рассмотрения самого актуального задания на текущий момент – из демоверсии экзамена 2026 года.
Формулировка звучит следующим образом:
«В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно.
Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.
Определите максимальное количество процессов, которые могут быть завершены за первые 17 мс. Считать, что каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с 1.»
Нас здесь интересует только последний абзац, в котором и кроется вопрос этого задания: нужно определить, сколько процессов заканчиваются до 17 миллисекунды включительно.
Что же, перейдём к решению. Открываем приложенный файл в LibreOffice Calc и видим такую картину.
Сразу разобьём третий столбец на два с помощью операции «Текст по столбцам».
В появившемся окне ничего не трогаем и просто нажимаем кнопку «ОК».
В результате вместо одного столбца со всеми зависимостями получаем два, в каждом из которых по одной зависимости.
Теперь добавим границы, приведём размер ячеек к общему виду и раскрасим каждый столбец в свой цвет. Мы будем использовать цвета, введённые еще в прошлой статье. Вам же это делать не обязательно, главное – всё привести к такому виду, чтобы вам было комфортно работать с данными, и при этом не потерять драгоценное время на наведение излишней красоты в таблице.
Далее добавляем столбцы с длительностями каждой зависимости и временем начала и конца каждого процесса.
Начнём заполнять столбец «E». Формула в ячейке «E2» будет такая: «=ЕСЛИОШИБКА(ВПР(C2;$A:$H;8;0);0)». Как уже говорилось ранее, здесь мы «подтягиваем» время конца процесса, от которого зависит текущий.
Эту формулу растягиваем на весь столбец «E». И аналогично поступаем со столбцом «F», в котором будет время окончания второго процесса: «=ЕСЛИОШИБКА(ВПР(D2;$A:$H;8;0);0)».
Осталось заполнить столбцы «G» и «H». Формула в ячейке «G2» у нас такая: «=H2 — B2 + 1». А в «H2» такая: «=B2 + МАКС(E2:F2)». Обе растягиваем вниз до конца таблицы. И получаем такую картину.
И для получения ответа осталось лишь отфильтровать столбец «Конец» по значению «<=17» и подсчитать количество оставшихся строк в таблице.
Выделяем диапазон ячеек от «H1» до «H26», применяем к выбранному диапазону «Автофильтр» сочетанием клавиш «Ctrl+Shift+L». Нажимаем на появившуюся внизу ячейки «H1» стрелку вниз. И в контекстном меню выбираем «Фильтр по условию» → «Стандартный фильтр».
В графе «Условие» выбираем меньше или равно «<=», а в графу «Значение» вписываем число 17.
После применения фильтрации количество строк в таблице резко уменьшится.
Останется лишь их подсчитать и записать полученное значение в ответ. В нашем случае ответом является число 12.
Пример 1
Для закрепления рассмотрим еще одну задачу первого типа. Формулировка звучит так:
«В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.
Определите минимальное время (в мс), за которое завершатся 14 процессов. Считать, что каждый процесс начинается в самое раннее допустимое время. Минимальное время отсчитывается непрерывно с первой миллисекунды. В ответе укажите только число — количество мс.»
Обратите внимание, что теперь нам нужно определить не количество процессов, а время, за которое завершатся 14 процессов. В целом, подход в решении остаётся таким же, только в конце будет делать не фильтрацию, а сортировку по времени завершения и смотреть на строку с 14-ым процессом, там и будет ответ.
Действуем по описанной ранее схеме. Разделяем третий столбец на два, добавляем границы и цвет заливки каждой ячейки.
Добавляем еще 4 столбца.
Вписываем формулы в столбцы «E» и «F».
И вычисляем время начала и окончания каждого процесса.
Всё, мы на финишной прямой. Осталось лишь отсортировать таблицу по возрастанию значений в столбце «Конец». Таким образом, мы выстроим процессы так, чтобы сначала шли те, что закончатся раньше.
После сортировки можно для удобства добавить номера процессов по порядку выполнения. В итоге находим четырнадцатый по порядку процесс (15-ая строка таблицы) и смотрим на время его завершения (ячейка «H15»).
Значение этой ячейки – 14 – и пишем в ответ.
Также отметим, что подобные задания могут иметь в своём условии такую формулировку «Определите минимальное время, через которое завершится выполнение всей совокупности процессов». Здесь подход к решению будет аналогичным, только искать придётся не 14-ый по счёту процесс, а самый последний.
Как раз время окончания работы самого последнего процесса (при сортировке столбца «Конец» по возрастанию) и будет означать минимальное время, через которое завершится выполнение всей совокупности процессов.
Пример 2
Заключительное для этой статьи задание будет иметь такую формулировку:
«В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.
Определите максимальное количество процессов, которые параллельно выполняются на 15-й мс. Считать, что каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с 1»
Здесь снова определяем количество процессов. Теперь надо, чтобы время начала и окончания процесса принадлежали такому диапазону:
«время начала <=15 <= время окончания»
То есть чтобы процесс начинался на 15 миллисекунде и ранее или заканчивался на этой же миллисекунде и позже.
Приступим к решению. Теперь подробно расписывать все шаги не будем, сразу приведём данную таблицу к привычному виду.
И впишем все необходимые формулы.
Теперь нас ждёт развилка из двух путей решения:
- Можно построить диаграмму, найти на неё столбец с 15-ой миллисекундой и посмотреть, сколько в этом столбце «единиц» процессов
- Можно просто воспользоваться условием, о котором мы говорили в начале разбора, и подсчитать, сколько строк в таблице ему удовлетворяют
Мы пойдём вторым путём. Итак, у нас было вот такое двойное неравенство: «время начала <=15 <= время окончания». Для первой строки таблицы оно бы выглядело так: «G2 <=15 <= H2».
Но, к сожалению, передать такое двойное неравенство в функцию «ЕСЛИ()» мы не можем. Зато можем из двойного сделать два обычных неравенства и объединить их с помощью логической операции И(): «И(G2<=15; 15<=H2)».
Теперь эту запись можем передать как аргумент функции «ЕСЛИ()». Пусть, если условие истинно, то в ячейку записывается число 1, если же ложно – 0. Формула будет такая: «=ЕСЛИ(И(G2<=15; 15<=H2);1;0)».
Вписываем её в ячейку «I2» и растягиваем до конца таблицы.
Осталось лишь подсчитать количество единиц в столбце «I». Это можно сделать через функцию «СУММ()» или выделить нужный диапазон и посмотреть справа внизу подсчитанную сумму.
В данном задании количество процессов, которые одновременно работают на 15-ой миллисекунде, равняется 5.
Мы научились решать задания 22 самого простого типа. В следующей статье разберём более сложный тип 22 заданий, а также научимся анализировать диаграмму Ганта.
<<< Предыдущая статья Следующая статья >>>