22 задание ЕГЭ информатика: как решать процессы и ВПР
В 22 задании ЕГЭ по информатике нужно найти, за какое время завершатся все процессы, если зависимые процессы ждут результатов других, а независимые идут параллельно. Главная идея: начало процесса = максимум из времён окончания тех, от кого он зависит; конец = начало + длительность; ответ — наибольший конец. Это можно посчитать на бумаге, в Excel через ВПР или короткой программой на Python.
Что проверяет 22 задание ЕГЭ по информатике
Задание № 22 посвящено многопроцессорным системам и математической модели процессов. Тебе дают таблицу: у каждого процесса есть номер, длительность и список процессов, результаты которых нужны для старта. Если зависимостей нет (прочерк или ноль), процесс стартует сразу.
Если процессоров достаточно, всё, что может идти параллельно, идёт параллельно. Поэтому общее время определяется самой долгой цепочкой зависимостей. Сумма всех длительностей здесь почти всегда неверный путь.
Точную форму задания в текущем году (формат файла, число запросов, ограничения на процессоры) смотри в демоверсии и спецификации на сайте ФИПИ (fipi.ru): формулировки могут меняться, а способ решения остаётся тем же.
Как решать 22 задание ЕГЭ по информатике: алгоритм
Работай по одной схеме для каждого процесса, и путаницы не будет.
- Выпиши для каждого процесса: длительность и список зависимостей.
- Для процессов без зависимостей: начало = 0, конец = длительность.
- Для остальных: начало = максимальный конец среди всех процессов, от которых он зависит. Не первый в списке и не последний, а именно максимальный.
- Конец = начало + длительность.
- Ответ — максимальный конец среди всех процессов (если в условии не спрашивают другое).
- Проверь: ответ не меньше самой длинной одиночной длительности и не больше суммы всех длительностей.
Пример задания из банка «Ранга»
Этот пример показывает базовую ситуацию задания № 22: часть процессов идёт параллельно, а общее время задаёт самая долгая цепочка зависимостей. Реши его сам по алгоритму выше и только потом сверься с ответом.
Условие. В таблице описан вычислительный процесс: для каждого процесса указаны его номер, время выполнения в миллисекундах и номера процессов, результаты которых нужны для его начала (прочерк — процесс может начаться сразу).
| № | время | зависит от |
|---|---|---|
| 1 | 3 | — |
| 2 | 8 | 1 |
| 3 | 6 | 1, 2 |
| 4 | 4 | 1, 3 |
| 5 | 4 | 3, 4 |
| 6 | 5 | 1, 2 |
| 7 | 8 | 4 |
| 8 | 8 | 4 |
Процессы, у которых есть все необходимые результаты, могут выполняться одновременно (число процессоров не ограничено). Определи минимальное время, через которое завершатся все процессы. В ответе запиши только целое число.
Показать ответ и решение
- Процессоров сколько угодно, значит время определяется самой длинной цепочкой зависимостей. Время окончания процесса равно его длительности плюс наибольшее время окончания среди тех, от кого он зависит.
- Начни с процессов без зависимостей: их время окончания равно их длительности.
Ответ: 29
22 задание ЕГЭ по информатике: разбор на примере
Ниже в статье приведён пример из банка «Ранга» с проверенным ответом. Пройди его по алгоритму сам и сверься: процесс 1 идёт с 0 до 3, процесс 2 стартует в момент 3 (ждёт процесс 1), процесс 3 ждёт и 1, и 2, поэтому стартует после окончания процесса 2.
Обрати внимание на момент, где ученики чаще всего ошибаются: если процесс зависит от двух результатов, его старт определяет более поздний из них. Когда пройдёшь цепочку до конца, найди максимум по всем концам, а не конец последнего процесса в таблице.
22 задание ЕГЭ информатика Excel и ВПР: шаблон решения
Когда процессов много (в файловом варианте их может быть заметно больше, чем в учебной таблице), удобнее посчитать в таблице. Идея шаблона: два расчётных столбца — «начало» и «конец». Пусть номер процесса в столбце A, длительность в B, зависимости в C, D, E (пустые ячейки или нули — нет зависимости), начало в F, конец в G.
Формула конца: =F2+B2. Формула начала: максимум из конца каждой зависимости, найденного через ВПР. Для одной зависимости это выглядит так: =ЕСЛИОШИБКА(ВПР(C2;$A$2:$G$1000;7;0);0), где 7 — номер столбца G в выбранном диапазоне, а ЕСЛИОШИБКА превращает «не найдено» (пустая зависимость) в ноль.
Для нескольких зависимостей оберни такие ВПР в МАКС, перечислив их через точку с запятой: по одному ВПР на каждый столбец зависимостей. Формулу протяни вниз на все строки. Ответ — МАКС по столбцу G.
Если в файле зависимости записаны одной ячейкой через запятую, сначала разбей их на столбцы (Данные — Текст по столбцам). Названия функций и разделитель аргументов зависят от версии Excel: проверь, что формула у тебя принимается, на первых двух-трёх строках.
22 задание ЕГЭ информатика кодом: Python
Решение на питоне короткое и не зависит от порядка строк. Логика та же, что на бумаге: конец процесса = его длительность + максимальный конец зависимостей.
Шаблон из четырёх шагов:
- Прочитай данные в два словаря: t[i] — длительность, dep[i] — список зависимостей (пустой список, если зависимостей нет).
- Заведи словарь end для запомненных результатов.
- Напиши функцию конца процесса: если i уже в end, верни значение; иначе посчитай t[i] + max(конец(j) для j в dep[i], default=0) и запомни.
- Ответ: max(конец(i) для всех i).
Типичные ошибки в 22 задании
Разберём то, что чаще всего стоит баллов на практике.
- Складывают длительности всех процессов вместо поиска самой долгой цепочки.
- Берут конец любой одной зависимости вместо максимума из всех.
- Теряют процессы без зависимостей: в Excel пустая ячейка даёт ошибку ВПР, а в коде — пустой max.
- Берут конец последнего процесса в таблице, хотя максимальный конец может быть у другого.
- Не проверяют единицы: время в условии может быть в миллисекундах, ответ нужен в тех же единицах.
- Не перечитывают вопрос: иногда спрашивают не общее время, а другое число, и алгоритм нужно подправить под условие.
Как потренироваться и проверить себя
Сначала реши 3–4 небольшие таблицы вручную, чтобы цепочка зависимостей стала привычной. Потом повтори те же задачи в Excel или на Python и сравни результаты: расхождение — повод найти ошибку в формуле или в коде.
Подборку заданий № 22 с проверкой ответа можно найти в тренажёре «Ранга»; общий порядок подготовки по предмету описан в статье про подготовку к ЕГЭ по информатике с нуля. Оформление и формат реальных вариантов всегда сверяй с материалами ФИПИ.
Частые вопросы
Можно ли решить 22 задание без Excel и программирования?
Да, если процессов немного: пройди таблицу по алгоритму «начало = максимум концов зависимостей». Для больших файловых вариантов быстрее Excel или Python, поэтому полезно уметь хотя бы один из способов.
Что лучше для 22 задания: ВПР или Python?
Оба способа дают один результат. Выбирай тот, в котором меньше шансов ошибиться именно у тебя: если уверенно пишешь код, достаточно короткой функции с запоминанием; если ближе таблицы, используй ВПР с МАКС.
Почему нельзя просто сложить все времена?
Потому что независимые процессы выполняются одновременно на разных процессорах. Складывать нужно только длительности внутри одной цепочки зависимостей, а из всех цепочек выбирается самая долгая.
Где посмотреть актуальный формат 22 задания?
Демоверсию, кодификатор и спецификацию публикует ФИПИ на сайте fipi.ru. Сравни формулировку и формат данных там со своими тренировочными задачами и при необходимости подстрой шаблон.
Что делать, если в таблице есть цикл или ссылка на несуществующий процесс?
В корректном задании цикла быть не должно: процесс не может ждать сам себя через цепочку. Если в учебных данных он появился, перепроверь, правильно ли ты переписал зависимости.
Полезно по теме
Читать дальше
Проверить себя в тренажёре
Открывается тренировочное задание в формате ЕГЭ: условие видно сразу, краткий ответ проверяется без регистрации.
Решить задание в тренажёреМатериал — разъяснение «Ранг». Официальные правила экзамена, расписание, шкалы баллов и перечни заданий публикуют ФИПИ (fipi.ru) и Рособрнадзор (obrnadzor.gov.ru). Мы не обещаем конкретных баллов: результат зависит от твоей работы.