takya.ru страница 1страница 2страница 3страница 4
скачать файл
Белгородский региональный институт повышения квалификации и профессиональной переподготовки специалистов

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

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

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

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



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

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

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

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

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

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

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

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



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

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

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

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

В качестве примера можно рассмотреть текст задачи, которая предлагалась на заключительном этапе 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). В результате анализа ее условия и возможных путей решения можно прийти к выводу, что здесь будет полезным рассмотреть граф состояния сталке­ра. Определив способ описания этого графа и возможный путь решения с его использованием, получаем, что в фор­мальной постановке исходная задача сведется к поиску кратчайшего пути в графе состояния сталкера.

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


скачать файл


следующая страница >>
Смотрите также:
Методические рекомендации по подготовке к олимпиадам по информатике
445.99kb.
Методические рекомендации для учителей по подготовке обучающихся основной школы к государственной (итоговой) аттестации в независимой форме по русскому языку в общеобразовательных учреждениях Методические рекомендации
406.47kb.
Краткие методические рекомендации курсантам (слушателям)
272.34kb.
Методические рекомендации по подготовке и оформлению рефератов для студентов: по специальности060501 Сестринское дело
168.31kb.
Методические рекомендации по подготовке к практическому занятию «Средства обучения для преподавателя»
103.6kb.
Данные рекомендации могут быть использованы также и при проведении собраний членов товариществ собственников жилья (тсж)
551.78kb.
Методические рекомендации по подготовке учащихся 9 класса к гиа по химии
89.86kb.
Рекомендации по подготовке открытого урока по информатике и икт
42.63kb.
Организация музыкально-театрализованных представлений в детском саду. Методические рекомендации
196.9kb.
Методические рекомендации аннотация
913.44kb.
Методические рекомендации/ сост. Лаврова Т. В., Уланова Е. А. Н. Новгород: ннгу, 2006
103.81kb.
Методические рекомендации по подготовке к итоговой аттестации в 9-х классах по физике в формате гиа-2012
88.63kb.