Задание 22 ЕГЭ по информатике · FABCEC
Критический путь / успевшие процессыВысокаяКЭС 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.
Показать ответ
136
Подсказки (3)
- Для каждого процесса определите момент его завершения с учётом всех процессов-предшественников.
- Если процесс зависит от нескольких процессов, он может начаться после завершения самого позднего из них: TB=tB+max(TA₁,TA₂,…).
- Обработайте процессы в порядке зависимостей, вычислите время завершения каждого процесса и выберите максимальное значение. Получается 136 мс.
Решение
1. Представим процессы в виде ориентированного графа: ребро направлено от процесса-зависимости к процессу, который можно запустить после него.
2. Для независимого процесса время завершения равно его длительности. Для остальных процессов сначала определяем время завершения всех предшественников.
3. Если процесс зависит от нескольких предшественников, его старт возможен только после завершения последнего из них. Поэтому время завершения вычисляется как сумма собственной длительности и максимального времени завершения предшественников.
Ti=ti+maxj∈PᵢTj
4. После обработки всех строк файла максимальное время завершения среди процессов равно 136 миллисекундам.
2. Для независимого процесса время завершения равно его длительности. Для остальных процессов сначала определяем время завершения всех предшественников.
3. Если процесс зависит от нескольких предшественников, его старт возможен только после завершения последнего из них. Поэтому время завершения вычисляется как сумма собственной длительности и максимального времени завершения предшественников.
Ti=ti+maxj∈PᵢTj
4. После обработки всех строк файла максимальное время завершения среди процессов равно 136 миллисекундам.
Частые ошибки
- Складывают длительности всех процессов, хотя независимые процессы выполняются параллельно.
- Берут минимум времени завершения предшественников вместо максимума.
- Не учитывают собственное время выполнения текущего процесса.
Похожие задания
22В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в…Критический путь / успевшие процессы · 55E2A122Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор…Критический путь / успевшие процессы · E9B7A322Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор…Критический путь / успевшие процессы · A6FA9D22Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор…Критический путь / успевшие процессы · E01A9D22Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор…Критический путь / успевшие процессы · EBDAEF22В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в…Критический путь / успевшие процессы · 50D06B22Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор…Критический путь / успевшие процессы · 25FE3022Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор…Критический путь / успевшие процессы · A8AC39
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.