Крылов 2023 Вар19
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор процесса (ID), во второй строке таблицы – время его выполнения в миллисекундах, в третьей строке перечислены с разделителем «;» ID
процессов, от которых зависит данный процесс. Если процесс является
независимым, то в таблице указано значение 0. Время выполнения одного из
процессов неизвестно и для данного процесса в соответствующей колонке
обозначено как t.
Пример организации данных в файле:
| ID процесса B | Время выполнения процесса B (мс) | ID процесса(ов) A |
| 1 | 4 | 0 |
| 2 | 3 | 0 |
| 3 | 1 | 1; 2 |
| 4 | 7 | 3 |
Определите максимально возможное
время t (время выполнения процесса), при котором выполнение всей
совокупности процессов, при условии, что все независимые друг от друга
процессы могут выполняться параллельно и один процесс может сменять
другой завершившийся мгновенно, завершилось не более чем за 15 мс.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Аналогично с решением задачи из демоверсии 2023 заполним таблицу из данного задания.
https://oldmoodle.gotovimsyakit.ru/pluginfile.php/617/mod_page/content/3/22var19%20%281%29.xlsx
Самое большое известное значение 15 (для процесса с ID 6). Самое большое значение с неизвестной - это t+12 (для процесса с ID 10). Соответственно, нам нужно, чтобы выполнялась одна из двух систем:
\( \left[ \begin{gathered} \left\{ \begin{gathered} t+12 \geq 15 \\ t+12 \leq15 \\ \end{gathered} \right. \hfill \\ \left\{ \begin{gathered} 15 \geq t+12 , \hfill \\ 15 \leq 15 . \hfill \\ \end{gathered} \right. \hfill \\ \end{gathered} \right. \)
Соответственно получаем
\( \left[ \begin{gathered} \left\{ \begin{gathered} t\geq3 \\ t \leq3 \\ \end{gathered} \right. \hfill \\ t \leq3 \hfill \\ \end{gathered} \right. \)
Наибольшее подходящее значение - 3.
Ответ: 3.