В этой статье будет разобрано задание 22.

Рассмотрим задачи последних лет из демоверсий ЕГЭ по информатике.

Данное задание относится к повышенному уровню сложности.

Время выполнения задания ≈ 7 минут.

Данное задание выполняется в одном из приложенных файлов(.ods, .xls, .xlsx) с помощью электронной таблицы. Краткий конспект по обработке информации в электронной таблице по ссылке:

Ссылка на статью: Обработка информации в электронных таблицах.

Задача 1 (Демоверсия ЕГЭ 2024 год)

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

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

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

Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение четырёх процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.

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

Решение:

Решение с помощью электронной таблицы

Решение производится в файле Excel. Или любом другом табличном процессоре(например, LibreOffice).

Рекомендуется "сжать" столбцы, чтобы было удобнее. Сделать это можно так: выделяем нужные буквы столбцов, вызываем контекстное меню, потом ширина столбца пропишем к примеру 5.

Вариант решения следующий:

Справа от нашей таблицы для каждой строчки мы будем выделять ячейки каким-нибудь цветом, сколько длиться соответствующий процесс. Если процесс зависит от какого-либо процесса, он должен дождаться его выполнения, а потом уже выполниться сам. Если процесс зависит от нескольких процессов, то он должен дождаться выполнения самого долгого процесса, а потом выполниться сам. После разрисовывания такой "диаграммы" по клеточкам расставим единицы в закрашенные клеточки, а внизу подсчитаем сумму единиц для каждого столбца. Для ячейки E15 пропишем формулу: =СУММ(E2:E13) и распространим эту формулу на всю строчку(до конца последнего процесса). Затем мы увидим, что при таком подходе максимальный отрезок, когда будет выполняться 4 процесса одновременно будет равен 4. Но в данной задаче не сказано, что все процессы должны завершиться за минимально возможное время. Поэтому мы можем смещать процессы по времени, если это возможно. Нужно сдвинуть четыре нижних процесса так, чтобы был максимальный отрезок с 4 процессами. И наконец, тогда длина максимального отрезка будет равна 7.

p.s. Подробнее с комментариями решения такой задачи ниже на видео:

Решение на Python

Для решения данной задачи с помощью кода на Python придётся предварительно создать текстовый файл с данными(скопировать данные из таблицы в текстовый файл):

Далее идёт пример решения задачи с кодом на Python и комментариями в самом коде:

# Скопируем содержимое таблицы в файл и прочитаем его.
# Заменим точки с запятой на пробелы
from copy import deepcopy

file = open('22_2024.txt').read().replace(';', ' ')
# преобразуем данные в список строк из чисел
nums = [[int(x) for x in s.split()]
        for s in file.split('\n')]
# создадим словарь вида
# № процесса: (время выполнения, процессы)
pr = {c[0]: [c[1], c[2:]] for c in nums}


# определим функцию, которая возвращает время работы процесса
# n - номер процесса
def f(n):
    # если номер равен 0, то время выполнения 0
    # (начало всех процессов)
    if n == 0:
        return 0
    # иначе максимальное время выполнения
    # для всех предыдущих процессов
    # плюс время выполнения процесса n
    return max(f(x) for x in pr[n][1]) + pr[n][0]


# находим максимальное значение
max_mc = max(f(x) for x in pr)

a_procs = []
b_procs = []

# A процессы независимые и могут запускаться сразу
# B процессы зависимые
for x in pr:
    if pr[x][1][0] == 0:
        a_procs.append(x)
    else:
        b_procs.append(x)

# print(a_procs)
# print(b_procs)
max_mc_four_count_proc = 0
count = 0
dict_proc = deepcopy(pr)
dict_mc = dict()
for mc in range(1, max_mc + 1):
    for a_pr in a_procs:
        dict_proc[a_pr][0] -= 1
        if dict_proc[a_pr][0] >= 0:
            if not dict_mc.get(mc, False):
                dict_mc[mc] = []
            dict_mc[mc].append(a_pr)
    for b_pr in b_procs:
        sup_proc = dict_proc[b_pr][1]
        for sup_pr in sup_proc:
            flag = False
            if dict_proc[sup_pr][0] < 0:
                flag = True
            else:
                break
        if flag:
            dict_proc[b_pr][0] -= 1
            if dict_proc[b_pr][0] >= 0:
                if not dict_mc.get(mc, False):
                    dict_mc[mc] = []
                dict_mc[mc].append(b_pr)

# print(dict_mc)

