Подготовка к олимпиаде по информатике методика. Фундаментальные исследования. Программирование в алгоритмах

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

Актуальность темы

В связи с актуализацией и активизацией олимпиадного движения все острее встает проблема подготовки учащихся к участию в олимпиадах. Подготовка «ученика-олимпиадника» начинается с подготовки учителя.

Проблемы, встающие перед учителем:

1. Изучение новых форм проведения олимпиад.

2. Знание алгоритмов решения олимпиадных задач.

3. Наличие самих задач.

4. Знание языков программирования.

5. Время на изучение, отладку и проверку задач.

6. Обучение учащихся правильной организации деятельности на олимпиаде.

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

Вот некоторые особенности подготовки школьников к олимпиадному программированию :

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

· Действует ограничение, что при решении задач желательно использовать только один из языков программирования (СИ или ПАСКАЛЬ).

· Постоянные тренировки идут почти на спортивном уровне.

· Большие затраты времени, длительность олимпиады с разбором часто превышает 6 часов.

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

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

· Возможно второе образование, профильный ВУЗ по программированию.

· ИПК учителей, курсы по изучению языков программирования, по олимпиадному программированию.

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

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

Педагогическая идея

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

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

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

В 1964 г. В. Врум предложил «теорию ожиданий». Он считал, что стимул к эффективному и качественному труду зависит от сочетания трех факторов - ожиданий человека:

1. Ожидание того, что усилия приведут к желаемому результату.

2. Ожидание того, что результаты повлекут за собой вознаграждение.

3. Ожидание того, что вознаграждение будет иметь достаточную ценность.

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

· Теория ожидания указывает на то, что должны делать учителя, чтобы стимулы к учебе у учеников были сильными:

o Учить учеников получать требуемые результаты и создавать для этого все необходимые условия;

o Устанавливать непосредственную связь между результатами труда и оценкой учеников;

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

· Исходя из этого, механизмы мотивации и основные факторы эффективности стимулирования можно выразить как:

o Знание учителями потребностей, интересов, нужд учеников.

o Установление справедливой непосредственной связи между результатами и вознаграждением.

o Безотлагательность вознаграждения.

o Степень удовлетворения ожиданий.

Для подготовки к олимпиадам по программированию можно применить методику с использованием системы тестирования «NSUTS» , разработанной на базе НГУ, которая позволяет оперативно решать многие из этих пунктов.

Технология использования системы « NSUTS »

Система находится по адресу https://olympic. *****/nsuts-test/nsuts_new_login. cgi . При переходе по этой ссылке попадаем на страницу авторизации , где, введя свой логин и пароль, можно войти в систему.

https://pandia.ru/text/78/392/images/image002_97.jpg" width="623" height="258 src=">

В данном случае выберем, например, Школьные тренировки , после чего вы попадёте на страницу «Страница регистрации на Школьные тренировки », где регистрация проста и понятна. Только нужно учесть, что данные, вводимые вами, должны быть достоверными.

https://pandia.ru/text/78/392/images/image004_80.jpg" width="623" height="306">

На вкладке «Help » можно прочесть краткую инструкцию по работе в системе. Рассмотрим содержимое этой страницы.

Система тестирования NSUTS. Очень краткое Описание.

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

В разделе «Тур » вы можете выбрать текущий тур олимпиады.

В разделе «Новости » вы можете прочитать объявления и комментарии от жюри и оргкомитета олимпиады. А так же узнать время начала и конца олимпиады. После начала олимпиады на этой странице появляются ссылки на условия задач.

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

Ваши решения должны считывать входную информацию из файла input. txt и выдавать результат в файл output. txt . Запрещено читать из стандартного потока ввода, писать в стандартный поток вывода, стандартный поток ошибок. Программа участника не должна открывать, читать и модифицировать файлы, кроме input. txt и output. txt или иных, указанных в условии задачи. Доступ к файловой системе и другим ресурсам, кроме перечисленных в формулировке задачи, запрещен. Нарушение этого требования может быть основанием для дисквалификации команды. Ограничение на размер исходного кода - 100 килобайт. Формат вывода должен точно соответствовать требованиям, описанным в условии задачи.

