Задание 22 ЕГЭ по информатике · 78A5DD
Критический путь / успевшие процессыПовышеннаяКЭС 1.1КЭС 1.2
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор процесса (ID), во второй строке таблицы — время его выполнения в миллисекундах, в третьей строке перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0. Пример организации данных в файле:
Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор процесса (ID), во второй строке таблицы — время его выполнения в миллисекундах, в третьей строке перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0. Пример организации данных в файле:
| ID процесса B | Время выполнения процесса B (мс) | ID процесса(ов) A |
|---|---|---|
| 1 | 4 | 0 |
| 2 | 3 | 0 |
| 3 | 1 | 1; 2 |
| 4 | 7 | 3 |
Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
К заданию прилагается файл с данными — скачайте его в задании внутри Precettore.
Показать ответ
165
Подсказки (3)
- Какая последовательность зависимых процессов определяет момент завершения всей совокупности?
- Для каждого процесса найдите время его завершения: время выполнения процесса плюс максимальное время завершения всех процессов, от которых он зависит.
- Вычислите времена завершения процессов по зависимостям из файла и выберите максимальное из них. Получается 165 мс.
Решение
1. Представим процессы в виде ориентированного графа зависимостей. Независимые процессы могут запускаться одновременно, поэтому общее время определяется самой длинной цепочкой зависимых процессов — критическим путём.
2. Для каждого процесса последовательно вычисляем время его завершения. Если процесс независим, его время завершения равно времени выполнения. Если у процесса есть предшественники, к его длительности прибавляется наибольшее время завершения предшественников.
Ti=ti+maxj∈PᵢTj
3. После обработки всех строк файла наибольшее время завершения процесса равно 165 миллисекундам.
Tmax=165
2. Для каждого процесса последовательно вычисляем время его завершения. Если процесс независим, его время завершения равно времени выполнения. Если у процесса есть предшественники, к его длительности прибавляется наибольшее время завершения предшественников.
Ti=ti+maxj∈PᵢTj
3. После обработки всех строк файла наибольшее время завершения процесса равно 165 миллисекундам.
Tmax=165
Частые ошибки
- Складывают времена всех процессов, хотя независимые процессы выполняются параллельно.
- Для процесса с несколькими предшественниками складывают времена всех предшественников вместо выбора максимального.
- Учитывают только непосредственные зависимости и не прослеживают всю цепочку предшествующих процессов.
Похожие задания
22Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор…Критический путь / успевшие процессы · 24EC2E22Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор…Критический путь / успевшие процессы · ECAE2C22Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор…Критический путь / успевшие процессы · 3E352F22Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор…Критический путь / успевшие процессы · 309D2922В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в…Критический путь / успевшие процессы · 55E2A122Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор…Критический путь / успевшие процессы · E9B7A322Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор…Критический путь / успевшие процессы · A6FA9D22Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор…Критический путь / успевшие процессы · E01A9D
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.