Анализ диаграммы Ганта. Задание 22 ЕГЭ по информатике

Постановка задачи

Задание 22 в ЕГЭ по информатике связано с анализом параллельных процессов и их зависимости друг от друга. Оно требует от учащихся навыков работы с диаграммой Ганта, которая визуализирует процессы и их временные промежутки. Разберем, как эффективно решать такие задачи на примере типичного задания.

Анализировать будем уже построенную в прошлой статье диаграмму Ганта. Выглядит она следующим образом:

Анализ диаграммы Ганта. Задание 22 ЕГЭ по информатике

Вспомним формулировку задания 22 в ЕГЭ: «…Определите максимальную продолжительность отрезка времени, в течение которого возможно одновременное выполнение четырёх процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно…».

Это означает, что нам необходимо сдвинуть процессы таким образом, чтобы количество чисел 4 в строке №14 было максимальное.

Анализ диаграммы Ганта

Шаг 1

Начнем наш анализ с того, что определим, какие процессы от каких зависят и выделим «зависимые» процессы в разные группы. Сначала определим независимые процессы — от них мы и будем впоследствии формировать группы. Сразу видим, что такими являются процессы 1 и 2.

Анализ диаграммы Ганта. Задание 22 ЕГЭ по информатике

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

Шаг 2

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

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

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

По аналогичной схеме находится вторая группа процессов (жёлтая), где от девятого зависит одиннадцатый процесс. И третья группа (зелёная), где от десятого процесса зависит двенадцатый.

Анализ диаграммы Ганта. Задание 22 ЕГЭ по информатике

Шаг 3

Теперь сдвинем вторую и третью группу правее, чтобы на экране оставалась только первая группа. Для этого нам достаточно в столбце I прописать значения 50 для девятого и десятого процессов.

Примечание

Обратите внимание, что в некоторых заданиях 22 ЕГЭ по информатике могут быть группы процессов, которые длятся и дольше 50 миллисекунд. Следовательно, вам необходимо самостоятельно определять подходящее значения для сдвига групп, с которыми вы не планируете работать на данном этапе.

Анализ диаграммы Ганта. Задание 22 ЕГЭ по информатике

На этом этапе следует определить максимальное количество процессов, которые могут работать одновременно в первой группе. Как мы видим, здесь максимум могут работать только 2 процесса, а максимальная продолжительность такой цепочки из двух процессов будет с 9 по 17 миллисекунды, то есть 9 миллисекунд.

Анализ диаграммы Ганта. Задание 22 ЕГЭ по информатике

Цепочки процессов во второй и третьей группах последовательные, значит в них может работать в один и тот же отрезок времени только 1 процесс.

Только вторая группа:

Анализ диаграммы Ганта. Задание 22 ЕГЭ по информатике

И только третья группа:

Анализ диаграммы Ганта. Задание 22 ЕГЭ по информатике

Шаг 4

Здесь наша задача заключается в том, чтобы передвинуть вторую и/или третью группу процессов так, чтобы в отрезке с 9 по 17 миллисекунду работало одновременно 4 процесса. Для этого можно, например, сдвинуть начало работы третьей группы процессов на 8 миллисекунд.

Анализ диаграммы Ганта. Задание 22 ЕГЭ по информатике

Тогда мы и получим максимальную продолжительность отрезка времени, в течение которого работают одновременно 4 процесса — с 9 по 13 миллисекунду. Ответ в этом задании — 5 миллисекунд.