Задача 22 ЕГЭ по информатике - многопроцессорные системы

Хотите готовиться со мной к ЕГЭ?
Пишите: ydkras@mail.ru
Немного обо мне.

В прошлом году в ЕГЭ по информатике появился новый тип задач - многопроцессорные системы (задача 22).

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

Простое решение

Для примера возьмем задачу из демонстрационного варианта ЕГЭ на 2023 г. К задаче прилагается файл Excel со следующей таблицей:

	A	B	C
1	ID процесса B	Время выполнения процесса B (мс)	ID процесса(ов) A
2	1	4	0
3	2	3	0
4	3	1	1; 2
5	4	7	3
6	5	6	3
7	6	3	5
8	7	1	4; 6
9	8	2	7
10	9	7	0
11	10	8	0
12	11	6	9
13	12	6	10

Если в столбце C стоит 0, то этот процесс не зависит от других процессов и может быть запущен в самом начале выполнения совокупности процессов. В противном случае в столбце C через точку с запятой перечисляются номера процессов, от которых зависит данный процесс.

В данном случае процессы 1, 2, 9 и 10 - независимые. Процесс 3 зависит от процессов 1 и 2 (т.е. может быть запущен не ранее, чем завершатся процессы 1 и 2), процесс 4 зависит от процесса 3 и т.д.

Данная задача легко решается вручную.

В столбце D будем записывать время начала каждого процесса, а в столбце E - время его завершения.

Для процессов 1, 2, 9 и 10 сразу же записываем, что их время начала - 0. Время завершения - очевидно, время начала плюс время выполнения процесса. Записываем в ячейку E2 формулу =D2+B2 и копируем эту формулу в ячейки E3, E10 и E11.

Теперь наша таблица выглядит так:

	A	B	C	D	E
1	ID процесса B	Время выполнения процесса B (мс)	ID процесса(ов) A	Начало	Конец
2	1	4	0	0	4
3	2	3	0	0	3
4	3	1	1; 2
5	4	7	3
6	5	6	3
7	6	3	5
8	7	1	4; 6
9	8	2	7
10	9	7	0	0	7
11	10	8	0	0	8
12	11	6	9
13	12	6	10

Теперь можно заполнять времена начала зависимых процессов.

Процесс 3 зависит от процессов 1 и 2. Мы видим, что процесс 1 завершается в момент времени 4, а процесс 2 - в момент 3. Значит, самое раннее время, когда можно запустить процесс 3 - это момент 4 (максимум из 4 и 3). Вписываем в ячейку D4 число 4, а в ячейку E4 - нашу формулу для вычисления времени окончания процесса. (Можно скопировать эту формулу нажатием клавиш Ctrl-C, а потом вставлять её в нужные ячейки, нажимая Ctrl-V.)

Процесс 3 завершается в момент времени 5.

От процесса 3 зависят процессы 5 и 6, ставим момент завершения процесса 3 (т.е. 5) как время начала процессов 4 и 5. Копируем формулу для времени завершения процесса в столбец D для процессов 4 и 5.

Теперь наша таблица вынлядит так:

	A	B	C	D	E
1	ID процесса B	Время выполнения процесса B (мс)	ID процесса(ов) A	Начало	Конец
2	1	4	0	0	4
3	2	3	0	0	3
4	3	1	1; 2	4	5
5	4	7	3	5	12
6	5	6	3	5	11
7	6	3	5
8	7	1	4; 6
9	8	2	7
10	9	7	0	0	7
11	10	8	0	0	8
12	11	6	9
13	12	6	10

Продолжаем заполнять столбец с временами начала процессов и вставляем формулу для времени окончания в ячейки столбца E.

В итоге наша таблица приобратвет следующий вид:

	A	B	C	D	E
1	ID процесса B	Время выполнения процесса B (мс)	ID процесса(ов) A	Начало	Конец
2	1	4	0	0	4
3	2	3	0	0	3
4	3	1	1; 2	4	5
5	4	7	3	5	12
6	5	6	3	5	11
7	6	3	5	11	14
8	7	1	4; 6	14	15
9	8	2	7	15	17
10	9	7	0	0	7
11	10	8	0	0	8
12	11	6	9	7	13
13	12	6	10	8	14

Наша таблица заполнена целиком. Из неё видно, что самое позднее время завершения - у процесса 8, это время равно 17 миллисекундам. В задаче спрашивалось, какое минимальное время завершения у данной совокупности процессов. Теперь мы вилим, что ответ на задачу - 17.

