ЕГЭ по информатике: оптимизация алгоритмов и профилирование

Зачем нужно

Экономить время выполнения программ, избегать лишних операций.
Понимать, когда стоит использовать перебор, а когда — динамическое программирование или «жадные» подходы.
Анализировать асимптотику алгоритмов и выбирать подход, соответствующий ограничениям.

Шаги анализа

1. Определите размер входных данных и ограничения задачи. 2. Оцените трудоёмкость текущего решения (перебор, рекурсия, хранение данных). 3. Ищите способы сокращения состояния: мемоизация, кэширование, использование структур данных. 4. Проверяйте изменения на тестах и фиксируйте в таблице «оптимизация → эффект».

Таблица «Стратегия → описание → примеры»

Стратегия	Краткое описание	Пример задачи
Сокращение перебора	Отсечение ветвей, прунинг, ранний выход	Задачи на размещение, поиск путей
Динамическое программирование	Хранение промежуточных результатов для переиспользования	Числа Фибоначчи, рюкзак, минимальная стоимость
Жадные алгоритмы	Выбор локально лучшего решения, ведущего к глобально приемлемому	Минимальные монеты, расписания
Предобработка данных	Сортировка, построение префиксных сумм/минимумов	Запросы на сумму/минимум/максимум
Параллелизм и профилирование	Разделение задач, измерение «узких мест»	Анализ больших массивов, работоспособность решений Python

Недельный спринт

**День 1:** анализ асимптотики, таблица «O(·) → пример → ограничение по n».
**День 2:** динамическое программирование: простые примеры, перевод рекурсии в DP.
**День 3:** жадные стратегии, доказательства корректности на конкретных задачах.
**День 4:** структурирование данных (стек, очередь, словарь), профилирование простых скриптов.
**День 5:** мини-пробник: три задачи (перебор → оптимизация) + отчёт «что изменилось».

Чек-лист выпускника

Умею быстро оценивать трудоёмкость предложенного решения.
Понимаю, когда использовать алгоритмы с мемоизацией.
Веду таблицу оптимизаций: «было → стало → прирост».
Применяю профилирование (timeit, встроенные счётчики) для проверки идей.

Работа в вики

Создайте «Оптимизация алгоритмов/ноябрь»: примеры, сравнения, ссылку на практикум.
Свяжите страницу с ЕГЭ/Информатика/Программирование и алгоритмы и Ресурсы:Генератор контрольных вопросов.
В проводите «оптимизационные баттлы» (кто быстрее улучшит решение).

Советы наставника

Попросите ученика объяснить, почему выбор структуры данных меняет скорость.
Поощряйте документирование оптимизаций (таблица «операция → эффект»).
Разбирайте реальные примеры из олимпиад и ЕГЭ-ориентированных задач.