Перечень вопросов для подготовки к муниципальному (межлицейскому) этапу олимпиад
Задания, предлагаемые на муниципальном (межлицейском) этапе олимпиад, составляются, исходя из того, чтобы уровень хотя бы 30% из всех заданий не превышал тот, который рекомендован для школьного (лицейского) этапа.
Участник должен знать:
• методы анализа правильности алгоритма;
• позиционные системы счисления;
• понятие вычислительной и емкостной сложности алгоритма;
• способы построения и определения в языке программирования сложных структур данных;
• определение рекурсивных функций;
• методы оптимизации кода программы.
Участник должен уметь:
· сравнивать различные алгоритмы и методы обработки структур данных по их производительности;
· анализировать результаты выполнения алгоритмов, собственные ошибки при выполнении задач;
· тестировать и отлаживать алгоритмы и программы;
· работать с проверяющей системой (отправка решений, получение и учет результата проверки);
· использовать метод динамического программирования с функцией от 1 параметра.
Основные структуры данных:
• массив;
• список;
• стек;
• очередь;
• двухсторонняя очередь;
• куча;
• множество.
Основные алгоритмы:
• перевод чисел из одной системы счисления в другую;
· расширенный алгоритм Евклида: решение диофантовых уравнений, восстановление числа по остаткам;
· двоичный поиск;
· метод двух указателей (слияние двух упорядоченных массивов);
|
|
|
· эффективные методы сортировки (пирамидальная, слияниями, быстрая сортировка);
· особые случаи сортировки (сортировка подсчетом, цифровая (поразрядная) сортировка);
· нахождение медианы (порядковых статистик);
· длинная арифметика (сложение, вычитание многозначных чисел, умножение многозначного числа на однозначное);
• вычисление расстояния между точками;
• вычисление углов между векторами;
· проверка принадлежности точки прямой, вычисление расстояния от точки до прямой;
• проверка пересечения двух отрезков;
• позиционирование точки относительно многоугольника;
• вычисление площади многоугольника;
• рекурсивный перебор с возвратом;
• подсчет количества комбинаторных объектов.
Перечень вопросов для подготовки к заключительному этапу олимпиад
Задания, предлагаемые на заключительном этапе олимпиад, составляются, исходя из того, чтобы уровень хотя бы 30% из всех заданий не превышал тот, который рекомендован для районного (межлицейского) этапа. Формулировки некоторых заданий могут допускать использование терминологии, не входящей в школьный курс по математике, информатике или другим дисциплинам, но с обязательным разъяснением соответствующих терминов в тексте условия.
|
|
|
Основные структуры данных:
• двусвязные и кольцевые списки;
• деревья;
• двоичные деревья;
• деревья поиска, красно-черные деревья;
• нагруженное дерево (бор);
• множество, отображение;
• хеш-таблица;
• семейство непересекающихся множеств.
Основные алгоритмы:
• умножение многозначных чисел;
• деление многозначных чисел;
• обход дерева (прямой, обратный, симметричный)
· поиск в глубину, проверка связности, наличия циклов, топологическая сортировка;
· поиск в ширину;
· нахождение кратчайших путей (алгоритмы Дейкстры, Беллмана-Форда, Флойда-Уоршолла);
· нахождение минимального остовного дерева (алгоритмы Прима, Краскала);
· построение эйлерова пути (цикла);
· построение гамильтонова пути (цикла);
· поиск подстроки в строке (алгоритмы Кнута-Морриса-Пратта, Бойера-Мура, Рабина-Карпа);
· метод динамического программирования с 2 и более параметрами;
· динамическое программирования на подстроках, на подмножествах.
· построение выпуклой оболочки (метод Грехема, метод Джарвиса);
• метод заметающей прямой;
· порождение комбинаторных объектов (перестановки, подмножества);
• анализ игр.
список литературы для подготовки обучающихся к Республиканской олимпиаде
|
|
|
1. Анисимов А.Е. Практикум по основам программирования: учебно-методическое пособие / А.Е. Анисимов. – Ижевск: Изд-во «Удмуртский университет», 2014. – 95 с.
2. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – Москва: Вильямс, 2000.
3. Бондарев В.М., Рублинецкий В.М., Качко Е.Г. Основы программирования. – Харьков: Фолио. Ростов-на-Дону: Феникс, 1997.
4. Брудно А.Л., Каплан Л.И. "Московские олимпиады по программированию" – Москва: Наука, 1990.
5. Вирт Н. "Алгоритмы + структуры данных = программы" – Москва: Мир, 1985.
6. Грехем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. – М.: Мир, 1998. – 703 с.
7. Дасгупта С. и др. Алгоритмы / С. Дасгупта, Х. Пападимитриу, У. Вазирани; Пер. с англ. под ред. А. Шеня. – М.: МЦНМО, 2014. – 320 с.
8. Дейкстра Э. Дисциплина программирования. – М.: Мир, 1978.
9. Ершов А.П., Монахов В.М., Бешенков С.А. и др. Основы информатики и вычислительной техники. – Москва: Наука, 1988.
10. Златопольский Д.М. Программирование: типовые задачи, алгоритмы, методы [Электронный ресурс] / Д.М. Златопольский. – 3-е изд. (эл.). – М.: БИНОМ. Лаборатория знаний, 2015.
11. Кирюхин В.М. Методика решения задач по информатике. Международные олимпиады / В.М. Кирюхин , С.М. Окулов. – М.:БИНОМ. Лаборатория знаний, 2007. – 600 с.
|
|
|
12. Кнут Д.Э. Искусство программирования. Том 1. Основные алгоритмы / под ред. С.Г. Тригуб, Ю.Г. Гордиенко и И.В. Красикова. – Москва: Вильямс, 2002. – Т.1. – 720 с.
13. Кнут Д. Э. Искусство программирования. Том 2. Получисленные алгоритмы / под ред. Л.Ф. Козаченко, В.Т. Тертышного и И.В. Красикова. – Москва: Вильямс, 2001. – Т.2. – 832 с.
14. Кнут Д. Э. Искусство программирования. Том 3. Сортировка и поиск / под ред. В.Т. Тертышного и И.В. Красикова. – 2-е изд. – Москва: Вильямс, 2007. – Т.3. – 832 с.
15. Кнут Д. Э. Искусство программирования, том 4, A. Комбинаторные алгоритмы, часть 1 / под ред. Ю.В. Козаченко. – Москва: Вильямс, 2013. – Т.4. – 960 с.
16. Кристофидес Н. Теория графов. Алгоритмический подход. – Москва: Мир, 1978.
17. Липский В. Комбинаторика для программистов. – Москва: Мир, 1988.
18. Меньшиков Ф.В. Олимпиадные задачи по программированию. – СПб: Питер, 2006. – 315 с.
19. Новиков Ф.А. Дискретная математика для программистов. – Санкт-Петербург: Питер, 2001.
20. Окулов С.М. Основы программирования [Электронный ресурс] / С.М. Окулов. – 6-е изд., перераб. (эл.). – М.: БИНОМ. Лаборатория знаний, 2012. — 336 с.
21. Окулов С.М. Программирование в алгоритмах / С.М. Окулов. – М.: БИНОМ. Лаборатория знаний, 2002. — 341 с.
22. Задачи по программированию [Электронный ресурс] / С.М. Окулов; под ред. С.М. Окулова. – 3-е изд. (эл.). – М.: Лаборатория знаний, 2017.
23. Пападимитриу Д., Стайглиц К., Комбинаторная оптимизация. Алгоритмы и сложность. – М.: Мир, 1984.
24. Порублев И.Н., Ставровский А.Б. Алгоритмы и программы. Решение олимпиадных задач. – М.: ООО «И.Д. Вильямс», 2007. – 480 с.
25. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. теория и практика. – М.: Мир, 1980. – 476 с.
26. Савченко B.C. Разработка алгоритмов: от простого к сложному. – Донецк, 1996.
27. Скиена С.С., Ревилла М.А., Олимпиадные задачи по программированию. Руководство по подготовке к соревнованиям. – М.: КУДИЦ-ОБРАЗ, 2005. – 416 с.
28. Уилсон Р. Введение в теорию графов. – Москва: Мир, 1977.
29. Фролов М.И. Учимся программировать на компьютере : Логич. и компьютер. сказки : Самоучитель для детей и родителей / М.И. Фролов. – М.: Лаб. Базовых Знаний, 2002. – 188 с.
30. Шень А.Х. Программирование: теоремы и задачи. – 6 изд., дополненное. – М.: МЦНМО, 2017. – 320 с.
Дата добавления: 2020-11-15; просмотров: 95; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!