ЕГЭ · задание с файлом

Задание 22 ЕГЭ по информатике — многопроцессорные системы (параллельные процессы)

Что проверяет номер, типичные ошибки, пример с решением на Python и 10 заданий с ответами под спойлером.

27заданий в банке
с ответамикак в КИМ
1 кликзадание на доске

Что проверяет задание 22 ЕГЭ

В файле — таблица процессов: номер, время выполнения и список процессов, после завершения которых он может начаться. Процессы выполняются параллельно, нужно найти минимальное время завершения всех процессов (длину критического пути) или максимальное число одновременно идущих процессов. Решается в Excel формулой «время = длительность + максимум времени предшественников» или на Python.

КЕГЭ, задание 22к заданию прилагается файл27 заданий в банке ИнфДоски

Типичные ошибки

  • Складывают длительности всех процессов, как будто они идут последовательно.
  • Берут сумму времени предшественников вместо максимума.
  • Неверно разбирают список зависимостей «1;3;4» в ячейке.
  • Забывают процессы без зависимостей — они начинаются в момент 0.

Пример с решением

Условие

Процессы и их зависимости (процесс начинается, когда завершились все указанные):

IDВремя, мсЗависит от
140
230
351
421; 2
563; 4
612

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

Решение

Время окончания: П1 — 4, П2 — 3, П3 — 4 + 5 = 9, П4 — max(4, 3) + 2 = 6, П5 — max(9, 6) + 6 = 15, П6 — 3 + 1 = 4. Все процессы завершатся через 15 мс.

procs = {1: (4, []), 2: (3, []), 3: (5, [1]), 4: (2, [1, 2]),
         5: (6, [3, 4]), 6: (1, [2])}
end = {}

def finish(p):
    if p not in end:
        t, deps = procs[p]
        end[p] = t + max((finish(d) for d in deps), default=0)
    return end[p]

print(max(finish(p) for p in procs))
Код на Python 3 — его можно запустить прямо на ИнфДоске.
Ответ: 15

Задания из банка

В банке ИнфДоски 27 заданий этого номера с файлами. Ниже — 10 из них, ответ спрятан под спойлером. Кнопка «Открыть на доске» ставит задание на вашу ИнфДоску.

Задание 1 Параллельные процессы Открыть на доске →

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

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

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

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

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

Например, для приведённой таблицы это 13 мс (процесс 5 может выполниться только после окончания процесса 4, их общая продолжительность мс).

Ответ
29
Задание 2 Параллельные процессы Открыть на доске →

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

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

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

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

Определите максимальное количество процессов, которые параллельно выполняются на 23-й мс. Считать, что каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с 1.

Например, для приведённой таблицы на 6-й мс параллельно выполняются три процесса. Это процессы 2, 5 и 6.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Ответ
1
Задание 3 Параллельные процессы Открыть на доске →

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

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

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

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

Определите минимальное время (в мс), за которое завершатся 17 процессов. Считать, что каждый процесс начинается в самое раннее допустимое время. Минимальное время отсчитывается непрерывно с первой миллисекунды. В ответе укажите только число — количество мс.

Например, для приведённой таблицы найдём время, за которое завершатся 3 процесса. Минимальное время, которое для этого требуется, — 7 мс. За это время завершатся процессы 1, 2 и 4.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Ответ
12
Задание 4 Параллельные процессы Открыть на доске →

В файле содержится информация о совокупности 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

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

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Ответ
148
Задание 5 Параллельные процессы Открыть на доске →

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

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

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

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

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

Для приведённой таблицы процесс 3 начинается на 8-й мс, заканчивается на 9-й мс.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Ответ
34
Задание 6 Параллельные процессы Открыть на доске →

В файле содержится информация о совокупности 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

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

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Ответ
218
Задание 7 Параллельные процессы Открыть на доске →

В файле содержится информация о совокупности 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

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

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Ответ
53
Задание 8 Параллельные процессы Открыть на доске →

В файле содержится информация о совокупности 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

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

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Ответ
165
Задание 9 Параллельные процессы Открыть на доске →

В файле содержится информация о совокупности 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

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

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Ответ
196
Задание 10 Параллельные процессы Открыть на доске →

В файле содержится информация о совокупности 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

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

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Ответ
229
ИнфДоска

Разбирайте задание 22 ЕГЭ на онлайн-доске

Задание из банка — на доску в один клик, ответ видите только вы. После урока доска сама составит отчёт маме или папе.

Другие задания ЕГЭ