Элективный курс «Олимпиадная информатика. Олимпиады по информатике: методика подготовки Интернет-ресурсы с коллекциями олимпиадных задач

Статья учителя ОИВТ Лицея №8 Паньгиной Н.Н. из журнала «Компьютерные инструменты в образовании», N1, 2000

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

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

Шесть лет на базе школы-лицея №8 г.Сосновый Бор ведется подготовка школьников к олимпиадам различного уровня. В течение пяти лет учащиеся лицея являются победителями областных олимпиад по программированию, участниками и призерами Всероссийских олимпиад.

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

Вопрос 1 . Так можно ли подготовить школьников к олимпиадам?

Можно, но только не в рамках базовой программы.

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

Виктор Баргачев, 2-кратный абсолютный чемпион мира по информатике среди школьников, является призером Международной олимпиады по математике (серебряная медаль);

Николай Дуров, 4-кратный призер Международных олимпиад по информатике (3 серебряных и одна золотая медаль), является обладателем двух золотых медалей Международных олимпиад по математике;

Владимир Мартьянов из Нижнего Новгорода (2-кратный абсолютный чемпион мира по информатике) являлся победителем зональных Российских олимпиад по математике и физике.

По Ленинградской области можно привести для примера Стратонникова Алексея, Потапова Алексея, Ананьева Артема, Паньгина Андрея.

Вопрос 2 . С какого же возраста необходимо начинать готовить школьников?

Чем раньше, тем лучше, но в разумных пределах.

Для уровня

областных олимпиад достаточно начинать с 7 – 8 класса;

Российских олимпиад желательно начинать с 5 – 6 класса.

Пример: чемпион г.Москвы по программированию среди школьников 1998 года Петр Митричев – ученик 7 класса, он же явился самым молодым участником 9 Всероссийской олимпиады школьников по информатике и участником тренировочных сборов по подготовке команды России к Международной олимпиаде.

Вопрос 3 . В какой форме проводить занятия по подготовке к олимпиадам?

В виде факультативов или спецкурсов.

Для хорошей подготовки ученика, говоря известной фразой, важно, в первую очередь, ”не только наполнить чашу знаний, но и зажечь факел”. Иными словами – привить интерес!

По опыту нашего лицея этому способствует следующее:

Большую роль играют межпредметные связи.

В лицее ведется уже пять лет спецкурс «Математика на компьютерах» для 5–6 классов. Учащиеся знакомятся в наглядной форме с математическими понятиями (например, анимационной разверткой куба, координатной плоскостью с целочисленной сеткой), учатся творчески подходить к решению стандартных задач (например, с помощью графического представления на компьютере задач переливания и взвешивания).

Развитию интереса способствуют уроки по теме ”Моделирование движения” от простейшего движения бильярдного шара до сложной картины линий напряженности электрического поля двух зарядов. Особенно производит впечатление моделирование на компьютере «полета бумажного самолетика» и демонстрация этого полета наяву. Также интересна задача моделирования движения спутника и определение первой, второй космической скорости, времени полета ракеты “Восток” с Юрием Гагариным вокруг Земли (это событие должен знать каждый!).

Такие уроки проводятся дифференцированно по степени подготовленности учащихся.

Для 7 – 8 классов организуется в течение первых двух-трех недель летних каникул школьный лагерь «Интеллект», где ребята занимаются информатикой по специальной программе.

Например, программа «Лабиринт» включает темы:

построение лабиринта (интересный алгоритм генерации случайного лабиринта различной сложности);

передвижение по лабиринту с помощью управляющих клавиш;

поиск выхода из лабиринта, начиная с простейшего по правилу левой руки (придерживаясь одной стороны лабиринта);

поиск кратчайшего пути в лабиринте.

Эта программа дает толчок учащимся для разработки собственных игр «ходилок» и «стрелялок». Главное – осознание того, что они сами могут это создавать!

Для 10 классов организуется летняя производственная практика на различных предприятиях г.Сосновый Бор в течение одного месяца. Учащиеся приобретают навыки решения практических задач, закрепляют знания по работе с базами данных, бухгалтерскими офисными приложениями, самостоятельно создают программы по заданиям кураторов, приобретают дополнительные знания (например, при работе с компьютерными сетями, операционной системой Unix). Похвальный отзыв с предприятия – обычный результат такой работы.

Собственные программы ребята демонстрируют на традиционной школьной конференции по информатике «Мы и компьютер», в этом году была уже шестая конференция. Лучшие из программных разработок ребята ежегодно представляют на Международной конференции «Школьная информатика и проблемы устойчивого развития», проходящей в Санкт-Петербурге, где работы ребят оцениваются дипломами I и II степени.

Отдельные программы используются как учебный материал.

Для группы «компьютерных фанатов» в хорошем смысле, а не в смысле, например, компьютерных игр, ведутся специально направленные факультативы и спецкурсы по темам: изучение дополнительного языка программирования, алгоритмизация нестандартных задач, олимпиадные задачи, теория графов и т.п.

Вопрос 4 . Сколько человек должно быть на занятиях специально ориентированных факультативов?

Группы по 6 – 12 человек .

При работе на конкретный результат, (то есть подготовка к городской, областной или Российской олимпиаде), должна быть группа от 3 до 6 человек. Эти занятия уже представляют собой тренировки, и тут преподаватель больше выступает в роли тренера, а не учителя. Как проходит занятие?

Называется тема.

Перечисляются задачи на данную тему.

Выбирается одна из наиболее популярных или интересных задач.

Устно совместно с ребятами обсуждается алгоритм решения.

Ребята пишут программу, преподаватель фиксирует время, оценивает реализацию решений, помогает искать ошибки, указывает на недочеты по эффективности (количество операций, использование оперативной памяти, время решения).

Вопрос 5 . Какие темы необходимо изучать на занятиях по подготовке к олимпиадам?

Всего не предусмотреть, но можно выделить следующие группы алгоритмов:

Алгоритмы над целыми числами.

Рекурсия.

Сортировка.

Переборные задачи.

Геометрические задачи.

Численные методы.

Статистическое моделирование.

Графы и деревья.

Текстовые преобразования.

Рассмотрим более подробно темы, необходимые для изучения при подготовке к олимпиадам. Теоретические занятия должны включать в себя определения, утверждения (в некоторых случаях обязательно с доказательствами).

Алгоритмы над целыми числами

Делимость

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

Первая модификация алгоритма Евклида (с вычитанием)

Последовательно уменьшая числа (большее заменяя разностью чисел) до тех пор, пока они не станут равны, придем к наибольшему общему делителю этих чисел.