Очевидно, что можно не искать максимальное число в столбце E глазами, а вписать в какую-нибудь свободную ячейку простую формулу =МАКС(E2:E13)

Просто? Да, пока просто. Но...

Сложности и как их побороть

Разобранная выше задача - очень простая. Но в задачах этого типа возможны многочисленные усложнения. Вот некоторые из тех, которые встречались мне в таких задачах.

Номера процессов могут быть, скажем, пятизначными числами, и вам придется искать в таблице процесс номер 10688, да ещё при этом не перепутать его с процессом номер 10668.

Число процессов может быть достаточно большим (скажем, 100), и тогда ручное заполнение таблицы потребует значительного времени.

В вышеприведенной задаче таблицу можно было заполнять сверху вниз. Но в других задачах вполне может оказаться, что процесс 3 зависит от процесса 12, который находится ниже в таблице, и тогда вам придется потратить немало времени на то, чтобы искать, какой процесс мы можем обработать на очередном шаге.

Каждый процесс в разобранной выше задаче зависит максимум от двух процессов. Но, вообще говоря, нет ограничений на количество процессов, от которых зависит данный процесс.

Выход из положения очевиден: надо заполнять нашу таблицу полностью автоматически. Давайте научимся это делать.

Будем решать одну из задач, предлагавшихся на ЕГЭ по информатике в 2023 г.:

	A	B	C
1	ID процесса B	Время выполнения процесса B (мс)	ID процессов A
2	1	20	0
3	2	26	0
4	3	41	12
5	4	28	0
6	5	29	2
7	6	25	5;7;8;15
8	7	31	4
9	8	32	1
10	9	28	12;20
11	10	34	7
12	11	30	18
13	12	29	0
14	13	32	11;12
15	14	33	11;16
16	15	39	9
17	16	33	7;15
18	17	36	13
19	18	37	0
20	19	24	12;17
21	20	33	1;3;4;13

Как видим, количество процессов тут больше, чем в первой задаче, некоторые процессы зависят от четырех других процессов, и заполнять таблицу по порялку сверху вниз не получится: процесс 3, например, зависит от процесса 12, поэтому строку процесса 3 мы не сможем заполнить до того, как будет заполнена строка процесса 12.

Шаг 1. Разбиваем столбец зависимости процессов.

В столбце C номера всех процессов, от которых зависит данный процесс, перечислены через точку с запятой. Разнесем каждый номер в отдельный столбец.

Выделим ячейки C2:C21 и вызовем мастер разбиения текста по столбцам (в LibreOffice Calc он находится в меню "Данные"). Обязательно проверяем, что выбран разделитель "точка с запятой". После выполнения данного мастера наша таблица выглядит так:

	A	B	C	D	E	F
1	ID процесса B	Время выполнения процесса B (мс)	ID процессов A
2	1	20	0
3	2	26	0
4	3	41	12
5	4	28	0
6	5	29	2
7	6	25	5	7	8	15
8	7	31	4
9	8	32	1
10	9	28	12	20
11	10	34	7
12	11	30	18
13	12	29	0
14	13	32	11	12
15	14	33	11	16
16	15	39	9
17	16	33	7	15
18	17	36	13
19	18	37	0
20	19	24	12	17
21	20	33	1	3	4	13

Шаг 2. Предварительная подготовка.

Итак, теперь у нас в столбцах C, D, E и F - номера процессов, от которых зависит данный процесс (или пустые ячейки, или число 0 в столбце C, если процесс независимый).

Отведем столбцы G и H для времени начала и конца каждого процесса, точно так же, как мы делали это ранее.

Со временем конца всё очень просто: надо в соответствующую ячейку вписать формулу для суммирования времени начала данного процесса и его продолжительности. Давайте не будем тянуть и сделаем это. В ячейку H2 впишем формулу =G2+B2, скопируем её и вставим в ячейки H3:H21.

Наша таблица приобретает такой вид:

	A	B	C	D	E	F	G	H
1	ID процесса B	Время выполнения процесса B (мс)	ID процессов A				Начало	Конец
2	1	20	0					20
3	2	26	0					26
4	3	41	12					41
5	4	28	0					28
6	5	29	2					29
7	6	25	5	7	8	15		25
8	7	31	4					31
9	8	32	1					32
10	9	28	12	20				28
11	10	34	7					34
12	11	30	18					30
13	12	29	0					29
14	13	32	11	12				32
15	14	33	11	16				33
16	15	39	9					39
17	16	33	7	15				33
18	17	36	13					36
19	18	37	0					37
20	19	24	12	17				24
21	20	33	1	3	4	13		33

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

