Центр поддержки одаренных детей ХКИРО

Всем снова привет!

Вот я уже в 11 классе, за 4 года обучения программированию(это и написание кода, и стиль, и просто изучение языка программирования) уже накопилось большое количество материала. Я занимаюсь 2 года олимпиадной информатикой. За последний год накопилось очень большое количество материала, который еще стоить освоить, но благо уже часть воспринята мной.

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

Для начала вы должны усвоить: практика, практика и еще раз практика. Вы не научитесь писать код, если не будете его писать. Чем больше вы решаете задач, чем больше вы познаете новых приемов решения, новых методов языка, тем большая вероятность победить на олимпиаде или даже просто похвастаться друзьями!

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

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

1. Т. Кормен - "Алгоритмы. Построение и анализ" - эту книгу уже стоит читать более менее подготовленному человеку, потому что теория там не очень простая и все алгоритмы на языке программирования придется в основном писать самим, т.к. там дается только псевдо алгоритмический язык.
2. А. Шень - "Программирование. Теоремы и задачи" - название книги говорит само за себя, но очень хороший сборник, в котором показываются порой нетрадиционные методы решения задач.
3. С. Окулов - "Программирование в алгоритмах" - отличная теория совмещенная с решением задач.
4. И. Н. Порублев - "Алгоритмы и программы. Решение олимпиадных задач" - аналогично книжке С. Окулова, правда есть и другие темы, а некоторых нет.
5. Ф. Меньшиков - "Олимпиадные задачи по программированию" - очень хорошие задачи, сначала идут просто условия, а потом детальное решение каждой задачки.

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

Теперь по поводу интернет-источников:

1. Codeforces - великолепный сайт, практически на каждой неделе проходят соревнования среди программистов. Это очень хорошая практика для олимпиадников, знаю многих людей, победителей финального этапа ВсОШ, которые стали таковыми благодаря этому сайту. Там есть архив задач, решение которых вы можете отправлять в автоматическую систему проверки. Вам выйдет информация о том, на каком тесте у вас идет ошибка, какие решения вы не учли, или же то, что у вас правильное решение. Также можно посмотреть чужие решения, что очень ценно, т.к. другие люди могут решить данную задачу рациональнее вас. Еще ресурс хорош тем, что условия проведения контестов (так соревнования у программистов-олимпиадников называются) практически такие же, как и на настоящей олимпиаде.
2. Дистанционная подготовка по информатике - отличный сайт с огромным количеством теории и задач, которые вы тоже можете отправить на автоматическую проверку.
3. Школа программиста - сайт, на котором вы можете решать задания и отправлять их в автоматическую систему.
4. E-maxx - сайт, на котором вы можете увидеть реализацию алгоритмов (правда все реализовано на С++)

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

Итак, с олимпиадами разобрались. Теперь остается вопрос: "На чем же писать?" Тут предпочтение у каждого свое. Кто пишет на С++, кто на Pascal, кто на Python. В любом случае, выбор остается за вами, но порекомендую я вам все же первый вариант. С++ очень удобный язык программирования, хоть и по началу сложный. Но начинать надо с Pascal. как только поймете, что значит программировать, для чего нужны переменные, массивы и т.д., то можете смело переходить на С++. Pascal хорошо знать потому что в большинстве книг примеры написаны именно на нем.

По поводу Pascal я могу порекомендовать поискать что-то в интернете или, что намного лучше, обратиться к вашему учителю информатики.

А вот по С++ есть парочка книг:

1. Г. Шилдт - "С++ Базовый курс" - именно с этой книги я начал своё изучение и ни капли не пожалел об этом.
2. Б. Страуструп - "Язык программирования C++" - книга от автора языка программирования, лучше увлечься ей после прочтения первой книги, т.к. материал преподносится на более высоком уровне.
3. Л. Аммерааль - "STL для программистов на C++" - замечательная книга, которая упрощает во многом жизнь каждого олимпиадника. Знакомиться начинать желательно после прочтения хотя бы одной из двух первых книг.

Отлично. В общем-то я обо всем рассказал. Забыл упомянуть только примерный список того, что желательно знать олимпиадникам. Прошу только не пугайтесь этого списка, на самом деле все вещи из него реально выучить. Просто нужно время и желание. Итак:

1. Обход в ширину, поиск кратчайших расстояний в невзвешенном графе
2. Обход в глубину
3. Выделение компонент связности
4. Выделение мостов, точек сочленения, компонент реберной и вершинной двусвязности
5. Топологическая сортировка
6. Топологическая сортировка за O(N)
7. Выделение компонент сильной связности, конденсация графа
8. Алгоритм Дейкстры
9. Алгоритм Флойда
10. Алгоритм Форда-Беллмана
11. Алгоритм Прима
12. Алгоритм Краскала
13. Построение эйлерова цикла в графе
14. Длинное сложение, вычитание
15. Длинное умножение
16. Длинное деление и извлечение корня
17. Алгоритм Карацубы
18. Перебор всех подмножеств данного множества
19. Быстрый перебор подмножеств заданной мощности данного множества
20. Быстрая генерация i-ой в лексикографическом порядке перестановки из N элементов
21. Быстрая генерация i-ой в лексикографическом порядке правильной скобочной последовательности из N пар скобок
22. Скалярное, векторное, смешанное произведения векторов
23. Нахождение площади многоугольника
24. Расстояние от точки до прямой
25. Нахождение точки пересечения двух прямых
26. Проверка пересечения отрезков
27. Нахождение выпуклой оболочки
28. Динамическое программирование: задача о рюкзаке
29. Динамическое программирование: наибольшая возрастающая подпоследовательность
30. Динамическое программирование: общие принципы
31. Метод рекурсивного спуска
32. Польская инверсная запись, алгоритм построение по выражению
33. Конечные автоматы, регулярные выражения
34. Контекстно-свободные грамматики, проверка принадлежности слова КС-языку
35. Коды Хаффмана
36. Алгоритм Кнута-Морриса-Пратта
37. Бор. Алгоритм Ахо-Корасик
38. Ab-отсечение, перебор с возвратом
39. Функция Гранди
40. Бинарные деревья, хранение в массиве
41. AVL-деревья
42. RB-деревья
43. Декартовы деревья
44. Нахождение наименьшего общего предка в дереве
45. Алгоритм Джонсона
46. Построение гамильтонова цикла в графе
47. Построение максимального паросочетания в двудольном невзвешенном графе
48. Венгерский алгоритм решения задачи о назначениях
49. Поиск максимального потока
50. Матрицы: определитель, обратная матрица, матричное произведение
51. Метод Гаусса решения систем уравнений
52. Дискретное преобразование Фурье
53. Дерево интервалов и его реализация
54. Динамическое дерево Тарьяна-Слейтора
55. Хэш-таблицы
56. Системы непересекающихся множеств
57. Обобщенный алгоритм Евклида, решение диофантовых уравнений
58. Метод шифрования RSA
59. Суффиксное дерево. Алгоритм Укконена.
60. Суффиксный массив. Построение без суффиксного дерева
61. Преобразование Бэрроуза-Уилера
62. Красно-черные деревья
63. Sqrt-декомпозиция
64. Дерево Фенвика
65. Дерево отрезков
66. Битово-индексированные деревья
67. Быстрая сортировка
68. Пирамидальная сортировка
69. Факторизация числа

Знаю ли я всё, что там написано? Не всё, но до края попытаюсь выучить.

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

Дорогие учителя и ребята! Если у вас есть дополнения или же замечания, напишите, пожалуйста, в комментарии! Я добавлю в запись или откорректирую!

P. S. Прошу за мой некрасивый стиль изложения мыслей, может где-то я ошибся, не поставил запятую. Только не ругайте
P. P. S. Забыл совсем написать слова благодарности!!! Спасибо большое Линник Людмиле Михайловне - моей учительнице по информатике, Пономарчук Юлии Викторовне и Сухобок Юрию Андреевичу - моим наставникам в олимпиадном движении! Они многому меня научили! И ЦПОД за то, что создал условия для подготовки к олимпиадам!
P. P. P. S. Мои контактные данные: почта: toxa.dj@mail.ru, или просто найдите меня в Вконтакте: vk.com/toshik_pro . Пишите мне, если есть вопросы, буду рад помочь!