Этот блог посвящён олимпиадному программированию.Если вы хотите узнать, что это такое и с чем его едят - милости просим.Если вы хотите чему-то научиться, что-то дополнить - добро пожаловать!
В данном блоге я буду стараться рассказать про особенности спортивного программирования.Также расскажу о различных типах задач и, конечно, алгоритмах.
В данном блоге я буду стараться рассказать про особенности спортивного программирования.Также расскажу о различных типах задач и, конечно, алгоритмах.
Как готовиться к олимпиадам
| Сейчас речь пойдет о том, как всё-таки готовится к олимпиаде.Вообще, подготовка к олимпиадам по информатике заключается в 2 китах - теория и практика. Вы должны очень хорошо знать математику, также Вы должны знать множество алгоритмов и место их применения.Всё это нужно учить.И учить придется очень много.Это теория. Что насчёт практики - вы должны постоянно решать задачи.Решать, разбирать, снова решать, опять решать, без перерыва.Чувствуете, что что-то подзабыли? Решайте задачу на эту тему.Будьте постоянно в форме.На каждый алгоритм нужно нарешивать много задач, чтобы он закрепился. Я рекомендую вести файл, в котором вы будете записывать уже изученные алгоритмы, и папку, в которой будут исходники этих алгоритмов.Если что-то надо вспомнить - глянули в папку и освежили память.Это очень удобно. Также было бы очень хорошо иметь единомышленников и олимпиадников сильнее, чем вы.Чтобы было у кого учиться. Было бы замечательно обучаться у хорошего тренера.Надо стараться участвовать во всех сборах.Вот залог успеха. Я в Интернете находил план подготовки к олимпиаде.Вот он: Раздел 1. Математические основы программирования Раздел 2. Техника программирования 1. Основы языка программирования (Паскаль, Си) Переменные и простейшие типы данных, размеры типов. Линейные программы. Условные операторы. Циклы. Процедуры и функции. Сложные типы данных (массивы, строки, записи, указатели, файлы). 2. Массивы Одномерные массивы. Двумерные массивы (матрицы). Многомерные массивы. 3. Строки. Элементы лексического и синтаксического разбора Операции над строками. Лексемы, подсчет лексем различных типов. Выделение чисел из строки. 4. Работа с файлами Чтение и запись в текстовый файл. Преобразование полученных из файла данных в удобную структуру. Работа с типизированными файлами. Нетипизированные файлы. Буферизация ввода. 5. Рекурсия Математические функции, задаваемые рекурсивно. Примеры рекурсивных подпрограмм. Проблема остановки рекурсии. Замена рекурсии итерацией. 6. "Длинная" арифметика Хранения в программе чисел, которые не вмещаются в стандартные типы. Арифметические операции над "длинными" числами. "Длинные" числа с десятичной частью. Извлечение корня с заданной точностью. 7. Хранение информации в динамической памяти. Хранение набора данных в линейных списках. Вставка в список, удаление из списка, поиск элемента в списке. Двусвязные списки. Понятия структур данных стека, кольца, очереди, дека; реализация их с помощью динамической памяти. Двоичные деревья. Деревья с неопределенным числом потомков. Хранение больших массивов. Раздел 3. Алгоритмы, методы и принципы решения задач 1. Понятие сложности алгоритма. Определение сложности. Классы задач P и NP. NP-полные задачи. 2. Алгоритмы поиска и сортировки Поиск элемента в неупорядоченном массиве. Двоичный поиск по ключу в упорядоченном массиве (дихотомия). Поиск методом Фибоначчи. Поиск в упорядоченном n-мерном массиве. Поиск k-го по величине элемента массива. Простые методы сортировки ("пузырек", "выборка", "вставка", "подсчет"). Быстрые методы ("быстрая", "слиянием", "пирамидальная"), балансировка двоичных деревьев. Сортировка методом черпака. 3. Решение задач методом перебора вариантов Применение рекурсии для перебора. Генерация сочетаний, размещений, перестановок и булеана множества. Полный перебор. Отсечение вариантов (эвристики). Метод ветвей и границ. 4. Вычислительная геометрия и численные методы Длина отрезка. Уравнение прямой. Скалярное и векторное произведение. Точка пересечения отрезков. Принадлежность точки фигуре на плоскости (например: треугольнику). Площадь выпуклого многоугольника. Выпуклая оболочка множества точек: алгоритмы Грэхема, Джарвиса, "разделяй и властвуй". Ближайшая пара точек. Метод Гаусса для решения системы линейных уравнений. Нахождение решения уравнения. 5. Принцип динамического программирования Понятие, применимость. Сравнение с перебором. 6. Жадные алгоритмы Понятие, применимость. Сравнение с перебором и динамическим программированием. 7. Теория графов. Алгоритмы на графах Понятие графа. Определения теории графов. Структуры данных для представления графа в программе. Алгоритмы обхода графа (поиски в ширину и глубину). Лабиринт (метод волны). Эйлеров цикл. Кратчайший путь во взвешенном графе (алгоритмы Дейкстры и Минти). Транзитивное замыкание графа (алгоритм Флойда-Уоршилла). Минимальное остовное дерево (алгоритмы Прима и Краскала). Топологическая сортировка графа. Потоки в сетях (алгоритм Форда-Фалкерсона). Паросочетания в двудольном графе (метод удлиняющей цепочки, потоковое решение). Задача о назначениях, назначения на узкое место (венгерский алгоритм). Игры на графах. Раскраска графа. Уложение графа на плоскости. Сильная связность и двусвязность графа. Изоморфизм графов. K-клика. Гамильтонов цикл. 8. Лексический и синтаксический анализ Задача "Калькулятор". Синтаксические диаграммы. Формы Бэкуса-Наура. Стековая и рекурсивная модель синтаксического разбора. Конечные автоматы. Грамматики. 9. Задачи с "изюминками" Раздел 4. Олимпиады по информатике 1. Правила проведения олимпиад по программированию 2. Типичные ошибки и отладка программ 3. Приемы олимпиадчика Как видите, обьём, который нужно изучить, достаточно велик.Но всё это со временем учится и отрабатывается. Но когда рядом нет тренера или друзей-олимпиадников, то как готовится?Нужны опять же теория и практика.И тут к нам на помощь приходят книги и сайты нужной нам тематики. Список книг(ссылки давать не буду, вы их и так спокойно найдете): Алгоритмы.Построение и анализ. Кормен - очень хорошая книга.В ней подробно описываются алгоритмы Сборник статей вычислительная геометрия на плоскости Андреевой - по геометрии Вычислительные машины и труднорешаемые задачи. Гэри - тоже неплохая книга по алгоритмам Сборник лекций Михаила Густокашина - хорошо описаны структуры данных и некоторые алгоритмы(только С++) Искусство программирования Кнут - великое произведение по теории алгоритмов Комбинаторика для программистов Липский - книга по комбинаторике Комбинаторная оптимизация.Алгоритмы и сложность Стайглиц - понятно из названия, о чём книга Конкретная математика Грэхэм - очень хорошая книга по математике Перечисление графов Харари - книга по графам(не читал, руки ещё не дошли) Программирование в алгоритмах Окулов - очень хорошая книга Решение сложных олимпиадных задач по программированию Долинский - разбор различных задач.рекомендую к прочтению Фундаментальные алгоритмы С++ Седжвик - хорошая книга по алгоритмам Строки, деревья и последовательности в алгоритмах Гэсфилд - тоже можно почитать. Теперь разберемся с сайтами: e-maxx - очень хороший сайт с множеством алгоритмов.Очень рекомендую algolist.manual.ru - неплохой сайт с алгоритмами habrahabr.ru - да-да, и там проскакивают интересные статьи olimp.bstu.by - контесты(можно задачи порешать) informatics.mccme.ru - очень большой архив задач, также есть теория dl.gsu.by - очень большой архив задач acmp.ru - неплохой архив задач и есть теория brtrg.com - регулярные соревнования и в блоге теорию можно почитать cppreference.com - описание функций и библиотек С++ cplusplus.com - описание функций и библиотек С++ codeforces.ru - очень хороший сайт по программированию (кстати, под ником tourist(№1 в рейтинге) гена Короткевич=) ) g6prog.narod.ru - сайт с разборами некоторых задач acm.timus.ru - сайт с большим кол-вом задач uva.onlinejudge.org - хороший архив задач, но по большей части для ACMщиков spoj.pl - тоже хороший архив e-olimp.com - архив задач и регулярно проводятся олимпиады Ну, думаю этого пока хватит.Есть ещё и сайты, и книги.Но для подготовки этого вполне хватит. |
Всего комментариев 2
Комментарии
-
добавлю свои 5 копеек
uva.onlinejudge.org - хороший архив задач, но по большей части для ACMщиков
spoj.pl - тоже хороший архив
e-olimp.com - архив задач, и регулярно проводятся олимпиады, какраз сейчас есть серия олимпиадЗапись от dr.curse размещена 26.05.2013 в 23:23 
-
О, спасибо!Сейчас добавлю.Запись от ZaMaZaN4iK размещена 27.05.2013 в 02:07
