Сколько баллов дают за задание 22 ЕГЭ по информатике?

До 1 балл из 29 первичных баллов (проект спецификации КИМ ЕГЭ-2027 ФИПИ). Уровень сложности — повышенный.

Сколько времени тратить на задание 22?

Примерное время выполнения по спецификации ФИПИ — 7 минут; на весь экзамен отводится 235 минут.

Где потренироваться на задании 22?

В тренажёре «Ранга» по этому номеру сейчас 30 заданий с проверкой ответа и разбором; первое задание открывается без регистрации.

Задание 22: Многопроцессорные системы: параллельные процессы

Теория к заданию № 22 ЕГЭ-2027 по информатике: коротко правило, приём решения по шагам, два разобранных примера из банка «Ранга» и ошибки, на которых теряют балл.

Что проверяет задание 22

Что проверяет: Умение построить математическую модель для расчёта времени выполнения взаимозависимых процессов на многопроцессорной системе.
Баллы: до 1 балл из 29 первичных
Уровень: повышенный
Время: около 7 минут (примерное время по спецификации ФИПИ; на весь экзамен — 235 минут)
Формат: краткий ответ; нужен компьютер (программа, таблица или файл)

Правило и теория

Процесс начинается сразу после завершения всех процессов, от которых он зависит (при неограниченном числе процессоров).
Время окончания процесса: end(i) = t(i) + max(end(j)) по всем j, от которых зависит i (для независимых — end(i) = t(i)).
Минимальное время выполнения всего комплекса — максимум end(i) по всем процессам (длина критического пути).
В таблице: столбец «время окончания» с формулой МАКС по зависимостям + своё время.
Вопросы «сколько процессов выполняется одновременно в момент T» решаются по интервалам [end − t; end).

Приём решения по шагам

Выпиши для каждого процесса его время и зависимости.
Посчитай время окончания процессов в порядке зависимостей.
Найди максимум — это минимальное время всего комплекса.
Ответь на конкретный вопрос (время, число одновременно идущих процессов).

Два разобранных примера из банка «Ранга»

Сначала реши сам — потом раскрой ответ и разбор. Ответы взяты из банка, по которому работает тренажёр, и проверены.

Пример 1

Комплекс из 8 процессов выполняется на вычислительной машине с неограниченным числом процессоров. Процесс может начаться только после того, как закончились все процессы, от которых он зависит; процессы, не зависящие друг от друга, идут одновременно. Номер процесса | длительность в миллисекундах | от каких процессов зависит: 1 | 7 | — 2 | 9 | 1 3 | 10 | 1 4 | 10 | 2 5 | 6 | 4 6 | 9 | 2 7 | 9 | 3 8 | 3 | 1, 7 Определи наименьшее возможное время выполнения всего комплекса процессов. Ответ — целое число миллисекунд.

Показать ответ и разбор

Ответ: 32

Ступень 1. Процессоров сколько угодно, поэтому время комплекса — это не сумма длительностей. Сумма всех 8 длительностей здесь 63 мс, и столько комплекс занял бы только на одном процессоре, по очереди. Ступень 2. Ограничение одно: процесс ждёт свои зависимости. Значит, для каждого процесса время окончания равно его длительности плюс самое позднее окончание среди тех, от кого он зависит. Ступень 3. Считай по возрастанию номеров — это можно делать сразу, потому что каждый процесс зависит только от процессов с меньшими номерами, и к моменту счёта их окончания уже известны. Ступень 4. Самым поздним оказался процесс 5: он заканчивается на 32-й миллисекунде. Самая длинная цепочка зависимостей — 1 → 2 → 4 → 5; её суммарная длительность и есть ответ 32 мс. Для сравнения: самый долгий отдельный процесс идёт 10 мс — ответ не может быть меньше. Ступень 5. То же время тремя независимыми способами (проход по возрастанию номеров, разбор зависимостей с памятью и круги уточнений до неподвижной точки) даёт 32 мс. Ответ: 32.

Карточка банка «Ранга» informatics-22-16 — авторское тренировочное задание в формате ЕГЭ, ключ проверен. Решить похожее в тренажёре

Пример 2

Задание выполняется с использованием прилагаемых файлов. В файле 22.ods (22.xlsx) содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0. Определи минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно. В ответе запиши только целое число. Для сверки: в файле 8 процессов; первые строки таблицы — ID 1: 9 мс, зависит от 0; ID 2: 7 мс, зависит от 1; ID 3: 5 мс, зависит от 1;2.

Файл к заданию: 22.ods · 22.xlsx

Показать ответ и разбор

Ответ: 34

Считаем окончания всех процессов. Самое позднее — у процесса 7: 34 мс. Критический путь: 1 (9 мс) → 2 (7 мс) → 3 (5 мс) → 6 (6 мс) → 7 (7 мс). Ответ: 34.

Карточка банка «Ранга» informatics-22-0 — авторское тренировочное задание в формате ЕГЭ, ключ проверен. Решить похожее в тренажёре

Типичные ошибки

Складывают времена всех процессов вместо поиска максимального пути.
Берут минимум вместо максимума по зависимостям.
Не учитывают зависимость, указанную через несколько ID (через точку с запятой).
Ошибаются с границами интервалов при подсчёте одновременных процессов.

Тренироваться: 30 заданий этого номера

Тренажёр «Ранга»: условие, проверка ответа сразу и разбор по шагам. Первое задание — без регистрации, дальше — в кабинете ученика.

Решать задание 22

Кабинет ученика · Разбор задания 22: 10 примеров

Частые вопросы о задании 22

Сколько баллов дают за задание 22 ЕГЭ по информатике?: До 1 балл из 29 первичных баллов (проект спецификации КИМ ЕГЭ-2027 ФИПИ). Уровень сложности — повышенный.
Сколько времени тратить на задание 22?: Примерное время выполнения по спецификации ФИПИ — 7 минут; на весь экзамен отводится 235 минут.
Что проверяет задание 22?: Умение построить математическую модель для расчёта времени выполнения взаимозависимых процессов на многопроцессорной системе.
Где потренироваться на задании 22?: В тренажёре «Ранга» по этому номеру сейчас 30 заданий с проверкой ответа и разбором; первое задание открывается без регистрации.

Источник: ФИПИ — демоверсии, спецификации, кодификаторы ЕГЭ, архив материалов 2027 года (проект спецификации и демоверсии КИМ ЕГЭ-2027 ФИПИ по информатике (опубликован как проект; 27 заданий, 29 первичных баллов, экзамен на компьютере)).

Тексты теории — авторские материалы «Ранга». Примеры — авторские тренировочные задания в формате ЕГЭ, не официальные задания ФИПИ. Мы не обещаем конкретных баллов: результат зависит от твоей работы.