Возьмем для примера строку 21 (процесс 20) и предположим, что в ячейке I21 находится время завершения процесса 1, в ячейке J21 - время завершения процесса 3, в ячейке K21 - время завершения процесса 4 и в ячейке L21 - время завершения процесса 13. (Номера процессов 1, 3, 4 и 13 перечислены в ячейках C21:F21.) Тогда время начала процесса 21 можно определить с помощью простой формулы =МАКС(I21:L21)

Впишем в ячейку G2 формулу =МАКС(I2:L2) и размножим её по ячейкам G3:G21. Получим таблицу:

	A	B	C	D	E	F	G	H
1	ID процесса B	Время выполнения процесса B (мс)	ID процессов A				Начало	Конец
2	1	20	0				0	20
3	2	26	0				0	26
4	3	41	12				0	41
5	4	28	0				0	28
6	5	29	2				0	29
7	6	25	5	7	8	15	0	25
8	7	31	4				0	31
9	8	32	1				0	32
10	9	28	12	20			0	28
11	10	34	7				0	34
12	11	30	18				0	30
13	12	29	0				0	29
14	13	32	11	12			0	32
15	14	33	11	16			0	33
16	15	39	9				0	39
17	16	33	7	15			0	33
18	17	36	13				0	36
19	18	37	0				0	37
20	19	24	12	17			0	24
21	20	33	1	3	4	13	0	33

Как видно, применение функции МАКС к группе пустых клеток дает в результате ноль. Это очень удобно для наших целей.

Пора сделать решающий шаг.

Шаг 3. Заполнение времен окончаний процессов с помощью функции ВПР.

Чтобы вычислить время окончание какого либо процесса, зная его номер, надо найти в таблице строку, где этот номер находится в столбце А, и взять из этой строки ячейку в столбце H. Именно такие операции и делает функция ВПР (Вертикальный ПРосмотр).

Функция ВПР имеет четыре параметра. Первый из них - "что ищем", второй - "где ищем", третий - "что выдаём как результат". Четвертый параметр в нашем случае должен быть равен нулю.

Запишем в ячейку I2 следующую формулу:

=ЕСЛИ(C2>0;ВПР(C2;$A$2:$H$21;8;0);"")

и размножим её во все ячейки диапазона I2:L21 - и решение готово (почти).

Небольшие пояснения. Если в ячейке C2 находится положительное число, то для заполнения ячейки I2 мы используем функцию ВПР, иначе ячейка будет пустой. Функция ВПР ищет в самом левом столбце области $A$2:$H$21 (т.е. в столбце A) содержимое ячейки, указанной первым её параметром. Если такая строка будет найдена, то функция возвращает результат из 8-го столбца области $A$2:$H$21 - т.е. из столбца H. (Если строка найдена не будет, то возникнет ошибка: именно поэтому мы вызываем ВПР только в том случае, если ячейка поиска >0, тем самым исключая пустые ячейки и ячейки с нулевыми значениями.)

Чтобы получить ответ, впишем в ячейку A23 (или любую другую свободную) формулу =МАКС(H2:H21) и увидим в этой ячейке число 265.

	A	B	C	D	E	F	G	H	I	J	K	L
1	ID процесса B	Время выполнения процесса B (мс)	ID процессов A				Начало	Конец	Тк1	Тк2	Тк3	Тк4
2	1	20	0				0	20
3	2	26	0				0	26
4	3	41	12				29	70	29
5	4	28	0				0	28
6	5	29	2				26	55	26
7	6	25	5	7	8	15	199	224	55	59	52	199
8	7	31	4				28	59	28
9	8	32	1				20	52	20
10	9	28	12	20			132	160	29	132
11	10	34	7				59	93	59
12	11	30	18				37	67	37
13	12	29	0				0	29
14	13	32	11	12			67	99	67	29
15	14	33	11	16			232	265	67	232
16	15	39	9				160	199	160
17	16	33	7	15			199	232	59	199
18	17	36	13				99	135	99
19	18	37	0				0	37
20	19	24	12	17			135	159	29	135
21	20	33	1	3	4	13	99	132	20	70	28	99
22
23	265

