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

Содержание

ВВЕДЕНИЕ.3

ГЛАВА I. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО РЕШЕНИЮ ОЛИМПИАДНЫХ ЗАДАЧ ПО ИНФОРМАТИКЕ.4

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

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

1.3. Алгоритмы на графах.7

1.4. Вычислительная геометрия.10

1.5. Комбинаторные алгоритмы.14

ГЛАВА II. ОРГАНИЗАЦИЯ УЧЕБНОЙ ДЕЯТЕЛЬНОСТИ ПО РЕШЕНИЮ ЗАДАЧ .16

ГЛАВА III. БИБЛИОТЕКА ОЛИМПИАДНОЙ ИНФОРМАТИКИ.24

ЗАКЛЮЧЕНИЕ.29

СПИСОК ЛИТЕРАТУРЫ.30

ПРИЛОЖЕНИЕ.34

Введение

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

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

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

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

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

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

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

Выдержка из текста работы

ГЛАВА I. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО РЕШЕНИЮ ОЛИМПИАДНЫХ ЗАДАЧ ПО ИНФОРМАТИКЕ

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

• динамическое программирование;

• алгоритмы перебора с возвратом;

• алгоритмы на графах;

• вычислительная геометрия;

• комбинаторные алгоритмы.

Рассмотрим краткое содержание этих разделов и особенности использования присущих им подходов и методов при решении олимпиадных задач по информатике.

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).

Заключение

Бытует точка зрения, что «простому» учителю информатики не под силу подготовить школьника к олимпиадам высокого уровня по информатике, что эта работа является уделом «избранных». Главным является создание творческой среды в работе с одаренными детьми. Безусловно, учителю или наставнику необходимо целенаправленно работать над данной проблематикой, но быть «асом» в решении задач совершенно не обязательно! Удивительно, но в основе практически любой сложности лежит простота. Увидеть (найти) эту простоту, идти от этой простоты к решению задачи в процессе совместной деятельности со школьником — это и есть лейтмотив работы учителя или наставника. Перед учителем информатики по- прежнему, как и в начале становления школьной информатики в 1985 году стоят те же самые проблемы: чему учить? как учить? какие учебники использовать? Эти проблемы остались, несмотря на возросшие возможности компьютера, как осталось неизменным и предназначение учителя — развивать школьника в рамках своего предмета так, чтобы он стал Личностью с большой буквы. Остался неизменным и такой критерий оценки деятельности учителя, как успешность выступления его учеников на предметной олимпиаде. Поэтому в своей работе я постаралась классифицировать олимпиадные задачи, описать структуру учебной деятельности по решению задачи и собрать в одном месте библиотеку олимпиадной информатики.

Список литературы

1. Алексеев А. В., Беляев С. Н. Подготовка школьников к олимпиадам по информатике с использованием веб-сайта: учеб.-метод. пособие для учащихся 7–11 классов. Ханты-Мансийск: РИО ИРО, 2008. 284 с.

2. Волчёнков С. Г., Корнилов П. А., Белов Ю. А. и др. Ярославские олимпиады по информатике. Сборник задач с решениями. М.: БИНОМ. Лаборатория знаний. 2010. 405 с.

3. Долинский М. С. Алгоритмизация и программирование на TurboPascal: от простых до олимпиадных задач: учеб.пособие. СПб.: Питер Принт, 2004. 240 с.

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

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