📌 Больше полезных статей по информатике и программированию вы можете найти у нас на сайте.
📢 Следить за новостями мира информатики, а также общаться, делиться впечатлениями и готовиться к экзаменам лучше вместе, в нашем Telegram-канале.
О задании
Задание 22 в ЕГЭ по информатике связано с анализом параллельных процессов и их зависимости друг от друга. Оно требует от учащихся навыков работы с диаграммой Ганта, которая визуализирует процессы и их временные промежутки. Разберем, как эффективно решать такие задачи на примере типичного задания.
Анализировать будем уже построенную в прошлой статье диаграмму Ганта. Выглядит она следующим образом:
Вспомним формулировку задания 22 в ЕГЭ: «…Определите максимальную продолжительность отрезка времени, в течение которого возможно одновременное выполнение четырёх процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно…».
Это означает, что нам необходимо сдвинуть процессы таким образом, чтобы количество чисел 4 в строке №14 было максимальное.
Анализ диаграммы Ганта
Шаг 1
Начнем наш анализ с того, что определим, какие процессы от каких зависят и выделим «зависимые» процессы в разные группы. Сначала определим независимые процессы — от них мы и будем впоследствии формировать группы. Сразу видим, что такими являются процессы 1 и 2.
В дальнейшем, для определения групп мы так и будем искать сначала независимые процессы, которые в третьем столбце имеют значение «0». Затем уже будем искать те процессы, которые от них зависят.
Шаг 2
Далее ищем процессы, зависимые от первых двух. Видим, что от них зависит третий процесс, от которого, в свою очередь, зависят четвёртый и пятый. Шестой процесс зависит от пятого, седьмой от четвёртого и шестого, восьмой от седьмого. Следовательно, все процессы от первого до восьмого будут составлять одну группу зависимых процессов.
Все зависимые процессы перемещаются по диаграмме вместе, поскольку они не могут начаться раньше окончания процесса, от которого зависят. Этот этап важен для корректного сдвига процессов на диаграмме и дальнейшего её анализа.
Например, здесь третий процесс не может начаться раньше завершения второго или первого, если его окончание будет позже второго в результате сдвига вправо. Соответственно, четвертый и пятый процессы также не могут начаться раньше заврешения третьего, так как являются зависимыми от него.
По аналогичной схеме находится вторая группа процессов (жёлтая), где от девятого зависит одиннадцатый процесс. И третья группа (зелёная), где от десятого процесса зависит двенадцатый.
Шаг 3
Теперь сдвинем вторую и третью группу правее, чтобы на экране оставалась только первая группа. Для этого нам достаточно в столбце I прописать значения 50 для девятого и десятого процессов.
Примечание
Обратите внимание, что в некоторых заданиях 22 ЕГЭ по информатике могут быть группы процессов, которые длятся и дольше 50 миллисекунд. Следовательно, вам необходимо самостоятельно определять подходящее значения для сдвига групп, с которыми вы не планируете работать на данном этапе.
На этом этапе следует определить максимальное количество процессов, которые могут работать одновременно в первой группе. Как мы видим, здесь максимум могут работать только 2 процесса, а максимальная продолжительность такой цепочки из двух процессов будет с 9 по 17 миллисекунды, то есть 9 миллисекунд.
Цепочки процессов во второй и третьей группах последовательные, значит в них может работать в один и тот же отрезок времени только 1 процесс.
Только вторая группа:
И только третья группа:
Шаг 4
Здесь наша задача заключается в том, чтобы передвинуть вторую и/или третью группу процессов так, чтобы в отрезке с 9 по 17 миллисекунду работало одновременно 4 процесса. Для этого можно, например, сдвинуть начало работы третьей группы процессов на 8 миллисекунд.
Тогда мы и получим максимальную продолжительность отрезка времени, в течение которого работают одновременно 4 процесса — с 9 по 13 миллисекунду. Ответ в этом задании — 5 миллисекунд.