МБОУ Лицей инновационных технологий
СОГЛАСОВАНО Протокол №___от__ | УТВЕРЖДАЮ Директор_____________ Приказ №_____ от _________ |
АВТОРСКАЯ ПРОГРАММА ФАКУЛЬТАТИВНОГО КУРСА
"МЕТОДЫ ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ
ОЛИМПИАДНЫХ ЗАДАЧ"
Автор: учитель информатики
МБОУ Лицея инновационных технологий
г. Хабаровск
2012г.
Пояснительная записка
ВВЕДЕНИЕ.
Предлагаемая вашему вниманию программа факультативного курса "Методы программирования для решения олимпиадных задач" была разработана в связи с необходимостью подготовки способных учащихся к олимпиадам по информатике. Чтобы решать олимпиадные задачи, необходимо не только быстро и логически мыслить, но и владеть специальными методами программирования, которые позволяют создавать оптимальные и эффективные программы. Количество часов, отводимое в школьном курсе информатики на раздел "Алгоритмизация и программирование", недостаточно для того, чтобы хотя бы ознакомить учащихся с этими методами. В связи с этим появилась идея привлечения способных учащихся к изучению данного факультативного курса.
ЦЕЛИ И ЗАДАЧИ ФАКУЛЬТАТИВНОГО КУРСА
"МЕТОДЫ ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ
ОЛИМПИАДНЫХ ЗАДАЧ"
В настоящее время основным документом, определяющим содержание школьного образования по информатике, является государственный стандарт общего образования (далее – государственный образовательный стандарт), который разработан в соответствии с Законом Российской Федерации «Об образовании» (ст. 7) и Концепцией модернизации российского образования на период до 2010 года, утвержденной распоряжением Правительства Российской Федерации от 01.01.01 года. В основу государственного образовательного стандарта были положены следующие основные направления модернизации общего образования:
- введение профильного обучения на старшей ступени школы;
- личностная ориентация содержания образования;
- деятельностный характер образования, направленность содержания образования на формирование общих учебных умений и навыков, обобщенных способов учебной, познавательной, коммуникативной, практической, творческой деятельности, на получение учащимися опыта этой деятельности;
- формирование ключевых компетенций – готовности учащихся использовать усвоенные знания, умения и способы деятельности в реальной жизни для решения практических задач.
Определение таких целей и формирование соответствующего этим целям содержания образования, позитивно отразилось на развитии олимпиадного движения по информатике в стране.
Программа факультативного курса "Методы программирования для решения олимпиадных задач" построена с учетом ФГОС поколения по предмету «Информатика и ИКТ» с перспективой стандарта для старшей ступени школьного образования, а также на основе структуры современного содержания олимпиад по информатике.
Не следует рассматривать данную программу как совокупность знаний и умений, необходимых для победы в олимпиадах по информатике. Путь к наивысшим достижениям на олимпиадах по информатике является эволюционным и включает несколько этапов. Эти этапы органично отражены в современном Положении о Всероссийских олимпиадах школьников. Это школьный этап (точка входа в этот этап - 5-6 классы, диапазон участия 5-11 классы), муниципальный этап (точка входа в этот этап – 7-8 классы, диапазон участия 7-11 классы), региональный этап и заключительный этап (точки входа в эти этапы – 9 класс, диапазон участия 9-11 классы). При этом наивысшие достижения могут проявляться учениками на разных этапах олимпиады, однако следует учитывать, что сильнейшие учащиеся устойчиво показывают наивысшие достижения в группе 9-11 классов только в случае, если они использовали точку входа в олимпиады уже в 5-6 классах. Каждый из этапов характеризуется своим уровнем сложности. Постепенно осваивая каждый такой уровень и переходя с одного уровня на другой, - только так можно подняться на вершину олимпиадной пирамиды и стать лучшим из лучших.
Основная цель факультативного курса "Методы программирования для решения олимпиадных задач" ¾ увлечь учащихся программированием, дать способным учащимся материал для работы и обеспечить качественное усвоение знаний о методах программирования для разработки и реализации эффективных и оптимальных алгоритмов решения задач повышенной сложности.
Задача данного курса заключается в том, чтобы помочь учащимся в поиске оптимальных алгоритмов для решения сложных задач и привлечь их к участию в олимпиадах по информатике.
Структура факультативного курса включает в себя следующие разделы, каждый из которых имеет свое логическое развитие:
· методы перебора вариантов;
· методы работы со случайными числами;
· рекурсия;
· структурное программирование;
· методы поиска эффективных алгоритмов;
· доказательство правильности программ;
· стиль программирования;
· занимательные задачи кибернетики;
· некоторые численные методы;
· структуры данных;
· управление таблицами;
· методы сортировки.
Программа рассчитана на двухлетнее изучение курса в объеме 128 часов:
· 1-ый год обучения ¾ 64 часа в год(2 часа в неделю);
· 2-ой год обучения ¾ 64 часа в год(2 часа в неделю).
Предлагаемая программа ориентирована на учащихся владеющих основами программирования на каком-либо языке, так как она не ставит своей целью изучение языка программирования.
В результате изучения данного курса учащиеся получать возможность:
ü познакомиться с методами решения задач, использующих перебор вариантов и сокращением количества вариантов, узнать различные методы сортировки данных;
ü использовать методы работы со случайными числами, применять рекурсию, создавать игровые программы;
ü применять численные методы для решения алгебраических и трансцендентных уравнений, а также систем уравнений с помощью компьютерных программ;
ü овладеть элементами структурного программирования, методами поиска эффективных алгоритмов;
ü использования стиля программирования, структур данных и управления таблицами.
В лицее инновационных технологий проводились факультативные занятия по курсу "Методы программирования для решения олимпиадных задач" по данной программе для учащихся восьмых-девятых классов. Положительным результатом можно считать успешное выступление учащихся на ежегодно проводимой в лицее научно-практической конференции, а также их участие в районной, городской и краевой олимпиадах по информатике. Предлагаемые структура и содержание курса могут быть расширены и дополнены другими методами программирования.
СОДЕРЖАНИЕ КУРСА.
1. Методы перебора вариантов.
1.1. Вычислительные задачи, использующие свойства натуральных чисел.
Нахождение НОД и НОК. Треугольник Паскаля. Пифагоровы тройки. Простые числа. Решето Эратосфена. Совершенные числа. Числа палиндромы, Мерсена, Армстронга, Фибоначчи. Несократимые дроби. Цепные дроби.
1.2. Перебор.
Алгоритм перебора вариантов на примере задачи о восьми ферзях. Улучшение алгоритма. Сокращение вариантов. Применение алгоритма перебора вариантов для решения других задач.
1.3. Игровые задачи.
Игры: "Семь лунок", "Прыгающие шарики", "Пятнадцать", "Расстановка трех чисел", "Расстановка девяти чисел".
2. Методы работы со случайными числами.
2.1. Элементы комбинаторики.
Размещения с повторениями. Перестановки. Подмножества. Разбиения.
2.2. Игровые задачи.
Игровые задачи на обработку случайных чисел (кроссворды, шахматные задачи, игральные кости, карточные игры и др.).
3. Рекурсия.
Рекурсивные определения и рекурсивные программы. Свойства рекурсивных алгоритмов. Игра "Ханойская башня". Численные задачи. Сортировка. Восходящее рекурсивное вычисление. Алгоритм последовательных испытаний. Рекурсивная форма.
4. Занимательные задачи кибернетики.
Задачи "Артиллерист и пехотинец", "Тройственная дуэль", "Справедливый дележ", "Выбор шара", "Удивительное рядом" и др.
5. Некоторые численные методы.
Вычисление определителя методом триангуляции. Решение уравнений методами итераций, половинного деления, Ньютона, хорд. Решение систем уравнений: метод Гаусса, метод Зейделя.
6. Методы поиска эффективных алгоритмов.
"Разделяй и властвуй". Уравновешивание. Компиляция и интерпретация.
7. Управление таблицами.
7.1. Последовательная неупорядоченная таблица.
Представления. Алгоритмы поиска. Алгоритм включения.
7.2. Упорядоченная последовательная таблица.
Последовательный поиск в упорядоченной таблице. Последовательное включение. Дихотомический поиск.
7.3. Двоичное дерево поиска.
Метод. Равновесные двоичные деревья.
8. Методы сортировки.
Сортировка включением: простое включение, метод Шелла. Сортировка обменами: быстрая сортировка, пузырьковая сортировка. Сортировка слиянием. Сортировка извлечением: древесная сортировка. Сортировка распределением.
9. Структуры данных.
Множества, стеки, файлы, списки, деревья, двоичные деревья ¾ логическое описание, физическое представление. Решение задач на использование различных структур данных.
10. Структурное программирование.
10.1. Нисходящая разработка.
Модульность. Нисходящее проектирование программ. Планирование. Детализация. Управляющие структуры.
10.2. Пошаговая детализация.
Правила детализации. Сегментирование. Сквозной структурный контроль. Тестирование.
11. Стиль программирования.
11.1. Читаемость программы.
Стандартизация стиля. Комментарии. Выбор имен. Размещение операторов.
11.2. Проектирование программ.
Описание задачи. Выбор алгоритма. Описание данных. Универсальность. Документирование.
11.3. Отладка программы.
Виды отладки. Обнаружение ошибок. Средства отладки.
11.4. Тестирование программы.
Методы тестирования. Тестовые данные. Примеры тестов. Модули. Средства тестирования.
12. Доказательство правильности программ.
Правильность программы. Доказательства: их роль и границы. Сравнение с традиционными методами. Средства диагностики при выполнении.
В приложении 1 к программе по некоторым разделам курса приведен банк заданий. В приложении 2 представлено положение о лицейской олимпиаде по информатике.
Список рекомендуемой литературы для олимпиадной подготовки по информатике
1. , Беляев школьников к олимпиадам по информатике с использованием веб-сайта: учебно-методическое пособие для учащихся 7-11 классов. – Ханты-Мансийск: РИО ИРО, 2008. – 284 с.
2. , , Фалина основы информатики. Элективный курс: Учебное пособие. – М.: БИНОМ. Лаборатория Знаний, 2007. – 312 с.
3. Программирование игр и головоломок. – М.: Наука, 1990. – 224 с.
4. Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — Пер. с англ. — М.: Мир, 1979. — 536 с.
5. Бентли Д. Жемчужины творчества программистов: пер. с англ. – М.: Радио и связь, 1990. – 224 с.
6. , , Коломенская задачи по информатике. – М.: БИНОМ. Лаборатория знаний. 2007. – 119 с.
7. , Каплан олимпиады по программированию/ Под ред. акад. .- 2-е изд., доп. и пераб. – М.: Наука, гл. ред. физ.-мат. лит., 1990. – 208 с.
8. , Цветкова для начинающих. – М.: БИНОМ. Лаборатория знаний. 2007. – 287 с.
9. Г., , и др. Ярославские олимпиады по информатике. Сборник задач с решениями. – М.: БИНОМ. Лаборатория знаний. 2010. – 405 с.
10. Долинский и программирование на Turbo Pascal: от простых до олимпиадных задач: Учебное пособие. – СПб.: Питер Принт, 2004. – 240 с.
11. Задачи по программированию /, , и др.; Под ред. . – М.: БИНОМ. Лаборатория знаний, 2006. – 820 с.
12. Златопольский : типовые задачи, алгоритмы, методы. – М.: БИНОМ. Лаборатория знаний, 2007. – 223 с.
13. , , Окулов анализа сложных задач по информатике: от простого к сложному // Информатика и образование. 2006. №10. С. 21 – 32.
14. Кирюхин олимпиада школьников по информатике. М.: АПК и ППРО, 2005. –212 с.
15. Кирюхин . Всероссийские олимпиады. Выпуск 1. – М.: Просвещение, 2008. – 220 с. – (Пять колец).
16. Кирюхин . Всероссийские олимпиады. Выпуск 2. – М.: Просвещение, 2009. – 222 с. – (Пять колец).
17. Кирюхин . Всероссийские олимпиады. Выпуск 3. – М.: Просвещение, 2010. – 201 с. – (Пять колец).
18. Кирюхин . Международные олимпиады. Выпуск 1. – М.: Просвещение, 2009. – 239 с. – (Пять колец).
19. , Окулов анализа сложных задач по информатике // Информатика и образование. 2006. №4. С. 42 – 54.
20. , Окулов анализа сложных задач по информатике // Информатика и образование. 2006. №5. С. 29 – 41.
21. , Окулов решения задач по информатике. Международные олимпиады. – М.: БИНОМ. Лаборатория знаний, 2007. – 600 с.
22. , Цветкова олимпиада школьников по информатике в 2006 году. – М.: АПК и ППРО, 2006. – 152 с.
23. Алгоритмы: построение и анализ.
– М.: МЦНМО, 1999. – 960с.
24. Меньшиков задачи по программированию. – СПб.: Питер, 2006. – 315 с.
25. Московские олимпиады по информатике. 2002 – 2009. / Под ред. , и . – М.: МЦНМО, 2009. – 414 с.
26. Окулов программирования. – М.: БИНОМ. Лаборатория знаний, 2005. – 440 с.
27. Окулов в алгоритмах. – М.: БИНОМ. Лаборатория знаний. 2002. – 341 с.
28. Окулов математика. Теория и практика решения задач по информатике: учебное пособие. – М.: БИНОМ. Лаборатория знаний. 2008. – 422 с.
29. Окулов обработки строк: учебное пособие. – М.: БИНОМ. Лаборатория знаний, 2009. – 255 с.
30. , Лялин башни. – М.: БИНОМ. Лаборатория знаний. 2008. – 245 с. (Развитие интеллекта школьников).
31. Пинаев задачи по программированию: Учебное пособие / РГАТА. – Рыбинск, 1997. – 41 с.
32. Просветов математика: задачи и решения: учебное пособие. – М.: БИНОМ. Лаборатория знаний. 2008. – 222 с.
33. 128 задач по началам программирования. – М.: БИНОМ. Лаборатория знаний. 2009. – 167 с.
34. Комбинаторные алгоритмы: теория и практика / Э. Рейнгольд, Ю. Нивергельт, Н. Део. – М.: Мир, 1980. – 476 с.
35. , Ревилла задачи по программированию. Руководство по подготовке к соревнованиям. – М.: Кудиц-образ, 2005. – 416 с.
36. , . Информатика. Представление данных и алгоритмы. – СПб.: Невский Диалект; М.: БИНОМ. Лаборатория знаний. 2007. –382 с.
37. Сулейманов внеклассной работы в школьном клубе программистов: методическое пособие. – М.: БИНОМ. Лаборатория знаний. 2010.
– 255 с.
38. Этюды для программистов. – М.: Мир, 1982. – 288 с.
39. Программирование: теоремы и задачи. – М.:МЦНМО, 1995. – 264 с.
