ЕГЭ-22. Математические модели. Параллельные вычисления

(А. Богданов) В файле 22-69.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно... (Условие совпадает с условием задачи из демо-варианта 2023 года).

Определите количество процессов, которых будут активны на 32-й мс после запуска первого процесса.

В файле 22-62.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно... (Условие совпадает с условием задачи из демо-варианта 2023 года).

Определите количество процессов, которых будут активны на 100-й мс после запуска первого процесса.

В файле 22-62.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно... (Условие совпадает с условием задачи из демо-варианта 2023 года).

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

В файле 22-62.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно... (Условие совпадает с условием задачи из демо-варианта 2023 года).

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

(А. Богданов) Ваня пишет скрипты для генерации заданий ЕГЭ. Известно время, которое затрачивает Ваня на написание каждого скрипта, и время выполнения скрипта. Запуск очередного скрипта возможен только после окончания выполнения скриптов, которые подготавливают для него данные, т. е. тех, от которых скрипт зависит. Пока скрипт работает, Ваня может писать следующий скрипт, но Ваня не может писать два скрипта одновременно и пишет все скрипты в том порядке, в котором они внесены в таблицу. Компьютер у Вани многоядерный и может обрабатывать много простых скриптов одновременно, без взаимного влияния на общую производительность. Определите минимальное время, через которое может завершиться выполнение всех скриптов при условии, что все независимые друг от друга скрипты могут выполняться параллельно.

Информация о скриптах записана в файле 22-65.xls. Типовой пример организации данных в файле:

В данном случае скрипт 1 можно запустить только через 5 минут после начала работы, он закончит выполняться через 5 + 4 = 9 минут. Скрипт 2 Ваня напишет через 5 + 2 = 7 минут, он сразу начнёт работу и закончит выполняться через 7 + 3 = 10 минут. Таким образом, через 11 минут все скрипты-поставщики данных для процесса 3 уже закончили работу, но сам скрипт 3 Ваня напишет (и сможет запустить) только через 5 + 2 + 7 = 14 мин после начала работы. Этот скрипт закончит выполняться через 14 + 1 = 15 минут. Последний скрипт 4 Ваня напишет через 14 + 4 = 18 мин, он закончит выполняться через 18 + 7 = 25 мин. Ответ: 25.

В файле 22-62.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно... (Условие совпадает с условием задачи из демо-варианта 2023 года).

Определите, сколько процессов будут в состоянии ожидания на 151-й мс после старта первого процесса (т.е., при 150 мс \< t \< 151 мс) при условии, что все независимые друг от друга процессы могут выполняться параллельно и каждый процесс начинает выполняться сразу, как только для этого есть возможность.

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

Определите, сколько процессов будут активны на 200-й мс после старта первого процесса (т.е., при 200 мс < t < 201 мс) при условии, что все независимые друг от друга процессы могут выполняться параллельно и каждый процесс начинает выполняться сразу, как только для этого есть возможность.

В файле 22-62.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно... (Условие совпадает с условием задачи из демо-варианта 2023 года).

Определите, сколько процессов закончатся не позднее, чем через 200 мс после старта первого процесса при условии, что все независимые друг от друга процессы могут выполняться параллельно и каждый процесс начинает выполняться сразу, как только для этого есть возможность.

(PRO100 ЕГЭ) В файле 22-61.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно... (Условие совпадает с условием задачи из демо-варианта 2023 года).

Определите минимальное время, через которое может завершится выполнение процесса с ID = 7, при условии, что все независимые друг от друга процессы могут выполняться параллельно.

(А. Богданов) В файле 22-60.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно... (Условие совпадает с условием задачи из демо-варианта 2023 года).

Определите максимальное количество процессов, которые завершатся за 73 мс, при условии, что все независимые друг от друга процессы могут выполняться параллельно.

(А. Богданов) В файле 22-59.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно... (Условие совпадает с условием задачи из демо-варианта 2023 года).

(Е. Джобс) В файле 22-58.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или двух других процессов -- поставщиков данных. Независимые процессы (не имеющие поставщиков данных) можно запускать в любой момент времени. Если процесс B (зависимый процесс) получает данные от процесса A (поставщика данных), то процесс B может начать выполнение сразу же после завершения процесса A. Любые процессы, готовые к выполнению, можно запускать параллельно, при этом количество одновременно выполняемых процессов может быть любым, длительность процесса не зависит от других параллельно выполняемых процессов.