Задачи, которые необходимо разобрать при изучении данной темы:

Определить, являются ли несколько чисел взаимно простыми

Сократить дробь (числитель и знаменатель дроби вводятся)

Написать программу «Калькулятор» в простых дробях

Вторая модификация алгоритма Евклида, использующая деление с остатком

где r – остаток от деления большего числа на меньшее.

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

Задача для решения : прямоугольник с длинами сторон a и b, где a и b – натуральные числа, разрезать на квадраты максимальной площади. Определить размер квадратов и их общее количество.

Диофантовы уравнения

Используя утверждение о представлении наибольшего общего делителя двух чисел в виде линейной комбинации этих чисел, приходим к утверждению о разрешимости в целых числах уравнения вида ax + by = c (диофантово уравнение).

Задачи , которые необходимо разобрать при изучении данной темы:

Задачи на размен денег монетами определенного достоинства.

Задачи на переливание.

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

Простые числа

С простыми числами связано множество олимпиадных задач разных уровней. Классический метод для нахождения простых чисел - решето Эратосфена. С этим алгоритмом связаны решения следующих задач :

Числа-близнецы;

Совершенные числа;

Скатерть Улама;

Дружественные числа и т.п.

«Длинная» арифметика

Задачи на «длинную» арифметику возникают тогда, когда в стандартных типах данных (целые или длинные целые) не представляется возможным хранить результат, настолько он велик. В этом случае используется прием хранения длинных чисел в виде массива цифр, а чтобы выполнять арифметические действия с такими числами, необходимо написать специальные процедуры сложения, умножения, деления длинных чисел.

Типовые задачи: найти число N! (N-факториал), определить период дроби.

Рекурсия

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

Чем младше ученики, тем важнее для них принципы наглядности и простоты. Введение в рекурсию можно начинать с известной считалки про «10 негритят».

Следующий этап – рекурсивные рисунки. Начинаем с простейших рисунков, например, рисования упрощенной «матрешки».

снежинки, падающие по всему экрану;

веточки разного цвета, разной пушистости и разного размера (в длину ветки вносится случайная составляющая).

Большой интерес представляют для ребят фрактальные множества: салфетка и скатерть Серпинского, модель Мандельброта человеческого легкого, фрактал Хартера-Хейтуэя (известен нам как ломаная Дракона), кривые Гильберта, снежинка Коха. Рекурсия здесь настолько естественна, что ни у кого не возникает вопроса, можно ли без нее обойтись. И лишь теперь, когда прелесть и красота рекурсии не вызывает ни у кого сомнений, можно переходить к задачам, которые по своему определению являются рекурсивными. Это следующие задачи: факториал числа, N-я степень числа, НОД(a , b ), функция Аккермана, числа Фибоначчи, перевод чисел из 10-й системы счисления в 2-ю, нахождение максимума и минимума в массиве. Многие задачи, оказывается, можно делать с помощью рекурсии. Главное, что появляется видение рекурсии в задачах, ранее решенных не рекурсивно. С целью новизны, например, в задаче о разрезании прямоугольника на квадраты максимальной площади предлагается сделать наглядное графическое сопровождение с помощью рекурсии. И уж совсем «плохо» без рекурсии при решении таких задач, как «Ханойская башня». В данном случае осознать это и на практике освоить рекурсивный алгоритм решения данной задачи помогает демонстрационно-обучающая программа «Ханойская башня».

Сортировка

Без знаний алгоритмов сортировки никак нельзя спокойно чувствовать себя на олимпиадах различного уровня. Задачи могут формулироваться как явно с упоминанием алгоритма сортировки, так и подразумевая внутри решения использование алгоритма сортировки. Два простейших алгоритма, которые необходимо знать, - это «пузырек» и сортировка обменом (с помощью поиска последовательных минимумов). При небольших объемах данных вполне хватает этих двух методов, но при работе с данными, измеряемыми десятками и сотнями Кбайт, необходимо знание какой-нибудь из быстрых сортировок. Предпочтение можно отдать быстрой сортировке Хоара, которая реализуется рекурсивно. Необходимо также знать некоторые приемы при упорядочивании данных в больших файлах. Весь файл разбивается на некоторое количество кусков, которые можно отсортировать с помощью QSORT, а затем произвести слияние отсортированных файлов уже без программы сортировки (кстати, это очень полезная с технической точки зрения задача, требующая аккуратности и хорошей техники программирования).

Перебор вариантов

Задачи перебора составляют огромный класс олимпиадных задач. Начинается перебор с простейшего поиска минимума и максимума в одномерном массиве или поиска элемента с заданными свойствами. Далее идет перебор пар элементов, использующий вложенный цикл, затем перебор троек элементов, использующий тройной цикл (как, например, в задаче о поиске трех точек на плоскости среди заданных N точек, которые образуют треугольник с максимальной площадью). А если перебирать сочетания из 4, 5, 6 и т.д. элементов? Сколько же необходимо циклов? Оказывается, существуют алгоритмы, существенно сокращающие перебор.

Довольно длинный по времени выполнения, но один из самых универсальных алгоритмов перебора, - перебор с возвратом или «бектрекинг». Программируется рекурсивно. Лучше всего объясняется на следующих задачах:

Ходом коня обойти шахматную доску N*M;

Расставить 8 ферзей на шахматной доске размера 8*8 так, чтобы они не угрожали друг другу;

Найти выход из лабиринта и т.п.

Необходимо также объяснять учащимся, что в случае слишком долгого времени выполнения программы, необходимо ограничивать «бектрекинг». Например, в задаче про шахматы при размере доски 8*8 выполняется программа уже довольно долго. Можно и даже нужно применять симметрию, зеркальное отображение, выполняя задание для половины или четверти шахматной доски.

Классической задачей на «бектрекинг» является задача о «рюкзаке», затем можно рассматривать производные от этой задачи:

Разбить N чисел на два подмножества, наиболее близких по сумме;

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

С перебором связаны и комбинаторные задачи. Следует освоить алгоритмы создания лексикографического упорядочения.

Задачи на геометрию

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

Уметь привести уравнение прямой, проходящей через две точки к виду

Ax + By + C = 0;

Уметь определить, принадлежит ли точка прямой или отрезку;

Уметь определить, пересекаются ли две прямые, и, если пересекаются, то определить их точку пересечения (для этого вычислять определитель 2-го порядка);

Уметь написать уравнение перпендикулярной прямой или определить, перпендикулярна ли одна прямая другой (использование свойства о равенстве нулю скалярного произведения перпендикулярных векторов);

