|
" . " Подготовка к олимпиадам по информатике
В России проводятся олимпиады различного уровня. С 1996 года я начал готовить школьников для участия в олимпиадах по информатике и занимаюсь этим до сих пор. Среди учеников всегда находились одаренные дети, которые легко усваивали обязательный материал по курсу информатики и которым хотелось большего. За годы работы накоплен значительный опыт работы с одаренными детьми, разработана методика подготовки к олимпиадам по информатике, которая включает в себя преемственность поколений детей, круглогодичный тренировочный и соревновательный цикл. Главное научить детей относиться к своей учебной и тренировочной деятельности профессионально. Подготовка к олимпиадам по информатике желательно начинать с шестого класса, но чаще всего дети приходят к нам с восьмого. Остаются только те, кто получает удовольствие от умственного труда и любит сам процесс решения задачи.
В олимпиадной информатике, людей, которые готовят детей, называют тренерами. И роль тренеров нельзя недооценивать.
В настоящее время в Казани подготовкой детей к олимпиадам по информатике профессионально занимаются четыре человека. Это Кононов В.Б., Михайлин С.И., Хохлов Д.Г., Миннигулова Р.М. Именно их ученики завоевывают дипломы Всероссийской олимпиады по информатике.
Процесс подготовки детей к олимпиадам по информатике условно делится на три этапа. Первый, самый тяжелый, занимает около года и включает в себя знакомство с элементарными алгоритмами, освоение языка программирования "Турбо-Паскаль". Первый этап включает в себя три ступени. На первой ступени детям даются условия задачи, алгоритм решения и текст программы. На второй даются условия задачи, алгоритм решения, а все остальное они должны сделать сами. На третьей ступени даются только условия задачи. Постепенно накапливается библиотечка алгоритмов, приобретаются практические навыки решения олимпиадных задач.
На втором этапе начинается участие в олимпиадах различного уровня. Конечно, ни о каких дипломах в этот период подготовки мы не думаем. Для ученика важно понять и освоить методику решения олимпиадных задач, научиться правильно распределять свое время, грамотно создавать полную систему тестов, правильно выбрать структуру данных.
На третьем этапе ученики расширяют круг своих знаний, изучают сложные алгоритмы и решают сложные задачи. Для успешного прохождения всех трех этапов необходима солидная математическая подготовка.
Нагрузка, конечно, колоссальная. Обычно теоретический материал дается в виде лекций.
Лекции по различным разделам олимпиадной информатики и математики чередуются с семинарами. На лекции излагаются основы рассматриваемой темы, затем на семинарах уточняются конкретные практические вопросы по лекциям и решаются задачи.
На семинарах разбирается способ решения задач на изучаемую тему, в некоторых случаях на доске выписывается блок-схема одной из задач или наиболее интересный фрагмент программы. Большая часть семинарских занятий уходит на проверку написанных программ. Это особо творческая часть работы преподавателя, построенная на индивидуальной работе с учеником.
Разработка и отладка программы - творческий процесс, который требует знания многих тонкостей программирования.
Оценка каждой программы проводится следующим образом:
• проверка работоспособности программы на тестах, охватывающих все вырожденные и критические случаи;
• проверка умения ученика найти программистскую ошибку при помощи отладчика;
• от ученика требуется умение найти ошибку, при наличии ее в алгоритме;
• большое внимание уделяется оформлению текста программы: в программе должны быть необходимые комментарии для пояснения решения и краткое условие задачи, все используемые идентификаторы должны быть мнемоничны, текст программы должен быть структурирован;
За прошедшие десять лет была отработана схема смены поколений. Тренируются ученики разные по возрасту, старшие передают опыт и знания младшим. На олимпиады ездим вместе, так как информатика единственный учебный предмет, в котором нет деления на параллели.
С 2000 года начали проводиться учебно-тренировочные сборы для подготовки сборной Республики Татарстан к Всероссийской олимпиаде по информатике под руководством Кононова Василия Борисовича. В проведении сборов принимали участие Хохлов Дмитрий Григорьевич - доцент КГТУ, Михайлин Сергей Иванович - учитель информатики лицея имени Н.И.Лобачевского при КГУ и студенты КГУ и КГТУ, наши бывшие ученики. Отработана методика проведения учебно-тренировочных сборов информатике и, как результат, от 3 до 5 дипломов ежегодно на Российской олимпиаде по информатике завоеванных сборной Татарстана. В этом году мы привезли четыре диплома: I степени -Лернер Эмиль, III степени-Валиев Карим (ученики лицея имени Н.И.Лобачевского при КГУ), Бадретдинов Рамиль (ученик лицея-интерната №7), Абакумов Константин (ученик гимназии №122).
Человек развивается на пределе своих возможностей и во время олимпиад, когда надо за отведенное время выполнить большой объем работы, развивается память и интеллект детей. За несколько лет олимпиадной жизни дети глубоко изучают математику, такие ее разделы как алгебра и теорию чисел, аналитическую геометрию, теорию графов, дискретную математику, теорию алгоритмов и становятся профессиональными программистами.
Наряду с личными олимпиадами, дети участвуют и в командных олимпиадах по информатике. В этом виде олимпиад на команду из трех учащихся выделяется один компьютер и за пять часов совместной работы дети должны полностью решить как можно больше предложенных задач. В командных олимпиадах развивается умение работать в коллективе, распределять обязанности, выкладываться до конца в достижении общей цели.
Каждые две недели мы проводим пятичасовую командную тренировку. Постоянный тренинг позволяет учащимся находиться в течении года в хорошей спортивной форме и успешно выступать на олимпиадах различного уровня. В финал Всероссийской командной олимпиады в городе С.Петербурге за последние пять лет постоянно выходили две команды от Республики Татарстан, и каждый год мы привозим дипломы I-III степени.
Каждый год наши школьные команды становятся призерами регионального командного турнира по программированию среди студентов и школьников, проводимого фирмой ICL. В 2007 году команда школьников в составе Лернера Эмиля, Салихова Камиля и Бадретдинова Рамиля стали абсолютными победителями этого турнира.
Готовиться к олимпиадам по информатике можно и самостоятельно. В сети Internet в настоящее время действуют несколько проектов по подготовке к личным и командным олимпиадам по информатике. В первую очередь это проект Санкт-Петербургского института точной механики и оптики, действующий с сентября по апрель месяц каждого учебного года. В режиме реального времени я провожу с учениками личные и командные тренировки. Этот проект можно найти на сайте http://neerc.ifmo.ru/school.
Второй проект находится на сайте http://olympiads.ru и называется «Дистанционные семинары для учащихся русских школ стран СНГ и Балтии по подготовке к олимпиадам по информатике». Возможность немедленного тестирования позволяет ученикам самостоятельно тренироваться и на занятиях в лицее и дома.
Нет способа вложить в голову ученика готовые знания кроме как упорным кропотливым трудом. Но работать учителю и учиться детям стало интереснее. И роль учителя и тренера, ведущего за собой учеников, возрастает с каждым днем.
Вот примерный план подготовки к олимпиадам по информатике
Целочисленная арифметика
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. Топологическая сортировка.
|
|
|
