Минимальное время выполнения процессов

ЕГЭ · Информатика · Задание 13 · Параллельные вычисления

ПовышеннаяФИПИ78A5DDКороткий ответ≈ 5 минутОтвет сверен с ключом

В файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Процесс $B$ зависит от процесса $A$, если для выполнения процесса $B$ необходимы результаты выполнения процесса $A$. В этом случае процессы могут выполняться только последовательно.

Информация о процессах представлена в файле в виде таблицы: в первой строке таблицы указан идентификатор процесса (ID), во второй строке — время его выполнения в миллисекундах, в третьей строке перечислены через разделитель «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, в таблице указано значение 0.

Определите минимальное время, через которое завершится выполнение всей совокупности процессов, если все независимые друг от друга процессы могут выполняться параллельно. Используйте данные из прилагаемого файла.

Файл к заданию

78A5DD.odsТаблица ODS · 3 КБ

Условие как в банке ФИПИ — открыть и сверить

Впишите правильный ответ.

Задание выполняется с использованием прилагаемых файлов.

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно.

Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор процесса (ID), во второй строке таблицы – время его выполнения в миллисекундах, в третьей строке перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.

Пример организации данных в файле:

ID процесса B	Время выполнения процесса B (мс)	ID процесса(ов) A
1	4	0
2	3	0
3	1	1; 2
4	7	3

Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Ваш ответ

Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.

3 уровня: от лёгкого толчка до почти готового решения. Следующий открывается, когда прочитан предыдущий, — чтобы не перепрыгнуть сразу к ответу.

1Мягкая — с чего смотретьуровень 1 из 3

Какая последовательность зависимых процессов определяет момент завершения всей совокупности?

2Наводящая — какие числа считатьуровень 2 из 3

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

3Прямая — фактически решениеуровень 3 из 3

Вычислите времена завершения процессов по зависимостям из файла и выберите максимальное из них. Получается 165 мс.

Всё равно не складывается?Полное решение с обоснованием каждого шага — на отдельной странице.

Открыть решение

ПредыдущаяМинимальное время процессовСледующаяМинимальное время выполнения процессов

Задание 13 ЕГЭ, информатика