Задание 22 ЕГЭ по информатике: процессы и ресурсы

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

Номер и тему сверяйте по демоверсии 2027 года. Файл, судя по публикациям о проекте демоверсии, в формате ods, как и в задании 9 про электронные таблицы, так что с форматом вы уже знакомы, если разобрали то задание. Общую карту первой части даёт статья про первую часть ЕГЭ по информатике, а структуру всей работы — разбор структуры экзамена.

Правило, из которого всё следует

Процесс может начаться, когда закончились все процессы, от которых он зависит. Значит, время его начала равно наибольшему из времён окончания предшественников, а время окончания равно времени начала плюс его длительность. Для процесса без зависимостей время начала равно нулю. Время окончания всей совокупности — наибольшее из времён окончания по всем процессам. Других идей в задании нет: всё остальное — способ аккуратно применить это правило к нескольким тысячам строк.

Разберём маленькую совокупность из пяти процессов. Первый длится 4 и ни от кого не зависит, второй длится 3 и тоже, третий длится 5 и ждёт первый и второй, четвёртый длится 2 и ждёт третий, пятый длится 6 и ждёт второй. Первый заканчивается в момент 4, второй в момент 3. Третий может стартовать, когда готовы оба, то есть в момент 4, и заканчивается в момент 9. Четвёртый стартует в 9 и заканчивается в 11. Пятый стартует в 3 и заканчивается в 9. Вся совокупность готова в момент 11, и самая длинная цепочка идёт через первый, третий и четвёртый процессы: 4 + 5 + 2. Её называют критическим путём, и ответ задачи всегда равен длине такого пути.

Заметьте, что пятый процесс, самый долгий по собственной длительности, на ответ не влияет вовсе. Так ошибаются, когда ищут самый долгий процесс вместо самого длинного пути.

На том же примере видно, как читается граница. В момент 9 заканчиваются третий и пятый процессы и стартует четвёртый, поэтому в этот момент идёт один процесс, а не три. В момент 3 заканчивается второй и стартует пятый: идут первый и пятый, то есть два. Одновременно работают не больше двух процессов за всё время, и это легко проверить, пройдя по моментам 0, 3, 4, 9 на черновике. Привычка записывать для каждого процесса пару «начало, окончание» и считать, что промежуток закрыт слева и открыт справа, избавляет от большинства споров с проверяющей машиной.

Таблицей

Для файлов с большим числом строк я бы выбрал таблицу: каждое промежуточное значение лежит на виду, и ошибку можно найти глазами. Работа идёт в несколько шагов, и ни один не требует ничего, кроме базовых функций.

Первый шаг — разбить столбец зависимостей. В нём номера процессов записаны через точку с запятой, и формулой с ними работать неудобно. В меню данных есть команда, которая делит текст ячейки на несколько столбцов по выбранному разделителю: выберите точку с запятой, и справа появятся столбцы с отдельными номерами. Посмотрите, сколько их вышло, это максимальное число предшественников у одного процесса. Убедитесь, что значения распознаны как числа: выровненные влево подозрительны.

Второй шаг — столбец времени окончания. Для каждой строки это длительность плюс наибольшее из времён окончания предшественников. Время окончания предшественника находится по его номеру в столбце с номерами процессов, функцией поиска по таблице. Если номера идут подряд от единицы и совпадают с порядком строк, можно брать значение прямо по позиции, но надёжнее искать по номеру, потому что в файле порядок строк может не совпадать с порядком зависимостей. Для процессов без предшественников вместо поиска ставится ноль: функция ЕСЛИ отдельно проверяет пустую ячейку или ноль в списке зависимостей. Не рассчитывайте на то, что формула сама догадается, что нуль не обозначает процесс.

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

Формулы ссылаются друг на друга, и порядок строк не мешает, пока нет замкнутых зависимостей. Замкнутых зависимостей в условии быть не может (процесс не способен ждать сам себя), и таблица разберётся без подсказок.

Третий шаг — максимум по столбцу окончаний. Это и есть ответ, если вопрос про общее время.

Те же столбцы отвечают и на соседние вопросы. Момент начала названного процесса — это его окончание минус длительность, поэтому отдельный столбец начала удобно иметь сразу. Число процессов, идущих в заданный момент, считается подсчётом строк, у которых начало не позже этого момента и окончание позже него: условие на границу читайте буквально, потому что в момент, когда один процесс закончился, а другой начался, они не работают одновременно. Это одна функция подсчёта по двум условиям, и она же ловит отличие «строго больше» от «не меньше», на котором расходятся ответы.

Программой