Участник может использовать любой компилятор из перечисленных в разделе «Сдать ».

Опции компиляции:

Visual C++ 6.0
Visual C++ 2005	cl. exe /EHsc /Ox task. cpp /link /STACK:
MinGW 5.1.4 (GCC 3.4.5)	c++.exe - Wall - Wl,--stack= - O2 task. cpp
Freepascal 2.2.0	ppc386.exe - O2 - Cs task. pas
Java 1.6.0_07	javac. exe Task. java
Запуск Java	java - Xmx480m - Xss32m - Djava. security. manager - Duser. language=en_US Task
Borland Delphi 2006

В секции «Результаты » вы можете просмотреть статус тестирования и результаты тестирования отправленных вами задач. В строке «Время » указано время на момент сдачи решения, язык программирования который вы указали, сдавая это решение. Ссылка «V iew source » покажет текст сданного решения.

В строке «Результат » отображается результат тестирования:

Queued - решение стоит в очереди на тестирование.

Testing... - тестируется прямо в этот момент.

Source code limit exceeded - превышено ограничение на исходный код программы.

Compile Error - не удалось скомпилировать (причина указывается).

Когда решение протестировано, статус принимает одно из следующих значений:

ACCEPTED! - решение засчитано как верное.

Wrong Answer - неверный ответ на тесте.

Time limit exceeded - решение не уложилось в отведенное процессорное время.

Timeout - решение не уложилось в отведенное время.

Run-time Error - решение вернуло код ошибки, отличный от нуля.

Memory limit exceeded - решение не уложилось в отведенное ограничение по памяти.

No output file - отсутствует файл output. txt.

Security violation - решение совершило действие запрещенное правилами.

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

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

Штрафное время - это сумма штрафного времени по всем задачам. Штрафное время для одной задачи равно 0, если задача не сдана. Если же задача сдана, то её штрафное время считается по формуле:

время_сдачи_правильного_решения + (количество_неудачных_попыток * 20).

Cекция «Вопросы и ответы » предназначена для общения с Жюри олимпиады. Вы можете задать жюри вопросы по условиям задач или указать на неточность формулировки задач.

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

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

На вкладке «Тур» выбираем необходимый нам тур по олимпиаде, например, «Подготовка к Всероссийской олимпиаде 2010.03.21 (Геометрия) » . После этого переходим на вкладку «Новости» и по ссылке «Условие тура» скачиваем файл формата MS Office Word, в котором находятся задачи, представленные к решению на данном туре.

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

Основные классы задач, выдвигаемых на олимпиады по информатике

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

1. В совершенстве владеть языком и средой программирования (в нашем случае - это Free Pascal), уметь строить и воплощать с помощью этого языка различные алгоритмы.

2. Владеть необходимым математическим аппаратом.

3. Знать алгоритмы решения основных классов задач, их оптимизацию.

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

1. Задачи, использующие сложные структуры данных, такие, как массивы, очереди, стеки, связанные списки и деревья.

2. Графы, как множество объектов с множеством связей.

3. Задачи, использующие аналитическую геометрию и опирающиеся на понятие «вектор».

4. Задачи динамического программирования.

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

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

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

В действительности структуры данных в ЭВМ строятся на основе базовых типов данных, таких как «char», «integer», «real». На следующем уровне находятся массивы, представляющие собой наборы базовых типов данных. Затем идут записи, представляющие собой группы типов данных, доступ к которым осуществляется по одному из данных, а на последнем уровне, когда уже не рассматриваются физические аспекты представления данных, внимание обращается на порядок, в котором данные хранятся и в котором делается их поиск. По существу физические данные связаны с «машиной данных», которая управляет способом доступа к информации в вашей программе. Имеется четыре такие «машины»:

1. очередь;

3. связанный список;

