Программа индивидуальной подготовки к муниципальному этапу Всероссийской олимпиады школьников по предмету «Информатика и ИКТ»

Муниципальное бюджетное общеобразовательное учреждение

основная общеобразовательная школа №2 р.п. Солнечный

Солнечного муниципального района Хабаровского края

Рассмотрено: Утверждаю:

Руководитель МО директор МБОУ ООШ № 2

________(Л.Т.Климова ) р.п. Солнечный

Протокол № _1_ от 30 .08.2015г _________(О.В.Зверева)

приказ от31.08.2015 № 121.

ПРОГРАММА

индивидуальной подготовки

к муниципальному этапу Всероссийской олимпиады школьников

по предмету «Информатика и ИКТ»

для ученицы 7 «А» класса

Составила:

Молчанова Светлана Николаевна,

учитель информатики, ВКК

2015– 2016 учебный год

п. Солнечный

1. Пояснительная записка:

2. Необходимость создания индивидуальной программы по информатики ученицы 7 класса обусловлена имеющимися результатами ученика в образовательной деятельности: отличная учёба, участия в конкурсах школьного уровня, олимпиадах, высокая познавательная активность, нестандартность мышления и т.д.

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

4. Информатика в нашей школе изучается с 7 по 9 классы 1 час в неделю на базовом уровне, что явно недостаточно для подготовки к олимпиаде по информатике. Так как олимпиада по информатике является, по сути, своей олимпиадой по программированию. Решение олимпиадных задач представляет собой самостоятельный учебный раздел с обширными теоретическими и практическими частями.

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

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

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

9. Задачи программы:

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

• определить и использовать при организации образовательного процесса методы и приемы, способствующие развитию возможностей ученика;

• организовать мероприятия для повышения социального статуса ученика;

• обучить учащихся реализации как стандартных, так нестандартных алгоритмов;

• развивать у учащихся навыки решения олимпиадных задач;

• привить учащимся навыки исследовательской работы;

• расширение кругозора учащихся и совместно с родителями поддерживать ученика в реализации его интересов в школе и семье;

• развитие рефлексивных умений.

2. Данная программа отличается от существующих школьных программ более углубленным изучением материала.

4. Образовательная направленность, в рамках которой реализуется программа — социально-педагогическая. Возраст обучающихся школьников — 7 класс основной общеобразовательной школы. Срок реализации программы составляет 1 месяц.

6. Ожидаемый результат: готовность учащегося к участию в муниципальном этапе Всероссийской олимпиады школьников по информатике.

7. Используемая литература:

• Кирюхин В. М., Окулов С. М. Методика решения задач по информатике. Международные олимпиады . - М. : БИНОМ. Лаб. знаний,2007

• Кирюхин В. М., Окулов С. М. Методика решения задач по информатике. Международные олимпиады . - М. : БИНОМ. Лаб. знаний,2009

• Программирование в алгоритмах: учебное пособие / С.М.Окулов. - М. : БИНОМ. Лаб. знаний, 2004. - 341, [3] с.

• Задачник по программированию / А.Г. Юркин. – СПб.: Питер, 2002. – 192 с.

• http://olymp.ifmo.ru/rus/11-12/inf-it/
  Интернет Олимпиады для школьников 7-11 классов.

• http://www.olympiads.ru
  Олимпиадная информатика. События, задачи, тесты, решения, комментарии.

• http://olympiads.win.tue.nl/ioi/
  Архивы всех международных олимпиад школьников по информатике.

2. Карта достижений Фиц Маргариты:

3. Учебный год	Уровень участия в олимпиадах	Результат
   2013-2014	Школьный этап	Призёр
   2014-2015	Школьный этап	Участник
   2015-2016	Школьный этап	Победитель

5. График занятий:

6. №	Тема	Изучаемые вопросы
   	Целочисленная арифметика	1.Алгоритм Евклида. Нахождение НОД(а,b), НОК(a,b) рекурсивная и прямая реализация 2. Определение простоты числа. 3. Нахождение всех простых чисел из промежутка (a,b). 4. Разложение данного натурального числа на простые множители. 5. Дано разложение данного натурального числа на простые множители. Найти все делители этого числа. 6. Нахождение всех делителей натурального числа. 7. Нахождение цифрового корня натурального числа. 8. Алгоритм Евклида. Нахождение НОД(а,b), НОК(a,b) рекурсивная и прямая реализация 9. Длинная арифметика: a) Считывание длинного числа из файла. b) Запись длинного числа в файл. c) Сложение двух длинных чисел d) Умножение длинного числа на короткое в системе счисления с основанием 1000. e) Умножение длинного числа на длинное. f) Деление длинного на короткое g) Вычисление n! и степени an при маленьких и больших значениях a и n, рекурсивная и нерекурсивная реализация. h) Индийский алгоритм вычисления an i) Дано натуральное число N. Найти последнюю ненулевую цифру суммы a1+a2+…+ak, где N=p1a1*p2a2*…*pkak. j) Дано натуральное число N. Найти последнюю ненулевую цифру числа N! k) Даны натуральные числа N и M. Найти последнюю ненулевую цифру числа сочетаний C из N по M. 10) Даны натуральные числа N и M. Вычислить число сочетаний C из N по M. 1 11) Найти все натуральные числа, не превосходящие данного натурального N, десятичная запись которых есть строго убывающая или строго возрастающая числовая последовательность. (длинная арифметика).
   	Алгоритмы над целыми числами
   	Одномерные массивы	1. Объявление и использование массивов. 2. Создание массивов:.вручную, по формуле, генератором случайных чисел, чтение из файла 3. Виды сортировок. Внешняя и внутренняя сортировка 4. Сортировка выбором. 5. Сортировка "пузырьком". 6. Сортировка Шелла. 7. Сортировка слиянием. 8. Внешняя сортировка слиянием. 9. Кучи. Сортировка с помощью кучи. 10. Сортировка подсчётом. 11. Хэширующая сортировка. 12. Цифровая сортировка 13. Сквозной поиск элемента в массиве. 14. Бинарный поиск элемента в массиве. 15. Извлечение корня n-ой степени из данного натурального числа. 16. Вычисление значения многочлена по схеме Горнера.
   	Двумерные массивы	Создание двумерных массивов. Задачи на двумерные массивы: 1 Нахождение максимального и минимального элементов массива. 2 Сортировка массива по возрастанию и убыванию в строках и столбцах. 3 Поменять местами первую и последнюю строки (столбцы). 4 Отобразить массив симметрично относительно горизонтальной оси. 5 Отобразить массив симметрично относительно вертикальной оси. 6 Отобразить массив n*n симметрично относительно главной диагонали 7 Отобразить массив n*n симметрично относительно побочной диагонали 8 Повернуть массив n*n против часовой стрелки на 90 градусов. 9 На шахматной доске стоит слон и еще несколько фигур. Сколько клеток контролирует слон?
   	Рекурсия. Комбинаторные объекты	1. Понятие "комбинаторных" алгоритмов. 2. Получение комбинаторных объектов. 3. Задачи: - Сгенерировать все последовательности длины n из чисел от 1 до k. - Сгенерировать все подмножества n-элементного множества. - Сгенерировать все перестановки чисел от 1 до N. - Сгенерировать все k-элементные подмножества n-элементного множества. - Сгенерировать все представления числа N в виде суммы натуральных чисел. - Код Грея и сходные задачи. - Генерация перестановок методом транспозиции соседних элементов. - Числа Каталана. Расстановка скобок.
   	Сортировка
   	Переборные задачи
   	Геометрические задачи	1. Логические функции сравнения вещественных чисел. 2. Площадь ориентированного треугольника (многоугольника). 3. Уравнение прямой проходящей через две точки 4. Общего вида ax+by+c=0 5. Каноническое (x-x1)/(x2-x1)=(y-y1)/(y2-y1) 6. параметрическое x:=x1+t(x2-x1); y:=y1+t(y2-y1); 7. Уравнение прямой перпендикулярной данной ax+by+c=0 и проходящей через данную точку (x0,y0). 8. Длина отрезка 9. Функция принадлежности точки отрезку
   	Численные методы	1. Элементарная структура данных - запись. Линейный список. 2. Специальные структуры данных: стек, очередь, дек. 3. Деревья. Упорядоченные деревья. 4. Обходы деревьев. 5. Двоичные деревья, деревья поиска. 6. Обходы двоичных деревьев. 7. Поиск элемента в дереве поиска. 8. Добавление/удаление элемента. 9. Характеристики кучи. 1. Способы представления графа. 2. Обход в глубину. 3. Обход в ширину. 4. Кратчайшие пути. 1 Алгоритм Форда-Беллмана. 2 Алгортим Флойда. 3 Алгоритм Дейкстры 5. Поиск Эйлерова цикла 6. Поиск Гамильтонова цикла 7. Поиск компонент сильной связности 8. Поиск мостов 9. Поиск точек сочленения 10. Поиск максимального потока 11. Топологическая сортировка.
   	Статистическое моделирование
   	Динамическое программирование
   	Графы и деревья
   	Текстовые преобразования	1.Процедуры и функции обработки текста на Паскале 2. Функции eof и eoln. 3. Функции seekeof и seekeoln. 4. Посимвольная обработка текста. 5. Отличие процедур read и readln. 5. Поиск заданной подстроки в тексте. Алгоритм Бойера-Мура. 7. Использование хэш-функции для поиска произвольной подстроки в строке. 8. Рекурсивный синтаксический анализ скобочных выражений. Динамическое программирование Концепция динамического программирования Сохранение решений, подзадач, которые приходится решать повторно или несколько раз. Построение динамических таблиц промежуточных результатов.
   	Решение олимпиадных задач	1. Перебор и его значение в программировании. 2. Методы оптимизации перебора. 3. Задача о расстановке ферзей. 4. Задача об обходе конём шахматной доски. 5. Задача комивояжора.
   	Решение олимпиадных задач