# Возможно неполное решение задачи, если процессы стартовые А, которые раньше заканчиваются вместе с подпроцессами
# в отличие от самой длинной цепочки процессов - смещать по времени от 1 мс нельзя!
count_four_procs = 0
for key_mc in dict_mc:
    if len(dict_mc[key_mc]) == 4:
        count_four_procs += 1

print(count_four_procs)  # Вывод ответа

p.s. Пример показывает возможность решить данную задачу с помощью программирования. На самом экзамене предпочтительно для ученика пользоваться способ решения данной задачи с помощью электронной таблицы.

Ответ: 7

Задача 2 (Демоверсия ЕГЭ 2025 год)

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

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

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

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

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

Решение:

Решение с помощью электронной таблицы

Решение производится в файле Excel. Или любом другом табличном процессоре(например, LibreOffice).

Рекомендуется "сжать" столбцы, чтобы было удобнее. Сделать это можно так: выделяем нужные буквы столбцов, вызываем контекстное меню, потом ширина столбца пропишем к примеру 4.

Вариант решения следующий:

Справа от нашей таблицы для каждой строчки мы будем выделять ячейки каким-нибудь цветом, сколько длиться соответствующий процесс. Если процесс зависит от какого-либо процесса, он должен дождаться его выполнения, а потом уже выполниться сам. Если процесс зависит от нескольких процессов, то он должен дождаться выполнения самого долгого процесса, а потом выполниться сам. После разрисовывания такой "диаграммы" по клеточкам расставим единицы в закрашенные клеточки, а внизу подсчитаем сумму единиц для каждого столбца. Для ячейки E16 пропишем формулу: =СУММ(E2:E14) и распространим эту формулу на всю строчку(до конца последнего процесса). Затем мы увидим, что при таком подходе максимальный отрезок, когда будет выполняться это 4 процесса одновременно будет равен 5. В данной задаче сказано, что все процессы должны завершиться за минимально возможное время. После записи решения видим, что мы можем смещать процессы по времени на 1мс. Но ответ при этом на задачу не поменяется, т.е. 4 процесса выполняются в данном случае по длине максимального отрезка равного 5.

p.s. Подробнее с комментариями решения такой задачи был здесь выше на видео(на примере задачи 1 из демоверсии 2024 года).

Решение на Python

Для решения данной задачи с помощью кода на Python придётся предварительно создать текстовый файл с данными(скопировать данные из таблицы в текстовый файл):

Далее идёт пример решения задачи с кодом на Python и комментариями в самом коде:

# Скопируем содержимое таблицы в файл и прочитаем его.
# Заменим точки с запятой на пробелы
from copy import deepcopy

file = open('22_2025.txt').read().replace(';', ' ')
# преобразуем данные в список строк из чисел
nums = [[int(x) for x in s.split()] for s in file.split('\n')]
# создадим словарь вида
# № процесса: (время выполнения, процессы)
pr = {c[0]: [c[1], c[2:]] for c in nums}


# определим функцию, которая возвращает время работы процесса
# n - номер процесса
def f(n):
    # если номер равен 0, то время выполнения 0
    # (начало всех процессов)
    if n == 0:
        return 0
    # иначе максимальное время выполнения
    # для всех предыдущих процессов
    # плюс время выполнения процесса n
    return max(f(x) for x in pr[n][1]) + pr[n][0]

# находим максимальное значение
max_mc = max(f(x) for x in pr)

a_procs = []
b_procs = []

# A процессы независимые и могут запускаться сразу
# B процессы зависимые
for x in pr:
    if pr[x][1][0] == 0:
        a_procs.append(x)
    else:
        b_procs.append(x)

# print(a_procs)
# print(b_procs)
max_mc_four_count_proc = 0
count = 0
dict_proc = deepcopy(pr)
dict_mc = dict()
for mc in range(1, max_mc + 1):
    for a_pr in a_procs:
        dict_proc[a_pr][0] -= 1
        if dict_proc[a_pr][0] >= 0:
            if not dict_mc.get(mc, False):
                dict_mc[mc] = []
            dict_mc[mc].append(a_pr)
    for b_pr in b_procs:
        sup_proc = dict_proc[b_pr][1]
        for sup_pr in sup_proc:
            flag = False
            if dict_proc[sup_pr][0] < 0:
                flag = True
            else:
                break
        if flag:
            dict_proc[b_pr][0] -= 1
            if dict_proc[b_pr][0] >= 0:
                if not dict_mc.get(mc, False):
                    dict_mc[mc] = []
                dict_mc[mc].append(b_pr)