4. двоичное дерево.

1) http://ru. wikipedia. org/wiki/%D0%A1%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85.

2) http://valera. *****/delphi/struct/ocher. html.

3) http://www. *****/informatika/pascal/struktury_dannyh.

4) Т. Кормен. Алгоритмы. Построение и анализ. 2-е изд. Стр.255

5) Задачи и решения http://*****/olimp/str_prb. php.

Графы, как множество объектов с множеством связей.

Граф – это абстрактный математический объект. Он состоит из вершин и ребер. Каждое ребро соединяет пару вершин. Если одну и ту же пару вершин соединяют несколько ребер, то эти ребра называются кратными. Ребро, соединяющее вершину с ней самой, называется петлей. По ребрам графа можно ходить, перемещаясь из одной вершины в другую. В зависимости от того, можно ли по ребру ходить в обе стороны, или только в одну, различают неориентированные и ориентированные графы соответственно. Ориентированные ребра называются дугами. Если у всех ребер графа есть вес (т. е. некоторое число, однозначно соответствующее данному ребру), то граф называется взвешенным. Вершины, соединенные ребром, называются соседними. Для неориентированного графа степень вершины – число входящих в нее ребер. Для ориентированного графа различают степень по входящим и степень по исходящим ребрам. Граф называется полным, если между любой парой различных вершин есть ребро.

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

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

Есть несколько способов представления графа в памяти компьютера. Далее с теорией можно ознакомиться по ссылкам:

1. http://*****/sng/index. shtml

2. http://*****/sng/4/index. shtml

3. https://sites. /site/vzsitgnovosibirsk/distancionnye-kursy/distancionnyj-kurs-graf

4. http://book. *****/10/grap1021.htm

5. http://ru. wikipedia. org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2

6. Задачи и решения http://*****/olimp/gra_prb. php

Задачи, использующие аналитическую геометрию и опирающиеся на понятие «вектор»

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

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

1) http://*****/?page=lib_viewarticle&article_id=12.

2) http://*****/article. asp? id_sec=1&id_text=1332.

3) Задачи и решения http://*****/olimp/geo_prb. php

Задачи динамического программирования.

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

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

Основы теории динамического программирования были заложены Р. Беллманом. Заметим, что слово программирование в приведенном названии (dynamic programming), также как и в “линейном программировании” (linear programming) не означает составление программ для компьютера.

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

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

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

3) вычислить оптимальное значение параметра для всех подзадач,

4) построить самое оптимальное решение, используя полученную информацию.

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

1) http://*****/blogs/algorithm/113108/.

2) http://www. *****/Olympiads/Rules_Olympiads/Rules21.htm.

3) http://*****/tag/%D0%B4%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5%20%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5/

4) Задачи и решения http://*****/olimp/rec_prb. php

Статья учителя ОИВТ Лицея №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.

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

системы задач

олимпиады школьников

конструирование систем задач

методика подготовки к олимпиадам

одаренность

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). Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»

МУНИЦИПАЛЬНОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ - МУЖЕВСКАЯ СРЕДНЯЯ ОБЩЕОБРАЗОВАТЕЛЬНА ШКОЛА ИМ.Н.В.АРХАНГЕЛЬСКОГО

«Олимпиады по информатике: методика подготовки»

Материал подготовил:

Учитель информатики

Галицкая Ирина Викторовна

Проблемы, встающие перед учителем:

· Изучение новых форм проведения олимпиад.

· Знание алгоритмов решения олимпиадных задач.

· Наличие самих задач.

· Знание языков программирования.

· Время на изучение, отладку и проверку задач.

· Обучение учащихся правильной организации деятельности на олимпиаде.

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

Вот некоторые особенности подготовки школьников к олимпиадному программированию:

1. В школьной программе нет такого предмета «программирование». Т.е. обучаемый должен иметь собственную, довольно сильную мотивацию.

2. Действует ограничение, что при решении задач желательно использовать только один из языков программирования (СИ или ПАСКАЛЬ).

