Задание 22 · ЕГЭ, информатика 2027
Матмодели и архитектура
Критический путь: сколько времени работает система на многих процессорах.
Пять вариантов задания
Данные в вариантах разные, приём решения один. Отмеченные галочкой уже решены — отметка хранится в этом браузере.
В файле приведена таблица процессов. Первый столбец — идентификатор процесса, второй — время его выполнения в миллисекундах, третий — идентификаторы процессов, от которых зависит данный (через точку с запятой; «-1» означает, что зависимостей нет). Процесс может начаться только после завершения всех процессов, от которых он зависит. Считая, что параллельно может выполняться любое количество процессов, определите минимальное время в миллисекундах, через которое завершатся все процессы.
Скачать таблицу (.ods)Лист «Процессы»: 40 строк с заголовком. Файл открывается в LibreOffice Calc, Excel или «Р7-Офис». Если офисного пакета нет — та же таблица в .csv (разделитель — точка с запятой).
Понять, что именно ограничивает время
Процессоров сколько угодно, значит ждать приходится только зависимостей. Минимальное время всей системы — это самая длинная цепочка зависимых процессов (её называют критическим путём).Посчитать время завершения каждого процесса
Добавляем столбец D. Для процесса без зависимостей время завершения равно его собственной длительности. Для остальных:T(i) = B(i) + МАКС(T(зависимости))
Процессы в файле пронумерованы так, что зависимости всегда имеют меньший номер, поэтому таблица заполняется сверху вниз за один проход.Найти максимум
=МАКС(D:D)по всему столбцу времён завершения.Ответ
Критический путь: 5 → 9 → 14 → 17 → 20 → 25 → 32 → 35. Суммарно 91 мс.
Где обычно теряют балл
- Сложить длительности всех процессов — это ответ для ОДНОГО процессора, а их здесь сколько угодно.
- Взять максимум из длительностей вместо максимума из времён завершения.
- Не заметить, что у процесса несколько зависимостей, и учесть только первую.
В файле приведена таблица процессов. Первый столбец — идентификатор процесса, второй — время его выполнения в миллисекундах, третий — идентификаторы процессов, от которых зависит данный (через точку с запятой; «-1» означает, что зависимостей нет). Процесс может начаться только после завершения всех процессов, от которых он зависит. Считая, что параллельно может выполняться любое количество процессов, определите минимальное время в миллисекундах, через которое завершатся все процессы.
Скачать таблицу (.ods)Лист «Процессы»: 40 строк с заголовком. Файл открывается в LibreOffice Calc, Excel или «Р7-Офис». Если офисного пакета нет — та же таблица в .csv (разделитель — точка с запятой).
Понять, что именно ограничивает время
Процессоров сколько угодно, значит ждать приходится только зависимостей. Минимальное время всей системы — это самая длинная цепочка зависимых процессов (её называют критическим путём).Посчитать время завершения каждого процесса
Добавляем столбец D. Для процесса без зависимостей время завершения равно его собственной длительности. Для остальных:T(i) = B(i) + МАКС(T(зависимости))
Процессы в файле пронумерованы так, что зависимости всегда имеют меньший номер, поэтому таблица заполняется сверху вниз за один проход.Найти максимум
=МАКС(D:D)по всему столбцу времён завершения.Ответ
Критический путь: 28 → 30 → 33 → 34 → 38. Суммарно 60 мс.
Где обычно теряют балл
- Сложить длительности всех процессов — это ответ для ОДНОГО процессора, а их здесь сколько угодно.
- Взять максимум из длительностей вместо максимума из времён завершения.
- Не заметить, что у процесса несколько зависимостей, и учесть только первую.
В файле приведена таблица процессов. Первый столбец — идентификатор процесса, второй — время его выполнения в миллисекундах, третий — идентификаторы процессов, от которых зависит данный (через точку с запятой; «-1» означает, что зависимостей нет). Процесс может начаться только после завершения всех процессов, от которых он зависит. Считая, что параллельно может выполняться любое количество процессов, определите минимальное время в миллисекундах, через которое завершатся все процессы.
Скачать таблицу (.ods)Лист «Процессы»: 40 строк с заголовком. Файл открывается в LibreOffice Calc, Excel или «Р7-Офис». Если офисного пакета нет — та же таблица в .csv (разделитель — точка с запятой).
Понять, что именно ограничивает время
Процессоров сколько угодно, значит ждать приходится только зависимостей. Минимальное время всей системы — это самая длинная цепочка зависимых процессов (её называют критическим путём).Посчитать время завершения каждого процесса
Добавляем столбец D. Для процесса без зависимостей время завершения равно его собственной длительности. Для остальных:T(i) = B(i) + МАКС(T(зависимости))
Процессы в файле пронумерованы так, что зависимости всегда имеют меньший номер, поэтому таблица заполняется сверху вниз за один проход.Найти максимум
=МАКС(D:D)по всему столбцу времён завершения.Ответ
Критический путь: 0 → 1 → 4 → 8 → 15. Суммарно 49 мс.
Где обычно теряют балл
- Сложить длительности всех процессов — это ответ для ОДНОГО процессора, а их здесь сколько угодно.
- Взять максимум из длительностей вместо максимума из времён завершения.
- Не заметить, что у процесса несколько зависимостей, и учесть только первую.
В файле приведена таблица процессов. Первый столбец — идентификатор процесса, второй — время его выполнения в миллисекундах, третий — идентификаторы процессов, от которых зависит данный (через точку с запятой; «-1» означает, что зависимостей нет). Процесс может начаться только после завершения всех процессов, от которых он зависит. Считая, что параллельно может выполняться любое количество процессов, определите минимальное время в миллисекундах, через которое завершатся все процессы.
Скачать таблицу (.ods)Лист «Процессы»: 40 строк с заголовком. Файл открывается в LibreOffice Calc, Excel или «Р7-Офис». Если офисного пакета нет — та же таблица в .csv (разделитель — точка с запятой).
Понять, что именно ограничивает время
Процессоров сколько угодно, значит ждать приходится только зависимостей. Минимальное время всей системы — это самая длинная цепочка зависимых процессов (её называют критическим путём).Посчитать время завершения каждого процесса
Добавляем столбец D. Для процесса без зависимостей время завершения равно его собственной длительности. Для остальных:T(i) = B(i) + МАКС(T(зависимости))
Процессы в файле пронумерованы так, что зависимости всегда имеют меньший номер, поэтому таблица заполняется сверху вниз за один проход.Найти максимум
=МАКС(D:D)по всему столбцу времён завершения.Ответ
Критический путь: 0 → 1 → 2 → 4 → 7 → 13 → 18 → 20 → 27 → 28 → 33 → 35. Суммарно 106 мс.
Где обычно теряют балл
- Сложить длительности всех процессов — это ответ для ОДНОГО процессора, а их здесь сколько угодно.
- Взять максимум из длительностей вместо максимума из времён завершения.
- Не заметить, что у процесса несколько зависимостей, и учесть только первую.
В файле приведена таблица процессов. Первый столбец — идентификатор процесса, второй — время его выполнения в миллисекундах, третий — идентификаторы процессов, от которых зависит данный (через точку с запятой; «-1» означает, что зависимостей нет). Процесс может начаться только после завершения всех процессов, от которых он зависит. Считая, что параллельно может выполняться любое количество процессов, определите минимальное время в миллисекундах, через которое завершатся все процессы.
Скачать таблицу (.ods)Лист «Процессы»: 40 строк с заголовком. Файл открывается в LibreOffice Calc, Excel или «Р7-Офис». Если офисного пакета нет — та же таблица в .csv (разделитель — точка с запятой).
Понять, что именно ограничивает время
Процессоров сколько угодно, значит ждать приходится только зависимостей. Минимальное время всей системы — это самая длинная цепочка зависимых процессов (её называют критическим путём).Посчитать время завершения каждого процесса
Добавляем столбец D. Для процесса без зависимостей время завершения равно его собственной длительности. Для остальных:T(i) = B(i) + МАКС(T(зависимости))
Процессы в файле пронумерованы так, что зависимости всегда имеют меньший номер, поэтому таблица заполняется сверху вниз за один проход.Найти максимум
=МАКС(D:D)по всему столбцу времён завершения.Ответ
Критический путь: 0 → 1 → 2 → 9 → 15 → 16 → 18 → 20 → 23 → 28 → 29 → 30 → 34. Суммарно 138 мс.
Где обычно теряют балл
- Сложить длительности всех процессов — это ответ для ОДНОГО процессора, а их здесь сколько угодно.
- Взять максимум из длительностей вместо максимума из времён завершения.
- Не заметить, что у процесса несколько зависимостей, и учесть только первую.
Многопроцессорная система и критический путь
Процессов много, процессоров сколько угодно. Значит ждать приходится только зависимостей, а не очереди. Минимальное время выполнения всей системы — длина самой длинной цепочки зависимых процессов, её называют критическим путём.
Считается одним проходом сверху вниз: время завершения процесса равно его собственной длительности плюс наибольшее из времён завершения тех процессов, от которых он зависит. Ответ — максимум по столбцу времён завершения.
Где теряют балл. Складывают длительности всех процессов (это ответ для одного процессора); берут максимум из длительностей вместо максимума из времён завершения; учитывают только первую зависимость из списка.
Функции редактора таблиц, которые нужны на экзамене
Названия даны по-русски (LibreOffice Calc, «Р7-Офис», русский Excel). В английской версии они пишутся иначе, но работают так же.
| Функция | Что делает |
|---|---|
| СУММ(диапазон) | сумма чисел |
| СЧЁТ(диапазон) | сколько ячеек содержат числа |
| СЧЁТЕСЛИ(диапазон; условие) | сколько ячеек удовлетворяет условию |
| СЧЁТЕСЛИМН(д1; у1; д2; у2; …) | то же по нескольким условиям сразу |
| СУММЕСЛИ(диапазон; условие; суммируемый) | сумма по условию |
| СУММЕСЛИМН(суммируемый; д1; у1; …) | сумма по нескольким условиям |
| МАКС / МИН(диапазон) | наибольшее и наименьшее значение |
| НАИБОЛЬШИЙ(диапазон; k) | k-е по величине значение |
| НАИМЕНЬШИЙ(диапазон; k) | k-е с конца |
| СРЗНАЧ(диапазон) | среднее арифметическое |
| ЕСЛИ(условие; тогда; иначе) | выбор одного из двух значений |
| И(…) / ИЛИ(…) | объединение условий |
| ВПР(что; где; номер_столбца; 0) | подтянуть значение из другой таблицы |
| ОСТАТ(число; делитель) | остаток от деления |
| ЦЕЛОЕ(число) | целая часть |
Три правила, без которых формула не работает.
- Точное совпадение у ВПР задаётся последним аргументом
0. Без него функция ищет приблизительное значение и на неотсортированных данных выдаёт чужую строку. - Знак
$закрепляет ссылку при протягивании:A$1— строку,$A1— столбец,$A$1— обе. - Разделитель аргументов в русской локали — точка с запятой, а не запятая.
Где эта тема разобрана подробно
Структура раздела и темы заданий соответствуют кодификатору и спецификации ФИПИ. Задания и файлы данных составлены редакцией reknow.ru. План варианта приведён по проекту спецификации и демоверсии ФИПИ 2027 года. После публикации утверждённой версии информация будет обновлена.