Программа индивидуальной подготовки к муниципальному этапу Всероссийской олимпиады школьников по предмету «Информатика и ИКТ. О методике решения олимпиадных задач Методические указание для изучения курса

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

Об обучении

Что же это за школа, как в ней учиться и как в нее поступить?

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

Меня всегда привлекало программирование (что это такое я понял аж в 4 классе). Я был очень рад, когда в седьмом классе начали преподавать Pascal и различные вычислительные алгоритмы. Именно тогда я написал первый «Hello World!», алгоритм Евклида; изучил условные операторы, циклы, массивы.
С восьмого класса учителя приглашали на факультативы по информатике, где мы изучали графы, алгоритмы сортировки массивов и многое другое.

Задачи

Посмотрим на совершенно типичную задачу для начинающих программистов-олимпиадников

Пятью пять - двадцать пять!
(Время: 1 сек. Память: 16 Мб Сложность: 8%)
Вася и Петя учатся в школе в одном классе. Недавно Петя поведал Васе о хитром способе возведения в квадрат натуральных чисел, оканчивающихся на цифру 5. Теперь Вася может с легкостью возводить в квадрат двузначные (и даже некоторые трехзначные) числа, оканчивающиеся на 5. Способ заключается в следующем: для возведения в квадрат числа, оканчивающегося на 5 достаточно умножить число, полученное из исходного вычеркиванием последней пятерки на следующее по порядку число, затем остается лишь приписать «25» к получившемуся результату справа. Например, для того, чтобы возвести число 125 в квадрат достаточно 12 умножить на 13 и приписать 25, т.е. приписывая к числу 12*13=156 число 25, получаем результат 15625, т.е. 1252=15625. Напишите программу, возводящую число, оканчивающееся на 5, в квадрат для того, чтобы Вася смог проверить свои навыки.
Входные данные
В единственной строке входного файла INPUT.TXT записано одно натуральное число А, оканчивающееся на цифру 5, не превышающее 4*10^5.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно натуральное число - A2 без лидирующих нулей.
Примеры:
INPUT.TXT
5
75
4255
OUTPUT.TXT
25
5625
18105025

Требования

Риски

Скрытый текст

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

Time limit exceeded
Превышен указанный в задаче лимит времени. Программа выполняется дольше установленного времени
Неэффективное решение или алгоритмическая ошибка в программе

Presentation Error
Отсутствие выходного файла OUTPUT.TXT
Файл не создан, неверное имя файла или сбой программы до открытия выходного файла

Compilation error
Ошибка компиляции. В результате компиляции не создан исполняемый файл
Синтаксическая ошибка в программе или неверно указано расширение файла. Возможно, что при реализации на языке Java был использован класс, отличный от Main

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

Runtime error
Ошибка исполнения. Программа завершила работу с ненулевым кодом возврата. В этом случае результат работы не проверяется
Возможно, в программе произошло обращение к несуществующему элементу массива, деление на ноль и т.д. Возможно, программа на C++ не завершается оператором «return 0» или по иной причине вернула ненулевой код возврата

Олимпиады

Этап среди старшеклассников

Муниципальный этап

Вот задача оттуда

Б. Бобр

