мария: хороший сайт
21-07-2024
Читать статью
мария: класс
20-07-2024
маша: мяу
Сегодня посмотрим 22 задание из ЕГЭ по информатике 2025.
В этом задании даётся файл в программе Excel.
Данное задание нетрудное, достаточно пару раз сделать, чтобы понять, как решать его.
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.
Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.
Типовой пример организации данных в файле:
В данном случае независимые процессы 1 и 2 могут выполняться параллельно, при этом процесс 1 завершится через 4 мс, а процесс 2 – через 3 мс с момента старта. Процесс 3 может начаться только после завершения обоих процессов 1 и 2, то есть, через 4 мс после старта. Он длится 1 мс и закончится через 4 + 1 = 5 мс после старта. Выполнение процесса 4 может начаться только после завершения процесса 3, то есть, через 5 мс. Он длится 7 мс, так что минимальное время завершения всех процессов равно 5 + 7 = 12 мс.
У нас есть различные процессы. Для каждого процесса известно время его выполнения (столбец B), а так же от каких процессов он зависит (столбец С).
Общее время выполнения процесса вычисляется следующим образом: процесс должен дождаться самый долгий процесс от которого он зависит, а потом выполнится сам.
Используем столбец D, чтобы вычислить окончательное время выполнения каждого процесса.
Важно помнить, что когда мы берём время процесса от которого зависит какой-то процесс, то мы должны взять это время из столбца D, т.е. уже окончательное время выполнения процесса.
Минимальное время, через которое завершится выполнение всей совокупности процессов будет равно времени самого медленного процесса.
Здесь есть процессы, которые зависят от других процессов. В столбце D вычислим время для всех процессов с учётом зависимостей.
Если процесс зависит от двух процессов, то время ожидания будет равно самому медленному из этих процессов.
В столбце D пишем для каждой строчки: время процесса + время ожидания самого медленного процесса, от которого зависит этот процесс (если такие есть).
Если пока нельзя вычислить реальное время выполнения процесса, то оставим эту ячейку пустой.
Теперь посмотрим ещё раз на всю таблицу и заполним оставшиеся процессы.
Выберем самый долгий процесс, это и есть минимальное время за которое могут закончится все процессы.
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.
Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение четырёх процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.
Рекомендуется ужать ширину столбцов, чтобы было удобно работать. Сделать это можно так: выделяем нужные буквы столбцов, вызываем контекстное меню, потом ширина столбца и выбираем, к примеру, 5.
Справа от нашей таблицы построим "диаграмму". Для каждой строчки мы будем выделять ячейки каким-нибудь цветом, сколько длиться соответствующий процесс.
Если процесс зависит от какого-либо процесса, он должен дождаться его выполнения, а потом уже выполниться сам.
Если процесс зависит от нескольких процессов, то он должен дождаться самый долгих процесс, а потом выполниться сам.
Вот какой рисунок получается. Отметка ноль выбрана на границе D и E столбцов.
Теперь расставим единицы в жёлтые клеточки, а внизу подсчитаем сумму единиц для каждого столбца. Для ячейки E15 пропишем формулу:
Распространим эту формулу на всю строчку.
При таком подходе максимальный отрезок, когда будет выполняться 4 процесса одновременно будет равен 4.
Но в данной задаче не сказано, что все процессы должны завершиться за минимально возможное время. Поэтому мы можем смещать процессы по времени, если это возможно.
Здесь мы сдвинули четыре нижних процесса так, чтобы был максимальный отрезок с 4 процессами.
Длина максимального отрезка равна 7.
Решим более удобным способом. Данный способ может не подходить, когда задача слишком сложная. Но это задание достаточно новое, поэтому, скорее всего, будет уровень не сильно завышен. Кроме того в этом способе тоже можно допустить ошибку, если рассмотреть не все варианты. Но в задачах лёгкого и среднего уровня он существенно позволяет сэкономить силы и помогает правильно решить задачу.
Изобразим наши процессы схематично, как показано на рисунке, чтобы было видно кто от кого зависит. Это сделать очень просто.
Нам нужно, чтобы четыре процесса выполнялись одновременно. У нас вариантов не так много. Процессы 1 и 2 идут параллельно друг другу, а так же есть ещё две параллельные ветки 9-11 и 10-12. Или другой вариант ветки 4 и 5-6, а так же 9-11 и 10-12.
Найдём в каком случае отрезок получится больше.
Максимальная продолжительность первого и второго процесса, когда они идут вместе будет 3 (Берём по минимальной длине).
Блок процессов 4, 5-6 будет длиться 7. В начале можно подсчитать 5-6. Эта ветка длится 6+2=8. Процесс 4 длится 7 мс. Берём по минимуму, значит, это блок длится 7 мс.
Аналогично вычисляем ветки 9-11 и 10-12.
Нам выгоднее использовать блок 4, 5-6, т.к. там длина получается наибольшая. Когда мы сделаем четыре параллельные ветки (10-12, 9-11, 4, 5-6), то нужно вновь взять по минимуму.
Ответ получается 7 мс.
Будем решать последним методом. Распишем процессы и покажем кто от кого зависит.
Как и в прошлой задаче у нас всего два варианта сделать, чтобы было 4 параллельных процесса. Блок состоящий из процессов 9, 11, 10, 12 передвинуть либо к процессам 1, 2, либо 4-6, 5-7.
Мы видим, что нижний блок немного сложней, чем в прошлой задаче, т.к. процесс 11 зависит ещё и 10. Нарисуем данный блок классическим методом.
Классическая диаграмма данного блока выглядит так:
Важно: всегда подобные запутанные блоки расписывайте классическим способом, чтобы не ошибиться.
Распишем все основные блоки.
Видим, что передвинуть нижний блок к веткам 4-6, 5-7 выгодней. В этом блоке получится 10 мс, т.к. берём по минимуму.
Чтобы выполнялось четыре процесса одновременно, получаем отрезок 9 мс, это длина нижнего блока.
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно.
Типовой пример организации данных в файле
Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение максимального количества процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно, а время завершения каждого процесса минимально.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Обратите внимание на то, что "время завершения каждого процесса минимально". Это означает, что процессы жёстко закреплены и их нельзя двигать. Они стремятся, как можно быстрее начаться и как можно быстрее завершиться.
Так же нужно найти отрезок, где будет максимальное количество процессов. Здесь нужно решать классической диаграммой, но теперь нам легче, т.к. не нужно думать, куда сдвигать те или иные процессы.
Максимальное количество параллельных процессов равно 4. Максимальный отрезок с 4 процессами равен 6.
