Решение (программа):

1. 
   можно решить задачу с помощью программы, если сохранить файл в CSV-формате (меню Файл – Сохранить как); файл будет выглядеть так:
   

ID процесса B;Время выполнения процесса B (мс);ID процесса (ов) A;

1;4;0;

2;3;0;

3;1;"1; 2";

4;7;3;

5;6;3;

6;3;5;

7;1;"4; 6";

8;2;7;

9;7;0;

10;8;0;

11;6;9;

12;6;10;

2. 
   для чтения CSV-файла проще всего применить объект reader из стандартного модуля csv:
   

from csv import reader

with open( "22-0.csv", encoding="cp1251" ) as F:

rdr = reader( F, delimiter=';', quotechar='"' ) # (1)

next( rdr ) # читаем заголовки и пропускаем их # (2)

...

параметр encoding, переданный функции open, означает, что файл сохранен в кодировке Windows (CP-1251), именно так сохраняет CSV-файлы Excel; тут проблема только в чтении русских букв, поэтому можно просто заранее удалить из файла первую строку с заголовками

3. 
   в строке (1) создается объект reader, в параметрах указываем, что разделитель данных (delimiter) – точка с запятой, а знак " используется как кавычка (quotechar)
   
4. 
   в строке (2) мы читаем (и не сохраняем) строку с заголовками, если, конечно, не удалили ее заранее; если удалили, то функцию next() вызывать не нужно
   
5. 
   теперь займемся хранением данных; будем использовать два словаря:
   

• 
  словарь finalTime содержит уже известные значения времени окончания процессов (вызов: finalTime[id] даёт время окончания процесса с идентификатором id)
  
• 
  словарь data содержит данные тех процессов, для которых время окончания неизвестно: вызов data[id] даёт кортеж (t, dependsOn), где
  

t – длительность процесса с идентификатором id,

dependsOn – массив идентификаторов процессов, от которых зависит данный процесс

6. 
   в цикле читаем данные из файла;
   

for s in rdr:

id, t = int(s[0]), int(s[1])

dependsOn = list( map( int, s[2].split(';') ) )

if dependsOn == [0]:

finalTime[id] = t # известно время окончания

else:

data[id] = ( t, dependsOn ) # неизвестно время окончания

массив строк s содержит данные одной строки CSV-файла

• 
  s[0] – идентификатор (эту строку нужно преобразовать в целое число, вызвав int)
  
• 
  s[1] – длительность процесса (тоже нужно преобразовать в целое число)
  
• 
  s[2] – перечисление идентификаторов процессов, от которых зависит данный процесс; эта строка может иметь, например, такой вид:
  

---

'1; 2'

в результате вызова s[2].split(';') получаем такой массив из двух строк

['1', '2']

применяя к каждому элементу функцию int, получаем массив целых чисел dependsOn:

[1, 2]

Если этот массив состоит только из нуля, сразу записываем в словарь finalTime идентификатор и соответствующее ему время окончания процесса, которое равно длительности процесса (считаем, что он стартует в момент 0):

if dependsOn == [0]:

finalTime[id] = t # известно время окончания

else:

data[id] = ( t, dependsOn ) # неизвестно время окончания

Если же у процесса есть зависимости, записываем в словарь data кортеж, в котором хранятся длительность процесса и массив dependsOn идентификаторов процессов, от которых он зависит.

7. 
   самое интересное – это обработка данных словаря data; все эти данные нужно преобразовать в соответствующие элементы словаря finalTime так чтобы словарь data стал пустым; делаем так:
   

while data:

ids = list(data.keys())

for id in ids:

# если известны моменты окончания всех процессов, от

# которых зависит процесс id, записать в finalTime время

# окончания этого процесса и удалить данные процесса id из

# словаря data

8. 
   чтобы определить, что моменты окончания всех нужных процессов известны, используем функцию all:
   

if all( (x in finalTime) for x in dependsOn ):

...

это значит «если все идентификаторы из массива dependsOn уже есть в словаре finalTime»

9. 
   определяем время старта процесса id как максимальное время завершения всех процессов, от которых он зависит:
   

startId = max( finalTime[x] for x in dependsOn )

10. 
    вычисляем время окончания процесса id:
    

finalTime[id] = startId + t

и удаляем данные этого процесса из массива data:

del data[id]

11. 
    вот полный цикл обработки:
    

while data:

ids = list(data.keys())

for id in ids:

t, dependsOn = data[id]

if all( (x in finalTime) for x in dependsOn ):