Уметь вычислять расстояние от точки до прямой.

В дополнение к этому для решения задач областного и Всероссийского уровня необходимы знания начального курса аналитической геометрии: скалярное и векторное произведение векторов, выражение их через координаты. Скалярное произведение используется для нахождения угла (или косинуса угла) при построении, например, выпуклой оболочки заданных точек. Векторное произведение двух векторов используется, во-первых, для вычисления площадей многоугольников, а во-вторых, для определения направления в соответствующих задачах. Эти знания необходимы также для того, чтобы решать такую классическую олимпиадную задачу, как содержится ли точка внутри произвольного многоугольника.

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

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

нулевое значение - параллельность векторов;

знак означает, что один вектор расположен «слева» или «справа» относительно другого;

результирующий вектор определяет нормаль к плоскости заданных векторов.

Численные методы

Метод дихотомии

Для поиска данных в упорядоченном множестве используется метод дихотомии (или деления пополам) с последующей проверкой искомых свойств. Этот метод, который более привычен для нахождения приближенных значений корней нелинейных уравнений, можно использовать для поиска среди «огромного» количества данных. В этом случае более употребим термин «бинарный поиск». Типовая задача – найти заданное слово в словаре.

В общем случае, данный метод является оптимальным.

Решение систем линейных уравнений: метод Крамера, метод Гаусса.

Классические методы. Обычно в задачах число уравнений не более трех. Но знание общего случая, вероятно, пригодится.

Задача с областной олимпиады 94 года.

Вводится в виде строчки уравнение химической реакции: необходимо уравнять, т.е. расставить коэффициенты.

Статистическое моделирование (метод Монте-Карло).

Очень полезным является знание данного метода:

для моделирования игровых вероятностных ситуаций (бросание монеты, кубика, блуждания). Именно «игровая» или связанная с чем-то знакомым (известным, «бытовым») формулировка задачи помогает в понимании метода, понятия вероятности. Можно предложить учащимся интересные задачи:

чего больше, сократимых или несократимых дробей? (Математическая формулировка: оценить вероятность того, что наудачу взятая дробь несократима);

лучшее пари для простаков («Квант» №5,1987);

комбинаторные задачи.

Для определения площадей фигур, когда затруднены аналитические решения.

Так, в задаче (областная олимпиада 99 года) по нахождению площади пересечения трех окружностей метод Монте-Карло можно использовать в качестве альтернативного прямому аналитическому методу, так как очень трудно вывести решение, используя тригонометрические соотношения. Наилучший путь - это «использовать геометрию» для анализа частных случаев (когда нет пересечения, когда пересечение в одной точке, одна окружность внутри другой), а метод Монте-Карло для общего случая.

Динамическое программирование.

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

Данный принцип легче всего воспринимается на конкретных задачах. Но объяснение его можно начать с занимательной истории про золотую лестницу Фараона (изложенную в журнале «Квант» №10, 1991 г.), а затем перейти к следующим задачам:

Классическая задача о нахождении такого кратчайшего пути в числовой матрице A размерности NхN из A(1,1) в A(n,n), в котором сумма цифр в клетках была минимальной или максимальной.

Нахождение общей подстроки максимальной длины (задача, возникшая из современной реальной задачи молекулярной биологии об общей генетической информации в молекулах ДНК).

Графы и деревья.

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

Разобрать основные алгоритмы на графах:

поиск в глубину (иными словами “бектрекинг” или перебор с возвратом);

поиск в ширину (или метод заливки);

Алгоритм Дейкстра для поиска кратчайших путей в графе из заданной вершины во все остальные;

алгоритм Флойда для поиска кратчайших путей в графе между всеми парами вершин.

Текстовые преобразования

Задачи, в которых необходимо проводить разбор строки, порой дополнительно предполагают работу с файлами, графическими построениями (подобие команд текстового или графического редактора) или использование каких-либо приемов программирования (например, представление “стека” в виде символьной строки в задаче о правильном скобочном выражении для нескольких типов скобок).

Представлен широкий, но далеко не полный набор тем, охватываемых олимпиадными задачами. Во многом это зависит от пристрастий организаторов олимпиад различных уровней (теоретические туры, задачи с использованием игровых стратегий, прикладного «офисного» характера).

Вопрос 6 . Что можно посоветовать при решении задач на олимпиаде?

Предполагая, что теория алгоритмов «проштудирована» и основы программирования освоены, участнику соревнования можно посоветовать следующее:

Обеспечьте «про запас» определенный «гарантированный» (по вашему мнению) набор баллов на простых задачах. Это не означает, что сложные задачи оставлять на последний момент. При обдумывании их решения может быть найден «хороший» алгоритм, и успехом послужит соответственно большая доля баллов.

Если задача трудна для вас или дефицит времени для решения, запрограммируйте простые частные случаи (авось некоторые тесты пройдут), либо используйте какой-нибудь неоптимальный, например, переборный алгоритм.

Если для задачи указано ограничение по времени решения, а ваш переборный алгоритм не укладывается в это время, то вставьте в алгоритм таймер, который при приближении к критическому времени заканчивает задачу и выводит наилучший найденный переборный вариант (возможно, он будет правильным).

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

Строго соблюдайте указанные в условии задачи форматы ввода-вывода: «автотестировщик» может неправильно воспринять лишний пробел, или исходные тесты содержат запятую там, где вы предусматривали во вводе своей задачи пробел (особенности операторов ввода Pascal и Basic).

В основном, любая программа имеет структуру:

Ввод данных

Расчетный блок

Вывод результата

Оформите и убедитесь, что ввод-вывод правильный (с возможным анализом ошибочных данных) прежде, чем программировать расчетный блок.

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

Проверьте задачу для заданных максимальных ограничений (например, если дано n  1000, проверьте для n = 1000). Следите за типом объявляемых переменных (предпочтительно для описания целочисленных переменных использовать тип «длинное целое»).

Разумно используйте апелляцию. Возможна двусмысленность понимания задачи. В жюри тоже люди, и вы можете отстоять свою позицию, убедить их добавить вам желанные баллы.

В крайнем случае, если вы «cool hacker» (крутой специалист по системной части), запустите программу «соседа», как свою (небось, никто не заметит).

Разрешается иметь свои шпаргалки (не в электронном виде) или воспользоваться «свободным» временем для изучения справочной литературы.

Некоторые из перечисленных советов являются «вредными», соответствуют принципам «авось, небось и как-нибудь». Просьба воспринимать их критически, но они жизненны.

