Методика подготовки к олимпиадам по информатике
Актуальность темы
В связи с актуализацией и активизацией олимпиадного движения все острее встает проблема подготовки учащихся к участию в олимпиадах. Подготовка «ученика-олимпиадника» начинается с подготовки учителя.
Проблемы, встающие перед учителем:
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. При переходе по этой ссылке попадаем на страницу авторизации, где, введя свой логин и пароль, можно войти в систему.
Кликнув registration page на той же странице, переходим к регистрации на участие в олимпиадах.
В данном случае выберем, например, Школьные тренировки, после чего вы попадёте на страницу «Страница регистрации на Школьные тренировки», где регистрация проста и понятна. Только нужно учесть, что данные, вводимые вами, должны быть достоверными.
После авторизации вы попадёте на главную страницу системы.
На вкладке «Help» можно прочесть краткую инструкцию по работе в системе. Рассмотрим содержимое этой страницы.
Система тестирования NSUTS. Очень краткое Описание.
Вы находитесь в автоматической системе тестирования NSUTS для проведения и проверки олимпиад по программированию. В верхней части экрана отображается текущий раздел. В правом верхнем углу — название текущей олимпиады, название вашей команды и кнопка завершения работы с системой — «Выйти».
В разделе «Тур» вы можете выбрать текущий тур олимпиады.
В разделе «Новости» вы можете прочитать объявления и комментарии от жюри и оргкомитета олимпиады. А так же узнать время начала и конца олимпиады. После начала олимпиады на этой странице появляются ссылки на условия задач.
В разделе «Сдать» осуществляется отправка задач на тестирование. Для того чтобы отправить задачу на тестирование, укажите язык, на котором написано решение, и номер задачи. Вставьте текст решения в поле ввода и нажмите кнопку «Отправить». Или выберите файл, пользуясь строкой выбора файла, а затем нажмите кнопку «Отправить». Ваше решение появится в списке отправленных задач в секции «Результаты».
Ваши решения должны считывать входную информацию из файла input. txt и выдавать результат в файл output. txt. Запрещено читать из стандартного потока ввода, писать в стандартный поток вывода, стандартный поток ошибок. Программа участника не должна открывать, читать и модифицировать файлы, кроме input. txt и output. txt или иных, указанных в условии задачи. Доступ к файловой системе и другим ресурсам, кроме перечисленных в формулировке задачи, запрещен. Нарушение этого требования может быть основанием для дисквалификации команды. Ограничение на размер исходного кода — 100 килобайт. Формат вывода должен точно соответствовать требованиям, описанным в условии задачи.
Участник может использовать любой компилятор из перечисленных в разделе «Сдать».
Опции компиляции:
Visual C++ 6.0 | cl. exe /EHsc /Ox task. cpp /link /STACK: |
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 | dcc32 - CC -$D- |
В секции «Результаты» вы можете просмотреть статус тестирования и результаты тестирования отправленных вами задач. В строке «Время» указано время на момент сдачи решения, язык программирования который вы указали, сдавая это решение. Ссылка «View 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 (Геометрия) [school]». После этого переходим на вкладку «Новости» и по ссылке «Условие тура» скачиваем файл формата MS Office Word, в котором находятся задачи, представленные к решению на данном туре.
Решив задачу, на вкладке «Сдать» отправляем её на проверку, выставив все необходимые параметры (язык, текст программы либо файл с программой). Результаты проверки можно узнать на вкладке «Результаты».
Основные классы задач, выдвигаемых на олимпиады по информатике
Для успешного выполнения не только олимпиадных, но и внутриурочных задач, требуется:
1. В совершенстве владеть языком и средой программирования (в нашем случае — это Free Pascal), уметь строить и воплощать с помощью этого языка различные алгоритмы.
2. Владеть необходимым математическим аппаратом.
3. Знать алгоритмы решения основных классов задач, их оптимизацию.
Задачи олимпиадного программирования охватывают очень большой спектр знаний, но наиболее часто встречаемые и вызывающие наибольшую сложность — это следующие:
1. Задачи, использующие сложные структуры данных, такие, как массивы, очереди, стеки, связанные списки и деревья.
2. Графы, как множество объектов с множеством связей.
3. Задачи, использующие аналитическую геометрию и опирающиеся на понятие «вектор».
4. Задачи динамического программирования.
Рассмотрим данные классы задач подробнее.
Задачи, использующие сложные структуры данных, такие, как массивы, очереди, стеки, связанные списки и деревья.
Программы состоят из алгоритмов и структур данных. Хорошие программы используют преимущества их обоих. Выбор и разработка структуры данных столь же важна, как и разработка процедуры, которая манипулирует ими. Организация информации и методы доступа к ней обычно определяются характером стоящей перед программистом задачи. Поэтому каждый программист должен иметь в своем «багаже» соответствующие методы представления и поиска данных, которые можно применить в каждой конкретной ситуации.
В действительности структуры данных в ЭВМ строятся на основе базовых типов данных, таких как «char», «integer», «real». На следующем уровне находятся массивы, представляющие собой наборы базовых типов данных. Затем идут записи, представляющие собой группы типов данных, доступ к которым осуществляется по одному из данных, а на последнем уровне, когда уже не рассматриваются физические аспекты представления данных, внимание обращается на порядок, в котором данные хранятся и в котором делается их поиск. По существу физические данные связаны с «машиной данных», которая управляет способом доступа к информации в вашей программе. Имеется четыре такие «машины»:
1. очередь;
2. стек;
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
