22 задание ЕГЭ информатика
Параллельные процессы
1 балл ≈ 7 мин уровень П Многопроцессорные системы: параллельные процессы
Задание 22 – файл с таблицей процессов: ID, время выполнения, список процессов, от которых зависит данный. Процессы выполняются параллельно, если независимы, и начинаются как можно раньше. Найти минимальное время завершения всех процессов, количество процессов, завершённых к моменту T, и т. п. 1 балл.
Ключевая формула: время окончания процесса = max(время окончания всех его зависимостей) + его длительность. Независимый процесс начинается в момент 0 и заканчивается в момент «длительность».
Алгоритм
- Для каждого процесса посчитай время окончания по формуле (в Excel – формулой с МАКС по зависимостям, в Python – рекурсией).
- Общее время выполнения всех процессов = максимум времён окончания.
- «Количество процессов, завершённых за первые T мс» – число процессов с окончанием ≤ T (миллисекунды нумеруются с 1: процесс длительностью 3, начатый в момент 0, занимает 1-ю, 2-ю и 3-ю мс).
Шаблон на Python (данные из таблицы – в словарь):
from functools import lru_cache
data = {} # id: (время, [зависимости])
for line in open("22.txt"):
pid, t, deps = line.strip().split("\t")
data[int(pid)] = (int(t), [int(d) for d in deps.split(";")])
@lru_cache(None)
def finish(i):
t, deps = data[i]
start = max((finish(d) for d in deps if d != 0), default=0)
return start + t
ends = [finish(i) for i in data]
print(max(ends), sum(1 for e in ends if e <= 17))Разобранный пример. 1: 3 мс, нет зависимостей; 2: 4 мс, от 1; 3: 2 мс, от 2 и 4; 4: 5 мс, нет. Окончание: 1 – 3, 4 – 5, 2 – 3 + 4 = 7, 3 – max(7, 5) + 2 = 9. Всё выполнится за 9 мс; за первые 6 мс завершатся процессы 1 и 4.
Ловушки: зависимости через «;» с пробелами – используй int() после split (он игнорирует пробелы); забыть, что процесс ждёт ВСЕ свои зависимости, а не первую; путать «начинается в мс» и «заканчивается в мс».
- В Excel добавь столбец «окончание» и считай его формулой =МАКС(окончания зависимостей)+время.
- Процесс с зависимостью 0 – независимый, стартует сразу.
- Проверь программу на примере из условия – там дан ответ для маленькой таблицы.
Разобранные задания 22 из открытого банка ФИПИ
Пример 1 · код ФИПИ E01A9D
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор процесса (ID), во второй строке таблицы – время его выполнения в миллисекундах, в третьей строке перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0. Пример организации данных в файле:
Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно. Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла. | ||||||||||||||||
Задание выполняется с использованием прилагаемых файлов.Показать ответ и решение
Ответ: 196
Время окончания процесса = длительность + максимум окончаний процессов, от которых он зависит.
Наибольшее время окончания – 196 мс.
Пример 2 · код ФИПИ 4A47D4
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены Определите максимальное количество процессов, которые параллельно выполняются на 22-й мс. Считать, что каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с 1. Типовой пример организации данных в файле
Для приведённой таблицы процесс 3 начинается на 8-й мс, заканчивается на 9-й мс.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла. | ||||||||||||||||||||||
Задание выполняется с использованием прилагаемых файлов.Показать ответ и решение
Ответ: 3
Находим самые ранние старты процессов и считаем, кто выполняется на 22-й мс.
Таких процессов 3.
Пример 3 · код ФИПИ 4128BD
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, Типовой пример организации данных в файле
Для приведённой таблицы процесс 3 начинается на 8-й мс, заканчивается на 9-й мс.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла. | ||||||||||||||||||||||
Задание выполняется с использованием прилагаемых файлов.Показать ответ и решение
Ответ: 34
Время окончания процесса = длительность + максимум окончаний процессов, от которых он зависит.
Минимальное общее время – 34 мс.
Частые вопросы о задании 22
Сколько баллов даёт задание 22 ЕГЭ по информатике?
Максимум – 1 первичный балл. Норма времени на экзамене – около 7 мин. Уровень сложности – П.
Что проверяет задание 22?
Задание 22 – файл с таблицей процессов: ID, время выполнения, список процессов, от которых зависит данный. Процессы выполняются параллельно, если независимы, и начинаются как можно раньше. Найти минимальное время завершения всех процессов, количество процессов, завершённых к моменту T, и т. п. 1 балл.
Как подготовиться к заданию 22?
Прочитайте теорию выше: алгоритм, нужные факты и ловушки. Затем решите подход из 10 заданий с автопроверкой и разбором – первые без регистрации – и вернитесь к ошибкам. В пробниках Сотки номер встречается в полных вариантах ФИПИ с подсчётом баллов.