# print(dict_mc)

# Полное решение задачи, если процессы стартовые А, которые раньше заканчиваются вместе с подпроцессами
# в отличие от самой длинной цепочки процессов - смещать по времени от 1 мс нельзя!
count_four_procs = 0
count_procs = 0   # задать 999999999 если ищем минимальную продолжительность процессов или 0 если максимальную
flag = True
for key_mc in dict_mc:
    if len(dict_mc[key_mc]) == 4:  # Меняем на 3 если максимальную продолжительность 3-х процессов ищем и т.п.
        if flag:
            count_four_procs += 1
        else:
            count_four_procs = 0
            count_four_procs += 1
            flag = True
    else:
        flag = False
        count_procs = max(count_procs, count_four_procs)  # min если ищем минимальную продолжительность процессов

print('Ответ: ',count_procs)

p.s. Пример показывает возможность решить данную задачу с помощью программирования. На самом экзамене предпочтительно для ученика пользоваться способ решения данной задачи с помощью электронной таблицы.

Ответ: 5

Задача 3 (Демоверсия 2026)

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

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

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

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

Решение:

Решение с помощью электронной таблицы

Решение производится в файле Excel. Или любом другом табличном процессоре(например, LibreOffice).

Рекомендуется "сжать" столбцы, чтобы было удобнее. Сделать это можно так: выделяем нужные буквы столбцов, вызываем контекстное меню, потом ширина столбца пропишем к примеру 4.

Вариант решения следующий:

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

p.s. Подробнее с комментариями решения такой задачи был здесь выше на видео(на примере задачи из демоверсии 2024 года).

Решение на Python

Для решения данной задачи с помощью кода на Python придётся предварительно создать текстовый файл с данными(скопировать данные из таблицы в текстовый файл):

Далее идёт пример решения задачи с кодом на Python и комментариями в самом коде:

file = open('22_2026.txt').read().replace(';', ' ')
# преобразуем данные в список строк из чисел
nums = [[int(x) for x in s.split()] for s in file.split('\n')]
# создадим словарь вида
# № процесса: (время выполнения, процессы)
prs = {c[0]: [c[1], c[2:]] for c in nums}


# определим функцию, которая возвращает время работы процесса
# n - номер процесса
def f(n):
    # если номер равен 0, то время выполнения 0
    # (начало всех процессов)
    if n == 0:
        return 0
    # иначе максимальное время выполнения
    # для всех предыдущих процессов
    # плюс время выполнения процесса n
    return max(f(x) for x in prs[n][1]) + prs[n][0]


# находим максимальное значение мс
max_mc = max(f(x) for x in prs)

num_prs = set(prs.keys())
dict_mc = dict()  # Словарь у которого ключ это время в мс по порядку, а значение это запущенные процессы в эту мс
for mc in range(1, max_mc + 1):
    dict_mc[mc] = []
    for key_pr in prs:
        proc_mc = prs[key_pr][0]
        sub_procs = prs[key_pr][1]
        for sub_proc in sub_procs:
            if sub_proc in num_prs:
                continue
            else:
                prs[key_pr][1].remove(sub_proc)
        sub_procs = prs[key_pr][1]
        if len(sub_procs) == 0 and proc_mc > 0:
            dict_mc[mc].append(key_pr)
            prs[key_pr][0] -= 1
    for key_pr in prs:
        if prs[key_pr][0] == 0:
            if key_pr in num_prs:
                num_prs.remove(key_pr)

print(dict_mc) # Показывает по ключам мс и запущенные процессы

# Полное решение задачи, если процессы стартовые А, которые раньше заканчиваются вместе с подпроцессами
# в отличие от самой длинной цепочки процессов - смещать по времени от 1 мс нельзя!
count = 0   # счётчик для ответа количество процессов которые завершаться за первые 17 мс
mc_check = 18 # ограничение до 18 мс
set_procs = set(dict_mc[1])  # записываем во множество id процессов которые запустились на 1 мс.
for key_mc in range(2, mc_check + 1): # проходим в цикле по мс
    procs = dict_mc[key_mc]
    for proc in procs:
        if proc in set_procs:
            set_procs.remove(proc)
    count += len(set_procs)
    set_procs = set(procs)

print('Ответ: ',count)

p.s. Пример показывает возможность решить данную задачу с помощью программирования. На самом экзамене предпочтительно для ученика пользоваться способ решения данной задачи с помощью электронной таблицы.

Ответ: 12