Параллельные процессы с зависимостями

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.

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

Файл к варианту: Ege22_v1.xlsx (31 процесс).

from openpyxl import load_workbook

ws = load_workbook('Ege22_v1.xlsx').active
time, deps = {}, {}
for pid, t, d in ws.iter_rows(min_row=2, values_only=True):
    time[pid] = t
    deps[pid] = [int(x) for x in str(d).split(';') if int(x) != 0]

finish = {}
def fin(p):                      # время завершения процесса p при самом раннем старте
    if p not in finish:
        finish[p] = time[p] + max((fin(q) for q in deps[p]), default=0)
    return finish[p]

for p in time:
    fin(p)
print(sum(1 for p in time if finish[p] <= 49))

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.

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

Файл к варианту: Ege22_v2.xlsx (28 процессов).

from openpyxl import load_workbook

ws = load_workbook('Ege22_v2.xlsx').active
time, deps = {}, {}
for pid, t, d in ws.iter_rows(min_row=2, values_only=True):
    time[pid] = t
    deps[pid] = [int(x) for x in str(d).split(';') if int(x) != 0]

finish = {}
def fin(p):                      # время завершения процесса p при самом раннем старте
    if p not in finish:
        finish[p] = time[p] + max((fin(q) for q in deps[p]), default=0)
    return finish[p]

for p in time:
    fin(p)
print(max(finish.values()))

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.

Определите, через какое минимальное время (в мс) от начала работы завершится процесс с ID = 9, если все процессы, которые могут выполняться параллельно, выполняются параллельно.

Файл к варианту: Ege22_v3.xlsx (28 процессов).

from openpyxl import load_workbook

ws = load_workbook('Ege22_v3.xlsx').active
time, deps = {}, {}
for pid, t, d in ws.iter_rows(min_row=2, values_only=True):
    time[pid] = t
    deps[pid] = [int(x) for x in str(d).split(';') if int(x) != 0]

finish = {}
def fin(p):                      # время завершения процесса p при самом раннем старте
    if p not in finish:
        finish[p] = time[p] + max((fin(q) for q in deps[p]), default=0)
    return finish[p]

for p in time:
    fin(p)
print(finish[9])

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.

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

Файл к варианту: Ege22_v4.xlsx (29 процессов).

from openpyxl import load_workbook

ws = load_workbook('Ege22_v4.xlsx').active
time, deps = {}, {}
for pid, t, d in ws.iter_rows(min_row=2, values_only=True):
    time[pid] = t
    deps[pid] = [int(x) for x in str(d).split(';') if int(x) != 0]

finish = {}
def fin(p):                      # время завершения процесса p при самом раннем старте
    if p not in finish:
        finish[p] = time[p] + max((fin(q) for q in deps[p]), default=0)
    return finish[p]

for p in time:
    fin(p)
print(sum(1 for p in time if finish[p] <= 20))

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.

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

Файл к варианту: Ege22_v5.xlsx (27 процессов).

from openpyxl import load_workbook

ws = load_workbook('Ege22_v5.xlsx').active
time, deps = {}, {}
for pid, t, d in ws.iter_rows(min_row=2, values_only=True):
    time[pid] = t
    deps[pid] = [int(x) for x in str(d).split(';') if int(x) != 0]

finish = {}
def fin(p):                      # время завершения процесса p при самом раннем старте
    if p not in finish:
        finish[p] = time[p] + max((fin(q) for q in deps[p]), default=0)
    return finish[p]

for p in time:
    fin(p)
print(max(finish.values()))

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.

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

Файл к варианту: Ege22_v6.xlsx (32 процесса).

from openpyxl import load_workbook

ws = load_workbook('Ege22_v6.xlsx').active
time, deps = {}, {}
for pid, t, d in ws.iter_rows(min_row=2, values_only=True):
    time[pid] = t
    deps[pid] = [int(x) for x in str(d).split(';') if int(x) != 0]

