В предыдущих статьях мы освоили азы построения диаграммы Ганта и научились справляться с самыми простыми заданиями 22. Пришло время подняться на новую ступень!
Теперь мы рассмотрим задания второго типа, в которых нам уже придётся строить диаграмму Ганта и передвигать процессы по временной оси для получения требуемого результата.
Ключевая фраза-маркер звучит так: «в течение которого возможно одновременное выполнение процессов». Именно в этих словах скрыта вся суть работы: нужно добиться того, чтобы независимые друг от друга процессы выстраивались параллельно и работали в одно время.
Чаще всего в таких заданиях требуется найти максимальную продолжительность отрезка, на котором одновременно работает максимальное количество процессов. Для этого мы сдвигаем независимые блоки и ищем их самое долгое пересечение.
Для успешного решения вам необходимо задать себе несколько вопросов:
Как выделить блоки взаимосвязанных процессов среди всех остальных?
Сколько максимально процессов может работать одновременно внутри каждого блока?
Можно ли увеличить количество параллельно работающих процессов в блоках?
Как долго работает это максимальное количество процессов в каждом блоке?
Можно ли растянуть это время ещё больше?
Ответы на эти вопросы станут нашими инструментами при анализе диаграммы Ганта. Именно ими мы будем руководствоваться, перемещая процессы в поисках оптимального решения.
Три идеи, без которых анализ не сложится
Первая идея — блоки. Если две группы процессов никак не зависят друг от друга, их можно передвигать по временной оси независимо. Именно такие группы мы будем называть блоками.
Вторая идея — критическая цепочка. Если сдвинуть её элемент, вправо уедут и все зависящие от него процессы. При ограничении на общий срок такую цепочку часто двигать нельзя.
Третья идея — пересечение отрезков. Если несколько процессов должны работать вместе, их общий отрезок начинается в самом позднем из начал и заканчивается в самом раннем из концов.
Если начала процессов равны 12, 16 и 14, общий отрезок начнётся в 16. Если их концы равны 30, 25 и 28, общий отрезок закончится в 25.
Отсюда формула: длина пересечения = минимальный конец − максимальное начало + 1. В нашем примере: 25 − 16 + 1 = 10.
Что же, давайте перейдём от слов к делу. Начнём разбирать алгоритм решения с такой формулировки:
В файле содержится информация о совокупности 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
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Сразу обратите внимание на фразу «время окончания работы всех процессов минимально». Сначала мы запускаем все процессы как можно раньше и получаем минимальный срок всего проекта.
Обозначим этот минимальный срок буквой T. После сдвигов ни один процесс не должен заканчиваться позже T. Иначе мы уже не выполняем требование о минимальном времени всего проекта.
Важно: это не значит, что нельзя сдвигать никакие процессы. Сдвигать можно, но новое время окончания должно оставаться не больше T.
Теперь приступим к решению. Подробно останавливаться на построении самой диаграммы Ганта в данной статье мы не будем. Все это уже разобрано в двух предыдущих статьях.
Открываем приложенный к заданию файл и оформляем таблицу.
Теперь добавляем временную шкалу. Для этого в ячейке «J1» поставим единицу, в следующей за ней ячейке «K1» напишем формулу: =J1+1 и скопируем её до конца листа.
Для построения диаграммы Ганта осталось нарисовать «полосы» процессов. В J2 запишем =ЕСЛИ(И($G2<=J$1;J$1<=$H2);1;""), а затем растянем формулу вправо и вниз. По желанию можно добавить условное форматирование, как мы это делали здесь.
Теперь начнём анализировать диаграмму. Сначала добавим под всеми процессами вспомогательную строку. В ячейку J15 впишем =СУММ(J2:J14) и растянем формулу вправо.
Каждая единица в столбце J означает один процесс, работающий в этот момент. Поэтому сумма единиц показывает количество одновременно работающих процессов.
Перемещаемся в конец диаграммы. Здесь мы видим процесс, который заканчивается позже всех.
Это означает, что позже 37-й миллисекунды ни один процесс заканчиваться не может. Иначе общее время выполнения всех процессов увеличится. Иными словами, ни одна «полоса» не должна заходить правее столбца AT.
Процесс 112 заканчивается в граничный момент 37, поэтому сдвигать его вправо нельзя. Давайте посмотрим, от каких процессов он зависит.
От 110 и 111 процессов, которые, в свою очередь, зависят от 109. Это означает, что ни один из них мы не можем сдвигать.
Что же, раз блок процессов 109-113 у нас жёстко зафиксирован, то, может, получится сдвинуть другие так, чтобы получить максимальную цепочку процессов, работающих одновременно?
На прошлом изображении мы видели, что процесс 108 критически близко подобрался к границе — буквально на одну ячейку. Давайте так же проследим зависимости этого процесса:
108 зависит от 107
107 зависит от 105 (106 тут не важен)
105 – от 103
103 – от 101
Все эти зависящие друг от друга процессы образуют непрерывную «лестницу» выполнения.
Сдвинув любой из них, мы сдвинем и 108, который уже переступит «границу».
Что это для нас означает? Что нам даже не надо двигать никакие процессы. Давайте просто найдём сначала максимум процессов, а затем максимальную их длительность.
Здесь максимум 4 процесса выполняются параллельно. Самый длинный отрезок их одновременной работы идёт с 15-й по 19-ю миллисекунду включительно. Его длительность равна 19 − 15 + 1 = 5 мс.
Запомните правило подсчёта клеток: если отрезок идёт от a до b включительно, его длина равна b − a + 1. Единица возвращает левую границу, которую мы тоже считаем.
Число 5 и будет ответом на это задание.
Пример 1
Что же, в прошлом задании нам так и не удалось «подвигать» процессы, а очень хотелось. Давайте тогда разберём такое, в котором без этого не обойтись.
Формулировка будет следующая:
В файле содержится информация о совокупности 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
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Шаг с построением диаграммы Ганта мы опустим. Выглядеть она будет следующим образом.
Вспоминаем про последнюю фразу из условия и перемещаемся в конец диаграммы. Сразу отметим столбец «AT» красным, чтобы в будущем случайно его не пересечь.
Казалось бы, ситуация похожа на предыдущую, что же, снова не будем ничего двигать? Не спешите с выводами!
Итак, вспоминаем про наши 5 вопросов, о которых говорили в начале. В прошлом примере они нам не сильно пригодились, но сейчас как никогда кстати.
Давайте выделим блоки взаимозависимых процессов. Мы их будем определять единым «таймлайном», то есть рисовать непрерывную «лесенку» из зависимых процессов, идущих друг за другом. Первый блок состоит из процессов от 101 до 108.
Что такая «лесенка» означает? Что, сдвинув любой процесс, на котором нарисована стрелка, сдвинутся все остальные процессы со стрелками. То есть в нашем случае нельзя двигать процессы: 101, 103, 105, 107 и 108.
Но процессы без стрелок в этой группе можно двигать в пределах вертикальных линий. То есть процесс 102 можно сдвинуть на 1 ячейку, процессы 104 и 106 – вплоть до конца 33 миллисекунды.
Аналогичная история со вторым блоком взаимозависимых процессов: с 109 по 113.
Здесь процесс 111 можно сдвигать вправо до конца процесса 110. Процесс 113 можно двигать свободнее, потому что от него никто не зависит. Но закончиться он должен не позднее 36-й мс, чтобы общий срок не вырос.
Переходим ко второму вопросу: сколько процессов может одновременно работать в каждом блоке? В обоих блоках одновременно работают не более двух процессов. Значит, общий максимум равен 2 + 2 = 4.
Теперь определим, как долго этот максимум работает внутри каждого блока. В первом блоке два процесса работают 14 мс — с 19-й по 32-ю. Во втором — тоже 14 мс, с 9-й по 22-ю.
Теперь нужно наложить эти два отрезка друг на друга. Их общая часть начнётся в более позднем из двух начал и закончится в более раннем из двух концов.
Если первый отрезок идёт с 19-й по 32-ю мс, а второй после сдвига — с 20-й по 31-ю, их пересечение идёт с 20-й по 31-ю. Длина равна 31 − 20 + 1 = 12 мс.
Обратите внимание на форму группы процессов 111 и 113. Они так и просят передвинуть их на 8 ячеек вправо и сравнять «границы» 110 и 111 процессов.
Давайте так и поступим: у 111 процесса в колонке «Сдвиг» пишем число 8.
И получается вот такая красота.
Мы получили 4 одновременно работающих процесса на протяжении 12 мс. Но можно ли увеличить это время?
Чтобы не подбирать сдвиг вслепую, используйте простое правило: сдвиг = желаемая граница − текущая граница.
Например, если начало блока находится в момент 9, а мы хотим перенести его на 17, в столбец «Сдвиг» нужно записать 17 − 9 = 8.
То же правило работает для конца. Если нужно перенести конец с 35-й на 36-ю мс, сдвиг равен 36 − 35 = 1.
Давайте обратим наш взгляд на правую часть диаграммы Ганта.
Во-первых, второй блок можно сдвинуть ещё на одну ячейку. Во-вторых, длительность общей работы четырёх процессов ограничивается вторым блоком, а именно процессом 113.
Так что давайте сдвинем второй блок на одну миллисекунду. Второй блок начинается с 109 процесса, именно в его строке и впишем значение сдвига, равное 1.
Готово, теперь наша цепочка из четырёх процессов длится целых 13 миллисекунд.
В ответ запишем число 13.
Пример 2
И завершим разбор алгоритма решения 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
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Теперь в условии нет ограничения на минимальное время окончания всех процессов. Значит, блоки можно спокойно двигать вправо: нам важна длительность их пересечения, а не общий срок.
Сразу построим диаграмму Ганта и начнём анализ.
Выделим все блоки взаимозависимых процессов. Для наглядности временно присвоим каждой группе свой цвет. Сразу уточним термины: внутри одного блока может быть несколько связанных групп. Разные блоки друг от друга не зависят.
Итак, от 101 процесса зависит 103, за ним идёт 105, за которым 108 и 109.
Эти процессы можно, условно, выстроить в одну линию.
Далее идёт вторая группа: процессы 102 и 104. От процесса 104 ничего не зависит, поэтому его можно свободно двигать вправо. Движение влево ограничивает процесс 102. Сам 102 можно сдвигать вправо лишь до начала 103, который от него зависит.
То есть можно воспринимать 103 процесс как некий «шлагбаум»: дальше него не могут «проехать» ни 101, ни 102 процесс.
Есть еще одна группа процессов: 106 и 107. Их также можно выстроить в линию, а их «шлагбаумом» является 108 процесс. «Сзади» же их подпирает 103 – раньше него они начаться не могут.
Все рассмотренные выше группы процессов организуют первый блок.
Ну и второй блок – это оставшиеся процессы 110-113. В единую линию выстраиваются 110, 112 и 113 процессы, а 111 может спокойно двигаться вправо, а его движение влево ограничивает 110 процесс.
Что же, с тем, как допускается передвигать процессы, разобрались. Теперь определим, сколько максимально процессов может работать одновременно внутри каждого блока. В верхнем блоке одновременно уже работают по 2 процесса: с 1 по 14 мс и с 16 по 27 мс.
Но давайте уделим особое внимание второй группе.
Мы же помним, что 104 процесс у нас может беспрепятственно двигаться вправо? Так давайте поместим его начало на 16 миллисекунду.
Для этого сдвинем его на 12 единиц.
Таким образом, с 16 по 26 мс у нас будут одновременно работать сразу 3 процесса.
К сожалению, увеличить длительность их работы пока не представляется возможным. Так что, давайте перейдём ко второму блоку.
Здесь у нас параллельно выполняются 2 процесса. Следовательно, грамотно совместив оба блока, можем получить 5 параллельных процессов.
Давайте внимательно посмотрим на границы процессов, которые начинаются на 16-й и 8-й миллисекундах. Нижний блок можно сдвинуть вправо так, чтобы конец процесса 110 совпал с началом процессов 104–106.
Тем самым мы сможем получить группу из 5 процессов, работающих одновременно. Для этого давайте сдвинем группу, зависящую от 110 процесса на 7 миллисекунд.
В итоге с 16-й по 25-ю миллисекунду включительно одновременно работает максимальное количество процессов.
Значит, мы готовы дать ответ: максимальное время, в течение которого работают 5 процессов, равно 25 − 16 + 1 = 10 мс.
Итоги
Во втором типе задания 22 мы разбиваем процессы на независимые блоки, находим критические цепочки и совмещаем интервалы, в которых одновременно работает максимальное число процессов.
Если общий срок должен остаться минимальным, сначала фиксируем самый поздний конец T. Общий интервал максимумов начинается в самом позднем из начал и заканчивается в самом раннем из концов; его длина равна разности границ плюс один.
Нужный сдвиг получается обычным вычитанием желаемой границы из текущей. После каждого сдвига остаётся проверить зависимости и ограничение T. Так формулы восстанавливаются из смысла диаграммы, а не вспоминаются наизусть.
На этом мы закончили разбор алгоритмов решения задания 22 ЕГЭ по информатике. А попрактиковаться в решении заданий данного типа вы можете в нашем тренажёре.
Разберём эту тему на бесплатном пробном занятии
Преподаватель покажет, как решать такие задачи, и подскажет, с чего начать подготовку. Группы до 8 человек, очно в Калининграде и онлайн.
Мы используем файлы cookie. Необходимые обеспечивают работу сайта: корзину и вход в личный кабинет. С вашего согласия мы также используем сервис Яндекс Метрика, чтобы анализировать посещаемость и улучшать сайт.
Подробнее — в политике конфиденциальности.
