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