Ограничения по памяти: 64 Мб
Бобр собирается построить каскад плотин и уютную хатку в русле неширокой реки. Так получилось, что река протекает по идеально прямой траектории, и ширина реки настолько мала, что в рамках данной задачи мы можем ею пренебречь. На берегах реки стоят деревья, которые бобр может использовать для строительства. Ученые решили выяснить, насколько оптимально бобр выбирает места для строительства плотин и хатки с точки зрения минимального суммарного расстояния, на которое необходимо переносить деревья.
Напишите программу, которая по заданным координатам деревьев относительно начала прямого участка реки, если считать ось сонаправленной течению определяет координаты объектов, соответствующие минимальному суммарному расстоянию, на которое необходимо переносить деревья.
Формат входных данных:
<=T<=10 – количество тестовых блоков, идущих друг за другом. В первой строке каждого тестового блока содержится два целых положительных числа 1<=N<=1000, 0<=М<=10, 0<=L<=100 – соответственно количество деревьев, растущих на берегах реки, количество деревьев, необходимое для возведения одного объекта и количество объектов, которые необходимо возвести. В каждой из следующих N строчек записано единственное положительное вещественное число – расстояние в метрах от начала прямого участка реки (самого высокого по течению) до места, где растет соответствующее дерево. Известно, что деревьев гарантированно хватает, чтобы построить все объекты (N>=M*L)
Формат выходных данных:
Для каждого тестового блока в отдельной строке необходимо вывести единственное число - сумму координат мест, в которых необходимо возвести объекты, чтобы суммарное расстояние, на которое потребуется перенести деревья для строительства, было минимальным, указав три точных знака после десятичного разделителя.

Входные данные
2
5 3 1
0.1
1.2
5.6
7.3
9.4
2 2 1
1
2
Выходные данные
7.300
1.000

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

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

А. Альбатрос
Ограничения по времени: 1 секунда на тест
Ограничения по памяти: 64 Мб
Альбатрос может совершать длительные перелеты, преодолевая длинные расстояния над просторами океана. Орнитологи решили определить, сколько километров может пролететь альбатрос, не посещая сушу. Для этого флотилия плавучих исследовательских лабораторий рассредоточилась по океану и записала данные об изучаемой особи, к которой прикреплена радиометка. Ученые фиксируют момент времени и текущие координаты того места, где они обнаружили альбатроса.
Напишите программу, определяющую расстояние, которое преодолел альбатрос в течение эксперимента, если считать, что в зоне наблюдений наша планета представляет собой идеальный шар радиусом 6366,197 километров.
Формат входных данных:
В первой строке входных данных содержится единственное целое положительное число 1<=T<=10 – количество тестовых блоков, идущих друг за другом. В первой строке каждого тестового блока содержится единственное целое положительное число 2<=N<=1000, количество записей о появлении альбатроса. В каждой из следующих N строчек записаны по двенадцать целых неотрицательных чисел (0<=d1<=90, 0<=m1<=90, 0<=s1<=90, 0<=d2<=90, 0<=m2<=90, 0<=s2<=90, 0<=h<=23, 0<=mt<=59, 0<=sec<=59, 1<=dd<=31, 1<=mm<=12, 2000<=yy<=2012) – соответственно градусы минуты и секунды северной широты, градусы, минуты и секунды западной долготы того места, где плавучая исследовательская лаборатория заметила альбатроса; время в формате часы, минуты, секунды и дата наблюдения в формате день, месяц, год.
Формат выходных данных:
Для каждого из тестовых блоков в отдельной строке необходимо вывести единственное целое число – расстояние, которое преодолел альбатрос, округленное до ближайшего четного целого числа.
Пример входных и выходных данных:
Входные данные
2
3
0 0 0 0 0 0 0 0 0 1 1 2012
0 0 0 0 2 0 0 0 0 3 1 2012
0 0 0 0 1 0 0 0 0 2 1 2012
2
0 0 0 0 0 0 0 0 0 1 1 2012
0 0 0 0 1 0 0 0 0 2 1 2012
Выходные данные
4
2

Полный текст муниципального этапа можно найти .

Дистанционный тур

Вот первая

Г. Герой дня
Ввод/вывод: стандартный