startId = max( finalTime[x] for x in dependsOn )

finalTime[id] = startId + t

del data[id]

12. 
    ответ – это максимальное время окончания процесса из словаря finalTime:
    

print( "Ответ:", max(finalTime.values()) )

13. 
    полная программа:
    

from csv import reader

with open( "22-0.csv", encoding="cp1251" ) as F:

rdr = reader( F, delimiter=';', quotechar='"' )

next( rdr ) # читаем заголовки и пропускаем их

data = {}

finalTime = {}

for s in rdr:

id, t = int(s[0]), int(s[1])

dependsOn = list( map( int, s[2].split(';') ) )

if dependsOn == [0]:

finalTime[id] = t # известно время окончания

---

else:

data[id] = ( t, dependsOn ) # неизвестно время окончания

while data:

ids = list(data.keys())

for id in ids:

t, dependsOn = data[id]

if all( (x in finalTime) for x in dependsOn ):

startId = max( finalTime[x] for x in dependsOn )

finalTime[id] = startId + t

del data[id]

print( "Ответ:", max(finalTime.values()) )

14. 
    обратим внимание, что программа не использует никаких предположений о расположении данных о процессах в исходном списке, они могут быть расположены в произвольном порядке
    
15. 
    программа зациклится, если данные будут некорректны, например, процесс 1 зависит от процесса 2, а процесс 2 – от процесса 1 (циклическая ссылка)
    
16. 
    Ответ: 17.
    

---

Задачи для тренировки:

1. 
   (В. Шубинкин) В файле 22-1.xls содержится информация о совокупности 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 могут выполняться параллельно, при этом процесс 1 завершится через 4 мс, а процесс 2 – через 3 мс с момента старта. Процесс 3 может начаться только после завершения обоих процессов 1 и 2, то есть, через 4 мс после старта. Он длится 1 мс и закончится через 4 + 1 = 5 мс после старта. Выполнение процесса 4 может начаться только после завершения процесса 3, то есть, через 5 мс. Он длится 7 мс, так что минимальное время завершения всех процессов равно 5 + 7 = 12 мс.

2. 
   (В. Шубинкин) В файле 22-2.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно… (Условие совпадает с условием задачи из демо-варианта 2023 года).
   
3. 
   (В. Шубинкин) В файле 22-3.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно… (Условие совпадает с условием задачи из демо-варианта 2023 года).
   
4. 
   (В. Шубинкин) В файле 22-4.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно… (Условие совпадает с условием задачи из демо-варианта 2023 года).
   
5. 
   (А. Кожевникова) В файле 22-5.xls содержится информация о процессах внутри проектов P1 и P2. Каждый проект состоит из совокупности вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс В зависит от процесса А, если для выполнения процесса В необходимы результаты процесса А. В этом случае процессы могут выполняться только последовательно. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.
   

---

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

6. 
   (А. Кожевникова) В файле 22-5.xls содержится информация о процессах внутри проектов P1 и P2. Каждый проект состоит из совокупности вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс В зависит от процесса А, если для выполнения процесса В необходимы результаты процесса А. В этом случае процессы могут выполняться только последовательно. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.
   

Найдите минимальное время завершения процесса 12 из проекта P1.

7. 
   (А. Кожевникова) В файле 22-5.xls содержится информация о процессах внутри проектов P1 и P2. Каждый проект состоит из совокупности вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс В зависит от процесса А, если для выполнения процесса В необходимы результаты процесса А. В этом случае процессы могут выполняться только последовательно. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.
   

Найдите минимальное время завершения процесса 4 из проекта P2.

8. 
   (Л. Шастин) В файле 22-6.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно… (Условие совпадает с условием задачи из демо-варианта 2023 года).
   

Среди всех независимых процессов найдите самый длительный и самый быстрый (заканчивающийся за минимальное время). В качестве ответа укажите разницу между временами выполнения этих процессов.

9. 
   (Л. Шастин) В файле 22-6.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно… (Условие совпадает с условием задачи из демо-варианта 2023 года).
   

Эта группа процессов выполняется дважды при различных условиях:

---

Смотрите также файлы

• Физическое самовоспитание и самосовершенствование как необходимое условие здорового образа жизни.docx

• Тест для сдачи задолженности по дисциплине Управление затратами.docx

• Программа по математике составлена на основе Федерального государственного образовательного стандарта начального общего.docx

• Правила сумо Площадка для сумо Экипировка Судейство в сумо Сумо.docx

• Закон букв. правила ведения домашнего хозяйства.docx