265 - это и есть правильный ответ для данной задачи.

Более сложные вопросы

В разобранных задачах вопрос формулировался примерно так: каково минимальное время завершения совокупности всех процессов? Мы видели, что ответ на этот вопрос - максимальное из времен завершения процессов.

Однако вопросы, как известно, бывают разные. Так, в одной из задач спрашивалось, сколько процессов начнутся не ранее чем через 100 миллисекунд с момента начала выполнения. Ответить на этот вопрос также несложно. Сначала найдем для каждого из процессов время его начала и время завершения, как было описано выше. А затем найдем, сколько раз в столбце "Начало выполнения" встречаются числа, большие либо равные 100. Это можно сделать с помощью функции СЧЕТЕСЛИ.

А вот пример более сложного вопроса: какова суммарная длительность всех промежутков времени, в течение которых выполнялось ровно 3 процесса?

Попробуем решить эту задачу. Исходные данные для неё следующие:

	A	B	C
1	ID процесса B	Время выполнения процесса B (мс)	ID процессов A
2	1	4	0
3	2	2	0
4	3	5	1; 2
5	4	7	3
6	5	6	3
7	6	2	5
8	7	5	4; 6
9	8	2	6
10	9	7	0
11	10	9	0
12	11	6	9
13	12	6	10

Начнем с того, что найдем для каждого процесса время его начала и время завершения (см. предыдущий раздел). В результате получается такая таблица:

	A	B	C	D	E	F	G	H
1	ID процесса B	Время выполнения процесса B (мс)	ID процессов A		Начало	Конец	Тк1	Тк2
2	1	4	0		0	4
3	2	2	0		0	2
4	3	5	1	2	4	9	4	2
5	4	7	3		9	16	9
6	5	6	3		9	15	9
7	6	2	5		15	17	15
8	7	5	4	6	17	22	16	17
9	8	2	6		17	19	17
10	9	7	0		0	7
11	10	9	0		0	9
12	11	6	9		7	13	7
13	12	6	10		9	15	9

Теперь для каждого момента времени найдем, сколько процессов выполняются в данный момент. Это можно сделать с помощью функции СЧЁТЕСЛИМН.

В столбце A, начиная с ячейки А16, запишем моменты времени: 0, 1, 2 и т.д. до 25 (из таблицы видно, что максимальный нужный нам момент времени - 22, но я люблю делать всё с небольшим запасом). Для ускорения процесса можно в ячейку A16 занести число 0, в ячейку A17 - формулу =A16+1 и размножить эте формулу в нижерасположенные ячейки в столбце A.

В ячейку B16 запишем формулу

=СЧЁТЕСЛИМН($E$2:$E$13;"<="&A16;$F$2:$F$13;">"&A16)

и размножим её ниже по столбцу B. (Важно: для нижней границы мы используем нестрогое неравенство "<=", а для верхней - строгое ">".) Знак амперсанда "&" используется для того, чтобы осуществлять сравнение не с конкретно заданным числом, а со значением из указанной ячейки.

Получаем следующее:

	A	B	C	D	E	F	G	H
1	ID процесса B	Время выполнения процесса B (мс)	ID процессов A		Начало	Конец	Тк1	Тк2
2	1	4	0		0	4
3	2	2	0		0	2
4	3	5	1	2	4	9	4	2
5	4	7	3		9	16	9
6	5	6	3		9	15	9
7	6	2	5		15	17	15
8	7	5	4	6	17	22	16	17
9	8	2	6		17	19	17
10	9	7	0		0	7
11	10	9	0		0	9
12	11	6	9		7	13	7
13	12	6	10		9	15	9
14
15	t	Кол-во
16	0	4
17	1	4
18	2	3
19	3	3
20	4	3
21	5	3
22	6	3
23	7	3
24	8	3
25	9	4
26	10	4
27	11	4
28	12	4
29	13	3
30	14	3
31	15	2
32	16	1
33	17	2
34	18	2
35	19	1
36	20	1
37	21	1
38	22	0
39	23	0
40	24	0
41	25	0

Мы видим, что в моменты 0 и 1 выполняются четыре процесса, в моменты с 2 по 8 - три и т.д.

Вписываем в любую свободную ячейку формулу =СЧЁТЕСЛИ(B16:B41;3) и видим ответ: число 9.

А как же Питон?

В задаче 9 ЕГЭ по информатике вполне работающий способ решения - сохранить данные из электронной таблицы в текстовом файле (формат csv) и обработать этот файл с помощью совсем небольшой и несложной программы на питоне.

