Задание 22: время выполнения параллельных процессов
Коротко
Дана таблица процессов: время выполнения и список процессов, от которых зависит каждый. Независимые процессы идут параллельно. Время завершения процесса = его длительность + максимум времён завершения процессов, от которых он зависит. Минимальное время всего комплекса — максимум времён завершения. Удобно считать в электронной таблице или рекурсией.
Формула
fin(P) = dur(P) + max(fin(Q) для Q в зависимостях P), 0 если зависимостей нет.
Ответ: max fin(P).
Пример
| Процесс | Время | Зависит от |
|---|---|---|
| A | 3 | — |
| B | 2 | — |
| C | 4 | A |
| D | 1 | B, C |
fin(A) = 3, fin(B) = 2, fin(C) = 7, fin(D) = 1 + max(2, 7) = 8. Ответ: 8.
Варианты вопроса
- Сколько процессов выполняются одновременно в момент t.
- Наибольшее время, на которое можно задержать процесс без изменения общего времени.
Типичные ошибки
- Складывают все времена, забыв о параллельности.
- Берут минимум вместо максимума из зависимостей.
Что дальше
Проверьте себя на заданиях этого типа в тренажёре Upward. Начните с диагностики по предмету: она покажет, какие номера уже получаются, а какие стоит подтянуть, и по её итогам соберётся личный план подготовки.
Как это выглядит в задании 22
Пример 1 из 2
A — 3 мс; B — 2 мс; C — 4 мс, зависит от A; D — 1 мс, зависит от B и C. Минимальное время?
- Разбор
- fin(C) = 7, fin(D) = 1 + max(2, 7) = 8; программа даёт 8.
- Ответ
- 8
Пример 2 из 2
Процесс без зависимостей длится 5 мс. Когда он закончится?
- Разбор
- Начинается в момент 0.
- Ответ
- В момент 5 мс
Мини-тест: 5 вопросов
- Вопрос 1 из 5
Когда начинается процесс без зависимостей?
Показать ответ
Ответ: В момент 0.
Сразу.
- Вопрос 2 из 5
Время завершения процесса?
Показать ответ
Ответ: Длительность + максимум завершений зависимостей.
Ждём самую позднюю.
- Вопрос 3 из 5
Ответ задачи о минимальном времени?
Показать ответ
Ответ: Максимум времён завершения.
Последний процесс.
- Вопрос 4 из 5
Можно ли решать в Excel?
Показать ответ
Ответ: Да.
МАКС по зависимостям.
- Вопрос 5 из 5
Складывать ли все длительности?
Показать ответ
Ответ: Нет.
Процессы идут параллельно.
Проверьте всё задание 22, а не одну тему
Диагностика Upward покажет, какие задания ЕГЭ по информатике стоит подтянуть в первую очередь.
Уже есть аккаунт? Войти