Задание 22 ЕГЭ по информатике

Что проверяет: Параллельные вычислительные процессы

Задание 22 ЕГЭ по информатике проверяет тему «параллельные вычислительные процессы». Ниже вы найдёте 1 вариант с условием, ответом и разбором, а под ними теория и алгоритм решения этого номера.

Скачать файл

Ответ

Теория к заданию 22 ЕГЭ по информатике: параллельные вычислительные процессы

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

Что нужно знать

Процесс может начаться, только когда завершены все процессы, от которых он зависит.
Время начала процесса равно максимуму времён окончания всех его предшественников.
Время окончания = время начала + длительность процесса.
Независимые процессы (значение 0 в третьем столбце) начинаются с первой миллисекунды.
Задача сводится к обходу графа зависимостей в топологическом порядке.

Параллельные процессы

Каждый процесс имеет длительность и список процессов, от которых он зависит.
Процесс начинается не раньше, чем завершатся все процессы, от которых он зависит.
Время начала процесса равно максимуму времён завершения его предшественников.
Время завершения равно времени начала плюс длительность.
Считайте по порядку: сначала процессы без зависимостей (время начала 0), затем те, чьи предшественники уже посчитаны.
Минимальное время выполнения всего набора равно максимуму среди времён завершения всех процессов.
Это критический путь: самая длинная цепочка зависимостей по суммарной длительности.
В электронной таблице удобно завести столбцы «начало» и «конец» и заполнять их итеративно.

Как решать задание 22

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

Разбор примера

Процесс 1 длится 4 мс и ни от чего не зависит. Процесс 2 длится 3 мс и зависит от процесса 1. Процесс 3 длится 6 мс и ни от чего не зависит. Процесс 4 длится 2 мс и зависит от процессов 2 и 3. Найдите минимальное время выполнения всех процессов.

Процесс 1: зависимостей нет, начинается в 0, завершается в 4.
Процесс 3: зависимостей нет, начинается в 0, завершается в 6.
Процесс 2: зависит от первого, начинается в 4, завершается в 4 + 3 = 7.
Процесс 4: зависит от второго (завершён в 7) и третьего (завершён в 6), значит, начинается в момент максимума, то есть в 7.
Процесс 4 завершается в 7 + 2 = 9.
Максимум среди времён завершения равен 9 мс.

Ответ9

Частые ошибки

Берут время начала как сумму, а не максимум времён предшественников.
Считают процессы, завершившиеся позже указанного момента.

Задание 22 входит в ЕГЭ по информатике. На этой странице собраны все варианты этого номера, которые разобраны на сайте: условие, правильный ответ и разбор решения. Остальные номера открываются в списке выше, а целиком все задания ЕГЭ по информатике с ответами собраны на странице предмета.