Вопрос 7 . Какой литературой необходимо пользоваться при подготовке к олимпиадам?

Данной статьей, а также следующими источниками.

А.Шень. Программирование: теоремы и задачи, М. МЦНМО,1995.

А.Л.Брудно, Л.И.Каплан. Московские олимпиады по программированию, М: наука, 1990.

В.А.Дагене, Г.К.Григас. 100 задач по программированию, М: Просвещение, 1993.

В.М.Бондарев, В.И.Рублинецкий, Е.Г.Качко. Основы программирования, Харьков: Фолио, 1997.

В.М.Кирюхин, А.В.Лапунов, С.М.Окулов. Задачи по информатике. Международные олимпиады. М: ABF, 1996.

Н.М.Бадин, С.Г.Волченков, Н.Л.Дашниц. Ярославские олимпиады по информатике. Ярославль, 1995.

С.М.Окулов. Конспекты занятий по информатике (алгоритмы на графах). Киров,1996.

А.В.Алексеев. Олимпиады школьников по информатике. Красноярское книжное иэдательство,1995.

А.С.Сипин, А.И.Дунаев. Областные олимпиады по информатике. Вологда, 1994.

В.Пинаев. Городская олимпиада по программированию. Рыбинск, 1998.

С.А.Абрамов. Математические построения и программирование. 1987.

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

В лицее города Фрязино эта проблема решается комплексно :

· В профильных математических 8-х классах выделяется дополнительно к программе один час в неделю на предмет информатика

· В профильных классах старшей школы Программирование выделено как отдельный предмет

· С 2007 года у нас действует учреждение дополнительного образования Школа «Юный программист», которая не заменяет, а дополняет школьный курс информатики

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

В последние 6 лет ученики Лицея неоднократно становились победителями и призерами олимпиад самого различного уровня: Заключительного этапа Всероссийской олимпиады, Московской областной олимпиады, Открытой олимпиады «Информационные технологии»», Олимпиады школьников «Ломоносов», Открытой олимпиады школьников по информатике и программированию, Муниципальных олимпиад, Московской олимпиады по программированию, Всероссийского конкурса КИТ и других.

Как готовить к олимпиадам по информатике в таких условиях?

· Найти способных учеников и увлечь их программированием

· Удержать от «соблазнов» on-line жизни

· Стать им другом и сформировать из них команду

· Тесно взаимодействовать с родителями, администрацией, классными руководителями и учителями - предметниками

· Быть готовым к тому, что на каком-то этапе кто-то из них вас перерастет

Календарно-тематическое планирование курса по информатике «Подготовка к олимпиаде» 8 класс

Всего - 68 часа (по 2 ч . в неделю)

	Раздел/тема	Кол-во часов	Основные виды учебной деятельности	Дата проведения
	Раздел/тема	Кол-во часов	Основные виды учебной деятельности	по плану
Республиканская олимпиада школьников по информатике. Нормативное обеспечение Республиканской олимпиады по информатике - 10 ч
	Положение о Республиканской, Всероссийской, Международной олимпиаде школьников.
			восприятие, осмысление и запоминание информации
			восприятие, осмысление и запоминание информации
	План самостоятельной работы по программе олимпиадной информатики.		восприятие, осмысление и запоминание информации
	Заполнение учащимся индивидуальной карты подготовки.		восприятие, осмысление и запоминание информации
- 8 ч
	Структура олимпиадной задачи. Типы олимпиадных задач по информатике. Основные разделы математической информатики. Типовые примеры решения задач по разделам из коллекции		Конспектирование, полученной информации, ответы на вопросы, после объяснения материала
	Этапы решения олимпиадной задачи: формализация условия задачи, выбор метода решения задачи. План разбора олимпиадной задачи по информатике.		Решать логические задачи различными способами; осуществлять системный анализ объекта, выделять среди его свойств существенные свойства с точки зрения целей моделирования; выявлять различие в унарных, позиционных и непозиционных системах счисления;
	Автоматизированная среда проверки решений олимпиадных задач.		выявлять общее и отличия в разных задачах
	Коллекция олимпиадных задач в Интернете. Полезные ресурсы для подготовки к олимпиадам. Тренировочные туры в Интернете.		позиционных системах счисления;
Технологические ресурсы олимпиадной информатики. Среда программирования - 27 ч
	Основные инструменты среды программирования.		строить цепочки команд, дающих нужный результат при конкретных исходных данных для исполнителя, преобразующего строки символов; анализировать логическую структуру высказываний.
	Сравнение сред программирования для разных языков программирования.		преобразовывать запись алгоритма с одной формы в другую; восприятие, осмысление и запоминание информации,участие в дискуссии
	Среда программирования в свободном доступе. Инсталляция, шаги для освоения.		выполнять операции сложения и умножения над небольшими двоичными числами; восприятие, осмысление и запоминание информации
	Проведение тренировочного тура в реальном времени.		Участие в разные очных, дистанционных олимпиад
	Разбор задач тура. Диагностика дефицитов в теоретической, практической и технической подготовке.
	Кодирование числовой информации. Кодирование текстовой информации		строить таблицы истинности для логических выражений; восприятие, осмысление и запоминание информации
	Кодирование графической информации. Кодирование звуковой информации.		Двоичный код. Кодирование. Декодирование. Недостаток двоичного кодирования.Система счисления.Позиционные. Непозиционные
	Равномерное и неравномерное кодирование.		определять по блок-схеме, для решения какой задачи предназначен данный алгоритм; слушание,конспектирование, ответы на вопросы после объяснение материала
	Рещение задач на количество информации. Скорость передачи информации.		анализировать изменение значений величин при пошаговом выполнении алгоритма; конспектирование.
	Абсолютная и относительная адресация в Excel. Формулы в Excel. Решение задач с графами.		определять по выбранному методу решения задачи, какие алгоритмические конструкции могут войти в алгоритм; восприятие, осмысление и запись в тетради
	Языки программирования. Переменные и типы данных		восприятие, осмысление и запоминание информации, конспектирование полученной информации
	Механизмы абстракции. Особенности программирования фундаментальных алгоритмов		восприятие, осмысление и запоминание информации, конспектирование полученной информации
	Основы синтаксиса и семантики языков высокого уровня. Основные конструкции программирования		рассмотреть этапы развития языков программирования. познакомить с интегрированной средой программирования
- 6 ч
	Нахождение НОД и НОК. Алгоритмы Евклида.		в беседе по данной теме
	Пифагоровы тройки. Простые числа. Числа близнецы.		слушание, конспектирование, участие в беседе по данной теме
	Совершенные числа. Числа палиндромы, Мерсенна, Армстронга, Фибоначчи. Диофантовы уравнения. «Длинная» арифметика		восприятие, осмысление и запоминание информации
