Информатика. ЕГЭ

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

Требуется построить или проанализировать таблицу истинности для логического выражения с конъюнкцией, дизъюнюнкцией, импликацией и отрицанием. Часто нужно определить, при каких наборах переменных выражение ложно, либо восстановить формулу по частичной таблице. Решается подстановкой значений или написанием короткой программы. Без компьютера, базовый уровень.

Даны связанные таблицы реляционной базы данных и условие отбора записей. Нужно найти количество строк, удовлетворяющих условию, или определить максимальное/минимальное значение поля. Проверяет понимание связей между таблицами и умение применять фильтры с логическими операциями. С использованием компьютера (файл базы данных), базовый уровень.

Дано бинарное кодовое дерево или набор кодовых слов для символов. Нужно подобрать кратчайшее кодовое слово для нового символа так, чтобы выполнялось условие Фано (никакое кодовое слово не является префиксом другого), либо определить, можно ли однозначно декодировать сообщение. Без компьютера, базовый уровень.

Дан алгоритм для формального числового, который преобразует число или строит геометрическую фигуру. Требуется определить результат работы алгоритма при заданных входных данных, либо найти количество чисел, для которых алгоритм выдаёт определённый результат. Решается пошаговым моделированием или программой. Без компьютера, базовый уровень.

Дан более сложный алгоритм с ветвлением или циклом — например, исполнитель перемещается по координатной плоскости. Нужно определить, сколько точек с заданными координатами попадает внутрь области, которую обходит исполнитель, либо найти максимальное/минимальное значение параметра, при котором выполняется условие. Без компьютера, базовый уровень.

Проверяет расчёт объёма данных: размер растрового изображения, глубина цвета, разрешение, частота дискретизации звука, количество каналов. Нужно перевести единицы измерения и применить формулы \(V = W \times H \times i\) для изображений или \(V = f \times i \times t \times k\) для звука. Часто требуется сравнить два варианта хранения или передачи. Без компьютера, базовый уровень.

Предлагается составить слова из заданного набора букв по правилам (ограничения на позиции, повторения, порядок). Нужно найти количество слов, удовлетворяющих условию, или определить слово, стоящее на определённом номере при лексикографическом упорядочивании. Решается формулами комбинаторики или программным перебором. Без компьютера, базовый уровень.

Дан файл с числовой таблицей. Нужно применить формулы и функции (СУММ, СРЗНАЧ, ЕСЛИ, СЧЁТЕСЛИ, МАКС, МИНИМУМ и др.) для обработки данных и получить числовой ответ. Проверяет умение работать с диапазонами, условиями и вложенными функциями. С использованием компьютера, базовый уровень.

Новое на этой позиции с 2027 года (ранее — №13). Дана IP-адресация и маска подсети, нужно определить количество адресов в подсети, адрес сети или номер конкретного компьютера. Требуется понимать двоичное представление IP-адреса и маски, а также логическую операцию побитового «И» для вычисления адреса сети. Без компьютера, базовый уровень.

Проверяет расчёт объёма информации при кодировании текста: мощность алфавита, количество бит на символ, длина сообщения, общее число комбинаций. Нужно применить формулу Хартли \(N = 2^i\) и аккуратно перевести единицы (биты, байты, килобайты). Часто встречается задача с паролем фиксированной длины и заданным набором символов. Без компьютера, повышенный уровень.

Прототип обновлён в 2026 году. Дана лента с символами и программа для исполнителя, работающего по правилам машины Тьюринга: головка читает символ, записывает новый, сдвигается влево или вправо. Нужно определить десятичное число, которое получится на ленте после выполнения программы. Требуется аккуратно смоделировать шаги исполнителя или написать программу-эмулятор. Без компьютера, повышенный уровень.

Переехало с позиции 23 в 2027 году. Дано описание алгоритма, выполняемого над числами или строками (арифметические преобразования, обработка цифр, перестановки). Требуется определить, сколько существует начальных значений, для которых алгоритм выдаёт заданный результат, либо найти сам результат для конкретного входа. Решается моделированием или программным перебором. Без компьютера, повышенный уровень.

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

Связано с преобразованием логических выражений и анализом условий. Часто встречается тип «отрезки на числовой прямой»: нужно найти наименьшее/наибольшее значение параметра, при котором выражение тождественно истинно. Также бывает тип с побитовыми операциями (конъюнкция по маске). Решается программным перебором или аналитически. Без компьютера, повышенный уровень.

