ФИПИ · ЕГЭ · все форматы ответа · 2475 заданий
Тип задачи: Параллельные вычисления.
| КЭС: | 1.1 Основные тенденции развития компьютерных технологий. Параллельные вычисления. Многопроцессорные системы. Распределённые вычислительные системы и обработка больших данных 1.2 Принципы построения и аппаратные компоненты компьютерных сетей. Сетевые протоколы. Сеть Интернет. Адресация в сети Интернет. Протоколы стека TCP/IP. Система доменных имён. Разделение IP-сети на подсети с помощью масок подсетей 1.3 Файловая система. Поиск в файловой системе. Принципы размещения и именования файлов в долговременной памяти. Шаблоны для описания групп файлов |
| Тип ответа: | Краткий ответ |
Ответ: 165
Решение.
Открываем исходный файл ODS. Полная таблица содержит 17 процессов; иллюстративная таблица в тексте задания показывает только формат данных. Для ответа используем именно файл. Все времена ниже указаны в миллисекундах.
Обозначим длительность процесса i через d(i), самое раннее время начала — S(i), завершения — F(i). Время отсчитываем от нуля: независимые процессы начинаются в момент 0 и работают уже на первой миллисекунде.
Процесс может начаться, когда завершатся все его непосредственные предшественники. Поэтому S(i) равно максимуму их времён F. Для независимого процесса S(i) = 0. После начала процесс выполняется непрерывно, так что F(i) = S(i) + d(i).
Сначала рассчитываем независимые процессы, затем те, у которых известны времена завершения всех предшественников. Номер процесса не задаёт порядок вычисления. Параллельные ветви не складываем между собой: в формуле начала нужен максимум.
В таблице ниже процессы расположены в порядке расчёта. Знак «—» означает отсутствие зависимостей. В столбцах S и F показаны численные подстановки.
| ID | Длительность | Предшественники | Начало S | Завершение F |
|---|---|---|---|---|
| 1 | 20 | — | 0 | 0 + 20 = 20 |
| 2 | 22 | — | 0 | 0 + 22 = 22 |
| 3 | 19 | 1, 2 | max(20; 22) = 22 | 22 + 19 = 41 |
| 4 | 24 | — | 0 | 0 + 24 = 24 |
| 5 | 19 | 1, 3 | max(20; 41) = 41 | 41 + 19 = 60 |
| 6 | 16 | 4, 5 | max(24; 60) = 60 | 60 + 16 = 76 |
| 7 | 20 | 1, 4, 6 | max(20; 24; 76) = 76 | 76 + 20 = 96 |
| 8 | 19 | 3, 5, 7 | max(41; 60; 96) = 96 | 96 + 19 = 115 |
| 9 | 13 | 2, 6 | max(22; 76) = 76 | 76 + 13 = 89 |
| 10 | 11 | — | 0 | 0 + 11 = 11 |
| 11 | 22 | 4, 7 | max(24; 96) = 96 | 96 + 22 = 118 |
| 12 | 22 | 8 | 115 = 115 | 115 + 22 = 137 |
| 13 | 25 | 5, 8, 10 | max(60; 115; 11) = 115 | 115 + 25 = 140 |
| 14 | 22 | — | 0 | 0 + 22 = 22 |
| 15 | 19 | 13, 14 | max(140; 22) = 140 | 140 + 19 = 159 |
| 16 | 18 | 14 | 22 = 22 | 22 + 18 = 40 |
| 17 | 25 | 11, 13 | max(118; 140) = 140 | 140 + 25 = 165 |
Проверка расписания: каждая длительность равна F(i) − S(i), а начало не меньше завершения любого предшественника. Все готовые процессы можно запускать одновременно: ограничения на число исполнителей в условии нет.
Докажем, что получены самые ранние времена. Независимый процесс нельзя начать раньше нуля. Если самые ранние завершения его предшественников уже найдены, зависимый процесс не может начаться раньше их максимума. Запуск в этот момент допустим. Продолжая рассуждение по порядку зависимостей, получаем самые ранние начала и завершения всех процессов.
Вся совокупность завершится, когда закончит последний процесс. Наибольшее F в таблице равно 165; оно достигается у процессов с номерами 17.
Проверим минимальность отдельно по цепочке зависимостей 2 → 3 → 5 → 6 → 7 → 8 → 13 → 17. Каждый следующий процесс в ней ждёт предыдущий, поэтому их длительности обязательно складываются:
22 + 19 + 19 + 16 + 20 + 19 + 25 + 25 = 165.
Любое допустимое расписание занимает не меньше 165 мс, а построенное расписание завершает все процессы за это время. Следовательно, минимум равен 165 мс.
Ответ: 165.
Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINF78A5DD.
Сообщение увидит только команда сайта: на странице оно не публикуется.
Комментарии к решению
Комментарии видны всем посетителям сайта.
Комментариев пока нет. Будьте первым.
Чтобы оставить комментарий, войдите или зарегистрируйтесь.