А можно ли решить и данную задачу с помощью программы? Разумеется, можно. Рассмотрим возможный способ её рашения.

Исходные данные.

Обрабатывать файл xls/xlsx программой на питоне, разумеется, мы не будем. Сохраним информацию из него в текстовом формате. Сперва удалим из таблицы первую строку с заголовками стоьбцов - она нам совершенно не нужна.

Теперь скажем "Сохранить как...", выберем формат сохранения "Текст CSV" и запишем файл на диск под каким-нибудь именем. При сохранении в качестве разделителя полей выберем точку с запятой или пробел.

На диск запишется файл со строками вида

19;24;"12;17"
20;33;"1;3;4;13"

Можно предварительно применить к третьему столбцу со списками процессов, от которых зависит данный процесс, операцию "Текст по столбцам" (см.выше), тогда файл после сохранения будет выгляденть несколько иначе:

19;24;12;17;;;
20;33;1;3;4;13

Программа.

Чтобы правильно обработать и тот, и другой формат, поступим следующим образом: заменим в прочитанной строке точки с запятой и двойные кавычки на пробелы, а потом применим операцию split().

Вот фрагмент программы, которая превратит наш текстовый файл в список lines, каждый элемент которого - это список целых чисел из одной строки нашего текстового файла:

f=open('22.csv')

lines=[list(map(int,s.replace('"',' ').replace(';',' ').split())) for s in f]

Так, две приведенные выше строки превратятся в следующие списки:

[19,24,12,17]
[20,33,1,3,4,13]

Первый элемент (т.е. с индексом "0") этих списков - это номер процесса, второй - его продолжительность, а далее перечисляются процессы, от которых этот процесс зависит (либо ноль, если процесс не зависит от других).

На основе этих списков создадим словарь w. Ключом в элементе словаря будет номер процесса, а значением - список из остальных чисел (т.е. длительность процесса и номера процессов, от которых зависит данный процесс).

w={line[0]:line[1:] for line in lines}

Приведенные выше две строки превратятся в следующие элементы нашего словаря:

19:[24,12,17]

20:[33,1,3,4,13]

Напишем функцию tstart(p), определяющую время начала процесса с номером p. Если процесс независимый, т.е. элемент w[p][1] нашего словаря равен нулю, то время начала процесса - 0. В противном случае нам нужен максимум из времен завершения всех процессов, от которых зависит данный. Время завершения - это время начала процесса плюс его продолжительность.

Вот наша функция:

def tstart(p): return 0 if w[p][1] == 0 else max(tstart(i) + w[i][0] for i in w[p][1:])

Нам осталось написать лишь одну строчку - определение времени завершения последнего процесса в нашей совокупности и его печать. Вот эта строчка:

print(max(tstart(p)+w[p][0] for p in w))

Приведем программу целиком:

def tstart(p): return 0 if w[p][1] == 0 else max(tstart(i) + w[i][0] for i in w[p][1:])
f=open('22.csv')
lines=[list(map(int,s.replace('"',' ').replace(';',' ').split())) for s in f]
w={line[0]:line[1:] for line in lines}
print(max(tstart(p)+w[p][0] for p in w))

Эти пять строчек - вот, собственно, и всё.

Более сложная задача.

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

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

Приведем код программы:

def tstart(p): return 0 if w[p][1] == 0 else max(tstart(i) + w[i][0] for i in w[p][1:])

f=open('22.csv')

lines=[list(map(int,s.replace('"',' ').replace(';',' ').split())) for s in f]

w={line[0]:line[1:] for line in lines}

final=max(tstart(p)+w[p][0] for p in w)

kolp=[sum(1 if tstart(p) <= time < (tstart(p)+w[p][0]) else 0 for p in w) for time in range(final+1)]

print(kolp.count(3))

Нам пришлось построить список kolp, в котором элемент kolp[0] - это количество процессов, выполняемых в момент времени 0, kolp[1] - их количество в момент 1 и т.д. Перед этим мы определяем общее время выполнения всех процессов и запоминаем его в переменной final. Значение range(final+1) гарантирует, что мы проведем расчет для всех моментов времени, пока идет выполнение процессов. Затем мы печатаем количество миллисекундных интервалов, когда количество процессов равно трем.

Поиск по этому блогу

Информатика, ЕГЭ, Питон и т.п.