Задание 22 ЕГЭ по информатике

1. 1. A и B независимы: стартуют на 1-м такте. Завершение A = 1 + 4 − 1 = 4, завершение B = 1 + 3 − 1 = 3.
2. 2. C зависит только от A: старт = 4 + 1 = 5, завершение = 5 + 5 − 1 = 9.
3. 3. D зависит только от B: старт = 3 + 1 = 4, завершение = 4 + 2 − 1 = 5.
4. 4. E ждёт обоих: старт = max(9, 5) + 1 = 10, завершение = 10 + 3 − 1 = 12.
5. 5. Максимум времён завершения — 12.

Ответ: 12

1. 1. Считать надо в порядке, в котором зависимости уже известны. Процессы 1 и 2 ни от кого не зависят — начнём с них.
2. 2. Процесс 1: зависимостей нет, значит старт на 1-й мс. Длительность 4, финиш = 1 + 4 − 1 = 4.
3. 3. Процесс 2: старт 1, длительность 3, финиш = 1 + 3 − 1 = 3.
4. 4. Процесс 3 зависит от 1. Тот финишировал на 4-й мс, значит старт = 4 + 1 = 5. Длительность 5, финиш = 5 + 5 − 1 = 9.
5. 5. Процесс 4 зависит от 2 (финиш 3): старт 4, длительность 2, финиш = 4 + 2 − 1 = 5.
6. 6. Процесс 6 тоже зависит от 1: старт 5, длительность 6, финиш = 5 + 6 − 1 = 10. Обратите внимание: процессы 3 и 6 стартуют одновременно на 5-й мс и идут параллельно — они друг от друга не зависят.
7. 7. Процесс 5 зависит от 3 и 4. Финиши 9 и 5, берём максимум — 9. Старт = 10, длительность 3, финиш = 10 + 3 − 1 = 12. Процесс 4 закончился ещё на 5-й мс и четыре миллисекунды просто ждал — это нормально и на ответ не влияет.
8. 8. Процесс 8 зависит от 6 (финиш 10): старт 11, длительность 4, финиш = 14.
9. 9. Процесс 7 зависит от 5 (финиш 12): старт 13, длительность 2, финиш = 14.
10. 10. Процесс 9 зависит от 7 и 8, оба финишировали на 14-й мс: старт 15, длительность 3, финиш = 15 + 3 − 1 = 17.
11. 11. Ответ: максимум всех финишей равен 17 мс. Сумма длительностей при этом 4 + 3 + 5 + 2 + 3 + 6 + 2 + 4 + 3 = 32 мс — почти вдвое больше, и это наглядно показывает, сколько даёт параллельность.
12. 12. Проверка через критический путь. Самая длинная цепочка: 1 → 3 → 5 → 7 → 9, её длительности 4 + 5 + 3 + 2 + 3 = 17. Есть и вторая цепочка той же длины: 1 → 6 → 8 → 9, это 4 + 6 + 4 + 3 = 17. Обе критические — задержка любого процесса в любой из них отодвинет общий финиш.

Ответ: 17 мс

1. 1.

   from functools import lru_cache

   processy = {}
   for line in open('22.txt'):
       chasti = line.split()
       nomer = int(chasti[0])
       dlitelnost = int(chasti[1])
       zavisimosti = [int(x) for x in chasti[2:] if int(x) != 0]
       processy[nomer] = (dlitelnost, zavisimosti)

   @lru_cache(None)
   def finish(p):

   dlitelnost, zavisimosti = processy[p]

       start = max((finish(z) for z in zavisimosti), default=0) + 1
       return start + dlitelnost - 1

   print(max(finish(p) for p in processy))

