Олимпиады по информатике

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

С чего начинать

В первую очередь надо выбрать язык программирования. Из популярных сейчас вариантов есть C++, Python, Java, Pascal. Надо понимать при выборе, что Pascal на студенческих олимпиадах по программированию не пригодится, потому что его отменили. Python часто используется на олимпиадах, очень многих школьников учат ему, но в реальности он является интерпретатором и на нем нельзя решить все задачи, потому что он медленный. Если вы уже знаете Python, это поможет решить несколько простых задач, например, задачи с длинной арифметикой. Либо что-то быстро написать – какой-то скрипт для тестирования. Но в целом рекомендуемый язык для олимпиад по информатике – это C++.

В C++ надо знать базовый синтаксис, стандартные структуры данных в библиотеке STL, классы функций в С/C++, уметь работать со списками, векторами, Map, множествами и подобными базовыми классами. Освоить язык проще, если изучить сначала самые базовые вещи и решать самые простые задачи: ввод, преобразование данных, операторы цикла, перебор. Для начинающих лучше всего брать задачи с онлайн-архивных ресурсов – например, acm.timus.ru или с informatics.mccme.ru. Начинать лучше с тех задач, которые на платформе решили больше всего пользователей. Потом надо переходить к базовым алгоритмам, например, начать с алгоритма сортировки, двоичного поиска, простейших понятий о динамическом программировании. При подготовке важно уделять внимание самым разным темам и быть готовым ко всему. Например, если на олимпиаде дают восемь задач, то скорее всего все восемь задач будут на разные темы. Но главное – это понимать, что в информатике без серьезной математической подготовки вероятность успеха невелика.

ММатематическая подготовка

По математике нужно знать следующее: делимость, свойства делимости, представление целых чисел, геометрические задачи. Геометрия в информатике немного другая, не такая, как в школе. 90% задач по геометрии в информатике решаются через векторы. В векторном представлении формулы выглядят совсем не страшными. Можно решать задачи на e-maxx.ru, acm.mipt.ru или codeforces.com и потом участвовать в онлайн-соревнованиях.

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

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

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

Также для участия в олимпиадах надо знать динамическое программирование. Задачи на динамику будут практически в каждой олимпиаде, включая региональные. Это очень важная тема. Уметь оценивать скорость работы программы, асимптотику, растет ли скорость как сложность программы от N, растет ли как N^2 или как логарифм.

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

ЧЧто еще по математике?

Хотя в стандартной сишной (C) библиотеке сортировка есть, но все равно уметь написать алгоритмы сортировки лучше, чем за N^2. Например, знать сортировку слияния (Merge sort).

Нужно уметь решать уравнения методом двоичного поиска. Задача может звучать так: «найти корень уравнения, если известно, что в одной точке величина отрицательная, в другой – положительная». Для решения всякий раз берем середину отрезка и смотрим, поменялся ли знак в этой середине.

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

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

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

ООт теории к практике

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

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

В качестве примера разбора возьмем классическую олимпиадную задачу.

Задача B. Рыцари и лжецы

Имя входного файла: standard input

Имя выходного файла: standard output

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

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

На острове Буяне жили N человек, каждый из которых был либо рыцарем, либо лжецом. Все они встали в круг. Рыцари говорят только правду, лжецы всегда только лгут. Каждому человеку в кругу задали вопрос: «Кто ты и кто твой сосед слева: рыцарь или лжец?». При этом каждый человек сказал, что он — рыцарь. А ответы всех людей о левом соседе были записаны в следующем формате: ответ «он рыцарь» обозначался за 1, ответ «он лжец» — за 0.

Все ответы были записаны в строку через пробел в порядке опроса (совпадающем с порядком обхода). Последний спрошенный человек отвечал на вопрос о первом.

Написать программу, которая по ответам жителей определяет, какое количество рыцарей заведомо присутствует в круге.

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

Первая строка входного файла содержит число N (1 6 N 6 255) — количество жителей острова Буян. Во второй строке заданы N целых чисел ai (0 6 ai 6 1), где a_i — ответ i-го в порядке обхода жителя на вопрос о его соседе слева. Гарантируется, что входные данные непротиворечивы, то есть что как минимум одно решение всегда существует.

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

Выведите одно число — наименьшее возможное количество рыцарей среди жителей острова.

Решение: Задача B. Рыцари и лжецы

Имя входного файла: standard input

Имя выходного файла: standard output

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

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