Медиахолдинг «Пермь Великая» отслеживает сообщения блоггеров Пермского края и каждый день пытается выяснить, кто является наиболее популярным в записях для того чтобы включить этого человека в традиционную рубрику «Герой дня».
Для каждой записи, попавшей в список отслеживания, известно количество просмотров и те персоналии, которые в ней упоминаются. Напишите программу, определяющую человека, для которого суммарное количество просмотров для записей, где он упоминается, максимально.
Формат входных данных:
В первой строке входных данных приводится единственное целое число 1<=L<=10000 – количество записей, попавших в обзор за текущий день. В каждой из следующих строк вначале указывается число – количество просмотров соответствующей записи и затем имена и фамилии людей, упоминающихся в записи. Имена и фамилии состоят из букв английского алфавита, число, а также все соседние слова отделяются друг от друга ровно одним пробелом. Суммарная длина строки составляет не более 200 символов.
Формат выходных данных:
В единственной строке выходных данных необходимо вывести имя и фамилию человека, записи с упоминанием которого набрали больше всего просмотров. Если таких людей несколько нужно вывести того, кто идет раньше других по алфавиту.

Входные данные
1
100500 John Travolta John Lennon

5
5 Vasya Pupkin Sergey Syroezhkin
10 Harry Potter
5 Garry Potter Vasya Pupkin
5 Sergey Syroezhkin
12341234463456234123466543342 Arnold Schwarzenegger
Выходные данные
John Lennon
Arnold Schwarzenegger

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

Вторая задача или задача архивации

В. Великий архиватор
Ввод/вывод: стандартный
Ограничения по времени: 1 секунда
На планете роботов очень любят автоматическую обработку текстов. Для этого роботы ввели специальную должность Великого Архиватора. В обязанности Великого Архиватора входит составление списка всех слов текста и замена слов на число, обозначающее номер этого слова в списке.
Напишите программу, выполняющую функции Великого Архиватора.
Формат входных данных:
В единственной строке входных данных приводится строка длиной не более миллиона символов, состоящая из строчных и заглавных букв английского алфавита и пробелов. Любые два соседних слова в тексте разделены ровно одним пробелом. Слова считаются одинаковыми, если они равны с точки зрения сравнения строк, причем строчные и заглавные буквы считаются различными.
Формат выходных данных:
В единственной строке выходных данных необходимо вывести последовательность номеров слов текста, причем слова в списке должны быть упорядочены в порядке их появления в тексте. Нумерация слов должна начинаться с единицы.
Примеры входных и выходных данных:
Входные данные
To be or not to be
Why do you cry Willie Why do you cry Why Willie Why Willie Why Willie Why
Выходные данные
1 2 3 4 5 2
1 2 3 4 5 1 2 3 4 1 5 1 5 1 5 1

Пояснение к примерам входных и выходных данных: текст во втором примере не содержит символов перевода строки и возврата каретки.

Достаточно простой алгоритм сжатия (не помню как называется). Мне было интересно реализовать. Я решил эту задачу созданием массива из слов, добавлял туда первое слово. Затем считывал каждое следующее слово, проверял, нет ли его в массиве. Если оно было - записывал в выходной поток номер слова, иначе - добавлял в массив, записывал номер.
В принципе, мое решение не получило полный балл.
Полный текст заданий можно найти .
На дистанционном туре я занял 1 место среди девятиклассников.

Региональный этап

Подготовка

Что делать, если Вам это тоже интересно и Вы хотите принять во всем этом участие?

1. Существуют системы подготовки школьников к олимпиадам по программированию, на них есть тестовая система и куча условий с решениями. Насколько я понимаю, на всех таких системах нужна регистрация. Я готовился при помощи двух:
   • acmp.ru Есть достаточно много задач разной сложности, так же интересен раздел «Курс олимпиадника»
   • http://acm.timus.ru/ Куча задач с самых разных олимпиад, некоторые на английском. В разделе http://acm.timus.ru/offline у нас проводился дистанционный и региональный этапы.
2. Существуют онлайн олимпиады, я участвовал лишь в одной: NetOI от украинцев. Отзыв такой: ХАРДКОР!!! Дальше второго тура не прошел. Код нужно писать ужасно оптимально (я так не умею), для каждого теста индивидуальные условия (удвоенное время программы жюри).

Что же дальше?

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

Вопрос 1. Как научиться решать олимпиадные задачи по информатике?

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

