Задание 22 ЕГЭ по информатике · 55E2A1
Критический путь / успевшие процессыВысокаяКЭС 1.1
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.
Определите минимальное время (в мс), за которое завершатся 16 процессов. Считать, что каждый процесс начинается в самое раннее допустимое время. Время отсчитывается непрерывно с первой миллисекунды. В ответе укажите только число — количество миллисекунд.
Типовой пример организации данных в файле
Для приведённой таблицы процесс 3 начинается на 8-й мс, заканчивается на 9-й мс.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.
Определите минимальное время (в мс), за которое завершатся 16 процессов. Считать, что каждый процесс начинается в самое раннее допустимое время. Время отсчитывается непрерывно с первой миллисекунды. В ответе укажите только число — количество миллисекунд.
Типовой пример организации данных в файле
| ID процесса B | Время выполнения процесса B (мс) | ID процесса(-ов) A |
|---|---|---|
| 1 | 3 | 0 |
| 2 | 4 | 1 |
| 3 | 2 | 2; 4 |
| 4 | 5 | 0 |
| 5 | 8 | 1; 4 |
| 6 | 3 | 1 |
Для приведённой таблицы процесс 3 начинается на 8-й мс, заканчивается на 9-й мс.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
К заданию прилагается файл с данными — скачайте его в задании внутри Precettore.
Показать ответ
19
Подсказки (3)
- Для каждого процесса определите самое раннее время его запуска с учётом завершения всех процессов-зависимостей.
- Время завершения процесса равно времени его наиболее поздно завершившейся зависимости плюс длительность самого процесса.
- Последовательно обработав зависимости процессов из файла, найдите максимальное время завершения среди 16 процессов: оно равно 19 мс.
Решение
1. Представим процессы в виде ориентированного графа: ребро направлено от процесса-зависимости к процессу, который использует его результат.
2. Для каждого процесса вычислим раннее время завершения. Для независимого процесса оно равно его длительности, а для зависимого — сумме его длительности и максимального времени завершения всех зависимостей.
Ti=ti+maxj∈DᵢTj
3. Обработав таблицу процессов в порядке, при котором зависимости рассматриваются раньше зависимых процессов, получаем максимальное время завершения всех 16 процессов.
4. Максимальное время завершения равно 19 миллисекундам.
2. Для каждого процесса вычислим раннее время завершения. Для независимого процесса оно равно его длительности, а для зависимого — сумме его длительности и максимального времени завершения всех зависимостей.
Ti=ti+maxj∈DᵢTj
3. Обработав таблицу процессов в порядке, при котором зависимости рассматриваются раньше зависимых процессов, получаем максимальное время завершения всех 16 процессов.
4. Максимальное время завершения равно 19 миллисекундам.
Частые ошибки
- Складывают длительности всех процессов, не учитывая возможность параллельного выполнения.
- Учитывают только одну зависимость, хотя процесс может зависеть от нескольких процессов.
- Берут сумму времени по любой цепочке, а не длину критического пути.
Похожие задания
22Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор…Критический путь / успевшие процессы · ECAE2C22Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор…Критический путь / успевшие процессы · 3E352F22Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор…Критический путь / успевшие процессы · 309D2922Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор…Критический путь / успевшие процессы · 78A5DD22Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор…Критический путь / успевшие процессы · E9B7A322Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор…Критический путь / успевшие процессы · A6FA9D22Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор…Критический путь / успевшие процессы · E01A9D22Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор…Критический путь / успевшие процессы · FABCEC
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.