Реферат: О школьных олимпиадах по информатике

О ШКОЛЬНЫХ ОЛИМПИАДАХ ПО ИНФОРМАТИКЕ

Емельченков Е.П.

Смоленский государственный университет, г. Смоленск


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

Л. Волков, Н. Шамгунов. Как стать чемпионом Урала по программированию


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

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

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

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

В России существуют несколько центров подготовки школьников, в которых обучение программированию ведется на очень высоком уровне. Это подтверждается, в частности, успехами российских школьников на международных олимпиадах. С 1993 года российские школьники являются постоянными фаворитами на международной олимпиаде школьников по информатике (International Olympiad in Informatics, IOI). Кубок чемпиона мира по информатике пять раз побывал в России, и до 2005 года по этому показателю России не было равных. В настоящее время лучший результат имеет только одна страна в мире - Китай. По общему количеству медалей российская команда уступает две медали китайской команде [1]. В 2008 г. на международной олимпиаде российские школьники завоевали 3 золотых и 1 серебряную медали, а китайские - 4 золотых медали. В общей же сложности без медалей российские школьники ни разу не приезжали домой с 1991 г.

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

структуры данных (множество, стек, очередь);

перебор вариантов и методы его сокращения;

динамическое программирование;

сортировка и поиск;

обработка последовательностей;

арифметика многоразрядных чисел.

алгоритмы работы в различных системах счисления;

комбинаторные алгоритмы (генерация комбинаторных объектов, перестановки, размещения, сочетания);

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

алгоритмы вычислительной геометрии (многоугольники, площади плоских фигур, выпуклая оболочка);

задачи из разных предметных областей (задачи на географической карте, задачи на шахматной доске).

Необходимый для изучения перечисленных тем материал содержится в книгах [1-7], а также доступен в Интернет, например на сайтах Саратовского государственного университета (http://acm.sgu.ru) или Уральского государственного университета (http://acm.timus.ru). Ссылки на архивы задач и иные материалы схожей тематики можно найти на сайтах http://acm.sgu.ru,   http://acm.timus.ru  и  http://neerc.ifmo.ru/school.

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

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

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


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

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

Требуется написать программу, решающую указанную задачу.

Формат входных данных

Входной файл содержит в первой строке целое число n (3 ≤ n ≤ 1500). Каждая из последующих строк содержит по два разделенных пробелом целых числа – xi и yi , определяющих координаты i-ой точки. Все координаты точек не превосходят по абсолютной величине. Среди заданных точек нет совпадающих.

Формат выходных данных

В выходной файл необходимо вывести ответ на вышеназванную задачу.


^ Комментарий к задаче. В формулировке задачи первый абзац следовало бы удалить. Упоминание мальчика Романа, термина «симметрия» и «определения» равнобедренного треугольника не делает задачу более интересной и только отвлекает от ее сути.

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


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

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

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

Формат входных данных

Входной файл содержит в одной строке три целых числа a, b и c (1 ≤ a, b, c ≤ 1 000 000). Все числа в строке разделены пробелом.

Формат выходных данных

В первую строку выходного файла необходимо вывести слово ^ YES, если данные три числа можно сложить разными способами и получить разные суммы. В противном случае, необходимо вывести слово NO.

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


^ Комментарий к задаче. Во-первых, в школе не используют термин «ассоциативный закон сложения». Следовало использовать знакомый школьникам термин «сочетательный закон сложения».

Во-вторых, пояснение ассоциативного закона фразой «можно складывать заданные три числа в разном порядке» не соответствует определению ассоциативного (сочетательного) закона хорошо известного школьникам в виде: (a + b) + с = a + (b + c).


Задача № 8. Перестановки

Задано множество из n различных натуральных чисел. Перестановку элементов этого множества назовем k-перестановкой, если для любых двух соседних элементов этой перестановки их наибольший общий делитель не менее k. Например, если задано множество элементов S = {6, 3, 9, 8}, то перестановка {8, 6, 3, 9} является 2-перестановкой, а перестановка {6, 8, 3, 9} – нет.

Перестановка {p1, p2, …, pn} будет лексикографически меньше перестановки {q1, q2, …, qn}, если существует такое натуральное число i (1 ≤ i ≤ n), для которого pj = qj при j < i и pi < qi.

В качестве примера упорядочим все k-перестановки заданного выше множества в лексикографическом порядке. Например, существует ровно четыре 2-перестановки множества S: {3, 9, 6, 8}, {8, 6, 3, 9}, {8, 6, 9, 3} и {9, 3, 6, 8}. Соответственно, первой 2-перестановкой в лексикографическом порядке является множество {3, 9, 6, 8}, а четвертой – множество {9, 3, 6, 8}.

Требуется написать программу, позволяющую найти m-ую k-пере­становку в этом порядке.

Формат входных данных

Входной файл в первой строке содержит три натуральных числа – n (1 ≤ n ≤ 16), m и k (1 ≤ m, k ≤ 109). Вторая строка содержит n различных натуральных чисел, не превосходящих 109. Все числа в строках разделены пробелом.

Формат выходных данных

В выходной файл необходимо вывести m-ую k-перестановку заданного множества или –1, если такой нет.


^ Комментарий к задаче. В математике фигурные скобки используются для обозначения множеств, а не перестановок. Для школьника записи {3, 9, 6, 8} и {8, 6, 3, 9} обозначают одно и то же множество, а не разные перестановки. Для обозначения перестановок в задаче следовало использовать круглые скобки.

Из определения k-перестановки следует, что 6-перестановка (6; 18; 42) является 5-перестановкой, а 1-перестановка (81; 63; 49) является 6-пере­становкой.


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

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

«Все хорошо, прекрасная маркиза».


^ Список литературы, рекомендуемой для подготовки
к олимпиадам по информатике


[1]. Кирюхин В.М. Методика решения задач по информатике. Международные олимпиады / В. М. Кирюхин, С. М. Окулов. – М.: БИНОМ. Лаборатория знаний, 2007. – 600 с.: ил.

[2]. Окулов С. М. Программирование в алгоритмах / С. М. Окулов. - М.: БИНОМ. Лаборатория знаний, 2004. – 341 с.: ил.

[3]. Меньшиков Ф.М. Олимпиадные задачи по программированию (+CD) / Ф.М. Меньшиков. - СПб.: Питер, 2006. - 315 с.: ил.

[4]. Долинский М. С. Решение сложных и олимпиадных задач по программированию: Учебное пособие / М. С. Долинский - СПб.: Питер, 2006. - 366 с: ил.

[5]. Скиена С. С, Ревилла М. А. Олимпиадные задачи по программированию. Руководство по подготовке к соревнованиям / Пер. с англ. - М: КУДИЦ-ОБРАЗ, 2005. - 416 с.

[6]. Емельченков Е.П., Петухов А.О. Смоленские школьные олимпиады по информатике: Книга для учащихся и учителей общеобразовательных школ. Смоленск: Смоленский гос. пед. ун-т, Смоленск. областной ин-т усовершенствования учителей, 1999. – 114 с.

[7]. Емельченков Е.П., Петухов А.О. Методы программирования. Смоленск: Смоленский областной институт усовершенствования учителей, 2004. - 120 с.