Реферат: Методические рекомендации по подготовке к олимпиадам по информатике

Методические рекомендации

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


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

^ Методика решения олимпиадных задач

Если задача задана, то тут же возникает вопрос: с чего начать ее решение? Можно выде­лить следующие этапы, которые присущи процессу реше­ния большинства олимпиадных задач:

Разбор условия задачи.

Формализация условия задачи.

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

Программная реализация алгоритма.

Отладка и тестирование программы.

Отправка решения на проверку.

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

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

^ Разбор условия задачи

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

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

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

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

В традиционной музыке используются музыкальные зву­ки из некоторого набора, именуемого звукорядом. Звуки звукоряда принято группировать в октавы, в каждой из которых 12 звуков. Порядковый номер звука в преде­лах одной октавы назовем нотой. Таким образом, каж­дый звук можно задать парой чисел — номером октавы и номером ноты. Номер октавы К - произвольное целое число, номер ноты N принимает значение из интервала [01, 12]. Звуки можно обозначать этими двумя числами, записанными рядом без пробелов (второе число всегда двузначное). Эту запись, назовем кодом Q. Например, Q = -108 для (-1)-й октавы, восьмой ноты. Значение Z, определяемое по формуле Z = К • 12 + N, назовем абсо­лютным номером Z звука в звукоряде (для приведенного выше примера Z = -4).

Набор всех звуков, ноты которых принадлежат задан­ному подмножеству номеров нот Р, назовем гармонией G. Это означает, что любой звук с абсолютным номером Z = К • 12 + п, где п — номер ноты из Р, принадлежит этой гармонии при любом значении К. Отсюда следует, что гармония однозначно определяется указанием Р. Две гармонии назовем эквивалентными, если при прибав­лении некоторого одного и того же целого числа ко всем абсолютным номерам звуков первой гармонии получают­ся все элементы второй гармонии. Ограничимся рассмот­рением только таких наборов гармоний, в которые наря­ду с каждой из гармоний входят и все эквивалентные ей. Для описания набора такого вида достаточно указать из каждой совокупности эквивалентных гармоний по одной гармонии Gi или соответствующему ей подмножеству Рi;. Базой В набора гармоний назовем совокупность всех та­ких Pi.

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

Будем говорить, что некоторый звук в тему для некото­рого аккорда, если этот звук принадлежит хотя бы одной гармонии из множества всех гармоний этого аккорда. Последовательное звучание произвольных звуков назовем мелодией. Каждому звуку мелодии может быть сопостав­лен аккорд в порядке исполнения мелодии. Будем счи­тать мелодию благозвучной для этой последовательности аккордов, если каждый ее звук оказывается в тему для соответствующего ему аккорда. Кучерявостъю мелодии назовем сумму модулей разностей абсолютных номеров Z последовательно исполняемых звуков данной мелодии. Пусть известны: база В набора гармоний, последователь­ность аккордов А и начальный звук Q. Требуется напи­сать программу, находящую наименее кучерявую из всех благозвучных мелодий, начинающихся с этого звука.


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

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

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

Помощь в понимании условий задач во время соревно­ваний могут оказать вопросы к членам жюри. Такая воз­можность всегда предусмотрена правилами проведения олимпиады, и в течение определенного времени с начала тура (как минимум, 1 ч) любой участник может это сде­лать. Вопросы задаются в письменном виде на специаль­ном бланке и должны быть сформулированы так, чтобы от­вет был либо «да», либо «нет». Если вопрос касается не условия задачи, а ее решения или ответ на этот вопрос не­посредственно содержится в тексте условия, то возможный вариант ответа жюри: «без комментариев».

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

^ Формализация условия задачи

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

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

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

В качестве примера рассмотрим выполнение этапа фор­мализации при решении задачи «Сталкер» (см. задачу 32005-06 из главы 6). В результате анализа ее условия и возможных путей решения можно прийти к выводу, что здесь будет полезным рассмотреть граф состояния сталке­ра. Определив способ описания этого графа и возможный путь решения с его использованием, получаем, что в фор­мальной постановке исходная задача сведется к поиску кратчайшего пути в графе состояния сталкера.

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