2. 2. Шаг 1. Чтение файла. Строка вида «5 3 3 4» означает: процесс 5, длительность 3, зависит от 3 и 4. Первые два числа фиксированы, всё остальное — список зависимостей. Ноль в столбце зависимостей означает «их нет», и он отфильтровывается.
3. 3. Шаг 2. Порядок обработки. Рекурсия решает эту проблему сама: чтобы посчитать финиш процесса, она сначала посчитает финиши всех его зависимостей. Никакой сортировки процессов заранее не нужно.
4. 4. Шаг 3. default=0 в max — это случай процесса без зависимостей: максимум по пустому списку не существует, а нам нужен ноль, чтобы старт получился первой миллисекундой.
5. 5. Шаг 4. Кэш обязателен. Без него процесс, от которого зависят пятеро, пересчитается пять раз, а каждый из них — ещё по нескольку. На 14 процессах это ещё терпимо, на сотне — нет.
6. 6. Шаг 5. Проверка на разобранном примере. Если положить в словарь девять наших процессов, программа напечатает 17 — то же, что и ручной расчёт.
7. 7. Шаг 6. Если в задании спрашивают не общую продолжительность, а что-то другое, меняется только последняя строка. «Сколько процессов завершится не позже 20-й мс» — это sum(1 for p in processy if finish(p) <= 20). «На какой миллисекунде стартует процесс 7» — печатаем старт вместо финиша. «Какой процесс завершится последним» — max(processy, key=finish).
8. 8. Шаг 7. Одно предостережение: программа предполагает, что в зависимостях нет циклов. В корректном задании их и не бывает — процесс не может зависеть сам от себя через цепочку, — но при опечатке в наборе данных рекурсия уйдёт в бесконечность и упадёт по переполнению стека. Если такое случилось, ищите ошибку в данных, а не в коде.

Ответ: 17 для разобранного примера; на боевом файле — число из печати

1. 1. Шаг 0. На все три вопроса отвечает одна и та же таблица финишей, которую мы уже построили: процесс 1 — 4, процесс 2 — 3, процесс 3 — 9, процесс 4 — 5, процесс 5 — 12, процесс 6 — 10, процесс 7 — 14, процесс 8 — 14, процесс 9 — 17.
2. 2. Шаг 1. Старт процесса 8. Он зависит только от процесса 6, а тот финиширует на 10-й миллисекунде. Значит, старт = 10 + 1 = 11. Проверка: 11 + 4 − 1 = 14 — совпадает с таблицей ✔
3. 3. Шаг 2. Сколько процессов завершится не позже 10-й миллисекунды. Пробегаем таблицу и отбираем финиши, не превышающие 10: процесс 1 (4), процесс 2 (3), процесс 3 (9), процесс 4 (5) и процесс 6 (10). Итого пять процессов.
4. 4. Шаг 3. Обратите внимание на процесс 6: его финиш ровно 10, и слово «не позже» означает, что он входит. Если бы спрашивали «раньше 10-й», ответом было бы четыре. Такие формулировки в линии 22 встречаются регулярно, и разница всегда в один процесс.
5. 5. Шаг 4. Какой процесс финиширует последним. Максимум таблицы равен 17 и достигается на процессе 9. Он же и определяет общую продолжительность работы — это всегда так: общее время равно наибольшему финишу.
6. 6.

   Шаг 5. Все три ответа программой, без пересчёта:

   print('старт 8:', max(finish(z) for z in processy[8][1]) + 1)
   print('не позже 10:', sum(1 for p in processy if finish(p) <= 10))
   print('последний:', max(processy, key=finish))

7. 7. Шаг 6. Печатается 11, 5 и 9 ✔ Функция finish считается один раз благодаря кэшу, поэтому три вопроса стоят ровно столько же, сколько один.
8. 8. Шаг 7. Вывод для экзамена: в линии 22 считать надо всю таблицу целиком, а не только тот процесс, о котором спросили. Таблица строится за то же время, зато отвечает на любой вопрос и позволяет проверить себя — например, сверить сумму по критическому пути с общим временем.

Ответ: 11; пять процессов; процесс 9