В таблице представлены идентификатор (ID) каждого процесса, его длительность и ID поставщиков данных для зависимых процессов.

Для одного из процесса неизвестно, после какого процесса х он должен начать работать. Известно, что минимальное время выполнения всех процессов равно 17 мс. Найдите номер процесса х.

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

Пусть минимальное время выполнения данной совокупности процессов равно 10 мс. В данном случае минимальное время окончания процесса 1 -- 4 мс от начала запуска процессов, процесса 2 -- 3 мс, процесса 4 -- 6 мс (3 мс + 3 мс), следовательно, третий процесс может завершиться за 10 мс. Так как время его выполнения 6 мс, то он должен начаться не позднее, чем через 4 мс после начал выполнения всех процессов. Через 4 мс заканчивается только один процесс -- процесс 1. Значит, х равен 1.

(Е. Джобс) В файле 22-57.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или двух других процессов -- поставщиков данных. Независимые процессы (не имеющие поставщиков данных) можно запускать в любой момент времени. Если процесс B (зависимый процесс) получает данные от процесса A (поставщика данных), то процесс B может начать выполнение сразу же после завершения процесса A. Любые процессы, готовые к выполнению, можно запускать параллельно, при этом количество одновременно выполняемых процессов может быть любым, длительность процесса не зависит от других параллельно выполняемых процессов.

В таблице представлены идентификатор (ID) каждого процесса, его длительность и ID поставщиков данных для зависимых процессов.

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

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

Пусть выполнение данной совокупности процессов закончилось за 15 мс. В данном случае независимые процессы 1 и 2 могут выполняться параллельно, при этом процесс 1 завершится через 4 мс, а процесс 2 -- через 3 мс с момента старта. Процесс 3 может начаться только после завершения обоих процессов 1 и 2, то есть, через 4 мс после старта. Он длится t мс и закончится через 4 + t мс после старта. Выполнение процесса 4 может начаться только после завершения процесса 3, то есть, через 4 + t мс. Он длится 7 мс, так что минимальное время завершения всех процессов равно 4 + t + 7 = 15 мс. Следовательно, t = 15 -- 4 -- 7 = 4 мс. Ответ для этого примера: 4.

(А. Кабанов) В файле 22-56.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или двух других процессов -- поставщиков данных. Независимые процессы (не имеющие поставщиков данных) можно запускать в любой момент времени. Если процесс B (зависимый процесс) получает данные от процесса A (поставщика данных), то процесс B может начать выполнение сразу же после завершения процесса A. Любые процессы, готовые к выполнению, можно запускать параллельно, при этом количество одновременно выполняемых процессов может быть любым, длительность процесса не зависит от других параллельно выполняемых процессов.

В таблице представлены идентификатор (ID) каждого процесса, его длительность и ID поставщиков данных для зависимых процессов.

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

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

Пусть нас интересуют процессы, которые завершились в первые 6 мс. В данном случае независимые процессы 1 и 2 могут выполняться параллельно, при этом процесс 1 завершится через 4 мс, а процесс 2 -- через 3 мс с момента старта. Процесс 3 может начаться только после завершения обоих процессов 1 и 2, то есть, через 4 мс после старта. Он длится 1 мс и закончится через 4 + 1 = 5 мс после старта. Выполнение процесса 4 может начаться только после завершения процесса 3, то есть, через 5 мс. Он длится 7 мс и закончится через 5 + 7 = 12 мс. За первые 6 мс успеют завершиться процессы 1, 2, 3. Ответ для этого примера: 3.

(А. Кабанов) В файле 22-55.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или двух других процессов -- поставщиков данных. Независимые процессы (не имеющие поставщиков данных) можно запускать в любой момент времени. Если процесс B (зависимый процесс) получает данные от процесса A (поставщика данных), то процесс B может начать выполнение сразу же после завершения процесса A. Любые процессы, готовые к выполнению, можно запускать параллельно, при этом количество одновременно выполняемых процессов может быть любым, длительность процесса не зависит от других параллельно выполняемых процессов.

В таблице представлены идентификатор (ID) каждого процесса, его длительность и ID поставщиков данных для зависимых процессов.

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

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

