Автор статьи: Андрей Рогов
Введение
Задание № 22 в его нынешнем виде появилось в 2023 году. За прошедшие три года формулировка задания несколько раз менялась, причём довольно сильно. В качестве исходных данных представлена таблица, описывающая процессы. Для каждого процесса известен его номер, время выполнения и от каких процессов он зависит.
Один из популярных методов решения таких заданий — построение диаграммы Ганта. Диаграмма Ганта — это горизонтальный столбчатый график. Его часто используют в менеджменте проектов, чтобы проиллюстрировать относительное время выполнения разных этапов и задач.
Для решения 22-го задания такие диаграммы можно строить как в черновике на бумаге, так и с помощью компьютера. Наиболее удобный способ решения — с помощью электронных таблиц. Во многих редакторах электронных таблиц есть примеры построения таких диаграмм. На рисунке ниже изображён шаблон диаграммы Ганта в LibreOffice Calc.
В этом шаблоне задачи обозначаются заливкой ячеек. Ещё можно использовать геометрические фигуры. В статье мы рассматриваем задачи, где не придётся менять время процессов, поэтому воспользуемся заливкой.
Построим диаграмму Ганта для приведённой таблицы. Сократим ширину столбцов правее исходных данных и расположим там временну́ю шкалу. Выделим цветом ячейки независимых процессов (т. е. 101 и 102), по одной ячейке на 1 миллисекунду.
Процесс 103 зависит от процессов 101 и 102, следовательно он может начаться только после завершения последнего из них. Так, процесс 103 начнётся с 5-й мс. А процесс процесса 104 зависит от 103-го, который к текущему моменту не завершился. Поэтому сначала изображаем 103-й процесс и только потом 104-й. Нельзя начинать процесс, пока не закончились все процессы, от которых он зависит.
Итоговая диаграмма представлена на картинке.
Задача 1. Минимальное время всей совокупности процессов
Уменьшим ширину столбцов, сделаем временну́ю шкалу и заполним ячейки независимых процессов.
Далее, соблюдая порядок процессов, изобразим все оставшиеся.
Несколько полезных советов при заполнении:
- удобно выделять цветом сразу все ячейки одного процесса. Для этого их необходимо выделить, например удерживая Shift и нажимая стрелку вправо. При этом в нижней части окна указывается, сколько ячеек выделено
- для наглядности можно выделять целиком строки процессов, от которых зависит текущий, — так удобнее искать его возможное время начала
- для вертикальной прокрутки окна таблицы используется Shift + колёсико мыши
- для изменения масштаба используется Ctrl + колёсико мыши
Полученная диаграмма представлена на рисунке.
По ней видно, что последним завершился процесс с ID 15 — через 51 мс.
Задача 2. Минимальное время завершения всех процессов с большой длительностью
Обратим внимание на исходные данные.
Здесь длительность выполнения процессов намного больше. Знакомый способ решения всё равно сработает, но это будет долго, а при закрашивании диапазонов больше 20 мс легко ошибиться.
Альтернативный вариант решения — построить диаграмму вручную, указывая продолжительность цепочки процессов в виде числа. Чтобы вычислить время окончания процесса, необходимо взять время окончания всех процессов, от которых зависит текущий, и из них выбрать максимальное. К нему прибавляем время выполнения текущего процесса.
Например, чтобы вычислить время процесса 6, возьмём максимальное время из процессов 4, 5, 7 и 8. Это время завершения 8-го процесса — 67 мс. Когда так выстроятся все процессы, максимальное время и будет ответом. Продемонстрируем в виде рисунка.
В таком решении придётся многое делать вручную, что часто приводит к ошибкам в вычислениях. Попробуем формализовать основные шаги решения.
- Вычисляем время завершения процесса
- если этот процесс независимый, берём его время
- если процесс зависит от других и их время завершения известно, то берём максимальное время и прибавляем время текущего процесса
- Если необходимо, для каждого процесса вычисляем время его начала
Последний пункт необходим для некоторых формулировок заданий.
Все эти пункты тоже можно реализовать в электронных таблицах, без вычислений вручную. Продемонстрируем решение в программе LibreOffice Calc. В других программах для работы с таблицами решение аналогичное.
На первом шаге разобьём столбец C на несколько, так, чтобы каждое число было в отдельной ячейке. Для этого используем команду «Данные» → «Текст по столбцам» и укажем в качестве разделителя «;».
Теперь оформим заготовку для остальных ячеек. Размечать таблицу разными цветами не обязательно, но это позволяет лучше ориентироваться в данных.
Столбцы C, D, E и F содержат исходные данные, разделённые по столбцам. В столбцах G, H, I и J будет записано время завершения процессов из столбцов С — F. Так мы узнаем время завершения всех процессов, от которых зависит текущий процесс. Зная эту информацию, мы сможем вычислить время завершения текущего процесса. Его занесём в столбец L. А столбец K необходим, если вопрос задачи требует знать время начала процесса.
Начнём с заполнения столбцов G — J. Зная ID процесса, будем вносить время его окончания с помощью функции ВПР. Поскольку нам предстоит копировать формулу на весь диапазон ячеек, область поиска необходимо зафиксировать с помощью абсолютной адресации. Некоторые процессы зависят от процесса с ID 0, т. е. являются независимыми.
У функции ВПР в LibreOffice Calc есть одна особенность. Если искомое значение — пустая ячейка, то функция выдаёт #Н/Д, то есть «неопределённые данные». Чтобы избежать этой ошибки, можно заполнить все пустые ячейки с ID процессов А нулями или использовать функцию ЕСНД. Она позволяет указать, какое значение заносить в ячейку, если получен результат #Н/Д.
Используем второй вариант. Итоговая формула в ячейке G2:
G2=ЕСНД(ВПР(C2;$A$2:$L$19;12;0);0)
Скопируем формулу на весь диапазон ячеек G1 — J18. На этом этапе решения значениями ячеек будут нули, поскольку мы ещё не внесли формулу для времени окончания процесса. В ячейках, содержащих время ненулевых ID, будут пустые значения.
В ячейку L2 внесём формулу вычисления времени окончания процесса: максимальное время завершения процессов, от которых зависит текущий, плюс время этого процесса.
L2=МАКС(G2:J2)+B2
Время начала процесса заполним как время окончания минус время выполнения процесса. Для удобства к разности прибавим единицу. Тогда время начала и окончания будет содержать миллисекунды, в которые процесс шёл, т. е. время будет указано включительно.
K2=L2-B2+1
Итоговая таблица представлена на рисунке.
Чтобы определить время завершения всех процессов, возьмём максимальное время из столбца L. Его тоже лучше не искать глазами, а использовать функцию МАКС или выделить весь столбец и посмотреть на значение в строке состояния.
Задача 3. Максимальное количество процессов за определённое время
В исходных данных содержится 25 процессов. Хотя время выполнения каждого процесса небольшое, всего процессов довольно много, поэтому рисовать диаграмму вручную будет долго. Решим задание с помощью функции ВПР, как в предыдущем.
Чтобы ответить на вопрос, сколько процессов завершилось за первые 17 мс, необходимо посчитать, у скольких процессов время окончания меньше или равно 17. Таких процессов 12. Можно посчитать вручную, а можно использовать фильтр или формулу:
=СЧЁТЕСЛИ(H2:H26;"<=17")
Схожим образом можно решить задачу с вопросом «Определите минимальное время (в мс), за которое завершится n процессов». Сортируем данные по времени окончания и находим время окончания n-го процесса.
Задача 4. Максимальное количество процессов на определённой миллисекунде
Теперь нужно найти и время начала процессов. Построим таблицу.
Чтобы определить, что процесс выполняется на 15-й мс, число 15 должно быть между временем его начала и конца (включая границы). В этом примере нам подойдут ячейки, выделенные на скриншоте жёлтым:
Также время начала понадобится, чтобы ответить на вопросы вида «Определите максимальное количество процессов, которые могут начаться не ранее чем с 8-й мс от начала отсчёта».
Заключение
В статье рассмотрены различные подходы к решению задания № 22 ЕГЭ по информатике без использования сдвигов процессов, с применением электронных таблиц. Преимущества предложенного подхода:
- наглядность представления данных
- возможность автоматизации вычислений
- удобство анализа временных интервалов
- гибкость при изменении условий задачи
Освоение этих методов позволит эффективно решать задание № 22, даже если появятся новые вариации условий. Полученные навыки также можно применять при решении других задач, связанных с анализом временных зависимостей.
Рекомендуем решить подборку задач для практики.