^ Разработка алгоритма решения задачи

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

^ Программная реализация алгоритма

Когда в том или ином виде алгоритм решения задачи получен, возникает проблема написания собственно про­граммы. Естественно, сначала надо выбрать стратегию раз

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

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

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

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

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

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

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

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

^ Отладка и тестирование программы

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

Отладка программы — это процесс, направленный на обнаружение и исправление ошибок в программе путем ее исполнения, в то время как тестирование — это процесс выполнения программы на некотором наборе данных, для которого заранее известен правильный результат ее работы или известны правила ее поведения. Указанный набор дан­ных называется тестовым или просто тестом. Таким об­разом, отладку можно представить в виде многократного повторения трех процессов: тестирования, в результате ко­торого может быть определена ошибка в программе, поис­ка места ошибки в программе и редактирования текста программы с целью устранения обнаруженной ошибки.

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

Для начала необходимо'добиться, чтобы программа ком­пилировалась. Это можно делать с использованием встроен­ных в среду программирования отладчиков, и овладение этими навыками является неотъемлемой частью подготов­ки к олимпиадам по информатике.

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

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

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

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

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

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

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

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

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

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

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

^ Отправка решения на проверку

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

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

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

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


Таблица 3.1



Пример команд для компиляции решений


Компилятор

Команда компиляции

Borland Pascal 7.0

bpc <имя файла>

Free Pascal 1.0.10

fpc <имя файла>

Borland C++ 3.1

bcc -ml <имя файла>

Borland С 3.1

bcc -ml <имя файла>

GNU C++ 3.2.1

qpp -О2 -х с++ <имя файла>

GNU С 3.2.1

qсс -О2 -х с <имя файла>

Borland Delphi 6.0

dcc32 -cc <имя файла>

Microsoft Visual Basic 6.0

vb6 /make <имя файла>

Microsoft Visual С 6.0

cl /O2 /TС <имя файла>


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

В-третьих, проверяемая программа всегда должна завер­шаться с кодом 0, т. е. либо командой halt(O), либо коман­дой return 0 (при написании программы на языке C/C++), или оператором end с точкой (при написании программы на языке Паскаль). Если это условие не будет выполнено, то проверяющая система считает, что в ходе работы про­граммы произошла ошибка, и такое решение получит нуль баллов.

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

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

^ Примерная программа по олимпиадной информатике

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

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

1.4.1. Основы вычислений:

- Правила суммы и произведения

- Арифметические и геометрические прогрессии

- Числа Фибоначчи

- Принцип включения-выключения *

Рекуррентные соотношения

Матрицы и действия над ними *

^ 1.5. Методы доказательства

Прямые доказательства

Доказательство через контрпример

Доказательство через противопоставление

Доказательство через противоречие

Математическая индукция

Структура формальных доказательств *

^ 1.6. Основы теории чисел

Простые числа. Основная теорема арифметики

Деление с остатком

Наибольший общий делитель

Взаимно простые числа

Делимость. Кольцо вычетов по модулю *

^ 1.7. Основы алгебры

Многочлены и операции над ними. Решение квадратных уравнений. Теорема Виета

Общий случай теоремы Виета. Симметрические многочлены *

1.7.3. Понятие группы *

1.7.4. Свойства групп *

1.7.5. Теоремы о гомоморфизме и изоморфизме *

^ 1.8. Основы комбинаторики

1.8.1. Перестановки, размещения и сочетания:

Основные определения
Тождество Паскаля

Биномиальная теорема

Коды Грея: подмножества, сочетания, перестановки *

Таблицы инверсий перестановок *

Разбиения на подмножества. Числа Стирлинга *

Скобочные последовательности *

^ 1.9. Теория графов

Типы графов

Маршруты и связно