Задание 22 ЕГЭ по информатике · 50D06B
Критический путь / успевшие процессыВысокаяКЭС 1.1
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.
Определите минимальное время (в мс), за которое завершатся 18 процессов. Считать, что каждый процесс начинается в самое раннее допустимое время. Время отсчитывается непрерывно с первой миллисекунды. В ответе укажите только число — количество миллисекунд.
Типовой пример организации данных в файле
Для приведённой таблицы процесс 3 начинается на 8-й мс, заканчивается на 9-й мс.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.
Определите минимальное время (в мс), за которое завершатся 18 процессов. Считать, что каждый процесс начинается в самое раннее допустимое время. Время отсчитывается непрерывно с первой миллисекунды. В ответе укажите только число — количество миллисекунд.
Типовой пример организации данных в файле
| 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.
Показать ответ
15
Подсказки (3)
- Для каждого процесса определите момент, когда завершатся все процессы, от которых он зависит.
- Если процесс зависит от нескольких процессов, его начало определяется максимальным временем их завершения.
- Последовательно вычислите ранние моменты окончания всех процессов из файла; время завершения последнего процесса равно длине критического пути и составляет 15 мс.
Решение
1. Представим процессы в виде ориентированного графа: зависимость означает, что процесс-источник должен завершиться до начала зависимого процесса.
2. Для каждого процесса вычисляем его раннее время начала: оно равно нулю для независимых процессов, а для остальных — максимальному времени окончания всех процессов-предшественников.
tнач(B)=maxA∈P(B)tок(A)
3. Время окончания процесса равно сумме его раннего времени начала и длительности. После обработки всех 18 процессов максимальное время окончания равно 15 мс.
tок(B)=tнач(B)+τB=15
2. Для каждого процесса вычисляем его раннее время начала: оно равно нулю для независимых процессов, а для остальных — максимальному времени окончания всех процессов-предшественников.
tнач(B)=maxA∈P(B)tок(A)
3. Время окончания процесса равно сумме его раннего времени начала и длительности. После обработки всех 18 процессов максимальное время окончания равно 15 мс.
tок(B)=tнач(B)+τB=15
Частые ошибки
- Складывают длительности всех процессов, не учитывая возможность параллельного выполнения.
- Для процесса с несколькими предшественниками берут минимальное, а не максимальное время их окончания.
- Путают раннее время начала процесса с временем его окончания.
Похожие задания
22Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор…Критический путь / успевшие процессы · A6FA9D22Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор…Критический путь / успевшие процессы · E01A9D22Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор…Критический путь / успевшие процессы · FABCEC22Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор…Критический путь / успевшие процессы · EBDAEF22Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор…Критический путь / успевшие процессы · 25FE3022Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор…Критический путь / успевшие процессы · A8AC3922Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор…Критический путь / успевшие процессы · B6388322В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в…Критический путь / успевшие процессы
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.