- 17 ч
	Стратегии реализации алгоритмов Реализация рекурсии		практическая работа за компьютером, работа с дополнительными источниками
	Введение в моделирование. Компоненты компьютерной модели и способы их описания: входные и выходные переменные, переменные состояния, функции перехода и выхода, функция продвижения времени		оценивать адекватность модели моделируемому объекту и целям моделирования; определять вид информационной модели в зависимости от стоящей задачи; подготовка сообщений по выбранным темам, анализ выполненных работ
	Компьютерные сетевые технологии. Основные этапы и особенности построения компьютерных моделей.		выявлять общие черты и отличия способов взаимодействия на основе компьютерных сетей; анализировать доменные имена компьютеров и адреса документов в Интернете; работа с Интернет - ресурсами, конспектирование, анализ найденной информации
	Основные этапы использования компьютерных моделей при решении практических задач		практическая работа на компьютере
	Организация олимпиадной подготовки: режим дня, занятия спортом, . Методы самодиагностики уровня подготовленности.		восприятие, осмысление и запоминание информации
	Основные критерии олимпиадной подготовки: теоретические, практические, технологические, технические, психологические.		восприятие, осмысление и запоминание информации
	Мониторинг школьником выполнения индивидуального плана для самостоятельной олимпиадной подготовки. Настройка индивидуального плана по итогам мониторинга.		восприятие, осмысление и запоминание информации
	Рефлексия
ИТОГО		68 час.

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
ВВЕДЕНИЕ.

Программа курса «Подготовка к олимпиаде по
информатике для 8 классов» была разработана в связи с необходимостью
подготовки способных учащихся к олимпиадам по информатике. Чтобы
решать олимпиадные задачи, необходимо не только быстро и логически
мыслить, но и владеть специальными методами программирования, которые
позволяют создавать оптимальные и эффективные программы. Количество
часов, отводимое в школьном курсе информатики на раздел
"Алгоритмизация и программирование", недостаточно для того, чтобы хотя
бы ознакомить учащихся с этими методами. В связи с этим появилась идея
привлечения способных учащихся к изучению данного курса.
Олимпиады являются одним из эффективных и проверенных на
практике педагогических механизмов выявления и развития творческих
способностей школьников, важной составляющей профильного обучения,
обеспечивающей высокую мотивацию к образовательной и научной
деятельности. Немаловажным является и то обстоятельство, что олимпиады
стимулируют педагогов-наставников к повышению профессионального
уровня и качества работы. Методика подготовки к интеллектуальным
соревнованиям, содержание заданий, их типы, критерии оценки привлекают
пристальное внимание и интерес не только участников олимпиады, но и
ученых, педагогов, методистов, родителей учащихся. Предметные
олимпиады способствуют также формированию новых требований к
содержанию и качеству образования, формам и методам учебной работы,

Сетевая интернет-поддержка существенно обогатила формы работы с одаренными школьниками за счет активного использования в образовательном процессе интернет-видеотехнологий. Использование интернет-видеосистем очно-удаленного присутствия позволило модель обучения «ученик - компьютер - учитель» вывести на новый уровень и обеспечить непосредственное общение ученика и учителя в процессе обучения.

ЦЕЛИ И ЗАДАЧИ

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

Структура курса включает в себя следующие разделы:

Республиканская олимпиада школьников по информатике. Нормативное обеспечение Республиканской олимпиады по информатике

Интеллектуальные ресурсы олимпиадной информатики. Коллекции олимпиадных задач

Технологические ресурсы олимпиадной информатики. Среда программирования

Вычислительные задачи, использующие свойства натуральных чисел

Методы вычислений и моделирование. Индивидуальная траектория олимпиадной подготовки

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

Методические указание для изучения курса

Изучение модуля строится на основе методических разработок толимпиады школьников. Методические материалы содержат рекомендации по порядку
проведения олимпиад по информатике, требования к структуре и содержанию олимпиадных задач, рекомендуемые источники информации для подготовки задач, а также рекомендации по оцениванию решений Коллекции олимпиадных задач с 1989 по 2011 год и методические материалы к ним представлены на сайтах:

Виртуальные лаборатории по информатике в начальной школе: методическое пособие Авторы: Цветкова М. С., Курис Г. Э.

Коллекции олимпиадных задач с 1989 по 2016 год и методические материалы к ним представлены на сайтах:

http://old.info.rosolymp.ru/

Представлены интернет-ресурсы олимпиадной информатики:

1. Интернет-ресурсы для теоретической подготовки к олимпиадам:

2. Интернет-ресурсы с коллекциями олимпиадных задач:

http://olimpic.nsu.ru/nsu/ (сайт открытой Всесибирской олимпиады по программированию им. И.В. Поттосина).

3. Интернет-ресурсы с коллекциями олимпиадных задач и возможностью их тестирования в реальном масштабе времени:

4. Сайты интернет-олимпиад для школьников:

Список литературы

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/

1. Интернет-ресурсы для теоретической подготовки к олимпиадам:

http://www.intuit.ru/courses.html (сайт Интернет-университета информационных технологий);

http://ips.ifmo.ru/ (сайт Российской Интернет-школы информатики и программирования);

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/archive/2005/index.shtml (сайт открытой Всесибирской олимпиады по программированию им. И.В. Поттосина).

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 (сайт тренировочных олимпиад школьников, поддерживаемый Новосибирским государственным университетом).

5. Олимпиадные сайты зарубежных стран:

http://acm.uva.es (сайт университета Valladolid с крупнейшей в интернете общедоступной коллекцией задач с возможностью проверки в реальном времени и проведения соревнований по программированию );

http://train.usaco.org/usacogate (сайт подготовки к американским олимпиадам по информатике);

http://www.acsl.org (Сайт организации American Computer Science League, которая организует соревнования по программированию среди школьников);

http://www.topcoder.com/tc (сайт интернет-соревнований компании TopCoder);

http://www.inf.bme.hu/contests/tasks (сайт с большим количеством задач, предлагавшихся на соревнованиях по информатике во многих странах); http://www.i-journals.org/olympiads_in_informatics/ (сайт международного журнала «Олимпиады по информатике» (Olympiadsininformatics);

http://www.ut.ee/boi (сайт Балтийских олимпиад по информатике);

http://ipsc.ksp.sk (сайт ежегодных интернет-соревнований по командному программированию);