3. Постоянные тренировки идут почти на спортивном уровне.

4. Большие затраты времени, длительность олимпиады с разбором часто превышает 6 часов.

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

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

· Возможно второе образование, профильный ВУЗ по программированию.

· Курсы по изучению языков программирования, по олимпиадному программированию.

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

Педагогическая идея опыта

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

В 1964 г. В. Врум предложил «теорию ожиданий». Он считал, что стимул к эффективному и качественному труду зависит от сочетания трех факторов - ожиданий человека:

1. Ожидание того, что усилия приведут к желаемому результату.

2. Ожидание того, что результаты повлекут за собой вознаграждение.

3. Ожидание того, что вознаграждение будет иметь достаточную ценность.

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

Теория ожидания указывает на то, что должны делать учителя, чтобы стимулы к учебе у учеников были сильными:

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

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

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

Исходя из этого, механизмы мотивации и основные факторы эффективности стимулирования можно выразить как:

1. Знание учителями потребностей, интересов, нужд учеников.

2. Установление справедливой непосредственной связи между результатами и вознаграждением.

3. Безотлагательность вознаграждения.

4. Степень удовлетворения ожиданий.

Технология использования опыта

Конечно, подготовка к олимпиадам - это длительный и трудоемкий процесс.

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

Внедрение опыта

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

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

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

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

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

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

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

Результативность

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

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

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

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

На следующих этапах работы идет усложнение заданий.

Проблема психологической и физической перегрузки

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

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

Раздел 1. Математические основы программирования

Раздел 2. Техника программирования

1. Основы языка программирования (Паскаль, Си) Переменные и простейшие типы данных, размеры типов. Линейные программы. Условные операторы. Циклы. Процедуры и функции. Сложные типы данных (массивы, строки, записи, указатели, файлы).

2. Массивы Одномерные массивы. Двумерные массивы (матрицы). Многомерные массивы.

3. Строки. Элементы лексического и синтаксического разбора Операции над строками. Лексемы, подсчет лексем различных типов. Выделение чисел из строки.

4. Работа с файлами Чтение и запись в текстовый файл. Преобразование полученных из файла данных в удобную структуру. Работа с типизированными файлами. Нетипизированные файлы. Буферизация ввода.

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

6. "Длинная" арифметика Хранения в программе чисел, которые не вмещаются в стандартные типы. Арифметические операции над "длинными" числами. "Длинные" числа с десятичной частью. Извлечение корня с заданной точностью.

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

Раздел 3. Алгоритмы, методы и принципы решения задач.

1. Понятие сложности алгоритма. Определение сложности.

2. Алгоритмы поиска и сортировки Поиск элемента в неупорядоченном массиве. Двоичный поиск по ключу в упорядоченном массиве (дихотомия). Поиск методом Фибоначчи. Поиск в упорядоченном n-мерном массиве. Поиск k-го по величине элемента массива. Простые методы сортировки ("пузырек", "выборка", "вставка", "подсчет"). Быстрые методы ("быстрая", "слиянием", "пирамидальная"), балансировка двоичных деревьев. Сортировка методом черпака.

3. Решение задач методом перебора вариантов Применение рекурсии для перебора. Генерация сочетаний, размещений, перестановок и булеана множества. Полный перебор. Отсечение вариантов (эвристики). Метод ветвей и границ.

4. Вычислительная геометрия и численные методы Длина отрезка. Уравнение прямой. Скалярное и векторное произведение. Точка пересечения отрезков. Принадлежность точки фигуре на плоскости (например: треугольнику). Площадь выпуклого многоугольника. Выпуклая оболочка множества точек: алгоритмы Грэхема, Джарвиса, "разделяй и властвуй". Ближайшая пара точек. Метод Гаусса для решения системы линейных уравнений. Нахождение решения уравнения.

5. Принцип динамического программирования Понятие, применимость. Сравнение с перебором.

