«Методика решения олимпиадных задач»

В настоящее время школьные олимпиады по информатике являются важными составляющими национальной системы выявления и работы с талантливой молодежью. Важное место в этой системе занимает методическая и информационная поддержка всех этапов Всероссийской олимпиады школьников, начиная со школьного этапа, и международной олимпиады по информатике, которые проводятся ежегодно в рамках системных мероприятий Министерства образования и науки Российской Федерации. Если сами по себе олимпиады позволяют только выявлять одаренных школьников, то систематическая работа с одаренными детьми по развитию их способностей становится ключевой в олимпиадном движении по любому предмету, в том числе и по информатике. И здесь возникает много вопросов: анализ олимпиадных и сложных задач по информатике и их объяснения учащимся и т.д.

Все это позволило сформулировать тему нашей квалификационной работы «Решение олимпиадных задач по информатике».

Целью является разработка методических рекомендаций по решению олимпиадных задач по информатике.

Объектом является процесс обучения информатике.

Предметом является решение олимпиадных задач по информатике.

Выпускная квалификационная работа состоит из введения, глав, заключения, литературы и приложения.

1.1. Динамическое программирование

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

В том случае, когда исходная задача определяется одним параметром N, определяющим размерность задачи, идея метода динамического программирования очень похожа на идею метода математической индукции. А именно, предположим, что мы уже знаем решение Fk задачи размерности k для всех k, меньших N, и хотим получить решение для k, равного N. Если нам удастся выразить это решение через уже известные, то тем самым будет получен алгоритм решения задачи для произвольного N. В частности, зная решения задач F0, F1, …, Fs, вычисляем в цикле решения Fs+1, Fs+2 и т.д. до искомого решения FN.

Задачи, решение которых основано на использовании метода динамического программирования, зачастую требуют только правильного применения основной идеи этого метода. После этого нужна только аккуратная реализация алгоритма. Сложно выделить какие-то общие ошибки или проблемы, возникающие в таких задачах. Все же отметим, что часто «лобовое» применение принципа динамического программирования не укладывается в ограничения, например, по памяти (такие задачи требовательны к памяти, ведь мы экономим время работы, в том числе за счет хранения промежуточных результатов). Поэтому, возможно, потребуется аккуратная реализация хранения большого количества данных (динамическая память, структуры данных).

Наиболее интересной с точки зрения сложности используемых при решении методов является: задача «Почтовые отделения» (12-я МОИ, 2-й тур) – сложная как по поиску динамической схемы решения, так и по ее реализации (Приложение 1).

1.2. Перебор с возвратом

Метод перебора с возвратом (backtracking) более правильно назвать методом поиска с деревом решений. Классическими задачами, на которых обычно демонстрируется этот подход, являются обход конем доски размером N´N, расстановка N ферзей на доске N´N и задача коммивояжера.

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

Основной принцип, на котором базируется рассматриваемый метод, состоит в следующем. Рассмотрим, для определенности, задачу P0 оптимизационного типа. Декомпозируем задачу P0 на некоторое число подзадач P1, …, Pk, представляющих в целом всю задачу P0. Далее попытаемся по очереди решить каждую из этих подзадач. Под решением подзадачи обычно подразумевается:

• либо показать, что подзадача Pi не является допустимой;

• либо показать, что решать задачу Pi не имеет смысла, поскольку значение оптимального решения для Pi заведомо хуже, чем для наилучшего из ранее найденных решений;

• либо определить оптимальное решение задачи Pi, если эта задача настолько проста, что оптимальное решение находится очевидным образом;

• либо разбить задачу Pi на подзадачи Pi1, …, Pis и рекурсивно перейти к рассмотрению задачи Pi1.

Смысл описанного разбиения задачи на некоторое число подзадач состоит в том, что или эти подзадачи проще разрешить, или они имеют меньшую размерность, или обладают какой-то дополнительной структурой, не присущей первоначальной задаче. Поскольку мы должны отсекать те ветви дерева решений, которые заведомо не могут содержать решения, лучшего уже найденного, то становится важным как можно раньше найти хорошее приближение к оптимальному решению. Поэтому бывает выгодно найти начальное решение с помощью эвристики (например, жадного алгоритма) и организовать перебор таким образом, чтобы наиболее «перспективные» варианты рассматривались первыми. Кроме того, можно найти несколько начальных решений с помощью различных эвристик, а затем выбрать из них наилучшее.