Пусть нас интересуют процессы, которые завершились в первые 6 мс. В данном случае независимые процессы 1 и 2 могут выполняться параллельно, при этом процесс 1 завершится через 4 мс, а процесс 2 -- через 3 мс с момента старта. Процесс 3 может начаться только после завершения обоих процессов 1 и 2, то есть, через 4 мс после старта. Он длится 1 мс и закончится через 4 + 1 = 5 мс после старта. Выполнение процесса 4 может начаться только после завершения процесса 3, то есть, через 5 мс. Он длится 7 мс и закончится через 5 + 7 = 12 мс. За первые 6 мс успеют завершиться процессы 1, 2, 3. Ответ для этого примера: 3.

(А. Куканова) В файле 22-46.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы -- время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.

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

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

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

Рассмотрим пример выше в случае, если устройство имеет 2 вычислительных ядра: ядро I и ядро II. Независимые процессы 1, 2 и 5 готовы к выполнению, но запустятся только процессы 5 (пусть на ядре I) и 1 (на ядре II) как имеющие большее время выполнения. При этом процесс 1 завершится через 4 мс после старта, и на освободившемся ядре II начнётся выполнение процесса 2. Оно продлится 3 мс и завершится через 4 + 3 = 7 мс после старта. Процесс 5 завершится через 5 мс после старта, но процесс 3 может быть запущен только после завершения процессов 1 и 2, поэтому ядро I останется свободным. Заметим, что процессы 3 и 4 выполняются последовательно и могут быть выполнены на одном и том же ядре. К моменту завершения процесса на ядре I был выполнен 1 процесс (ID 5), а на ядре II --- 2 процесса (ID 1 и 2). Тогда максимальное число процессов, выполненных на одном ядре, будет достигнуто, если процессы 3 и 4 запустить на ядре II, и составит 4. Процесс 3 продлится 1 мс и закончит выполнение через 7 + 1 = 8 мс после старта. Процесс 4 продлится 7 мс и завершится через 8 + 7 = 15 мс после старта. Таким образом, вычисления завершились через 15 мс. Ответ будем сумма 15 и 4 (наибольшее число процессов на одном ядре), т.е. 19.

(А. Куканова) В файле 22-46.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы -- время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.

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

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

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

Рассмотрим пример выше в случае, если устройство имеет 2 вычислительных ядра: ядро I и ядро II. Независимые процессы 1, 2 и 5 готовы к выполнению, но запустятся только процессы 5 (пусть на ядре I) и 1 (на ядре II) как имеющие большее время выполнения. При этом процесс 1 завершится через 4 мс после старта, и на освободившемся ядре II начнётся выполнение процесса 2. Оно продлится 3 мс и завершится через 4 + 3 = 7 мс после старта. Процесс 5 завершится через 5 мс после старта, но процесс 3 может быть запущен только после завершения процессов 1 и 2, поэтому ядро I останется свободным. Заметим, что процессы 3 и 4 выполняются последовательно и могут быть выполнены на одном и том же ядре. К моменту завершения процесса на ядре I был выполнен 1 процесс (ID 5), а на ядре II --- 2 процесса (ID 1 и 2). Тогда максимальное число процессов, выполненных на одном ядре, будет достигнуто, если процессы 3 и 4 запустить на ядре II, и составит 4. Процесс 3 продлится 1 мс и закончит выполнение через 7 + 1 = 8 мс после старта. Процесс 4 продлится 7 мс и завершится через 8 + 7 = 15 мс после старта. Таким образом, вычисления завершились через 15 мс. Ответ будем сумма 15 и 4 (наибольшее число процессов на одном ядре), т.е. 19.

(А. Куканова) В файле 22-46.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы -- время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.

Вычислительное устройство имеет 3 вычислительных ядра. Каждый из параллельных процессов выполняется на отдельном ядре. Готовые к выполнению процессы добавляются в очередь. Если в очередь одновременно добавляется несколько процессов, они располагаются в ней в порядке возрастания ID. Первый в очереди процесс запускается, как только появляется свободное ядро, и выходит из очереди (если остались свободные ядра, процесс повторяется). Какой процесс завершился последним? В ответе укажите сумму его ID и времени, прошедшего с момента начала вычислений до их завершения.

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