finish = {}
def fin(p):                      # время завершения процесса p при самом раннем старте
    if p not in finish:
        finish[p] = time[p] + max((fin(q) for q in deps[p]), default=0)
    return finish[p]

for p in time:
    fin(p)
print(sum(1 for p in time if finish[p] <= 38))

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.

Определите, через какое минимальное время (в мс) от начала работы завершится процесс с ID = 6, если все процессы, которые могут выполняться параллельно, выполняются параллельно.

Файл к варианту: Ege22_v7.xlsx (26 процессов).

from openpyxl import load_workbook

ws = load_workbook('Ege22_v7.xlsx').active
time, deps = {}, {}
for pid, t, d in ws.iter_rows(min_row=2, values_only=True):
    time[pid] = t
    deps[pid] = [int(x) for x in str(d).split(';') if int(x) != 0]

finish = {}
def fin(p):                      # время завершения процесса p при самом раннем старте
    if p not in finish:
        finish[p] = time[p] + max((fin(q) for q in deps[p]), default=0)
    return finish[p]

for p in time:
    fin(p)
print(finish[6])

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.

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

Файл к варианту: Ege22_v8.xlsx (23 процесса).

from openpyxl import load_workbook

ws = load_workbook('Ege22_v8.xlsx').active
time, deps = {}, {}
for pid, t, d in ws.iter_rows(min_row=2, values_only=True):
    time[pid] = t
    deps[pid] = [int(x) for x in str(d).split(';') if int(x) != 0]

finish = {}
def fin(p):                      # время завершения процесса p при самом раннем старте
    if p not in finish:
        finish[p] = time[p] + max((fin(q) for q in deps[p]), default=0)
    return finish[p]

for p in time:
    fin(p)
print(sum(1 for p in time if finish[p] <= 25))

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.

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

Файл к варианту: Ege22_v9.xlsx (24 процесса).

from openpyxl import load_workbook

ws = load_workbook('Ege22_v9.xlsx').active
time, deps = {}, {}
for pid, t, d in ws.iter_rows(min_row=2, values_only=True):
    time[pid] = t
    deps[pid] = [int(x) for x in str(d).split(';') if int(x) != 0]

finish = {}
def fin(p):                      # время завершения процесса p при самом раннем старте
    if p not in finish:
        finish[p] = time[p] + max((fin(q) for q in deps[p]), default=0)
    return finish[p]

for p in time:
    fin(p)
print(max(finish.values()))

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.

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

Файл к варианту: Ege22_v10.xlsx (24 процесса).

from openpyxl import load_workbook

ws = load_workbook('Ege22_v10.xlsx').active
time, deps = {}, {}
for pid, t, d in ws.iter_rows(min_row=2, values_only=True):
    time[pid] = t
    deps[pid] = [int(x) for x in str(d).split(';') if int(x) != 0]

finish = {}
def fin(p):                      # время завершения процесса p при самом раннем старте
    if p not in finish:
        finish[p] = time[p] + max((fin(q) for q in deps[p]), default=0)
    return finish[p]

for p in time:
    fin(p)
print(sum(1 for p in time if finish[p] <= 29))

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.

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

Файл к варианту: Ege22_v11.xlsx (32 процесса).

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.

Определите, через какое минимальное время (в мс) от начала работы завершится процесс с ID = 6, если все процессы, которые могут выполняться параллельно, выполняются параллельно.

Файл к варианту: Ege22_v12.xlsx (20 процессов).

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.

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

Файл к варианту: Ege22_v13.xlsx (29 процессов).

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.

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

Файл к варианту: Ege22_v14.xlsx (22 процесса).

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.

Определите, через какое минимальное время (в мс) от начала работы завершится процесс с ID = 13, если все процессы, которые могут выполняться параллельно, выполняются параллельно.

Файл к варианту: Ege22_v15.xlsx (21 процесс).