Подготовка школьников к олимпиаде по информатике. Подготовка к олимпиадам по информатике
Подготовка учащихся к олимпиаде по информатике
Не секрет, что уровень подготовленности по информатике городских и сельских школьников резко отличается. К середине 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.
1В статье представлены обоснование роли систем задач при подготовке школьников к олимпиадам по информатике, описания содержательной составляющей систем задач, используемых при подготовке, и требования, которые учитываются при конструировании систем задач; авторская этапная модель процесса конструирования систем задач и пример системы задач. Методика подготовки школьников к олимпиадам по информатике на основе использования систем задач и авторская стадийная модель формирования одаренности в условиях подготовки школьников к олимпиадам по информатике прошли длительную экспериментальную апробацию. Теоретическая значимость результатов исследования обусловлена вкладом в теорию формирования одаренности и формирования готовности к участию в олимпиадах по информатике. В ходе исследования обосновано, что результаты подготовки к олимпиадам обусловливают специфику процесса формирования одаренности у школьников.
системы задач
олимпиады школьников
конструирование систем задач
методика подготовки к олимпиадам
одаренность
1. Балл, Г.А. Теория учебных задач: психолого-педагогический аспект. – М.: Педагогика, 1990. – 184 с.
2. Кирюхин, В.М., Окулов, С.М. Методика решения задач по информатике. Международные олимпиады. – М.: БИНОМ. Лаборатория знаний, 2007. – 600 с.
3. Педагогика профессионального образования: перспективы развития: монография. Кн. 3 / О.В. Алексеева, Н.А. Бурмистрова, В.Д. Васильева, Н.Н. Головина, О.Н. Кравченко, Е.С. Павлова и др.; под ред. С.С. Чернова; Центр развития научного сотрудничества. – Новосибирск: Изд-во «СИБПРИНТ», 2010. – 245 с.
4. Рабочая концепция одаренности / Д.Б. Богоявленская, В.Д. Шадриков, Ю.Б. Бабаева, А.В. Брушлинский, В.Н. Дружинин, и др. – М.: ИЧП Изд-во «Магистр», 2003.
5. Смыковская, Т.К. Олимпиады по программированию как фактор развития одарённости студентов и школьников / Т.К. Смыковская, Е.С. Павлова // Вестник Волгоградской академии МВД России. – 2010. – № 1. – C. 125–127.
В настоящее время для учащихся старшего школьного возраста одним из наиболее эффективных средств выявления способностей и уровней одаренности, а также развития интеллектуальных и творческих способностей являются подготовка и участие в предметных олимпиадах . Среди всех школьных предметов можно выделить информатику как наиболее динамичный предмет, т.к. содержание олимпиадных задач по информатике постоянно изменяется. Следует отметить, что областные и региональные олимпиады по информатике традиционно являются олимпиадами по программированию, а школьные, а иногда и городские олимпиады - это олимпиады по ИКТ.
Проведенные нами опросы учителей информатики школ Волгоградской области показывают, что главную роль при подготовке школьников к олимпиадам по данному предмету занимают задачи. Анализ задач для олимпиад по информатике (программированию) в контексте содержания показал, что они включают задачи по сортировке и перебору данных, динамическому программированию, моделированию, оптимизации, длинной арифметике, линейному и двоичному поиску, жадным алгоритмам, рекурсии, теории графов, комбинаторике и по работе с данными строкового и файлового типов .
Многолетний опыт подготовки школьников к олимпиадам по программированию в Волгоградской области показывает, что в качестве основы для проведения занятий целесообразно использовать не отдельные задачи, а комплексные системы задач. Разнообразные наборы задач, входящих в системы задач для подготовки к олимпиадам по информатике, позволяют:
1) постепенно усложнять изучаемый материал;
2) поэтапно увеличивать объем работы;
3) повышать уровень самостоятельности учащихся;
4) привлекать элементы теории для решения познавательных задач;
5) обучать способам рассуждения (как по образцу, так и самостоятельно) с учетом принципа вариативности задач;
6) формировать важнейшие характеристики творческих способностей: беглость мысли (количество идей, возникающих за единицу времени), гибкость ума (способность переключаться с одной мысли на другую), оригинальность (способность находить решения, отличающиеся от общепринятых); любознательность (чувствительность к проблемам в окружающем мире), умение выдвигать и разрабатывать гипотезы.
При построении систем задач мы учитываем требования, определяющие педагогическую целесообразность их использования : дидактические, отражающие соответствующие традиционные и специфические принципы обучения; и методические, учитывающие особенности информатики как учебного предмета и науки. При подготовке к олимпиадам по информатике мы выделили следующие требования к системам задач:
1) ключевая задача (наличие задач, сгруппированных в узлы вокруг объединяющих центров - задач, в которых рассматриваются факты или способы деятельности, применяемые при решении других задач и имеющие принципиальное значение для усвоения предметного содержания);
2) связность (возможность графически представить совокупность задач связным графом, в узлах которого ключевые задачи, выше них - подготовительные и вспомогательные, ниже - следствия, обобщения и так далее);
3) целевая достаточность (наличие достаточного количества задач для тренировки в классе и дома, аналогичных задач для закрепления метода решения, задач для индивидуальных и групповых заданий разной направленности, задач для самостоятельной (в том числе исследовательской) деятельности учащихся, задач для текущего и итогового контроля с учетом запасных вариантов и так далее);
4) психологическая комфортность (система задач учитывает наличие разных темпераментов, типов мышления, видов памяти).
На первых этапах подготовки к олимпиадам по информатике мы конструировали системы задач эмпирическим путем, но в дальнейшем мы пришли к тому, что процесс создания систем задач должен включать в себя следующие этапы: аналитический (анализ содержания учебного материала и требований стандарта, формулирование целей и установление их взаимного соответствия, отбор содержания), проектировочный (выбор методов и методических приемов, определение форм представления учебного материала, способов его подачи) и технологический (техническое создание систем задач в соответствии с предъявляемыми требованиями).
По теме «Техника программирования» нами разработаны системы задач по программированию разветвляющихся и циклических вычислительных процессов, системы задач для работы с одномерными и двумерными массивами, для обработки строк символов, для изучения рекуррентных алгоритмов, алгоритмов длинной арифметики и динамических структур данных, а по теме «Алгоритмы, методы и принципы решения задач» − системы задач для изучения алгоритмов линейного и двоичного (бинарного) поиска, алгоритмов сортировки информации, перебора (перестановки) данных, динамического программирования, алгоритмов работы с графами.
Приведем пример системы задач для изучения алгоритмов поиска информации, которая состоит из задач, построенных путем модификации условия или требования ключевых задач. При описании системы используются следующие обозначения : У (условие) - задан массив переменной длины, Б (базис) - умение просматривать весь массив (с первого до последнего элемента), Т (требование) - найти элементы массива по заданным условиям, С (способ) - просмотреть весь массив и отпечатать элементы, удовлетворяющие заданному условию.
Задача 1. В одномерном массиве A(N) (N≤100) найти все положительные элементы (ограничение условия).
Задача 2. В одномерном массиве A(N) (N ≤ 100) найти все четные элементы (ограничение условия).
Задача 3. В одномерном массиве A(N) (N ≤ 100) найти все четные положительные элементы (получена из предыдущей добавлением в условие).
Задача 4. В одномерном массиве A(N) (N≤100) найти все четные положительные элементы с индексами, кратными 3 (получена из предыдущей добавлением в условие).
Задача 5. В одномерном массиве A(N) (N ≤ 100) увеличить в два раза все четные положительные элементы (получена из задачи 4 путем изменения требования).
Задача 6. В одномерном массиве A(N) (N ≤ 100) возвести в квадрат все элементы, попадающие в интервал от -2 до 5 (получена из задачи 4 путем изменения требования).
В процессе апробации разработанных нами систем задач была создана методика подготовки к олимпиадам по информатике на основе использования систем задач, которая построена с учетом специфик целевого (система целей - обучение с использованием системы задач), содержательного (дидактические единицы содержания, требующие отображения в системах задач) и процессуального (информации, определение видов, форм и способов подачи учебной информации в соответствии с особенностями методического стиля педагога) компонентов методической системы учителя информатики, реализуемых в системах задач.
Данная методика используется преподавателями Лицея при факультете довузовской подготовки ФГБОУ ВПО «Волгоградский государственный технический университет» при подготовке школьников к олимпиадам по информатике с 2003 и по настоящее время.
Многолетние наблюдения за школьниками, участвующими в процессе подготовки к олимпиадам по информатике показали, что использование систем задач, кроме подготовки к олимпиадам, еще влияет на развитие одаренности . Поэтому в процессе педагогического исследования нами была разработана трехстадийная модель формирования одаренности в условиях подготовки школьников к олимпиадам по информатике, при построении которой мы ориентировались на то, что на каждой из стадий подготовки к олимпиадам учащиеся непосредственно участвуют в процессе формирования своей одаренности. Первая стадия является стадией самоопределения (самоидентификации одаренности) школьника, вторая - стадией определения границ своей одаренности, на третьей стадии происходит осознание, каким образом можно самостоятельно участвовать в процессе формирования своей одаренности. Данная модель является теоретической основой для проведения нами дальнейшей методической работы.
Эта стадийная модель внесла коррективы в содержательный и процессуальный компоненты разработанной нами методики подготовки к олимпиадам по информатике на основе использования систем задач. Сконструированные системы задач становятся основой для разработки индивидуальных образовательных траекторий для каждого ученика, что приводит к формированию одаренности учащихся путем развития способностей учащихся и реализации их личностного творческого потенциала. Методика стала стадийной, обеспечивая таким образом разноуровневость индивидуальных образовательных траекторий и трехэтапность процесса подготовки к олимпиадам по информатике и формирования одаренности при использовании комплексов систем задач и сочетании очной и дистанционной форм обучения.
Рецензенты:
Смыковская Т.К., д.п.н., профессор кафедры теории и методики обучения математике и информатике, ФГОУ ВПО «Волгоградский социально-педагогический университет», г. Волгоград;
Петрова Т.М., д.п.н., профессор кафедры теории и методики обучения математике и информатике, ФГОУ ВПО «Волгоградский социально-педагогический университет», г. Волгоград.
Работа поступила в редакцию 08.10.2013.
Библиографическая ссылка
Павлова Е.С. МЕТОДИКА ФОРМИРОВАНИЯ ОДАРЕННОСТИ ПРИ ПОДГОТОВКЕ К ОЛИМПИАДАМ ПО ИНФОРМАТИКЕ // Фундаментальные исследования. – 2013. – № 10-6. – С. 1360-1362;URL: http://fundamental-research.ru/ru/article/view?id=32547 (дата обращения: 05.01.2020). Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
Итак, если Вы начинающий учитель информатики (а может и со стажем), желающий попытаться подготовить своих учеников к районной олимпиаде по информатике - эта страница для Вас.
В этом разделе будет размещаться информация, которая поможет Вам сделать первые шаги, вместе с автором сайта, на пути подготовки школьников к районным олимпиадам по информатике. Почему не к республиканским? Да потому, что помочь в этом, на данный момент, я не могу.
Решение попробовать подготовить учащихся 9-11 классов к районной олимпиаде по информатике, я принял сразу после того, как стал учителем информатики (4 года назад). Ознакомившись с заданиями за прошлые годы, я понял, что не могу решить ни одного из них. На этом можно было бы и остановиться, но я решил все-таки попробовать.
Что имеется на данный момент? С одной стороны начинающий учитель информатики, с другой стороны учащиеся знакомые лишь с основами программирования. Но, есть главное - обоюдное желание учиться.
Как вы понимаете, хорошее знание школьного курса информатики абсолютно не гарантирует успешного выступления на олимпиадах. Соответственно, заниматься с учащимися необходимо во внеурочное время. Лично мне не пришлось долго убеждать директора школы в необходимости организации кружка по программированию.
Что касается домашних компьютеров, то ситуация улучшается год от года. Однако, во многих сельских школах нашего района, у подавляющего большинства учащихся нет домашних компьютеров. Это звучит дико в 2009 году, но таковы реалии сельской жизни. В такой ситуации приходиться заниматься в школьном кабинете информатики.
Для начала рекомендую приобрести несколько хороших книг, я их размещаю в порядка возрастания сложности материала. Если книг нет в книжных магазинах, то можно заказать книги пройдя по прямым ссылкам расположенным ниже. Ссылки ведут в интернет-магазин books.ru , в котором я неоднократно заказывал книги для себя. Нареканий по качеству обслуживания у меня нет. Срок доставки книг составляет 10-14 дней.
Программирование на Pascal.Автор Сэм Аболрус. Если вы решили преподавать в школе язык программирования Pascal, но программирование ваша "ахиллесова пята", то эта книга для вас. Оригинальное название книги в переводе с английского - "Изучаем Паскаль за три дня". Действительно, освоить азы программирования на Паскале, при помощи это книги можно за пару дней. Автор работает программистом в корпорации Майкрософт. Настоятельно рекомендую ее приобрести. Моя оценка этой книги 5(отлично). |
Основы программированияОкулов С. Это книга, которую необходимо иметь каждому, кто решил научиться решать олимпиадные задачи по информатике. Пожалуй, это лучшая книга, которая мне попадалась по этой тематике. Повествование начинается от изучения среды программирования Turbo Pascal , а заканчивается решением задач на графах. Настоятельно рекомендую приобрести эту книгу. Моя оценка этой книги 5(отлично). |
Программирование в алгоритмахОчередной бестселлер Сергея Окулова. Кое-какая информация повторяется из книги расположенной выше, но в основном эта книга содержит уже более сложный материал чем предыдущая. Подробно рассмотрены такие темы как "Комбинаторное программирование", "Перебор и методы его сокращения", "Алгоритмы на графах" и т.д. В связи с тем, что ни одна олимпиада по информатике не обходится без сложных задач, к которым несомненно относятся и задачи на графах, то не плохо иметь эту книгу в арсенале. Моя оценка этой книги 5 (отлично). |
Олимпиадные задачи по программированию (+CD)Федор Меньшиков. Книга предназначена для пользователей уже знакомых с решением простых задач по программированию. Рассмотрены типовые задачи встречающиеся на различных олимпиадах для школьников и студентов. На прилагаемом к книге диске есть дополнительный материал, а также тестирующая система для компьютерной проверки решения задач. Моя оценка этой книги 5(отлично). /p> |
Кое-что полезное вы найдете и на этом сайте:
- Программирование на языке Turbo Pascal. Материалы к урокам. Довольно качественный материал, настоятельно рекомендую скачать в архиве ZIP(224Кб)
- Книга по решению олимпиадных задач на графах. Эту книгу, в электронном варианте, я нашел на сайте небезызвестного Михаила Густокашина (его статьи можно найти в журнале "Мир ПК" и газете "Информатика "). Пожалуй, этот материал один из лучших посвященных решению задач по программированию на графах. Привязка материала идет к языку Pascal . Рекомендую скачать эту книгу всем учителям информатики которые занимаются подготовкой школьников к олимпиадам по информатике. Скачать книгу Окулова в архиве RAR (724 Кб).
Видеоуроки по программированию
Элективный курс
«Олимпиадная информатика»
Программа 1. «Олимпиадная информатика» для учащихся 5-6 классов
Программа 2. «Олимпиадная информатика» для учащихся 7-8 классов
Программа 3. «Олимпиадная информатика» для учащихся 9-11 классов
Разработчик: Ярошевская Вера Ивановна
г. Москва 2016 г.
Программа содержат:
Пояснительную записку;
Методических указания по изучению тем;
Учебно-тематический план и программы подготовки к олимпиадам по информатике.
Электронные учебные материалы
Пояснительная записка.
Важной задачей образования является работа с одаренными учащимися, их подготовка к предметным олимпиадам. Олимпиада по информатике занимает одно из ведущих мест, в связи с интенсивным развитием информационных технологий как в нашей стране, так и за рубежом.
Участие в олимпиадах позволяет развивать творческие способности школьников и обеспечивает высокую мотивацию к образовательной деятельности.
Классическая олимпиада по информатике - это олимпиада по программированию, которая предполагает наличие обширных познаний в математике и языках программирования.
Решение олимпиадных задач позволяет раскрыть творческий потенциал школьника во время подготовки к олимпиаде, учитывая возрастные особенности ребенка и перспективу его развития. Использование многоуровневых олимпиадных задач, позволяет школьникам применить свой творческий потенциал, независимо от уровня подготовки.
Курс занятий по Олимпиадной информатике (решение олимпиадных задач по информатике) ориентирован на учащихся 5-11х классов, обладающих повышенной мотивацией к изучению информатики и имеющих начальные знания в области алгоритмизации на уровне понимания простейших алгоритмов.
Данный элективный курс позволяет провести непрерывную подготовку к олимпиадам по информатике начиная с 5-го класса, используя методическую коллекцию олимпиадных задач. В курсе использован системный подход при разработке модулей непрерывной подготовки одаренных детей к олимпиадам по информатике.
Основная цель курса: раскрыть значение программирования и суть профессии программиста, ознакомление учащихся со средой и основами программирования на языке PascalABC.NET, подготовить учащихся к практическому использованию полученных знаний при решении учебных задач, а затем профессиональной деятельности, вовлечение учащихся в участие в олимпиадах по программированию разного уровня.
Основные задачи курса: развитие навыков программирования алгоритмических структур; развитие логического мышления учащихся; развитие интеллекта учащихся.
Данная программа представляет большую практическую значимость с точки зрения совершенствования непрерывной работы с одаренными школьниками в рамках олимпиадного движения по информатике и школьного образования.
Методические указания по изучению тем
Олимпиадные задачи по информатике охватывают следующие ключевые разделы:
1. Математические основы информатики.
Этот раздел является фундаментальной основой информатики. В олимпиадах по информатике это особенно важно, так как школьникам сложно достичь успешности на олимпиадных состязаниях без хорошей подготовки в области теории множеств, логики, теории графов и комбинаторики.
Для успешного выступления на олимпиаде по информатике школьники должны
знать/понимать:
основы терминологии функций, отношений и множеств;
перестановки, размещения и сочетания множества;
формальные методы символической логики высказываний
основы построения рекуррентных соотношений;
основные методы доказательств;
основы теории чисел;
уметь:
выполнять операции, связанные с множествами, функциями и отношениями;
вычислять перестановки, размещения и сочетания множества, а также интерпретировать их значения в контексте конкретной задачи;
решать типичные рекуррентные соотношения;
осуществлять формальные логические доказательства и логическое рассуждение для моделирования алгоритмов;
определять, какой вид доказательства лучше подходит для решения конкретной задачи;
использовать основные алгоритмы теории чисел;
1. Отношения, функции и множества.
2. Основные геометрические понятия.
3. Основы логики.
4. Основы вычислений.
5. Методы доказательства.
6. Основы теории чисел.
7. Основы алгебры.
8. Основы комбинаторики.
9. Теорию графов.
10. Основы теории вероятностей.
11. Основы теории игр.
2. Разработка и анализ алгоритмов.
В этом разделе определяется основная способность учащихся знать классы алгоритмов, которые предназначены для решения определенного набора известных задач, понимать их сильных и слабых сторон, применять различные алгоритмы в заданном контексте с оценкой его эффективности.
элементы теории алгоритмов;
основные структуры данных;
основные понятия теории графов, а также их свойства и некоторые специальные случаи;
связь графов и деревьев со структурами данных, алгоритмами и вычислениями;
свойства, присущие «хорошим» алгоритмам;
вычислительную сложность основных алгоритмов сортировки, поиска;
понятие рекурсии и общую постановку рекурсивно-определенной задачи;
простые численные алгоритмы;
основные комбинаторные алгоритмы;
основные алгоритмы вычислительной геометрии;
наиболее распространенные алгоритмы сортировки;
наиболее важные алгоритмы на строках;
фундаментальные алгоритмы на графах: поиск в глубину и в ширину, нахождение кратчайших путей от одного источника и
основы динамического программирования;
основные положения теории игр;
уметь:
выбирать подходящие структуры данных для решения задач;
использовать вышеназванные алгоритмы в процессе решения задач;
определять сложность по времени и памяти алгоритмов;
определять вычислительную сложность основных алгоритмов сортировки, поиска;
реализовывать рекурсивные функции и процедуры;
использовать при решении практических задач вышеназванные знания и умения.
Основными темами этого раздела являются:
1. Алгоритмы и их свойства.
2. Структуры данных
3. Основы анализа алгоритмов.
4. Алгоритмические стратегии.
5. Рекурсия.
6. Фундаментальные вычислительные алгоритмы.
7. Числовые алгоритмы.
8. Алгоритмы на строках.
9. Алгоритмы на графах.
10. Динамическое программирование.
11. Алгоритмы теории игр.
3. Основы программирования.
В этом разделе закладывается условие успешного выступления учащихся на олимпиадах по информатике. Данный раздел включает в себя материал по фундаментальным концепциям программирования, основным структурам данных и алгоритмам, а также собственно языки программирования.
В рамках этого раздела школьники должны знать/понимать:
основные конструкции программирования;
концепцию типа данных как множества значений и операций над ними;
основные типы данных;
основные структуры данных: массивы, записи, строки, связные списки, стек;
представление данных в памяти;
альтернативные представления структур данных с точки зрения производительности;
основы ввода/вывода;
операторы, функции и передача параметров;
статическое, автоматическое и динамическое выделение памяти;
управление памятью во время исполнения программы;
методы реализации стеков, очередей;
методы реализации графов и деревьев;
механизм передачи параметров;
особенности реализации рекурсивных решений;
стратегии, полезные при отладке программ;
уметь:
анализировать и объяснить поведение простых программ, включающих фундаментальные конструкции;
модифицировать и расширить короткие программы, использующие стандартные условные и итеративные операторы и функции;
разработать, реализовать, протестировать и отладить программу, которая использовать все наиболее важные конструкции программирования;
применять методы структурной (функциональной) декомпозиции для разделения программы на части;
реализовать основные структуры данных на языке высокого уровня;
реализовать, протестировать и отладить рекурсивные функции и процедуры;
использовать при решении практических задач вышеназванные знания и умения и уверенно программировать на олимпиадах по информатике на языке программирования Pascal.
Основными темами этого раздела являются:
1. Язык программирования Pascal.
2. Основные конструкции программирования.
3. Переменные и типы данных.
4. Типы структур данных.
4. Методы вычислений и моделирование.
Раздел «Методы вычислений и моделирование» представляет область информатики, тесно связанную с вычислительной математикой и численными методами.
В рамках этого раздела школьники должны знать/понимать:
понятия ошибки, устойчивости, машинной точности и погрешности приближенных вычислений;
источники погрешности в приближенных вычислениях;
основные алгоритмы решения задач вычислительной математики: вычисление значения и корней функции; вычисление периметра, площади и объема, вычисление точки пересечения двух отрезков и др.;
понятия модели и моделирования, основные типы моделей;
компоненты компьютерной модели и способы их описания: входные и выходные переменные, переменные состояния, функции перехода и выхода, функция продвижения времени;
основные этапы и особенности построения и использования компьютерных моделей;
уметь:
вычислять оценку погрешности приближенных вычислений;
использовать при решении задач основные методы вычислительной математики;
формализовывать объекты моделирования;
разрабатывать компьютерные модели простейших объектов;
использовать при решении практических задач компьютерные модели в виде «черного ящика»;
использовать при решении практических задач вышеназванные знания и умения.
Основными темами этого раздела являются:
1. Основы вычислительной математики.
2. Введение в моделирование.
Учебно-тематическое планирование к программе «Олимпиадная информатика»
На основании выше сказанного составлены программы 1, 2 и 3, которые учитывают возрастные особенности учащихся.
Программа 1. Для учащихся 5-6 классов
| Тема | Количество часов |
| 1 |
|
| Типы олимпиадных задач по информатике для 5-6 классов. | 2 |
| Отношения (рефлексивность, симметричность, транзитивность, эквивалентность, лексикографический порядок) Точка, прямая, отрезок, вектор, угол Декартовы координаты в евклидовом пространстве Треугольник, прямоугольник, многоугольник Выпуклые многоугольники Основы логики Логические переменные, операции Таблицы истинности Булевы функции Основы вычислений Основы вычислений: Правила суммы и произведения Рекуррентные соотношения Методы доказательства Прямые доказательства Доказательство через контрпример Доказательство через противопоставление Основы теории чисел Простые числа. Деление с остатком Наибольший общий делитель Основы комбинаторики Перестановки, размещения и сочетания: Основные определения Теория графов Типы графов Маршруты и связность Деревья Остовные деревья Основы теории вероятностей Понятие вероятности Основы теории игр Понятие игры и результата игры Простейшие игры и стратегии | 20 |
| Этапы решения олимпиадной задачи: формализация условия задачи, выбор метода решения задачи. План разбора олимпиадной задачи по информатике. | 5 |
| Алгоритмы Алгоритмы и их свойства Понятие алгоритма Концепции и свойства алгоритмов Запись алгоритма на неформальном языке Структуры данных Простые базовые структуры Множества Последовательности Списки Неориентированные графы Алгоритмические стратегии Алгоритмы полного перебора Рекурсия Понятие рекурсии Простые численные алгоритмы Классические комбинаторные алгоритмы Алгоритмы с подмножествами: генерация, восстановление по номеру и построение номера, генерация следующего и предыдущего (прибавление и вычитание единицы) Алгоритмы с сочетаниями и перестановками: генерация, восстановление по номеру и построение номера, генерация следующего и предыдущего. Алгоритмы последовательного и бинарного поиска Числовые алгоритмы Разложение числа на простые множители Решето Эратосфена Алгоритм Евклида Алгоритмы на строках Поиск подстроки в строке. Наивный метод Алгоритмы на графах Вычисление длин кратчайших путей в дереве Обход графа в ширину и в глубину Способы реализации поиска в ширину (“наивный” и с очередью) Геометрические алгоритмы Алгоритмы определения совпадения точек, лучей, прямых и отрезков Решение / моделирование алгоритмических задач в среде Исполнителя | 20 |
| Введение в реальную среду программирования как инструмент реализации алгоритмов на компьютере Типовые инструменты среды программирования (режим помощь, режим редактирования, режим отладки) Среда программирования. Начало программирования. Языки программирования Переменные и типы данных Типы структур данных Особенности программирования фундаментальных алгоритмов. Введение в моделирование. Классификация языков программирования Процедурные языки Переменные, типы, выражения и присваивания Основы ввода/вывода Операторы проверки условия и цикла Концепция типа данных как множества значений и операций над ними Примитивные типы Массивы Стратегии решения задач Роль алгоритмов в процессе решения задач Среды программирования Понятия модели и моделирования Основные типы моделей www.olympiads.ru . | 20 |
Программа 2. Для учащихся 7-8 классов
| Тема | Количество часов |
| Положение о Всероссийской олимпиаде школьников. Методические рекомендации по проведению школьного, муниципального и регионального этапов Всероссийской олимпиады школьников по информатике. | 1 |
| Типы олимпиадных задач по информатике для 7-8 классов. | 2 |
| Основные разделы математической информатики. Функции, отношения и множества Обратная функция, композиция Множества (дополнения, декартовы произведения) Основные геометрические понятия Евклидово расстояние Векторное и скалярное произведение на плоскости Основы логики Логические выражения Формы задания и синтез логических функций Преобразование логических выражений Основы вычислений Основы вычислений: Арифметические и геометрические прогрессии Числа Фибоначчи Методы доказательства Доказательство через противоречие Математическая индукция Основы теории чисел Основная теорема арифметики Взаимно простые числа Основы алгебры Многочлены и операции над ними. Решение квадратных уравнений. Теорема Виета Основы комбинаторики Тождество Паскаля Биномиальная теорема Теория графов Операции над графами Раскраска графов Эйлеровы и гамильтоновы графы Основы теории вероятностей Понятие математического ожидания. | 20 |
| Алгоритмы Алгоритмы и их свойства Ориентированные графы Деревья Основы анализа алгоритмов Стандартные классы сложности Асимптотический анализ поведения алгоритмов в среднем и крайних случаях Алгоритмические стратегии "Жадные" алгоритмы Рекурсия Рекурсивные математические функции Простые рекурсивные процедуры Реализация рекурсии Фундаментальные вычислительные алгоритмы Квадратичные методы сортировки (сортировка методом выбора, сортировка вставками) Сортировка подсчетом за линейное время. Алгоритмы сортировки за время (быстрая сортировка, пирамидальная сортировка Алгоритмы на строках Проверка графа на связность Алгоритмы поиска кратчайшего пути во взвешенных графах Основная идея динамического программирования. Рекурсивная реализация и развертывание в цикл. Задачи с монотонным направлением движения в таблице Задача о рюкзаке - решение методом динамического программирования Геометрические алгоритмы Представление точек, прямых и отрезков на плоскости | 20 |
| Среда программирования . Языки программирования Переменные и типы данных Типы структур данных Механизмы абстракции. Особенности программирования фундаментальных алгоритмов. Основы синтаксиса и семантики языков высокого уровня
Функции и передача параметров Свойства объявлений (связывание, область видимости, блоки и время жизни) Обзор проверки типов Записи Стратегии выбора подходящей структуры данных Процедуры, функции и итераторы как механизмы абстракции Модули в языках программирования Стратегии реализации алгоритмов Реализация рекурсии Введение в моделирование. Компоненты компьютерной модели и способы их описания: входные и выходные переменные, переменные состояния, функции перехода и выхода, функция продвижения времени Основные этапы и особенности построения компьютерных моделей Основные этапы использования компьютерных моделей при решении практических задач Типовые примеры решения задач по разделам из коллекции www.olympiads.ru | 25 |
Программа 3. Для учащихся 9-11 классов
| Тема | Количество часов |
| Положение о Всероссийской олимпиаде школьников. Методические рекомендации по проведению школьного, муниципального и регионального этапов Всероссийской олимпиады школьников по информатике. | 1 |
| Типы олимпиадных задач по информатике для 9-11 классов. | 2 |
| Основные разделы математической информатики. Функции, отношения и множества Вполне упорядоченные множества Мощность и счетность Основы логики Минимизация булевых функций Основные законы логики суждений Логика предикатов Основы вычислений Основы вычислений: Принцип включения-выключения Матрицы и действия над ними Методы доказательства Структура формальных доказательств Основы теории чисел Кольцо вычетов по модулю Основы алгебры Симметрические многочлены Понятие группы Свойства групп Теоремы о гомоморфизме и изоморфизме Основы комбинаторики Коды Грея: подмножества, сочетания, перестановки Таблицы инверсий перестановок Разбиения на подмножества. Числа Стирлинга Скобочные последовательности Теория графов Покрытия и независимость Укладка графов. Плоские (планарные) графы Двусвязность графа. Мосты, блоки, точки сочленения Связь ориентированных ациклических графов и отношений порядка. Транзитивное замыкание Двудольные графы Потоки и сети Основы теории вероятностей Аксиомы теории вероятностей Формула полной вероятности и формула Байеса. Условное математическое ожидание Основы теории игр Игры на матрицах | 20 |
| Алгоритмы Алгоритмы и их свойства Пирамида и дерево отрезков Сбалансированные деревья Хэш-таблицы и ассоциативные массивы Бор Основы анализа алгоритмов Компромисс между временем и объемом памяти в алгоритмах Использование рекуррентных отношений для анализа рекурсивных алгоритмов NP-полнота Алгоритмические стратегии Алгоритмы "разделяй и властвуй" Перебор с возвратом Эвристики Рекурсия Стратегия "разделяй и властвуй" Рекурсивный перебор с возвратами Фундаментальные вычислительные алгоритмы Алгоритмы сортировки ( сортировка слиянием) Цифровая сортировка Алгоритм вычисления номера слова в лексикографически упорядоченном множестве перестановок его символов Арифметика многоразрядных целых чисел Числовые алгоритмы Расширенный алгоритм Евклида. Способы реализации алгоритма без деления Решение линейных сравнений с помощью алгоритма Евклида Эффективная проверка числа на простоту Быстрые алгоритмы разложения чисел на простые множители. Алгоритмы на строках Алгоритмы поиска подстроки в строке за Периодические и циклические строки Алгоритм поиска нескольких подстрок за линейное время Алгоритмы на графах Топологическая сортировка графа, нахождение компонент сильной связности и построение диаграммы порядка Циклы отрицательной длины - критерий наличия, поиск Задача о синхронизации времени и задача о системе неравенств Алгоритм поиска эйлерова цикла (в том числе лексикографически минимального) Нахождение транзитивного замыкания графа Алгоритмы нахождения взвешенных остовных деревьев Алгоритмы отыскания компонент двусвязности, точек сочленения, мостов с помощью поиска в глубину Алгоритм нахождения максимального паросочетания и минимального вершинного покрытия в двудольном графе Поиск максимального потока в сети Динамическое программирование Оптимизация решения задачи динамического программирования на примере задачи о рюкзаке (исключение лишних параметров) Восстановление решения в задачах динамического программирования Общая схема решения задач динамического Алгоритмы теории игр Динамическое программирование и полный перебор как методы решения игровых задач. Игры на ациклическом графе Оценка позиций. Альфа-бета отсечение Геометрические алгоритмы Нахождение расстояний между объектами на плоскости Алгоритмы определения пересечения отрезков на плоскости Алгоритмы вычисления площади многоугольника с заданными координатами вершин. Случай целочисленной решетки (формула Пика) Алгоритмы построения выпуклой оболочки (алгоритмы Грэхема и Джарвиса) Окружности на плоскости, пересечение их с другими геометрическими объектами Эффективный алгоритм нахождения пары ближайших точек на плоскости | 20 |
| Среда программирования. Языки программирования Основные конструкции программирования Типы структур данных Особенности программирования фундаментальных алгоритмов. Программные средства и окружения. Проверка соответствия программного обеспечения. Формальные методы описания синтаксиса: Объектно-ориентированные языки Структурная декомпозиция Представление данных в памяти Статическое, автоматическое и динамическое выделение памяти Связанные структуры Методы реализации стеков, очередей и хэш-таблиц Методы реализации графов и деревьев Стратегии отладки Инструментальные средства тестирования Основы тестирования, включая создание тестового плана и генерацию тестов Тестирование методом "черного ящика" и "белого ящика" Тестирование элементов, интеграционное, системное тестирование и проверка соответствия Основы вычислительной математики. Основные методы вычислительной математики
Вычисление функций с шагом. Метод сеток Арифметика с плавающей точкой Ошибка, устойчивость, сходимость Типовые примеры решения задач по разделам из коллекции www.olympiads.ru . | 25 |
Диагностические задания
В качестве диагностических заданий используются представленные ниже типы олимпиадных задач и требуется провести их методический разбор.
Анализ всех задач, предлагавшихся на олимпиадах по информатике, позволил выделить следующие темы, тесно связанные с соответствующими разделами информатики и прикладной математики:
1) комбинаторика;
2) сортировка и поиск;
3) обработка последовательностей;
4) перебор вариантов и методы его сокращения;
5) алгоритмы на графах;
6) динамическое программирование;
7) элементы вычислительной геометрии;
8) задачи на технику программирования;
9) задачи на идею.
Методические указание для изучения
Алгоритмическая компьютерная среда
Набор задач по нескольким уровням сложности
Разные типы алгоритмических заданий (перестановки, переливания, взвешивания, переправы, переезды, работа с числами) (Виртуальные Лаборатории по информатике)
Алгоритмы на координатной плоскости (управление перемещением с условиями)
система автоматической проверки решений и оценивания
/ video / kuris . php
Адрес ресурса: http://school-collection.edu.ru , раздел «Информатика», 2-6 классы, выбрать «Интерактивный задачник по информатике для 2-6 классов»
Методическое пособие и 100 алгоритмических задач http :// lbz . ru / books /264/5211
Виртуальные лаборатории по информатике в начальной школе: методическое пособие Авторы: Цветкова М. С., Курис Г. Э.
Коллекции олимпиадных задач с 1989 по 2016 год и методические материалы к ним представлены на сайтах:
http://old.info.rosolymp.ru/
Представлены интернет-ресурсы олимпиадной информатики:
1. Интернет-ресурсы для теоретической подготовки к олимпиадам:
http://www.intuit.ru/courses.html (сайт Интернет-университета информационных технологий);
http://www.olympiads.ru/sng/index.shtml (сайт МИОО, МЦНМО, и оргкомитета Московской олимпиады по информатике для проведения дистанционных семинаров по подготовке к олимпиадам по информатике);
http://vzshit.net.ru/ (сайт Всесибирской заочной школы информационных технологий).
2. Интернет-ресурсы с коллекциями олимпиадных задач:
http://old.info.rosolymp.ru (сайт с самой большой в России коллекцией задач международных и всероссийских олимпиад по информатике с методическими рекомендациями по их решению);
http://www.olympiads.ru/moscow/index.shtml (сайт московских олимпиад по информатике);
http://neerc.ifmo.ru/school/russia-team/archive.html (сайт с архивом задач Всероссийских командных олимпиад школьников по программированию);
http://contest.ur.ru (сайт Уральских олимпиад по информатике );
http://www.olympiads.ru/ (сайт по олимпиадной информатике);
http://olimpic.nsu.ru/nsu/ (сайт открытой Всесибирской олимпиады по программированию им. И.В. Поттосина).
3. Интернет-ресурсы с коллекциями олимпиадных задач и возможностью их тестирования в реальном масштабе времени:
http://acm.timus.ru/ (сайт Уральского государственного университета, содержащий большой архив задач с различных соревнований по спортивному программированию);
http://acm.sgu.ru (сайт Саратовского государственного университета, содержащий архив задач с системой онлайн-проверки).
4. Сайты интернет-олимпиад для школьников:
http://info-online.rusolimp.ru/ (сайт интернет-туров заключительного этапа Всероссийской олимпиады школьников по информатике);
http://olymp.ifmo.ru/ (сайт городских интернет - олимпиад школьников Санкт-Петербурга);
http://neerc.ifmo.ru/school/io/index.html (сайт интернет-олимпиад по информатике, проводимых жюри Всероссийской командной олимпиады школьников по программированию);
http://www.olympiads.ru/online/index.shtml (сайт московских онлайн-олимпиад);
http://olimpic.nsu.ru/acmSchool/archive/2006-2007/train2006/index.shtml (сайт тренировочных олимпиад школьников, поддерживаемый Новосибирским государственным университетом).
Список литературы
1. Алексеев А. В., Беляев С. Н. Подготовка школьников к олимпиадам по информатике с использованием веб-сайта: учеб.-метод. пособие для учащихся 7-11 классов. Ханты-Мансийск: РИО ИРО, 2008. 284 с.
2. Волчёнков С. Г., Корнилов П. А., Белов Ю. А. и др. Ярославские олимпиады по информатике. Сборник задач с решениями. М.: БИНОМ. Лаборатория знаний. 2010. 405 с.
3. Долинский М. С. Алгоритмизация и программирование на TurboPascal: от простых до олимпиадных задач: учеб.пособие. СПб.: Питер Принт, 2004. 240 с.
4. Иванов С. Ю., Кирюхин В. М., Окулов С. М. Методика анализа сложных задач по информатике: от простого к сложному // Информатика и образование. 2006. № 10. С. 21-32.
5. Кирюхин В. М. Всероссийская олимпиада школьников по информатике. М.: АПК и ППРО, 2005. 212 с.
6. Кирюхин В. М. Информатика. Всероссийские олимпиады. Вып. 2. М.: Просвещение, 2009. 222 с. (Пять колец).
7. Кирюхин В. М. Информатика. Всероссийские олимпиады. Вып. 3. М.: Просвещение, 2011. 222 с. (Пять колец).
8. Кирюхин В. М. Информатика. Международные олимпиады. Вып. 1. М.: Просвещение, 2009. 239 с. (Пять колец).
9. Кирюхин В. М., Лапунов А. В., Окулов С. М. Задачи по информатике. Международные олимпиады 1989-1996 гг. М.: ABF, 1996. 272 с.
10. Кирюхин В. М., Окулов С. М. Методика анализа сложных задач по информатике // Информатика и образование. 2006. № 4. С. 42-54.
11. Кирюхин В. М., Окулов С. М. Методика анализа сложных задач по информатике // Информатика и образование. 2006. № 5. С. 29-41.
12. Кирюхин В. М., Окулов С. М. Методика решения задач по информатике. Международные олимпиады. М.: БИНОМ. Лаборатория знаний, 2007. 600 с.
13. Кирюхин В. М., Цветкова М. С. Всероссийская олимпиада школьников по информатике в 2006 году. М.: АПК и ППРО, 2006. 152 с.
14. Кирюхин В. М., Цветкова М. С. Методическое обеспечение олимпиадной информатики в школе / Сб. трудов XVII конференции-выставки «Информационные технологии в образовании». Ч. III. М.: БИТ про, 2007. С. 193-195
15. Кирюхин В. М. Информатика. Всероссийские олимпиады. Вып. 1. М.: Просвещение, 2008. 220 с. (Пять колец).
16. Меньшиков Ф. В. Олимпиадные задачи по программированию. СПб.: Питер, 2006. 315 с.
17. Московские олимпиады по информатике. 2002-2009 / под ред. Е. В. Андреевой, В. М. Гуровица и В. А. Матюхина. М.: МЦНМО, 2009. 414 с.
18. Нижегородские городские олимпиады школьников по информатике / под ред. В. Д. Лелюха. Нижний Новгород: ИПФ РАН, 2010. 130 с.
19. Никулин Е. А. Компьютерная геометрия и алгоритмы машинной графики. СПб.: БХВ-Петербург, 2003. 560 с.
20. Окулов С. М. Основы программирования. М.: БИНОМ. Лаборатория знаний, 2005. 440 с.
21. Окулов С. М. Программирование в алгоритмах. М.: БИНОМ. Лаборатория знаний. 2002. 341 с.
22. Окулов С. М. Дискретная математика. Теория и практика решения задач по информатике: учеб.пособие. М.: БИНОМ. Лаборатория знаний. 2008. 422 с.
23. Окулов С. М. Алгоритмы обработки строк: учеб.пособие. М.: БИНОМ. Лаборатория знаний, 2009. 255 с.
24. Окулов С. М., Пестов А. А. 100 задач по информатике. Киров: Изд-во ВГПУ, 2000. 272 с.
25. Окулов С. М., Лялин А. В. Ханойские башни. М.: БИНОМ. Лаборатория знаний. 2008. 245 с. (Развитие интеллекта школьников).
26. Просветов Г. И. Дискретная математика: задачи и решения: учеб.пособие. М.: БИНОМ. Лаборатория знаний. 2008. 222 с.
27. Скиена С. С., Ревилла М. А. Олимпиадные задачи по программированию. Руководство по подготовке к соревнованиям. М.: Кудиц-образ, 2005. 416 с.
28. Сулейманов Р. Р. Организация внеклассной работы в школьном клубе программистов: методическое пособие. М.: БИНОМ. Лаборатория знаний. 2010. 255 с.
29. Цветкова М. С. Система развивающего обучения как основа олимпиадного движения / Сборник трудов XVII конференции-выставки «Информационные технологии в образовании». Ч. III. М.: БИТ про, 2007. С. 205-207
30. Кирюхин В.М., Цветкова М.С. Образовательные программы по развитию одаренности у детей и подростков, составленные с учетом уровня подготовленности, направлений интересов, по направлению информационных технологий, 2012 .
Сайт Методического центра олимпиадной информатики:
http://metodist.lbz.ru/lections/6/
Портал Всероссийской олимпиады школьников:
http://www.rosolymp.ru/
Сайт с архивом олимпиадных задач:
http://old.rosolymp.ru/
Модуль поддержан видеолекциями членов Центральной предметно-методической комиссии на сайте
Статья учителя ОИВТ Лицея №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.