Вопрос 2. Сколько необходимо решить задач, чтобы достойно выступать на олимпиадах по информатике?

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

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

Вопрос 3. Можно ли подготовить школьников к олимпиадам по информатике в рамках школьной программы?

Думаю, что это нереально. Всем давно известно, что школьный курс информатики - это одно, а олимпиады по информатике - это совсем другое. Да, в примерной программе по информатике, в 9 классе, довольно большое количество часов уделено изучению программирования. В учебнике Семакина для 9 класса обучение программированию основано на языке Паскаль, у Угриновича примеры дана применительно к Visual Basic . Но, даже если применить дифференцированный подход к обучению школьников, вряд ли этих часов хватит для подготовки к олимпиадам отдельных школьников с "нуля".

Вопрос 4. Если часов по программе не достаточно для подготовки школьникам к олимпиадами, то как тогда готовиться?

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

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

Вопрос 5. У меня 25 (26, 30...) часов основной нагрузки, реально ли еще заниматься с учащихся на кружке по программированию?

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

Вопрос 6. Могут ли школьники готовиться к олимпиадам во внеурочное время и если могут, то как лучше организовать подготовку?

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

Вопрос 7. Что требуется от учителя для качественной подготовки школьников к олимпиаде?

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

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

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

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

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

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

одаренность

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.

Библиографическая ссылка

Подготовка школьников к олимпиаде

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

Владеть языком программирования (Pascal или Си/Си++)

1. придумывать и реализовывать алгоритмы решения задач;

2. оценивать время их работы;

3. тестировать;

4. отлаживать свои программы.

Знать следующие алгоритмы:

Алгоритмы целочисленной арифметики

1. Поиск делителей числа. Простые числа 2. Разложение числа на простые множители 3. Поиск наибольшего общего делителя (НОД) и наименьшего общего кратного (НОК) 4. Представление чисел. Выделение цифр числа 5. Перевод чисел из одной системы счисления в другую 6. Делимость чисел 7. Действия с многозначными (большими) числами

Рекуррентные уравнения и динамическое программирование

1. Понятие задачи и подзадачи

2. Понятие рекуррентного соотношения

Задачи комбинаторики

1. Перестановки

2. Сочетания

3. Размещения

4. Подмножества

5. Реализация перебора вариантов. Сокращение перебора

10-11 класс

Структуры данных

1. Очереди

Теория графов

1. Основные понятия теории графов

2. Смежность и инцидентность

3. Представление графов

4. Маршруты

5. Маршруты в графах

6. Поиск в ширину

7. Поиск в глубину

8. Исчерпывающий поиск с возвратом

9. Алгоритм построения кратчайших путей

10. Эйлеровы графы

11. Основная теорема об эйлеровом графе

12. Алгоритм построения эйлерова цикла

Сортировка

1. Понятие сортировки

2. Сортировка простым обменом

3. Квадратичные алгоритмы

4. Алгоритмы порядка n log n

5. Линейный поиск

6. Бинарный поиск

Геометрия

2. Треугольник

3. Площадь произвольного треугольника

4. Замечательные линии и точки треугольника

5. Многоугольник

6. Выпуклый многоугольник

7. Площадь простого плоского многоугольника

Рекурсия

1. Примеры рекурсивных программ.

2. Рекурсивная обработка деревьев

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

1. Если вы участвуете в турнире впервые, заранее посмотрите примеры предлагаемых на турнирных задач, например, в архивах олимпиад, представленных сайтах.

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

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

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

5. Прежде всего, вы должны уметь работать с текстовыми файлами (считывать и записывать информацию).

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

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

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

Задача. Даны целые числа A и B, по модулю не превышающие 32000. Найти их сумму.

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

Дело в ограничении на целые типы в системах программирования Borland Pascal и Borland C++, которые довольно часто используются школьниками.

Решение задачи (с разбором ошибок).

Во входном файле a.in записаны два натуральных числа, каждое из которых не превышает 32000. Числа во входном файле разделяются пробелами и (или) символами перевода строки. В выходной файл a.out вывести сумму этих двух чисел.