Часто бывает так, что все время работы переборного алгоритма уходит на попытки разрешить подзадачу P1 исходной задачи P0, в то время как оптимальное решение P0 находится в другой подзадаче Pi. В этом случае полезно использовать метод локальной оптимизации. Его идея заключается в том, что для каждого решения рассматриваемой задачи определяются «близкие» к нему решения. При нахождении алгоритмом перебора с возвратом более хорошего решения, чем наилучшее из ранее найденных, вызывается подпрограмма, которая перебирает все близкие решения в надежде еще более улучшить полученное. Эта схема перебора уже не является простым обходом дерева вариантов, поскольку близкие решения могут располагаться в этом дереве далеко друг от друга.

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

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

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

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

5. Кирюхин В. М. Всероссийская олимпиада школьников по информатике. М.: АПК и ППРО, 2005. 212 с.

6. Кирюхин В. М. Информатика. Всероссийские олимпиады. Вып. 2. М.: Просвещение, 2009. 222 с. (Пять колец).

7. Кирюхин В. М. Информатика. Всероссийские олимпиады. Вып. 3. М.: Просвещение, 2011. 222 с. (Пять колец).

8. Кирюхин В. М. Информатика. Международные олимпиады. Вып. 1. М.: Просвещение, 2009. 239 с. (Пять колец).

9. Кирюхин В. М., Лапунов А. В., Окулов С. М. Задачи по информатике. Международные олимпиады 1989–1996 гг. М.: ABF, 1996. 272 с.

10. Кирюхин В. М., Окулов С. М. Методика анализа сложных задач по информатике // Информатика и образование. 2006. № 4. С. 42–54.

11. Кирюхин В. М., Окулов С. М. Методика анализа сложных задач по информатике // Информатика и образование. 2006. № 5. С. 29–41.

12. Кирюхин В. М., Окулов С. М. Методика решения задач по информатике. Международные олимпиады. М.: БИНОМ. Лаборатория знаний, 2007. 600 с. 13. Кирюхин В. М., Цветкова М. С. Всероссийская олимпиада школьников по информатике в 2006 году. М.: АПК и ППРО, 2006. 152 с.

14. Кирюхин В. М., Цветкова М. С. Методическое обеспечение олимпиадной информатики в школе / Сб. трудов XVII конференции- выставки «Информационные технологии в образовании». Ч. III. М.: БИТ про, 2007. С. 193–195

15. Кирюхин В. М. Информатика. Всероссийские олимпиады. Вып. 1. М.: Просвещение, 2008. 220 с. (Пять колец).

16. Меньшиков Ф. В. Олимпиадные задачи по программированию. СПб.: Питер, 2006. 315 с.

17. Московские олимпиады по информатике. 2002–2009 / под ред. Е. В. Андреевой, В. М. Гуровица и В. А. Матюхина. М.: МЦНМО, 2009. 414 с.

18. Нижегородские городские олимпиады школьников по информатике / под ред. В. Д. Лелюха. Нижний Новгород: ИПФ РАН, 2010. 130 с.

19. Никулин Е. А. Компьютерная геометрия и алгоритмы машинной графики. СПб.: БХВ-Петербург, 2003. 560 с.

20. Окулов С. М. Основы программирования. М.: БИНОМ. Лаборатория знаний, 2005. 440 с.

21. Окулов С. М. Программирование в алгоритмах. М.: БИНОМ. Лаборатория знаний. 2002. 341 с.

22. Окулов С. М. Дискретная математика. Теория и практика решения задач по информатике: учеб.пособие. М.: БИНОМ. Лаборатория знаний. 2008. 422с.

23. Окулов С. М. Алгоритмы обработки строк: учеб.пособие. М.: БИНОМ. Лаборатория знаний, 2009. 255 с.

24. Окулов С. М., Пестов А. А. 100 задач по информатике. Киров: Изд-во ВГПУ, 2000. 272 с.

25. Окулов С. М., Лялин А. В. Ханойские башни. М.: БИНОМ. Лаборатория знаний. 2008. 245 с. (Развитие интеллекта школьников).

26. Просветов Г. И. Дискретная математика: задачи и решения: учеб.пособие. М.: БИНОМ. Лаборатория знаний. 2008. 222 с.

27. Скиена С. С., Ревилла М. А. Олимпиадные задачи по программированию. Руководство по подготовке к соревнованиям. М.: Кудиц- образ, 2005. 416 с. 28. Сулейманов Р. Р. Организация внеклассной работы в школьном клубе программистов: методическое пособие. М.: БИНОМ. Лаборатория знаний. 2010. 255 с.

29. Цветкова М. С. Система развивающего обучения как основа олимпиадного движения / Сборник трудов XVII конференции-выставки «Информационные технологии в образовании». Ч. III. М.: БИТ про, 2007. С. 205–207