📄Работа №205590
Тема: Исследование свойств декартова дерева при решении олимпиадных задач по программированию
Тип работы
Дипломные работы, ВКР
Предмет
математика
Объем:
107 листов
Год:
2016
Просмотров:
28
4900
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
АННОТАЦИЯ 5
Введение 6
1. Способы и методы решения задач олимпиадного программирования 7
1.1. Основные понятия и определения 7
1.2. Олимпиадное программирование 8
1.3. Подходы к решению олимпиадных задач 10
1.4. Существующая классификация задач спортивного программирования 10
1.4.1. Задачи на структуры данных 11
1.5. Двоичные деревья поиска и различные методы их балансировки 12
1.5.1. Аналоги двоичных деревьев поиска, применяемые в задачах 14
1.5.2. Разновидности декартовых деревьев 14
1.6. Выводы по первой главе 16
2. Декартовые деревья как особая разновидность двоичных деревьев поиска 18
2.1. Особенности задач на декартовые деревья 18
2.1.1. Решение задач с использованием декартовых деревьев 19
2.2. Задачи, в которых применение декартовых деревьев необходимо 19
2.2.1. Задача «Поединок с И-Так-Понятно-Кем» 19
2.2.2. Задача «Окончательная структура» 21
2.2.3. Задача «Последовательность» 24
2.3. Сравнение декартовых деревьев с аналогами в случае их применимости 26
2.3.1. Задача «Биржа» 26
2.3.2. Задача «Burek» 28
2.3.3. Задача «Snow White» 30
2.3.4. Задача «Отрезки на прямой возвращаются» 31
2.4. Выводы по второй главе 33
3. Разработка и анализ алгоритмов 34
3.1. Задача «Поединок с И-Так-Понятно-Кем» 34
3.2. Задача «Окончательная структура» 37
3.3. Задача «Последовательность» 42
3.4. Задача «Биржа» 42
3.5. Задача «Burek» 47
3.6. Задача «Snow White» 50
3.7. Задача «Отрезки на прямой возвращаются» 52
3.8. Выводы по третьей главе 54
Заключение 55
Литература 56
ПРИЛОЖЕНИЕ 1. Программная реализация разработанных алгоритмов 55
Введение 6
1. Способы и методы решения задач олимпиадного программирования 7
1.1. Основные понятия и определения 7
1.2. Олимпиадное программирование 8
1.3. Подходы к решению олимпиадных задач 10
1.4. Существующая классификация задач спортивного программирования 10
1.4.1. Задачи на структуры данных 11
1.5. Двоичные деревья поиска и различные методы их балансировки 12
1.5.1. Аналоги двоичных деревьев поиска, применяемые в задачах 14
1.5.2. Разновидности декартовых деревьев 14
1.6. Выводы по первой главе 16
2. Декартовые деревья как особая разновидность двоичных деревьев поиска 18
2.1. Особенности задач на декартовые деревья 18
2.1.1. Решение задач с использованием декартовых деревьев 19
2.2. Задачи, в которых применение декартовых деревьев необходимо 19
2.2.1. Задача «Поединок с И-Так-Понятно-Кем» 19
2.2.2. Задача «Окончательная структура» 21
2.2.3. Задача «Последовательность» 24
2.3. Сравнение декартовых деревьев с аналогами в случае их применимости 26
2.3.1. Задача «Биржа» 26
2.3.2. Задача «Burek» 28
2.3.3. Задача «Snow White» 30
2.3.4. Задача «Отрезки на прямой возвращаются» 31
2.4. Выводы по второй главе 33
3. Разработка и анализ алгоритмов 34
3.1. Задача «Поединок с И-Так-Понятно-Кем» 34
3.2. Задача «Окончательная структура» 37
3.3. Задача «Последовательность» 42
3.4. Задача «Биржа» 42
3.5. Задача «Burek» 47
3.6. Задача «Snow White» 50
3.7. Задача «Отрезки на прямой возвращаются» 52
3.8. Выводы по третьей главе 54
Заключение 55
Литература 56
ПРИЛОЖЕНИЕ 1. Программная реализация разработанных алгоритмов 55
📖 Введение
Олимпиады по программированию проводятся различными компаниями с конца XX века и успели зарекомендовать себя как способ выявить программистов, обладающих умением решать разнообразные задачи. При этом сами навыки спортивного программирования передаются от одних участников к другим, однако непосредственно умению решать задачи почти не учат, вместо этого призывая к накоплению собственного опыта, изучению теоретических основ и ознакомлению с разборами, проводимыми жюри соревнований или другими участниками.
В данной работе предполагается, что подобный подход недостаточно эффективен для быстрого и успешного решения задач, откуда следует предложение взглянуть на проблему иначе. Для исследования выбрана тема, с одной стороны достаточно редкая, чтобы участники не обладали достаточным опытом для её безошибочного распознавания, с другой — встречающаяся с достаточной частотой, чтобы у программистов имелась реальная возможность с ней столкнуться.
Такой темой оказалась структура данных, известная как декартовое (иногда также употребляется вариант «декартово») дерево, оно же трип или дерамида. Была поставлена цель определить чем задачи, в которых требуется использование этой структуры данных, отличаются от прочих. В результате выяснилось, что действительно существует такой критерий, его получение и использование описаны далее.
В данной работе предполагается, что подобный подход недостаточно эффективен для быстрого и успешного решения задач, откуда следует предложение взглянуть на проблему иначе. Для исследования выбрана тема, с одной стороны достаточно редкая, чтобы участники не обладали достаточным опытом для её безошибочного распознавания, с другой — встречающаяся с достаточной частотой, чтобы у программистов имелась реальная возможность с ней столкнуться.
Такой темой оказалась структура данных, известная как декартовое (иногда также употребляется вариант «декартово») дерево, оно же трип или дерамида. Была поставлена цель определить чем задачи, в которых требуется использование этой структуры данных, отличаются от прочих. В результате выяснилось, что действительно существует такой критерий, его получение и использование описаны далее.
✅ Заключение
В результате теоретического анализа свойств декартовых деревьев, а также других структур данных и приёмов, позволяющих решать некоторые из доступных дерамидам задач, был выдвинут критерий: трип целесообразно использовать для решения задачи тогда и только тогда, когда среди запросов одновременно имеются множественные запросы и запросы, характерные для двоичных деревьев поиска, либо присутствуют уникальные запросы декартовых деревьев, при этом саму задачу необходимо решать в режиме онлайн.
Попытки использовать критерий на практике показали, что он действительно применим и корректно отражает существующие закономерности, связывающие метод решения, время работы, объём используемой памяти и размер самой программы. В процессе были подтверждены известные результаты о соотношении эффективности рассмотренных методов, что является независимым показателем корректности проделанных выкладок.
Таким образом, принятие выдвинутого критерия гораздо более вероятно, чем его отклонение.
Попытки использовать критерий на практике показали, что он действительно применим и корректно отражает существующие закономерности, связывающие метод решения, время работы, объём используемой памяти и размер самой программы. В процессе были подтверждены известные результаты о соотношении эффективности рассмотренных методов, что является независимым показателем корректности проделанных выкладок.
Таким образом, принятие выдвинутого критерия гораздо более вероятно, чем его отклонение.
ИЛИ
Поиск аналога
📕 Список литературы
🖼 Скриншоты
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.