http://www.hsin.hr/coci/ (англоязычный сайт проведения Интернет-олимпиад в Хорватии);

http://uoi.kiev.ua (сайт украинских олимпиад школьников по информатике);

http://byoi.narod.ru (сайт белорусских олимпиад школьников по информатике).

Для формирования траектории развития талантливого школьника рекомендуется опираться на критерии оценивания его продвижения в олимпиадной подготовке. Критерии оценивания сформированы на основе оценки современных тенденций и международного опыта олимпиадного движения с учетом развития тематики олимпиадных задач, технологии структурного программирования и систем программирования, ориентированных на требования к ним, зафиксированные в рекомендациях для Всероссийской олимпиады школьников по информатике и правилах IOI (международной олимпиады по информатике). Анализ успешности обладателей первых десяти золотых медалей на IOI за последние пять лет также позволил сформулировать ряд критериев - особенно в части технологической умелости школьников.

Подготовка учащихся к олимпиаде по информатике

Не секрет, что уровень подготовленности по информатике городских и сельских школьников резко отличается. К середине 90-х годов сложилась такая практика, что призерами олимпиад областного уровня становились в основном ученики из городов области, прежде всего, из самого Белгорода. Причина этого – недостаточное оснащение компьютерной техникой , острая нехватка педагогических кадров на селе и недостаточная их квалификация. Учитель информатики сельской школы в 90% случаев совместитель (обычно учитель математики или физики), что приводит к перегрузке, и как следствие к невозможности уделять достаточно времени методике преподавания информатики и индивидуальной работе с учащимися. С другой стороны, сельские ученики часто не имеют возможности посещать кружки, занятия, курсы компьютерной грамотности вне школы.

Подготовка к олимпиаде требует отбора детей с определённым уровнем мотивации. Каждый учитель начинает учебный год с поиска таких детей – поиска одарённых детей для участия в предметных олимпиадах.

Мы с вами должны понимать, что олимпиада это не только престиж школы, а это ещё и рост уверенности в своих силах и знаниях учеников. Развитие творческого потенциала личности учащегося является одним из ведущих направлений деятельности учителей старшей школы.

Как правило, при подготовке к олимпиаде у каждого учителя возникают следующие вопросы:

1. Как, среди уменьшающегося количества часов, выкроить время на подготовку?

2. Как можно мотивировать учеников?

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

На протяжении двух последних лет в нашей области олимпиада по информатике проходила в альтернативном виде. Некоторые задания по программированию были заменены практическими заданиями на решение задач (логических, систем счисления, количество информации), вычисления в электронных таблицах, работу в текстовом редакторе. Олимпиада такого плана легче, чем олимпиада по программированию. Но по практическим и теоретическим заданиям она выходит за школьный курс программы и требует особого уровня подготовки и времени.

Чтобы подготовить учеников к олимпиаде приходиться использовать различные формы работы. Различные формы деятельность учащихся позволяют сократить время на подготовку к олимпиаде и изучение материала.

По подготовке к олимпиаде у меня сложилась определённая методика. Для успешного выступления в олимпиадах требуется целенаправленная подготовка, которая должна обеспечить отличное владение практическими и теоретическими знаниями.

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

Задачи, которые я ставлю перед собой при работе с одарёнными детьми:

1. учесть степень и меру самораскрытия одарённых учащихся;

2. удовлетворить их потребности в информатизации.

Основные направления деятельности с одарёнными детьми:

3. самообразование.

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

Способный ученик должен развиваться не только на уроке. Одних уроков недостаточно, даже если мы будем «напрягать» ученика заданиями повышенной сложности. Кроме уроков нужна система внеурочной работы по предмету.

Эффективной формой дифференцированного обучения и воспитания являются факультатив. Его основное предназначение – углубление и расширение знаний, развитие способностей и интересов учащихся.

Факультатив должен работать по определенной программе, которая не дублирует учебную.

Факультативное занятие может проходить следующим образом:

1. называется тема;

2. перечисляются задания на данную тему;

3. выбирается одна из наиболее популярных или интересных задач;

4. устно совместно с ребятами обсуждается алгоритм решения;

5. ребята в тетради оформляют решение (пишут программу), учитель фиксирует время, оценивает реализацию решений, помогает искать ошибки, указывает на недочёты по эффективности (количество операций, время решения);

6. раздаётся материал для изучения новой темы следующего занятия.

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

Для хорошей подготовки ученика важно, в первую очередь, «не только наполнить чашу знаний, но и зажечь факел».

Так как ребята приходят с разным уровнем подготовки приходиться использовать индивидуальные и групповые формы работы. Индивидуальные формы работы зачастую сопряжены с самообразованием. Здесь учитель выступает в роли консультанта.

Групповые формы работы используются для ребят с определённым багажом знаний.

Есть еще один метод работы с учащимися – работать индивидуально. Один на один. А «работать индивидуально» исходит уже не от учителя, а от ученика. Такие встречи носят характер консультаций, хотя иногда это совместный поиск решения какой-либо задачи.

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

Мотивацию у учеников можно вызвать различными творческими заданиями и проектами.

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

Олимпиады однозначно нужны детям как путь к самовыражению, к развитию. С одаренными детьми следует работать в течение всего года, нельзя понимать олимпиады как определенное мероприятие на 3 - 4 часа.

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

Как же готовиться к все время усложняющимся олимпиадам?

Я считаю наиболее правильной систему моих преподавателей.

На факультативном занятии (научить решать олимпиадные задачи можно только на факультативе, где занимается не более 6-7 человек, иначе - бардак) преподаватель кратко объясняет теорию. Затем предлагает задачи по только что объясненной теме не объясняя (но отлично зная!) решения ни одной из них. Ученики предлагают свои идеи по поводу решения, т. е. занятие проходит в форме семинара под руководством преподавателя. В случае затруднения преподаватель может помочь ученикам, предложив некоторую идею. Затем, в случае если есть возможность написать программу за достаточно короткое время, программа реализуется на компьютере. Однако здесь есть свои трудности: в случае разного уровня подготовки учащихся, время, затрачиваемое на написание программы, сильно различается, что приводит к тому, что уже решившие задачу сидят и скучают (при этом постепенно теряют интерес к занятиям), а те, кто еще пишет нервничают, смотрят на тех кто скучает, завидуют и также теряют интерес к занятиям. Здесь надо найти золотую середину. Время от времени следует организовывать мини или полномасштабные олимпиады по информатике, с задачами уровня не ниже областной городской, но со сниженными требованиями к участникам (разрешается ходить по кабинеты, иногда общаться, пить чай и т. п.). Важной частью подготовки является разбор нерешенных задач с олимпиады (такие чаще всего остаются, особенно после олимпиад достаточно высокого уровня). Здесь учитель часто находится в равных условиях с учеником, так как и он сам не знает решения такой задачи. Домашнее задание следует давать в разумных количествах (лучше больше) и по теме или, при подготовке к олимпиаде (обычно за 2 недели) задачи с прошлых олимпиад. Те кто не сильно хочет заниматься информатикой задание все равно не сделают, а те, кто хочет - сделают все. Для любимого предмета каждый человек может найти время.