6. Жадные алгоритмы Понятие, применимость. Сравнение с перебором и динамическим программированием.

7. Теория графов. Алгоритмы на графах Понятие графа. Определения теории графов. Структуры данных для представления графа в программе. Алгоритмы обхода графа (поиски в ширину и глубину). Лабиринт (метод волны). Эйлеров цикл. Кратчайший путь во взвешенном графе (алгоритмы Дейкстры и Минти). Транзитивное замыкание графа (алгоритм Флойда-Уоршилла). Минимальное остовное дерево (алгоритмы Прима и Краскала). Топологическая сортировка графа. Потоки в сетях (алгоритм Форда-Фалкерсона). Паросочетания в двудольном графе (метод удлиняющей цепочки, потоковое решение). Задача о назначениях, назначения на узкое место (венгерский алгоритм). Игры на графах. Раскраска графа. Уложение графа на плоскости. Сильная связность и двусвязность графа. Изоморфизм графов. K-клика. Гамильтонов цикл.

8. Лексический и синтаксический анализ Задача "Калькулятор". Синтаксические диаграммы. Формы Бэкуса-Наура. Стековая и рекурсивная модель синтаксического разбора. Конечные автоматы. Грамматики.

9. Задачи с "изюминками"

Раздел 4. Олимпиады по информатике

1. Правила проведения олимпиад по программированию

2. Типичные ошибки и отладка программ

3. Приемы олимпиадника

По-моему, наибольшую ценность представляют разделы 2 и 3. Если с изучением языка программирования у вас не должно возникнуть сложностей (огромное количество книг по этой теме), то вот с алгоритмами придется посложнее. Книг по этой теме тоже немало, но они, чаще всего, слишком перегружены теорией, а на олимпиадах нужна только практика. Из электронных источников по алгоритмам могу посоветовать книгу С.М.Окулова и сайт algolist.manual.ru, который менее нацелен на изучение "олимпиадной информатики", чем книга Окулова, но содержит большое количество алгоритмов, которых нет в книги, но которые неплохо было бы знать. Привыкайте работать в режиме: написание + отладка на Borland Pascal/Borland C++, а компиляция (с предварительным изменением констант) на Free Pascal/GNU C. Новые 32-битные компиляторы не имеют жесткого ограничения в памяти и работают существенно быстрее (особенно заметна разница в скорости выполнения 16 и 32-битных программ на P4). Такая хитрая тактика объясняется отсутствием приличного отладчика в новых платформах и их практически полной совместимостью с компиляторами фирмы Borland (в FP не забывайте делать close для выходного файла).

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

Олимпиада Всероссийская олимпиада по информатике Региональный этап пройдет 16 и 18 января 2020 года

Состязание для школьников 5-11 классов. Победители и призеры финала получают льготы при поступлении в вузы

Информатика

Codeforces.com . Портал, объединяющий огромное количество участников соревнований по программированию по всему миру. На сайте регулярно проводятся онлайн-соревнования для школьников самого разного уровня: от начинающих до многократных чемпионов мира. Многие известные компании, в том числе ВКонтакте, Mail.Ru, Тинькофф Банк и AIM Tech проводят на платформе официальные соревнования.

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

Вики-конспекты . Энциклопедия по дискретной математике и теории алгоритмов, составленная студентами ИТМО. В ней описано большинство алгоритмов, используемых на олимпиадах по программированию. Многие статьи содержат примеры задач и псевдокоды приведенных алгоритмов. Конспекты написаны очень подробно и качественно. Это один из немногих ресурсов на русском языке по данной теме.

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

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

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

Книги

Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы. Построение и анализ . Данная книга является классическим учебным пособием с подробным описанием алгоритмов и структур данных, а также базовыми сведениями из дискретной математики, необходимыми каждому программисту. Помимо этого книга содержит огромное количество упражнений различной сложности, которые будут интересны и самому искушенному читателю. В ней очень удачный стиль изложения, и хотя она ориентирована на студентов, большая часть материала будет доступна и школьникам.