Про питання підготовки до олімпіади з інформатики

Зараз мова піде про те, як все-таки готується до олімпіади. Взагалі, підготовка до олімпіад з інформатики полягає у 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 - дуже великий архив задач
brtrg.com - змагання 
cppreference.com - опис функцій і бібліотек С++
cplusplus.com - опис функцій і бібліотек С++
codeforces.ru - сайт по програмуванню 
g6prog.narod.ru - сайт з розборами деяких задач
acm.timus.ru - сайт з великою кількістю задач
uva.onlinejudge.org - архів задач
spoj.pl 
e-olimp.com - архів задач та регулярно проводяться олімпіади