Рассмотрим пример выше в случае, если устройство имеет 2 вычислительных ядра: ядро I и ядро II. Независимые процессы 1, 2 и 5 готовы к выполнению и располагаются в очереди в порядке возрастания ID. Запустятся процессы 1 (пусть на ядре I) и 2 (на ядре II), в очереди останется процесс 5. При этом процесс 2 завершится через 3 мс, и освободившемся ядре II запускается единственный в очереди процесс 5, который завершится через 3 + 5 = 8 мс после старта. Очередь становится пуста. Процесс 1 завершится через 4 мс после старта и позволит добавить в очередь процесс 3, который сразу же начнёт выполнение на освободившемся ядре I. Очередь снова пуста. Процесс 3 завершится через 4 + 1 = 5 мс после старта. Процесс 4 встанет в очередь и сразу же начнёт выполняться на освободившемся ядре I. Выполнение процесса 4 продлится 7 мс и закончится через 5 + 7 = 12 мс после начала вычислений. Все процессы выполнены, последним завершился процесс 4 через 12 мс после старта. Ответом будет сумма 4 и 12, т.е. 16.

(А. Куканова) В файле 22-46.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы -- время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.

Вычислительное устройство имеет 4 вычислительных ядра. Каждый из параллельных процессов выполняется на отдельном ядре. Готовые к выполнению процессы добавляются в очередь. Если в очередь одновременно добавляется несколько процессов, они располагаются в ней в порядке возрастания ID. Первый в очереди процесс запускается, как только появляется свободное ядро, и выходит из очереди (если остались свободные ядра, процесс повторяется). Какой процесс завершился последним? В ответе укажите сумму его ID и времени, прошедшего с момента начала вычислений до их завершения.

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

Рассмотрим пример выше в случае, если устройство имеет 2 вычислительных ядра: ядро I и ядро II. Независимые процессы 1, 2 и 5 готовы к выполнению и располагаются в очереди в порядке возрастания ID. Запустятся процессы 1 (пусть на ядре I) и 2 (на ядре II), в очереди останется процесс 5. При этом процесс 2 завершится через 3 мс, и освободившемся ядре II запускается единственный в очереди процесс 5, который завершится через 3 + 5 = 8 мс после старта. Очередь становится пуста. Процесс 1 завершится через 4 мс после старта и позволит добавить в очередь процесс 3, который сразу же начнёт выполнение на освободившемся ядре I. Очередь снова пуста. Процесс 3 завершится через 4 + 1 = 5 мс после старта. Процесс 4 встанет в очередь и сразу же начнёт выполняться на освободившемся ядре I. Выполнение процесса 4 продлится 7 мс и закончится через 5 + 7 = 12 мс после начала вычислений. Все процессы выполнены, последним

завершился процесс 4 через 12 мс после старта. Ответом будет сумма 4 и 12, т.е. 16.

(А. Куканова) В файле 22-46.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы -- время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.

Вычислительное устройство имеет 3 вычислительных ядра. Каждый из параллельных процессов выполняется на отдельном ядре. Будем говорить, что ядро простаивает, если ядро не выполняет никакой процесс и при этом не вся совокупность процессов выполнена. Из готовых к выполнению

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

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

Рассмотрим пример выше в случае, если устройство имеет 2 вычислительных ядра: ядро I и ядро II. Независимые процессы 1, 2 и 5 готовы к выполнению, но запустятся только процессы 1 (пусть на ядре I) и 2 (на ядре II) как имеющие меньшее время выполнения. При этом процесс 2 завершится через 3 мс. Поскольку процесс 3 может начаться только после завершения обоих процессов 1 и 2, на освободившемся ядре II запускается процесс 5, который завершится через 3 + 5 = 8 мс после старта. Процесс 1 завершится через 4 мс после старта и позволит начать выполнение процесса 3 на освободившемся ядре I. Процесс 3 завершится через 4 + 1 = 5 мс после старта. На освободившемся ядре I начнётся выполнение процесса 4, которое продлится 7 мс и закончится через 5 + 7 = 12 мс после начала вычислений. Таким образом, ядро I не простаивало, а ядро II начало простаивать через 8 мс после старта и простаивало до конца вычислений через 12 мс после старта. Тогда суммарное время простоя всех ядер равно времени простоя ядра II и составляет 12 - 8 = 4 мс. Ответ: 4.