Всем снова привет!
Вот я уже в 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 . Пишите мне, если есть вопросы, буду рад помочь!
Алексей Левичев
14 мая 2014
-1
В свете событий на Украине, ее власти, стремительно пытаются доказать народу, что они суверенная страна, со своим языком и историей. Что же, давайте проверим их аргументы, и действительно ли украинский народ незалежен.
Украины считают, что раз их язык древний, значит и этнос древний, а россияне - помесь финских туземцев и монгольских завоевателей, перенявших у древних украинцев все культурные достижения, а потом объявившие их своими.
В основном украинцы сравнивают свой язык с древнеславянским, но возникает вопрос: откуда филологи знают, каким был древний славянский язык. Гипотетически представление об этом языке могли бы дать письменные памятники, но их нет. В любом случае все они носят религиозный характер и писаны не живым, а КНИЖНЫМ церковно-славянским языком, который по официальной версии является адаптированным греками для диких восточных славян канцелярским болгарским письмом. Католики пользовались латынью. Даже если вы найдете церковный документ X века, вы ничего не сможете по нему сказать об итальянском или фламандском языке того времени. Вот и объясните, граждане украинцы, какой такой славянский язык вы сравниваете с сегодняшним украинским языком? Источником сведений о живом языке могут быть исключительно бытовые письменные источники. Где они? Да, я понимаю, что вопрос бессмысленный, потому что от эпохи, в которую грамотным был 1% населения, а в качестве "информационных носителей" применялась береста, ничего дойти не может.
Или вот еще очень смешной аргумент: укромовники утверждают, что раз украинский язык ближе, например, к чешскому, чем русский, то он более древний. Попробуйте найти в этом утверждении хоть крупицу здравого смысла! Чешский язык очень молодой, и создан он ИСКУССТВЕННО в начале XIX веке немцами. Ну, то есть чехами, конечно, но городские чехи в начале позапрошлого века говорили по-немецки, это был их родной язык. И вот группа немецкоговорящих интеллигентов взялась вернуть нации забытый язык. Вспомнить можно лишь то, что знал, а то, что давно бесследно кануло в лету, вспомнить чистой воды реконструкцией. Собрали слова по деревням, сформулировали законы словообразования и сочинили недостающие слова (неологизмы составили подавляющую часть всей лексической массы, ибо бытовая речь крестьян очень бедна).
Искусственность языка отлично видна хотя бы потому, что обычно литературный язык возникает на базе одного, наиболее распространенного диалекта, а чешский создавался путем механической компиляции всех диалектов, чтоб, значит, никому не было обидно. Йозеф Добровский с нуля разработал грамматику (весьма сложную именно из-за смешения разных диалектов), причем издал свой труд на немецком языке, что вполне логично: чешского литературного языка еще не существовало. Модным в то время стало менять себе привычные немецкие имена Карл, Франц, Густав на имена на искусственно сгенерированные - Судиправ, Любомир, Добромила, Спытигнев и т.д., к немецким фамилиям прибавляли окончания "ов" или "овский".
В связи с созданием чешского литературного языка, что называется, в лабораторных условиях, можно отметить множество любопытных курьезов. Например, французское слово "журнал" по-чешски звучит очень славянофильски - "часопис". Почти как "летопись". Но можно ли на этом основании утверждать, что чешский язык очень древний? Нет, потому что мы имеем дело с совершено искусственной архаизацией языка, когда лингвистически "удревняются" понятия, возникшие совсем недавно. В настоящее время в Чехии параллельно существует как бы два языка - литературный и разговорный. На литературном не общаются в быту даже профессора чешской филологии - до того он сложен и громоздок - 13 склонений и 13 спряжений, в то время, как в очень близком словацком 3 и 3 соответственно.
Почему же украинский и чешский языки схожи? Потому что создавались по схожим лекалам. Правда, при создании украинского языка был задействован принцип, нужды в котором не было у чехов - обеспечить максимальное расхождение между новоязом и русским языком, так, чтобы украинец и русский не могли понять друг друга пи встрече. Делалось это довольно примитивно. Например, в русском языке слово "галстук" является заимствованным из немецкого. Следовательно вводят в оборот слово "краватка", заимствуя его из французского cravat. То есть еще 100 лет назад никакого "древнего" украинского языка просто не существовало, точнее, существовало два враждебных лагеря, пропагндирующих разный языковой канон собственного изготовления. Широкие слои городского населения в "украинских" городах было абсолютно равнодушно к вражде этих двух группировок. Единый украинский язык был внедрен в массовое сознание только в ходе самой агрессивной и масштабной украинизаторской кампании - в 20-30е годы в СССР. Ну, понятно, если учредили Украинскую ССР, то и украинцев пришлось создавать.
Продолжение следует...