Тот же алгоритм записывается рекурсивно: время окончания процесса равно его длительности плюс наибольшее время окончания среди предшественников, и для процессов без зависимостей наибольшее по пустому набору считается нулём. Данные удобно держать в двух словарях: в одном длительность по номеру процесса, в другом список номеров предшественников. Функция принимает номер, а возвращает время окончания. Функция запоминает уже посчитанное, иначе один и тот же процесс пересчитывается столько раз, сколько путей к нему ведёт, и программа зависает. Это в точности та же техника, что в задании 16 про рекурсию, включая предел глубины вызовов: цепочка зависимостей из нескольких тысяч процессов упирается в него так же, как факториал.

Основное препятствие здесь — чтение файла, алгоритм прост. Стандартные средства Python, насколько я знаю, формат ods напрямую не читают, поэтому данные приходится передавать программе другим путём: например, скопировать таблицу в текстовый файл или сохранить в текстовом формате, если рабочее место это допускает. Это нужно выяснять заранее по описанию рабочего места и правилам проведения экзамена, до дня экзамена. Если выяснить не удалось, таблица остаётся единственным надёжным инструментом.

Что полезно сделать до экзамена

Пока файла перед глазами нет, потренируйтесь на маленьких наборах, придуманных самостоятельно: десять процессов с зависимостями, нарисованными на листе стрелками. Решите сначала руками, найдите критический путь, а потом переложите тот же набор в таблицу и сравните. Расхождение означает, что вы ошиблись либо в формулах, либо в руках, и разбираться в нём на маленьком наборе дешевле всего. Когда два способа сходятся на трёх придуманных наборах, переходите к файлам прошлых лет и держите время.

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

Когда процессоров мало

Бывают условия, где вопрос усложняется: число работ, идущих одновременно, ограничено, и надо узнать время окончания при таком ограничении или момент, когда в системе работает определённое число процессов. Простая формула максимума здесь не работает. Приходится моделировать ход времени: на каждом шаге из готовых к запуску работ выбираются те, на которые хватает ресурсов, и считается, когда освободятся места. Правило выбора среди готовых работ в условии задано (по номеру, по длительности), и менять его нельзя.

Модель такого рода в таблице делать мучительно, в программе она занимает два десятка строк, и это тот случай, когда программа выигрывает у таблицы. Какие именно вопросы встретятся в вашем году, видно по демоверсии. Я бы, как минимум, потренировал и вариант с общим временем, и вариант с ограничением, чтобы при встрече с любым не терять первые минуты на раздумья.

На чём ошибаются

Типичных потерь четыре:

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

Проверяется результат на маленьком примере: выделите первые пять-шесть процессов, посчитайте окончания руками, сравните с таблицей. Если расходятся, дело в ссылках.

С чего начать, если ничего не складывается

Первое, что стоит выяснить, — понимаете ли вы правило на примере из пяти процессов выше. Если не понимаете, решайте на бумаге три-четыре маленьких набора, пока критический путь не перестанет удивлять. Если правило понятно, а таблица не складывается, проверьте, получается ли у вас разбить столбец и найти значение по номеру: оба навыка из задания 9. Если же таблица получается, а программа нет, причина в чтении файла, и её лучше установить в начале подготовки, пока она не стоила баллов.

Курс информатики в школе про параллельные процессы говорит мало, обычно в связи с операционными системами и очень поверхностно, так что тема для большинства новая. Зато по сути это поиск самого длинного пути в графе без циклов, и тот, кто решал задачи с перебором делителей в задании 25, узнает ту же дисциплину: свести условие к одному правилу и проверить его на малом примере. Подробнее о том, что школьный курс даёт для экзамена, в статье информатика в школе: что учить и в каком порядке.

Начать поиск:

• репетиторы по информатике для подготовки к ЕГЭ
• все репетиторы для подготовки к ЕГЭ

Вопросы и ответы

Почему нельзя просто сложить все длительности? Сумма всех длительностей — это время, если бы процессы шли строго по одному. Параллельность его сокращает до длины самого длинного пути, и разница между двумя числами как раз и составляет содержание задачи. Если ваш ответ совпал с суммой, значит, зависимости не были учтены ни разу.

Что быстрее: таблица или программа? Для вопроса про общее время обычно таблица, если предшественников у процесса немного. Для вопросов с ограниченными ресурсами обычно программа.

Можно ли сначала отсортировать строки, чтобы предшественники шли раньше? Можно, и тогда формулы будут ссылаться только вверх, но сортировать разделённый на столбцы файл опасно: если сортируется не вся таблица целиком, номера и длительности разъедутся, и ответ перестанет быть правдой. Таблице порядок не мешает, поэтому лучше сортировку не делать.