Дано рекурсивное определение функции \(F(n),\) зависящей от \(F(n-1),\) \(F(n-2)\) и т.д. Нужно вычислить значение функции при заданном аргументе. Прямой рекурсивный подсчёт часто работает слишком медленно, поэтому требуется мемоизация (сохранение промежуточных результатов) или итеративный подход. С использованием компьютера, повышенный уровень.

Дан файл с последовательностью натуральных чисел. Нужно найти количество пар или троек элементов, удовлетворяющих заданному условию (например, оба элемента кратны заданному числу, их сумма оканчивается на определённую цифру), и максимальную или минимальную сумму среди таких пар. Требуется написать программу (10–15 строк), которая корректно считывает данные и перебирает комбинации. С использованием компьютера, повышенный уровень.

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

19 задание. Даны правила игры (две кучи камней, игроки делают ходы по определённому правилу, проигрывает тот, кто не может сделать ход). Нужно определить, кто выигрывает при заданной начальной позиции, если оба играют оптимально. Решается анализом позиций: проигрышная — та, из которой все ходы ведут в выигрышные, выигрышная — та, из которой есть ход в проигрышную. Без компьютера, базовый уровень.

20 задание. На основе тех же правил игры нужно найти все начальные позиции, при которых игрок, делающий первый ход, выигрывает своим вторым ходом независимо от действий противника. Требуется построить дерево игры на два уровня и проверить все ветви. Без компьютера, повышенный уровень.

21 задание. Нужно найти начальные позиции, при которых игрок выигрывает своим первым или вторым ходом, а также позиции, где выигрывает противник. Это самое сложное из заданий по теории игр — требуется полный анализ дерева игры или программный перебор всех позиций с мемоизацией. Без компьютера, высокий уровень.

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

Новое задание, появившееся в структуре ЕГЭ с 2027 года на месте бывшей задачи на анализ хода исполнения алгоритма. Дан текстовый файл с описанием ациклического ориентированного взвешенного графа: каждая строка содержит номер начальной вершины, номер конечной вершины и вес ребра. Требуется написать программу, которая находит целую часть длины кратчайшего пути между двумя заданными вершинами (алгоритм Дейкстры или релаксация рёбер) либо количество различных путей между ними (динамическое программирование по вершинам). Возможны вариации: путь, проходящий через заданную вершину, в обход вершины, самый длинный путь или путь с наименьшим числом рёбер. С использованием компьютера, повышенный уровень.

Дана длинная символьная строка. Нужно найти длину самой длинной подстроки, удовлетворяющей условию (например, не содержащей подряд одинаковых символов), максимальное количество идущих подряд групп символов, или заменить подстроки и посчитать результат. Требуется написать эффективную программу (10–20 строк), обрабатывающую строку за один проход. С использованием компьютера, высокий уровень.

Требуется найти все натуральные числа, соответствующие заданной маске (символы «?» — один разряд, «*» — любая последовательность), и для каждого найти делители по определённому правилу (например, максимальный нетривиальный делитель или количество чётных делителей). Нужно вывести первые пять чисел и соответствующие им значения. Решается программным перебором с проверкой маски и поиском делителей. С использованием компьютера, высокий уровень.

Дан файл с данными (например, товары со сроками хранения и годности, или пассажиры со временем прихода и продолжительностью обслуживания). Нужно применить жадный алгоритм: отсортировать данные по заданному критерию и выбрать максимальное количество объектов, удовлетворяющих ограничениям, а также определить определённое значение, связанное с выбором. В ответе — два числа. С использованием компьютера, высокий уровень, 2 балла.

Содержание обновлено с 2025 года. Дан файл с координатами точек. Нужно выполнить последовательность шагов анализа данных: разбить точки на кластеры (группы внутри непересекающихся прямоугольников заданного размера), вычислить координаты центров кластеров, найти расстояния между ними или радиусы кластеров. В ответе с 2027 года записывается одна строка из двух чисел (вместо двух строк по два числа, как было раньше). Требует сочетания Excel для визуализации и программы на Python для точных вычислений. С использованием компьютера, высокий уровень, 2 балла.