Задача о рыцарях и лжецах — переборная. К счастью, перебор можно ограничить всего лишь двумя вариантами: первый человек — рыцарь или лжец? Предположив один из двух вариантов, можно однозначно вычислить, рыцарь или лжец следующий (так как человек с известным статусом сказал про человека слева) и так далее по индукции до первого. В процессе индукции можно считать, сколько у нас рыцарей. Когда по индукции выяснен статус первого жителя, проверяем, соответствует ли он нашему предположению. Если же соответствующих вариантов 2, то выбираем тот, в котором меньше рыцарей (то есть заведомо присутствует столько-то, а может быть, есть и больше).

ЛЛагеря по подготовке

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

Например, на базе МФТИ ежегодно проводят «Олимпиадные школы». Это университетский лагерь, где занятия ведут преподаватели российских и зарубежных вузов, а дети живут на кампусе вуза. В «Олимпиадных школах» проводятся по две пары в день: полтора часа лекции, полтора часа практики. Зависимо от уровня подготовки ребят распределяют по группам: информатика профи, информатика профи hard, информатика+математика. Там есть группы по обучению C++ с нуля, и группы, в которых учат базовые алгоритмы и готовят победителей Всероса и Межнара.

А для более продвинутых программистов проводится Зимняя компьютерная школа (или Moscow Workshops Juniors). По результатам вступительного контеста, участники делятся на три дивизиона — A, B и C. Учеба состоит из общих тренировочных занятий и тематических лекций с практикой. Причем участники самостоятельно выбирают из предложенных тем наиболее интересные и, ориентируясь на свой уровень подготовки, составляют оптимальную учебную программу. Если окажется, что дивизион слишком простой или сложный, его можно поменять. Поэтому занятия полезны для ребят разного уровня подготовки.

ССложный уровень и Межнар

После базовых знаний надо приступать к освоению более продвинутых алгоритмов. В частности, познакомиться со структурой графов, деревьями, нахождением кратчайшего пути в графе, алгоритмами Флойда, декомпозицией графов. Также надо изучить геометрию: выпуклые оболочки, решение тернарным поиском, базовая теория игр, решение алгоритмов Теории Шпрага-Гранди, решение игры-ним, ретро-анализ. Более сложное динамическое программирование – динамика на деревьях, на отрезках, динамика по профилю.

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

На сайте международной олимпиады по информатике IOI опубликован текст «IOI Syllabus» – это тематическая программа IOI, где написано, что может быть на олимпиаде, а чего не может быть. На Всеросе не будут давать задачи на темы, которых нет на Межнаре, потому что Всерос – это отборочный этап перед IOI.

УУчастие в разных олимпиадах

Самой основной олимпиадой, которая дает возможность поступления без экзаменов в любой российский вуз по специальности – это индивидуальная Всероссийская олимпиада по информатике у школьников. Есть еще командная — Всероссийская командная олимпиада школьников, но она не имеет статуса для поступления.

Как и у Всероса, первый уровень олимпиады имеет также Открытая олимпиада школьников по программированию, она проводится Московским физико-техническим институтом, Московским государственным университетом им. М.В. Ломоносова, Центром педагогического мастерства и Московским центром непрерывного математического образования. У нее есть отборочный онлайн-этап, а в марте 600 победителей приглашают в 1С для оффлайн-соревнования. В МГУ им. Ломоносова проводится еще одна олимпиада первого уровня – олимпиада школьников «Ломоносов».

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

Есть замечательная олимпиада второго уровня — «Технокубок», организованная Mail.ru Group, МФТИ, МГТУ им. Баумана и Codeforces. Третий уровень представляет Открытая олимпиада школьников по программированию «Когнитивные технологии», которую проводит «МИСиС» и МФТИ совместно с компанией Cognitive Technologies. Отбор проходит в декабре, а олимпиада в январе. Третий уровень, если он включен в список, дает определенные баллы по информатике в определенные университеты.

ССтратегия на самой олимпиаде

На Всеросе дается по пять часов на решение четырех задач на каждый из двух дней участия. На Межнаре – два дня по три задачи.

Школьные олимпиады идут с зачетом частичных решений. Всегда есть задачи, которые решить относительно просто, на них можно набрать баллы. За задачу дают максимум 100 баллов, но даже за частичное решение задачи можно получить очки. Нужно выделить время, чтобы написать даже простое решение, которое получит 10 или 15 баллов из 100. Всегда уделяйте время стратегии получения частичных баллов.

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

З

Рабочая программа по информатике 5-6 класс

http://lbz.ru/metodist/iumk/informatics/files/bosova-5-6-prog.pdf

Авторизация
*
*
Регистрация
*
*
*
Генерация пароля
ПОЗВОНИТЕ МНЕ
+
Жду звонка!