Муниципальное бюджетное

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

«Кольчугинская школа №2 с крымскотатарским языком обучения»

Симферопольского района Республики Крым
ул. Новоселов, д. 13 А, Симферопольский район, РК, 297551 Тел./факс (0652)315 351, е-mail: ОГРН 1159102015600 ИНН 9109009294
ДОКЛАД

Подготовка к олимпиадам по информатике

Подготовила:
Учитель Информатики I категории Яковлева Антонина Алексеевна
с. Кольчугино 2015 г.

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

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

втором

этапе
начинается участие в олимпиадах различного уровня. Конечно, ни о каких дипломах в этот период подготовки мы не думаем. Для ученика важно понять и освоить методику решения олимпиадных задач, научиться правильно распределять свое время, грамотно создавать полную систему тестов, правильно выбрать структуру данных.
На третьем этапе
ученики расширяют круг своих знаний, изучают сложные алгоритмы и решают сложные задачи. Для успешного прохождения всех трех этапов необходима солидная математическая подготовка. Нагрузка, конечно, колоссальная. Обычно теоретический материал дается в виде лекций. Лекции по различным разделам олимпиадной информатики и математики чередуются с семинарами. На лекции излагаются основы рассматриваемой темы, затем на семинарах уточняются конкретные практические вопросы по лекциям и решаются задачи. На семинарах разбирается способ решения задач на изучаемую тему, в некоторых случаях на доске выписывается блок-схема одной из задач или наиболее интересный фрагмент программы. Большая часть семинарских занятий уходит на проверку написанных программ. Это особо творческая часть работы преподавателя, построенная на индивидуальной работе с учеником. Разработка и отладка программы - творческий процесс, который требует знания многих тонкостей программирования.

Оценка каждой программы проводится следующим образом:
• проверка работоспособности программы на тестах, охватывающих все вырожденные и критические случаи; • проверка умения ученика найти программистскую ошибку при помощи отладчика; • от ученика требуется умение найти ошибку, при наличии ее в алгоритме; • большое внимание уделяется оформлению текста программы: в программе должны быть необходимые комментарии для пояснения решения и краткое условие задачи, все используемые идентификаторы должны быть мнемоничны, текст программы должен быть структурирован; Человек развивается на пределе своих возможностей и во время олимпиад, когда надо за отведенное время выполнить большой объем работы, развивается память и интеллект детей. За несколько лет олимпиадной жизни дети глубоко изучают математику, такие ее разделы как алгебра и теорию чисел, аналитическую геометрию, теорию графов, дискретную математику, теорию алгоритмов и становятся профессиональными программистами. Наряду с личными олимпиадами, рекомендуется участие детей и в командных олимпиадах по информатике. В этом виде олимпиад на команду из трех учащихся выделяется один компьютер и за пять часов совместной работы дети должны полностью решить как можно больше предложенных задач. В командных олимпиадах развивается умение работать в коллективе, распределять обязанности, выкладываться до конца в достижении общей цели.
Готовиться к олимпиадам по информатике можно и

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

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

Вот примерный план подготовки к олимпиадам по информатике

Целочисленная арифметика
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. l) Даны натуральные числа N и M. Вычислить число сочетаний C из N по M. m) Найти все натуральные числа, не превосходящие данного натурального 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. Функции eof и eoln. 3. Функции seekeof и seekeoln. 4. Посимвольная обработка текста. 5. Отличие процедур read и readln. 5. Поиск заданной подстроки в тексте. Алгоритм Бойера-Мура. 7. Использование хэш-функции для поиска произвольной подстроки в строке. 8. Рекурсивный синтаксический анализ скобочных выражений.
Динамическое программирование

Концепция динамического программирования Сохранение решений, подзадач, которые приходится решать повторно или несколько раз. Построение динамических таблиц промежуточных результатов. Структуры данных 1. Элементарная структура данных - запись. Линейный список. 2. Специальные структуры данных: стек, очередь, дек. 3. Деревья. Упорядоченные деревья. 4. Обходы деревьев. 5. Двоичные деревья, деревья поиска. 6. Обходы двоичных деревьев. 7. Поиск элемента в дереве поиска. 8. Добавление/удаление элемента. 9. Характеристики кучи.
Геометрия
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. Функция принадлежности точки отрезку 10. Взаимное расположение двух отрезков (все случаи). 11. Нахождение точки пересечения отрезка и прямой или выяснения того факта, что они не пересекаются. 12. Нахождение уравнения биссектрис двух пересекающихся прямых. 13. Нахождение уравнения касательной к окружности (x-x0)2+(y-y0)2=r2 , проходящей через данную точку (x0,y0). 14. Является ли точка (x0,y0) внутренней для данного произвольного многоугольника. 15. Формула деления отрезка в данном отношении. 16. Расстояние от точки до прямой. 17. Расстояние между двумя параллельными прямыми. 18. Выяснить, какие стороны выпуклого многоугольника видны из данной точки. 19. Сортировка вершин выпуклого многоугольника (вершины заданы в произвольном порядке) по синусам углов. 20. Нахождение уравнения прямой проходящей через точку (x0,y0) и делящей данный выпуклый многоугольник на две равновеликие части. 21. Дано множество точек. Найти его выпуклую оболочку.
22. Дано множество точек. Соединить их простой замкнутой ломаной наименьшего периметра. 23. Найти медиану данного множества точек.
Перебор с возвратом
метод ветвей и границ, backtracking 1. Перебор и его значение в программировании. 2. Методы оптимизации перебора. 3. Задача о расстановке ферзей. 4. Задача об обходе конём шахматной доски. 5. Задача комивояжора.
Алгоритмы на графах
1. Способы представления графа. 2. Обход в глубину. 3. Обход в ширину. 4. Кратчайшие пути. 1 Алгоритм Форда-Беллмана. 2 Алгортим Флойда. 3 Алгоритм Дейкстры 5. Поиск Эйлерова цикла 6. Поиск Гамильтонова цикла 7. Поиск компонент сильной связности 8. Поиск мостов 9. Поиск точек сочленения 10. Поиск максимального потока 11. Топологическая сортировка.