Кажется, любой знакомый с программированием школьник с легкостью может написать ее решение:

Задача А: Сумма двух чисел

Имя входного файла: a.in

Имя выходного файла: a.out

Ограничение по времени: 1 сек

Ограничение по памяти: 64Мбайт

Воспользуемся стандартными файловыми переменными: Input и Output.

Они автоматически закрываются после работы программы.

Переменная Input по умолчанию связана с клавиатурой, a Output - с экраном дисплея

Так как во входном файле записаны только числа, то для чтения воспользуемся командой read - она сама пропускает пробелы и переходы на новую строку

Используя процедуру ASSIGN, переназначим идентификаторы ввода-вывода INPUT и OUTPUT и укажем имя входного и выходного файла:

ASSIGN (INPUT, "a.in"); RESET (INPUT);

ASSIGN (OUTPUT, "a.out"); REWRITE(OUTPUT);

1. На диске С создадим папку С:OLIMPIAD

var a,b,c:integer;

assign(input,"a.in"); {Устанавливаем связь с файлом a.in}

reset(Input); {Открываем файл для чтения}

read(Input,a,b); {Считываем данные из файла}

assign(Output,"a.out"); {Устанавливаем связь с файлом a.out}

rewrite(Output); {Открываем файл для записи}

writeln(Output,c); {Записываем данные в файл}

2. Сохраним в ней исходник С: OLIMPIAD a.pas (Рисунок 2)

Рисунок 2. Сохранение файла с исходным кодом

3. Откроем блокнот.

4. Занесём исходные данные через пробел (Рисунок 3)

Рисунок 3. Внесение исходных данных

5. Сохраним файл с исходными данными в папке OLIMPIAD под именем a. in

6. В папке OLIMPIAD два файла: (Рисунок 4)

Рисунок 4. Вид папки №1 OLIMPIAD

7. Запускаем программу на выполнение (Рисунок 5)

Рисунок 5. Запуск программы на выполнение

8. В папке OLIMPIAD третий файл (Рисунок 6):

Рисунок 6. Вид папки №2 OLIMPIAD

9. Посмотрим результат (Рисунок 7)

Рисунок 7. Вид окна с результатом

Кажется, задача решена

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

Несколько тестов прошло. На некоторых тестах происходит ошибка во время исполнения

Так в чем же ошибки? Еще раз внимательно прочитаем условие и остановимся на ограничениях

1. Числа натуральные, не превышающие 32000.

2. Мы объявили переменные типа integer, диапазон значений переменных этого типа - от -32768 до 32767, так что кажется, что тут все правильно.

3. Однако условию удовлетворяет тест, в котором оба числа равны 32000.

4. Конечно, оба числа входят в тип integer, чего нельзя сказать об их сумме!

5. Меняя в нашей программе тип integer на тип longint получаем уже действительно полное решение задачи

6. Если сделать тип переменной c - longint, а a и b оставить типа integer, то программа работать все равно не будет - подумайте почему.

var a,b,с:longint;

assign(input,"а.in");

assign(output,"а.out");

rewrite(output);

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

Популярность крупных соревнований по информатике и программированию стремительно растет. Их спонсорами выступают такие крупные корпорации, как AT&T, Microsoft, IBM, Google. Естественно, появились исследования о том, как эффективно участвовать в соревнованиях, готовиться к ним, многочисленные советы и рассказы очевидцев

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

По такому типу в марте 2011 года проходила и первая дистанционная олимпиада (см. выше, пункт 2.5) в Казахстане.

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

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

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

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

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

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 килобайт. Формат вывода должен точно соответствовать требованиям, описанным в условии задачи.

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

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

В секции «Результаты » вы можете просмотреть статус тестирования и результаты тестирования отправленных вами задач. В строке «Время » указано время на момент сдачи решения, язык программирования который вы указали, сдавая это решение. Ссылка «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