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

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

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

4 варианта с ответами

Приостановка выполнения процесса не допускается. Будем говорить, что процесс В зависит от процесса А, если для выполнения процесса В необходимы результаты выполнения процесса А. В этом случае процессы А и В могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. Если процесс независимый, то в таблице указано значение 0. Считать, что каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с 1. Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла

Текст распознан с изображения задания. Формулы, таблицы и рисунки смотрите на картинке ниже.

ЕГЭ по информатике: задание 22, условие
Скачать файл
Ответ
12

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

ПроцессВремяЗависит от
14—
231
371
422, 3
553
664, 5
Определите минимальное время, через которое будут завершены все процессы. Время указано в миллисекундах.

Ответ
22

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

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

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

ПроцессВремяЗависит от
12—
26—
341, 2
432
583, 4
615
753
Определите минимальное время, через которое будут завершены все процессы. Время указано в миллисекундах.

Ответ
19

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

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

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

ПроцессВремяЗависит от
15—
221
391
442
533, 4
675
Определите минимальное время, через которое будут завершены все процессы. Время указано в миллисекундах.

Ответ
24

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

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

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

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

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

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

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

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

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

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

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

Ответ9

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

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