Чтобы научиться решать задачи необходимо выполнить 7 пунктов:

1) Знать математику. Очень часто встречаются математические задачи.

2) Уметь общаться. В ходе обсуждения рождается множество новых идей.

3) Иметь способности. Я так и не научился играть на пианино:)

4) Осознавать, что тебе это нужно. На самом деле олимпиадные задачи - всего лишь "массаж для мозгов", но если бы их не было, вы бы умели писать программы так хорошо?

5) Сильно хотеть победить. Но не до умопомрачения.

6) Научить других решать задачи. Не обязательно. Но когда объясняешь другим, начинаешь лучше понимать сам.

7) (Самое главное) Быть хорошим человеком. Если вы плохой человек, то со всем вашим умение писать программы вы никому не нужны.

Чтобы научиться хорошо решать задачи необходимо кроме этого выполнить еще один пункт:

ПОСТОЯННЫЕ ТРЕНИРОВКИ . Каждая решенная задача должна доставлять вам удовольствие, и чем дольше вы над ней сидели тем больше радости от успешного ее решения (главное не перегибать палку - после 10 бессонных ночей над задачей ее решение вряд ли доставит вам радость).

Литература

1. , ., Москвина преподавания основ программирования в процессе создания компьютерных игр. // Мат-лы междунар. конференции "Новые информационные технологии в университетском образовании". Новосибирск, 1995, с.145-147.

2. Моя первая программа на Паскале: от компьютерных игр к профессиональному программированию. / и др. Вып. 1-3. Прилож. Новосибирск: НГУ, 1996.

Разбор задач олимпиадного характера.

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

Материалы мастер-класса (презентация)

на РМО учителей информатики.

учителя информатики и ИКТ

МОУ «Лицей №23»

Шуваловой Светланы Юрьевны.

В данной работе обобщены материалы, представленные мною на РМО учителей информатики в 2011, 2012 годах по итогам школьных этапов Всероссийской олимпиады школьников по информатике.

Число участников олимпиады школьников по программированию с каждым годом уменьшается, это связано с уменьшением доли часов по содержательной линии «Алгоритмизация и программирование» в учебной программе школьного курса информатики. Олимпиады предназначены выявлять наиболее одаренных в области информатики школьников, развивать их способности, повышать интерес к предмету. Они дают возможность школьникам получить раннюю профориентацию, что способствует становлению в дальнейшем российских специалистов в области информатики, вычислительной техники и программирования. Но хорошее знание школьного курса информатики не гарантирует успешного выступления на олимпиадах, необходимо заниматься с учащимися во внеурочное время.

Слайд 1.

Цель олимпиады по информатике - способствовать поиску наиболее одаренных школьников .

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

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

Слайд 2.

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

оригинальная формулировка задачи (или идея ее решения);
в тексте условия задачи не должны встречаться термины и понятия, выходящие за пределы изучаемых в рамках базового учебного плана предметов;
задача должна быть однозначно определена;
задача не должна требовать для своего решения специальных знаний;
формулировка задачи должна предполагать наличие этапа формализации при ее решении;
задача должна быть разумной сложности и трудоемкости.

Слайд 3.

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

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

комбинаторика;
сортировка и поиск;
обработка последовательностей;
алгоритмы на графах;
элементы вычислительной геометрии.
перебор вариантов и методы его сокращения;
динамическое программирование.

Слайд 4.

Этапы решения олимпиадных задач:

Разбор условия задачи.
Формализация условия задачи.
Разработка алгоритма решения задачи.
Программная реализация алгоритма.
Отладка и тестирование программы.
Отправка решения на проверку.

Слайд 5.

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

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

Необходимо помнить при написании программы, - это сохранение редактируемых файлов во время тура.

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

Слайд 6.

Часто встречающиеся ошибки:

Не соответствует формат ввода-вывода данных условию задачи

Рассмотрены не все возможные случаи

Не правильно задан тип данных (размерность)

Потеря редактируемых файлов во время тура

Слайд 7.

Минимальная база знаний для олимпиады по информатике.

Язык программирования:

базовые алгоритмические конструкции,
стандартные математические функции,
процедуры и функции для обработки строковых переменных,
процедуры и функции для работы с массивами.

Типовые алгоритмы.

Слайд 8.

Задачи на олимпиадах по информатике не всегда соответствуют «Стандарту основного и среднего (полного) общего образования по информатике и ИКТ». Более того, в качестве решения этих задач на олимпиаде требуется предъявить отлаженные программы, написанные на языке программирования высокого уровня, а не описания алгоритмов.

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

Слайд 9.

Интернет-ресурсы для подготовки к олимпиадам по информатике:

http://algolist.manual.ru/

Разбор задач школьного тура олимпиады 2011 года.

Задача №1 «Запись музыки» (15 баллов)

Проверить, поместится ли на диске компьютера музыкальная композиция, которая длится m минут и n секунд, если свободное дисковое пространство 6 мегабайт, а для записи одной секунды звука необходимо 16 килобайт.

Алгоритм решения:

Использование расчетной формулы и условного оператора

Задача №2 «Кодовый замок сейфа» (20 баллов)

Из 10 букв нужно набрать 3. Повторение букв допустимо. Подсчитать количество возможных комбинаций кодов.

Алгоритм решения:

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

Задача №3 «Прямоугольник» (30 баллов)

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

Алгоритм решения:

Если максимальная координата по оси Х левых нижних вершин прямоугольников будет меньше минимальной координаты правых верхних вершин и максимальная координата по оси У левых нижних вершин прямоугольников будет меньше минимальной координаты правых верхних вершин, то общая площадь есть.

Используется типовой алгоритм нахождения максимального (минимального) элемента массива.

Задача №4 «Магический квадрат» (35 баллов)

В квадрате размером 3x3 клетки поставить числа 1, 2, ... ,9 так, чтобы суммы чисел, стоящих в каждом ряду, столбце, в каждой диагонали, были равны.

