МОШ по информатике, заключительный этап, 10–11 класс — тренировочный комплект

«МОШ · Информатика · Заключительный этап · 10–11 класс» — тренировочный комплект для старшеклассников на заключительном этапе Московской олимпиады по информатике. Настоящий тур этого уровня решается написанием программ, поэтому здесь те же темы переложены на короткий проверяемый ответ: число операций, значение динамики, длина кратчайшего пути. Комплект составлен с нуля и не воспроизводит официальные варианты.

Какие темы охватывает набор

Первый блок — оценка сложности: сколько операций выполнит алгоритм с квадратичным и с логарифмическим временем при заданном размере входа, и во сколько раз вырастет время при удвоении данных. Это тот расчёт, который на олимпиаде решает, уложится решение в ограничение или нет. Второй блок посвящён динамическому программированию на классических сюжетах: число путей в прямоугольной сетке при движении только вправо и вниз, число способов подняться по лестнице шагами по одной и по две ступени (последовательность Фибоначчи в чистом виде) и наибольшая сумма при выборе без соседей. Третий блок отведён графам: число рёбер полного графа, сумма степеней вершин, условие существования эйлерова обхода и длина кратчайшего пути в небольшом взвешенном графе. Четвёртый блок разбирает кодирование и теорию информации: минимальная длина равномерного кода, объём данных при известной глубине цвета и разрешении, а также идея префиксного кода. Замыкают комплект вопросы о представлении целых чисел в памяти и о переполнении.

Как устроена работа

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

Разбор и подготовка

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

Кому пригодится

Набор подойдёт учителю информатики для профильного класса и олимпиадного кружка, а старшекласснику — для самопроверки перед заключительным этапом.

Форматы и условия прохождения

Работа доступна и на компьютере, и на мобильном телефоне: интерфейс сам подстраивается под размер экрана. Тест можно открыть на заданный промежуток времени — это удобно для выполнения дома. Предусмотрен контроль честности: переключение на другие вкладки и приложения во время теста отслеживается.