|
|
| Строка 1: |
Строка 1: |
| = ЕГЭ по информатике: оптимизация алгоритмов и профилирование = | | == Обсуждение == |
| | | * Форум: [url=https://forum.egebal.ru/viewforum.php?f=35]ЕГЭ — информатика[/url] |
| == Зачем нужно == | | * Тема: [url=https://forum.egebal.ru/viewtopic.php?t=488]Оптимизация решений — отчёты и советы[/url] |
| * Экономить время выполнения программ, избегать лишних операций. | | * Формат отчёта: задача, исходное решение, оптимизированное решение, прирост по времени. |
| * Понимать, когда стоит использовать перебор, а когда — динамическое программирование или «жадные» подходы.
| |
| * Анализировать асимптотику алгоритмов и выбирать подход, соответствующий ограничениям.
| |
| | |
| == Шаги анализа == | |
| 1. Определите размер входных данных и ограничения задачи.
| |
| 2. Оцените трудоёмкость текущего решения (перебор, рекурсия, хранение данных).
| |
| 3. Ищите способы сокращения состояния: мемоизация, кэширование, использование структур данных.
| |
| 4. Проверяйте изменения на тестах и фиксируйте в таблице «оптимизация → эффект».
| |
| | |
| == Таблица «Стратегия → описание → примеры» == | |
| {| class="wikitable"
| |
| ! Стратегия !! Краткое описание !! Пример задачи
| |
| |-
| |
| | Сокращение перебора || Отсечение ветвей, прунинг, ранний выход || Задачи на размещение, поиск путей
| |
| |-
| |
| | Динамическое программирование || Хранение промежуточных результатов для переиспользования || Числа Фибоначчи, рюкзак, минимальная стоимость
| |
| |-
| |
| | Жадные алгоритмы || Выбор локально лучшего решения, ведущего к глобально приемлемому || Минимальные монеты, расписания
| |
| |-
| |
| | Предобработка данных || Сортировка, построение префиксных сумм/минимумов || Запросы на сумму/минимум/максимум
| |
| |-
| |
| | Параллелизм и профилирование || Разделение задач, измерение «узких мест» || Анализ больших массивов, работоспособность решений Python
| |
| |}
| |
| | |
| == Недельный спринт ==
| |
| * **День 1:** анализ асимптотики, таблица «O(·) → пример → ограничение по n». | |
| * **День 2:** динамическое программирование: простые примеры, перевод рекурсии в DP.
| |
| * **День 3:** жадные стратегии, доказательства корректности на конкретных задачах.
| |
| * **День 4:** структурирование данных (стек, очередь, словарь), профилирование простых скриптов.
| |
| * **День 5:** мини-пробник: три задачи (перебор → оптимизация) + отчёт «что изменилось».
| |
| | |
| == Чек-лист выпускника == | |
| * Умею быстро оценивать трудоёмкость предложенного решения.
| |
| * Понимаю, когда использовать алгоритмы с мемоизацией.
| |
| * Веду таблицу оптимизаций: «было → стало → прирост».
| |
| * Применяю профилирование (timeit, встроенные счётчики) для проверки идей.
| |
| | |
| == Работа в вики ==
| |
| * Создайте «Оптимизация алгоритмов/{{CURRENTMONTHNAME}}»: примеры, сравнения, ссылку на практикум.
| |
| * Свяжите страницу с [[ЕГЭ/Информатика/Программирование и алгоритмы]] и [[Ресурсы:Генератор контрольных вопросов]].
| |
| * В [[Категория:Сообщество]] проводите «оптимизационные баттлы» (кто быстрее улучшит решение). | |
| | |
| == Советы наставника ==
| |
| # Попросите ученика объяснить, почему выбор структуры данных меняет скорость.
| |
| # Поощряйте документирование оптимизаций (таблица «операция → эффект»).
| |
| # Разбирайте реальные примеры из олимпиад и ЕГЭ-ориентированных задач.
| |
| | |
| [[Категория:ЕГЭ]]
| |
| [[Категория:Информатика]]
| |
| [[Категория:Предметы ЕГЭ]]
| |
