Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад

22. Вычислительные процессы: В файле содержится информация о совокупности N вычислительных…

Задание #298218
Решено верно
Решено неверно
Сообщить о проблеме

В файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс $B$ зависит от процесса $A$, если для выполнения процесса $B$ необходимы результаты выполнения процесса $A$. В этом случае процессы могут выполняться только последовательно.

Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение $0$.

Типовой пример организации данных в файле:

ID процесса $B$Время выполнения процесса $B$ (мс)ID процесса(-ов) $A$
$1$$4$$0$
$2$$3$$0$
$3$$1$$1$; $2$
$4$$7$$3$

Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.

Используя данные из файла, составим таблицу, на какой мс может закончиться каждый из процессов. Независимые процессы $1$, $2$, $4$ и $12$ завершатся на $20$, $26$, $28$ и $29$ мс соответственно.

Процесс $8$ зависит от $1$, значит завершится на $20+32=52$ мс. Процесс $5$ зависит от $2$ и завершится на $26+29=55$ мс. Процесс $7$ зависит от $5$, поэтому закончится на $55+31=86$ мс, а процесс $10$ зависит от $7$ и завершится на $86+34=120$ мс.

Процесс $13$ зависит от $10$ и $12$: позже заканчивается $10$ (на $120$ мс), значит $13$ завершится на $120+32=152$ мс. От него зависят два процесса — $3$ заканчивается на $152+22=174$ мс, а $17$ на $152+36=188$ мс.

Процесс $9$ зависит от $3$ и $4$, позже заканчивается $3$, поэтому $9$ завершится на $174+28=202$ мс. Дальше процесс $11$ зависит от $9$ и завершится на $202+30=232$ мс, а процесс $15$ тоже зависит от $9$ и завершится на $202+39=241$ мс.

Процесс $14$ зависит от $11$ и $15$: позже заканчивается $15$ (на $241$ мс), значит $14$ завершится на $241+33=274$ мс. Наконец, процесс $16$ зависит от $14$ и $15$, стартует после $274$ мс и завершается на $274+33=307$ мс. Для сравнения, процесс $6$ зависит от $5$, $7$, $8$ и $15$ и заканчивается лишь на $241+25=266$ мс — раньше, чем $16$.

Таким образом, вся совокупность процессов завершится на $307$ мс.

Время, мсID процесса
$20$$1$
$26$$2$
$28$$4$
$29$$12$
$52$$8$
$55$$5$
$86$$7$
$120$$10$
$152$$13$
$174$$3$
$188$$17$
$202$$9$
$232$$11$
$241$$15$
$266$$6$
$274$$14$
$307$$16$

Приведём другое решение на языке Python.

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-07.ods', engine='odf', header=None, skiprows=1)

t, dep = {}, {}
for _, row in df.iterrows():
    pid = int(row[0])
    t[pid] = int(row[1])
    s = str(row[2]).strip()
    dep[pid] = [] if s == '0' else [int(x) for x in s.split(';')]

@lru_cache(None)
def finish(p):                        # момент завершения процесса p
    return t[p] + max([finish(d) for d in dep[p]], default=0)

print(max(finish(p) for p in t))   # 307

Процесс не может стартовать раньше, чем закончатся все, от которых он зависит, но и ждать дольше незачем — значит время его завершения равно собственной длительности плюс максимум по временам завершения предшественников. Ответ — максимум по всем процессам, потому что вся совокупность закончится тогда, когда закончится самый поздний из них.

Показать
Очки опыта 20
Спросить Зави
0 заданий сегодня

Предложить улучшение