Алгоритм решения. Задача на способ заполнения двумерного массива.

(индийский способ):

В середине верхней строки ставим 1 , в последней строке соседнего справа столбца 2 .
Следующие числа ставят в диагональном направлении.
Дойдя до правого края квадрата, переходят к крайней левой клетке ближайшей вышележащей строки.
Дойдя до верхнего края квадрата, переходят к самой нижней клетке соседнего справа столбика. Примечание. Дойдя до правой верхней угловой клетки, переходят к левой нижней.
Дойдя до уже занятой клетки, переходят к клетке, лежащей непосредственно под последней заполненной клеткой.
Если последняя заполненная клетка находится в нижнем ряду квадрата, переходят к самой верхней клетке в том же столбце.

Разбор задач школьного тура олимпиады 2012 года.

Задача 1.

Напечатать все трехзначные десятичные числа, сумма цифр которых равна данному числу.

Алгоритм решения:

Один из вариантов решения перебором:

var a,b,c,n,k:integer;

begin

write("n="); readln (n);

for a:=1 to 9 do

For b:=0 to 9 do

For c:=0 to 9 do

If a+b+c=n then

begin

writeln (a,b,c," ");

k:=k+1;

end;

Writeln;

Writeln ("k=",k) ;

Writeln;

end.

Второй вариант решения перебором:

Var a,b,c,n,k,m: integer;

begin

write("n="); readln(n);

for m:=100 to 999 do

begin

c:=m mod 10;

b:= m div 10 mod 10;

a:= m div 100;

if a+b+c=n then

begin

write(m:5);

k:=k+1;

end;

writeln("k=",k)

end.

Задача 2. «Малыш и Карлсон».

Малыш и Карлсон живут в прямоугольной комнате размером А х В . Как им посчитать, сколько понадобится квадратных ковриков со стороной С , чтобы полностью покрыть пол комнаты? (Малыш и Карлсон не умеют ни делить, ни умножать.) Напишите программу для решения этой задачи.

Алгоритм решения:

Во внешнем цикле по одной из сторон комнаты (while p) резервируем место для ряда (р:=р+с ), затем во внутреннем цикле по другой стороне (while m) проверяем, сколькими ковриками можно закрыть ряд, оператор m:=m+с резервирует место для коврика, а оператор kovrik:=kovrik+1 подсчитывает общее количество уложенных ковриков.

var a, b, с, kovrik, m, p: integer;

begin

readln(a, b, с);

kovrik:= 0;

p:= 0;

while p

begin

p:= p + c;

m:= 0;

while m

begin

m:= m + c;

kovrik:= kovrik + 1

end;

writeln (kovrik)

end.

Задача 3. «Бактерии».

Колония состояла из n бактерий (не более 30000). В нее попал вирус, который в первую минуту уничтожил одну бактерию, а затем разделился на два новых вируса. Одновременно каждая из оставшихся бактерий тоже разделилась на две новые. В следующую минуту возникшие два вируса уничтожили две бактерии, а затем все вирусы и бактерии снова разделились и так далее. Будет ли эта колония жить бесконечно долго или вымрет?

Ваша программа должна:

Запросить число бактерий n ;
Выяснить и сообщить: через сколько суток, часов и минут колония бактерий прекратит свое существование или выдать сообщение, что колония вечна.

Пример ответа: Для n=A. Ответ – B суток C часов D минут (где A, B, C, D – числовые значения).

Алгоритм решения:

Программа на языке программирования Паскаль.

Var a, b, c: shortint;

t, n, v: longint;

begin

Write (‘Начальная численность колонии -"); readln (n);

v:=1;

while n>0 do

Begin

t:= t + 1; { минуты}

n:= (n - v) * 2; { бактерии}

v:= v * 2; { вирусы}

end;

a:= t div 1440;

b:= (t – a * 1440) div 60;

c:= t – a - b;

Write ("Колония прекратит существование через ",a, " суток ", b, " часов ", c , " минут");

end.

Задача 4.

Дан прямоугольник со сторонами А и В, где А, В - натуральные числа. Начинаем отсекать от него квадраты (рис.1). Сколько таких квадратов можно отсечь, если каждый раз отсекается самый большой квадрат?

Алгоритм решения:

1 способ.

Для решения этой задачи нам нужны функции МАХ и MIN , для их определения используем подпрограммы-функции.

Введем:

вспомогательные переменные X и Y (Y>=X) , соответствующие уменьшающимся сторонам прямоугольника;
вспомогательную переменную D , которая определяет уменьшение размеров прямоугольника после очередного отсечения наибольшего квадрата, сторона которого находится как X:=MIN(D,X).

Организуем цикл, в котором сторона Y уменьшается каждый раз на MIN(D,X) до тех пор, пока не останется последний квадрат или Y не станет меньше X. В последнем случае переименовываем стороны оставшегося прямоугольника как Y:=MAX(D,X) и X:=MIN(D,X) и продолжаем цикл.

Программа на языке программирования Паскаль.

var a, b, d, k, x, y: integer;

function min (i, j: integer): integer;

begin

if i

else min:=j

end;

function max (i, j: integer): integer;

begin

if i

else max:=i

end;

begin

repeat

Writeln ("vvedite dva naturalnix chisla");

Readln (a, b);

until (a>0) and (b>0);

k:=1;

x:=min(a,b);

y:=max(a,b);

while x y do

begin

k:=k+1;

d:=y-x;

y:=max(d,x);

x:=min(d,x);

end;

Writeln ("iskomoe chislo kvadratov:", k)

end.

2 способ.

Задачу можно решить с помощью стандартных функций PASCAL : Y DIV X и Y MOD X, используя алгоритм Евклида.

Алгоритм решения:

Организуем цикл, в котором формируем остатки от деления r 0 , r 1 , r 2 ,..., r n , r n+1 до тех пор, пока один из этих остатков не станет равен нулю r n+i =0 . Таким образом, мы строим функцию порождения остатка от деления r n+i = r n mod r n-i , где r 0 = А и r i =В . Для той же самой системы остатков мы можем посчитать, сколько раз нацело укладывается остаток r n-i в r n .

{алгоритм Евклида}

var А, В, R0, R, R1, K: integer;

begin

repeat

Write ("ВВЕДИТЕ НАТУРАЛЬНОЕ ЧИСЛО А = ");

Readln (А);

Write ("ВВЕДИТЕ НАТУРАЛЬНОЕ ЧИСЛО В

Readln (В);

until (В > 0) and (А > 0) and (А >=В);

R0:= А;

R1:= В;

К:= R0 div R1;