Муниципальное образовательное учреждение
«Суслонгерская средняя общеобразовательная школа»
| Рассмотрена на заседании педагогического совета МОУ «Суслонгерская СОШ» Протокол № 1 «24» августа 2020 года
| «Утверждаю» Директор МОУ «Суслонгерская СОШ» _____________С.Е. Желонкина «__27_»____08_______2020 года
|
Дополнительная общеобразовательная общеразвивающая программа олимпиадной направленности
«Информик»
для детей 15-17 лет, рассчитанная на 3 года обучения
Автор-составитель программы:
Облопова Елена Николаевна
Педагог высшей квалификационной категории информатики и математики
Суслонгер
2020
Программа содержит:
- пояснительную записку;
- методических указания по изучению тем;
- учебно-тематический план и программы подготовки к олимпиадам по информатике.
- электронные учебные материалы
- ссылки на источники информационного сопровождения (учебная и техническая литература, обучающие программы, электронные библиотеки).
Пояснительная записка.
Важной задачей образования является работа с одаренными учащимися, их подготовка к предметным олимпиадам. Олимпиада по информатике занимает одно из ведущих мест, в связи с интенсивным развитием информационных технологий как в нашей стране, так и за рубежом.
Участие в олимпиадах позволяет развивать творческие способности школьников и обеспечивает высокую мотивацию к образовательной деятельности.
Классическая олимпиада по информатике – это олимпиада по программированию, которая предполагает наличие обширных познаний в математике и языках программирования.
Решение олимпиадных задач позволяет раскрыть творческий потенциал школьника во время подготовки к олимпиаде, учитывая возрастные особенности ребенка и перспективу его развития. Использование многоуровневых олимпиадных задач, позволяет школьникам применить свой творческий потенциал, независимо от уровня подготовки.
Курс занятий по Олимпиадной информатике (решение олимпиадных задач по информатике) ориентирован на учащихся 9-11х классов, обладающих повышенной мотивацией к изучению информатики и имеющих начальные знания в области алгоритмизации на уровне понимания простейших алгоритмов.
Данный элективный курс позволяет провести непрерывную подготовку к олимпиадам по информатике начиная с 9-го класса, используя методическую коллекцию олимпиадных задач. В курсе использован системный подход при разработке модулей непрерывной подготовки одаренных детей к олимпиадам по информатике.
Основная цель курса: раскрыть значение программирования и суть профессии программиста, ознакомление учащихся со средой и основами программирования на языке PascalABC.NET, подготовить учащихся к практическому использованию полученных знаний при решении учебных задач, а затем профессиональной деятельности, вовлечение учащихся в участие в олимпиадах по программированию разного уровня.
Основные задачи курса: развитие навыков программирования алгоритмических структур; развитие логического мышления учащихся; развитие интеллекта учащихся.
Данная программа представляет большую практическую значимость с точки зрения совершенствования непрерывной работы с одаренными школьниками в рамках олимпиадного движения по информатике и школьного образования.
Методические указания по изучению тем
Олимпиадные задачи по информатике охватывают следующие ключевые разделы:
1. Математические основы информатики.
Этот раздел является фундаментальной основой информатики. В олимпиадах по информатике это особенно важно, так как школьникам сложно достичь успешности на олимпиадных состязаниях без хорошей подготовки в области теории множеств, логики, теории графов и комбинаторики.
Для успешного выступления на олимпиаде по информатике школьники должны
знать/понимать:
основы терминологии функций, отношений и множеств;
перестановки, размещения и сочетания множества;
формальные методы символической логики высказываний
основы построения рекуррентных соотношений;
основные методы доказательств;
основы теории чисел;
уметь:
выполнять операции, связанные с множествами, функциями и отношениями;
вычислять перестановки, размещения и сочетания множества, а также интерпретировать их значения в контексте конкретной задачи;
решать типичные рекуррентные соотношения;
осуществлять формальные логические доказательства и логическое рассуждение для моделирования алгоритмов;
определять, какой вид доказательства лучше подходит для решения конкретной задачи;
использовать основные алгоритмы теории чисел;
использовать при решении практических задач вышеназванные знания и умения.
Основными темами этого раздела являются:
1. Отношения, функции и множества.
2. Основные геометрические понятия.
3. Основы логики.
4. Основы вычислений.
5. Методы доказательства.
6. Основы теории чисел.
7. Основы алгебры.
8. Основы комбинаторики.
9. Теорию графов.
10. Основы теории вероятностей.
11. Основы теории игр.
2. Разработка и анализ алгоритмов.
В этом разделе определяется основная способность учащихся знать классы алгоритмов, которые предназначены для решения определенного набора известных задач, понимать их сильных и слабых сторон, применять различные алгоритмы в заданном контексте с оценкой его эффективности.
В рамках этого раздела школьники должны знать/понимать:
элементы теории алгоритмов;
основные структуры данных;
основные понятия теории графов, а также их свойства и некоторые специальные случаи;
связь графов и деревьев со структурами данных, алгоритмами и вычислениями;
свойства, присущие «хорошим» алгоритмам;
вычислительную сложность основных алгоритмов сортировки, поиска;
понятие рекурсии и общую постановку рекурсивно-определенной задачи;
простые численные алгоритмы;
основные комбинаторные алгоритмы;
основные алгоритмы вычислительной геометрии;
наиболее распространенные алгоритмы сортировки;
наиболее важные алгоритмы на строках;
фундаментальные алгоритмы на графах: поиск в глубину и в ширину, нахождение кратчайших путей от одного источника и
основы динамического программирования;
основные положения теории игр;
уметь:
выбирать подходящие структуры данных для решения задач;
использовать вышеназванные алгоритмы в процессе решения задач;
определять сложность по времени и памяти алгоритмов;
определять вычислительную сложность основных алгоритмов сортировки, поиска;
реализовывать рекурсивные функции и процедуры;
использовать при решении практических задач вышеназванные знания и умения.
Основными темами этого раздела являются:
1. Алгоритмы и их свойства.
2. Структуры данных
3. Основы анализа алгоритмов.
4. Алгоритмические стратегии.
5. Рекурсия.
6. Фундаментальные вычислительные алгоритмы.
7. Числовые алгоритмы.
8. Алгоритмы на строках.
9. Алгоритмы на графах.
10. Динамическое программирование.
11. Алгоритмы теории игр.
3. Основы программирования.
В этом разделе закладывается условие успешного выступления учащихся на олимпиадах по информатике. Данный раздел включает в себя материал по фундаментальным концепциям программирования, основным структурам данных и алгоритмам, а также собственно языки программирования.
В рамках этого раздела школьники должны знать/понимать:
основные конструкции программирования;
концепцию типа данных как множества значений и операций над ними;
основные типы данных;
основные структуры данных: массивы, записи, строки, связные списки, стек;
представление данных в памяти;
альтернативные представления структур данных с точки зрения производительности;
основы ввода/вывода;
операторы, функции и передача параметров;
статическое, автоматическое и динамическое выделение памяти;
управление памятью во время исполнения программы;
методы реализации стеков, очередей;
методы реализации графов и деревьев;
механизм передачи параметров;
особенности реализации рекурсивных решений;
стратегии, полезные при отладке программ;
уметь:
анализировать и объяснить поведение простых программ, включающих фундаментальные конструкции;
модифицировать и расширить короткие программы, использующие стандартные условные и итеративные операторы и функции;
разработать, реализовать, протестировать и отладить программу, которая использовать все наиболее важные конструкции программирования;
применять методы структурной (функциональной) декомпозиции для разделения программы на части;
реализовать основные структуры данных на языке высокого уровня;
реализовать, протестировать и отладить рекурсивные функции и процедуры;
использовать при решении практических задач вышеназванные знания и умения и уверенно программировать на олимпиадах по информатике на языке программирования Pascal.
Основными темами этого раздела являются:
1. Язык программирования Pascal.
2. Основные конструкции программирования.
3. Переменные и типы данных.
4. Типы структур данных.
5. Особенности программирования фундаментальных алгоритмов.
4. Методы вычислений и моделирование.
Раздел «Методы вычислений и моделирование» представляет область информатики, тесно связанную с вычислительной математикой и численными методами.
В рамках этого раздела школьники должны знать/понимать:
понятия ошибки, устойчивости, машинной точности и погрешности приближенных вычислений;
источники погрешности в приближенных вычислениях;
основные алгоритмы решения задач вычислительной математики: вычисление значения и корней функции; вычисление периметра, площади и объема, вычисление точки пересечения двух отрезков и др.;
понятия модели и моделирования, основные типы моделей;
компоненты компьютерной модели и способы их описания: входные и выходные переменные, переменные состояния, функции перехода и выхода, функция продвижения времени;
основные этапы и особенности построения и использования компьютерных моделей;
уметь:
вычислять оценку погрешности приближенных вычислений;
использовать при решении задач основные методы вычислительной математики;
формализовывать объекты моделирования;
разрабатывать компьютерные модели простейших объектов;
использовать при решении практических задач компьютерные модели в виде «черного ящика»;
использовать при решении практических задач вышеназванные знания и умения.
Основными темами этого раздела являются:
1. Основы вычислительной математики.
2. Введение в моделирование.
Учебно-тематическое планирование к программе «Олимпиадная информатика»
| Тема | Количество часов |
| Положение о Всероссийской олимпиаде школьников. Методические рекомендации по проведению школьного, муниципального и регионального этапов Всероссийской олимпиады школьников по информатике. | 1 |
| Типы олимпиадных задач по информатике для 9-11 классов. | 2 |
| Основные разделы математической информатики. Функции, отношения и множества Вполне упорядоченные множества Мощность и счетность Основы логики Минимизация булевых функций Основные законы логики суждений Логика предикатов Основы вычислений Основы вычислений: Принцип включения-выключения Матрицы и действия над ними Методы доказательства Структура формальных доказательств Основы теории чисел Кольцо вычетов по модулю Основы алгебры Симметрические многочлены Понятие группы Свойства групп Теоремы о гомоморфизме и изоморфизме Основы комбинаторики Коды Грея: подмножества, сочетания, перестановки Таблицы инверсий перестановок Разбиения на подмножества. Числа Стирлинга Скобочные последовательности Теория графов Покрытия и независимость Укладка графов. Плоские (планарные) графы Двусвязность графа. Мосты, блоки, точки сочленения Связь ориентированных ациклических графов и отношений порядка. Транзитивное замыкание Двудольные графы Потоки и сети Основы теории вероятностей Аксиомы теории вероятностей Формула полной вероятности и формула Байеса. Условное математическое ожидание Основы теории игр Игры на матрицах | 20 |
| Алгоритмы Алгоритмы и их свойства Пирамида и дерево отрезков Сбалансированные деревья Хэш-таблицы и ассоциативные массивы Бор Основы анализа алгоритмов Компромисс между временем и объемом памяти в алгоритмах Использование рекуррентных отношений для анализа рекурсивных алгоритмов NP-полнота Алгоритмические стратегии Алгоритмы "разделяй и властвуй" Перебор с возвратом Эвристики Рекурсия Стратегия "разделяй и властвуй" Рекурсивный перебор с возвратами Фундаментальные вычислительные алгоритмы Алгоритмы сортировки (сортировка слиянием) Цифровая сортировка Алгоритм вычисления номера слова в лексикографически упорядоченном множестве перестановок его символов Арифметика многоразрядных целых чисел Числовые алгоритмы Расширенный алгоритм Евклида. Способы реализации алгоритма без деления Решение линейных сравнений с помощью алгоритма Евклида Эффективная проверка числа на простоту Быстрые алгоритмы разложения чисел на простые множители. Алгоритмы на строках Алгоритмы поиска подстроки в строке за Периодические и циклические строки Алгоритм поиска нескольких подстрок за линейное время Алгоритмы на графах Топологическая сортировка графа, нахождение компонент сильной связности и построение диаграммы порядка Циклы отрицательной длины – критерий наличия, поиск Задача о синхронизации времени и задача о системе неравенств Алгоритм поиска эйлерова цикла (в том числе лексикографически минимального) Нахождение транзитивного замыкания графа Алгоритмы нахождения взвешенных остовных деревьев Алгоритмы отыскания компонент двусвязности, точек сочленения, мостов с помощью поиска в глубину Алгоритм нахождения максимального паросочетания и минимального вершинного покрытия в двудольном графе Поиск максимального потока в сети Динамическое программирование Оптимизация решения задачи динамического программирования на примере задачи о рюкзаке (исключение лишних параметров) Восстановление решения в задачах динамического программирования Общая схема решения задач динамического
программирования Алгоритмы теории игр Динамическое программирование и полный перебор как методы решения игровых задач. Игры на ациклическом графе Оценка позиций. Альфа-бета отсечение Геометрические алгоритмы Нахождение расстояний между объектами на плоскости Алгоритмы определения пересечения отрезков на плоскости Алгоритмы вычисления площади многоугольника с заданными координатами вершин. Случай целочисленной решетки (формула Пика) Алгоритмы построения выпуклой оболочки (алгоритмы Грэхема и Джарвиса) Окружности на плоскости, пересечение их с другими геометрическими объектами Эффективный алгоритм нахождения пары ближайших точек на плоскости | 20 |
| Среда программирования. Языки программирования Основные конструкции программирования Типы структур данных Особенности программирования фундаментальных алгоритмов. Программные средства и окружения. Проверка соответствия программного обеспечения. Формальные методы описания синтаксиса:
форма Бэкуса-Наура Объектно-ориентированные языки Структурная декомпозиция Представление данных в памяти Статическое, автоматическое и динамическое выделение памяти Указатели и ссылки Связанные структуры Методы реализации стеков, очередей и хэш-таблиц Методы реализации графов и деревьев Стратегии отладки Инструментальные средства тестирования Основы тестирования, включая создание тестового плана и генерацию тестов Тестирование методом "черного ящика" и "белого ящика" Тестирование элементов, интеграционное, системное тестирование и проверка соответствия Основы вычислительной математики. Основные методы вычислительной математики вычисление значения и корней функции вычисление периметра, площади и объема плоских фигур Вычисление функций с шагом. Метод сеток Арифметика с плавающей точкой Ошибка, устойчивость, сходимость Типовые примеры решения задач по разделам из коллекции www.olympiads.ru . | 25 |
Диагностические задания
В качестве диагностических заданий используются представленные ниже типы олимпиадных задач и требуется провести их методический разбор.
Анализ всех задач, предлагавшихся на олимпиадах по информатике, позволил выделить следующие темы, тесно связанные с соответствующими разделами информатики и прикладной математики:
1) комбинаторика;
2) сортировка и поиск;
3) обработка последовательностей;
4) перебор вариантов и методы его сокращения;
5) алгоритмы на графах;
6) динамическое программирование;
7) элементы вычислительной геометрии;
8) задачи на технику программирования;
9) задачи на идею.
Методические указание для изучения
Алгоритмическая компьютерная среда
Набор задач по нескольким уровням сложности
Разные типы алгоритмических заданий (перестановки, переливания, взвешивания, переправы, переезды, работа с числами) (Виртуальные Лаборатории по информатике)
Алгоритмы на координатной плоскости (управление перемещением с условиями)
система автоматической проверки решений и оценивания
персонализированный вход, индивидуальный набор заданий
Личная папка решений ученика
Открытая среда дополнения и редактирования наборов задач ЕК ЦОР : Виртуальные лаборатории по информатике
Видеолекция «Освоение среды Виртуальных лабораторий с системой проверки решений»
http://metodist.lbz.ru/content/video/kuris.php
Адрес ресурса: http://school-collection.edu.ru, раздел «Информатика», 2-6 классы, выбрать «Интерактивный задачник по информатике для 2-6 классов»
Методическое пособие и 100 алгоритмических задач http://lbz.ru/books/264/5211/
Виртуальные лаборатории по информатике в начальной школе : методическое пособие Авторы: Цветкова М. С., Курис Г. Э.
Коллекции олимпиадных задач с 1989 по 2016 год и методические материалы к ним представлены на сайтах:
http://old.info.rosolymp.ru/
Представлены интернет-ресурсы олимпиадной информатики:
1. Интернет-ресурсы для теоретической подготовки к олимпиадам:
http://www.intuit.ru/courses.html (сайт Интернет-университета информационных технологий);
http://www.olympiads.ru/sng/index.shtml (сайт МИОО, МЦНМО, и оргкомитета Московской олимпиады по информатике для проведения дистанционных семинаров по подготовке к олимпиадам по информатике);
http://vzshit.net.ru/ (сайт Всесибирской заочной школы информационных технологий).
2. Интернет-ресурсы с коллекциями олимпиадных задач:
http://old.info.rosolymp.ru (сайт с самой большой в России коллекцией задач международных и всероссийских олимпиад по информатике с методическими рекомендациями по их решению);
http://www.olympiads.ru/moscow/index.shtml (сайт московских олимпиад по информатике);
http://neerc.ifmo.ru/school/russia-team/archive.html (сайт с архивом задач Всероссийских командных олимпиад школьников по программированию);
http://contest.ur.ru (сайт Уральских олимпиад по информатике);
http://www.olympiads.ru/ (сайт по олимпиадной информатике);
http://olimpic.nsu.ru/nsu/ (сайт открытой Всесибирской олимпиады по программированию им. И.В. Поттосина).
3. Интернет-ресурсы с коллекциями олимпиадных задач и возможностью их тестирования в реальном масштабе времени:
http://acm.timus.ru/ (сайт Уральского государственного университета, содержащий большой архив задач с различных соревнований по спортивному программированию);
http://acm.sgu.ru (сайт Саратовского государственного университета, содержащий архив задач с системой онлайн-проверки).
4. Сайты интернет-олимпиад для школьников:
http://info-online.rusolimp.ru/ (сайт интернет-туров заключительного этапа Всероссийской олимпиады школьников по информатике);
http://olymp.ifmo.ru/ (сайт городских интернет – олимпиад школьников Санкт-Петербурга);
http://neerc.ifmo.ru/school/io/index.html (сайт интернет-олимпиад по информатике, проводимых жюри Всероссийской командной олимпиады школьников по программированию);
http://www.olympiads.ru/online/index.shtml (сайт московских онлайн-олимпиад);
http://olimpic.nsu.ru/acmSchool/archive/2006-2007/train2006/index.shtml (сайт тренировочных олимпиад школьников, поддерживаемый Новосибирским государственным университетом).
Список литературы
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
30. Кирюхин В.М., Цветкова М.С. Образовательные программы по развитию одаренности у детей и подростков, составленные с учетом уровня подготовленности, направлений интересов, по направлению информационных технологий, 2012 .
Электронные ссылки
Сайт Методического центра олимпиадной информатики:
http://metodist.lbz.ru/lections/6/
Портал Всероссийской олимпиады школьников:
http://www.rosolymp.ru/
Сайт с архивом олимпиадных задач:
http://old.rosolymp.ru/
640
91 445 
