Задание 22. Математические модели и архитектура компьютеров: ЕГЭ по информатике

Задание 22 ЕГЭ по информатике проверяет умение строить и анализировать математическую модель параллельно-последовательного выполнения вычислительных процессов с учётом зависимостей. Нужно по таблице процессов (ID, длительность, зависимости) определить момент старта каждого процесса (самое раннее…

Что нужно знать

Процесс B зависит от A, если для B нужны результаты A; тогда B не может начаться раньше, чем закончится A.
Процесс начинается в самое раннее допустимое время: как только завершены все процессы, от которых он зависит.
Если процесс независим (зависимость 0), он начинается на 1-й миллисекунде.
Время выполнения процесса задано в миллисекундах; процесс занимает целое число миллисекунд.
Если процесс начинается на миллисекунде t и длится d мс, то он выполняется в моменты t, t+1, …, t+d-1, а заканчивается перед миллисекундой t+d.
Нумерация миллисекунд начинается с 1.

Термины и понятия

Процесс: выполняемая программа или часть программы, которой нужны ресурсы процессора.
Зависимость: отношение, при котором процесс B требует результатов процесса A, поэтому B не может начаться до завершения A.
Параллельное выполнение: одновременное выполнение нескольких процессов на разных ядрах или в разные моменты времени на одном ядре (здесь …
Миллисекунда (мс): единица времени; в задании время дискретно, нумерация начинается с 1.
Время старта: номер миллисекунды, с которой процесс начинает выполняться.
Время окончания: номер миллисекунды, следующей сразу после последней миллисекунды выполнения процесса.
Длительность: количество миллисекунд, в течение которых процесс выполняется.
Топологическая сортировка: упорядочивание вершин графа зависимостей, при котором все зависимости идут раньше зависимых процессов.

Частые ошибки

Неверное определение времени старта процесса: забывают учесть все зависимости, а не только одну.
Путают момент окончания и момент начала: считают, что процесс заканчивается в миллисекунду старт+длительность, а не перед ней.
Не учитывают, что процессы начинаются в самое раннее допустимое время, и пытаются сдвигать их.
Ошибка в арифметике при сложении длительностей.

Как пройти тему

В курсе «Информатика» тема «Задание 22. Математические модели и архитектура компьютеров» занимает 5 занятий по 40 минут: репетитор объясняет материал, задаёт вопросы как на экзамене, разбирает ваши ответы и в конце ставит оценку. Это обзор темы, полный разбор — в занятии. ИИ может ошибаться: проверяйте важное по учебнику. Занятия не заменяют живого репетитора и не гарантируют результат на экзамене.

Начать бесплатно Открыть курс

Другие темы раздела

← Предыдущая тема: Задание 21. Дерево игры и выигрышная стратегия
Следующая тема: Задание 23. Анализ графов

Все темы: ЕГЭ по информатике