Введение 7
1 Анализ предметной области 8
1.1 Алгоритмы решения задач спортивного программирования 8
1.2 Классификация алгоритмов решения задач спортивного
программирования 9
1.3 Сравнительный анализ программных продуктов-аналогов 11
1.3.1 Стандартная библиотека шаблонов C++ 11
1.3.2 Библиотека алгоритмов emaxx algo 13
1.3.3 Competitive Programming Library 13
1.4 Постановка задачи на разработку программных средств для решения
задач спортивного программирования 14
1.5 Анализ требований к программным средствам 15
1.5.1 Анализ функциональных требований 15
1.5.2 Анализ нефункциональных требований 20
1.6 Технологии и средства разработки 20
2 Проектирование алгоритмов и программ решения олимпиадных
задач спортивного программирования 21
2.1 Проектирование алгоритмов и структур данных для решения задач
на подотрезках массива 21
2.2 Проектирование дерева отрезков 22
2.3 Проектирование алгоритмов для решения задач на графах 25
2.4 Проектирование суффиксного автомата 28
3 Реализация и тестирование алгоритмов и программ решения
олимпиадных задач спортивного программирования 32
3.1 Реализация программных средств 32
3.2 Тестирование программных средств 34
3.2.1 Функциональное тестирование 34
3.2.2 Структурное тестирование 37
3.2.3 Модульное тестирование 39
3.3 Анализ качества кода 40
3.4 Планирование разработки и оценка бюджета 43
Заключение 46
Список использованных источников 47
Приложение А Глоссарий 49
Приложение Б Листинг программы 52
Приложение В Результаты тестирования 73
Приложение Г Исходный код модульного тестирования 78
Спортивное (или олимпиадное) программирование - интеллектуальное соревнование по решению различных задач на ЭВМ, для решения которых необходимо придумать и применить какой-либо алгоритм или программу на одном из языков программирования [1].
Спортивное программирование - это перспективный интеллектуальный вид спорта. В настоящее время задачи по спортивному программированию набирают все большую популярность. Решение таких олимпиадных задач позволяет расширять знания по математике, алгоритмам, языкам программирования, а также совершенствоваться в написании эффективных программ в условиях ограниченного времени. Рост популярности олимпиадного программирования положительно влияет на другие сферы жизнедеятельности человека. Алгоритмы, которые применяются для решения задач олимпиадного программирования, применяются при разработке сложных программ [2].
Особенностью алгоритмов спортивного программирования является их эффективность. Для решения задачи необходимо не только разработать правильную программу, но и создать ее таким образом, чтобы время работы программы и используемая память укладывались в ограничения. Алгоритмы, которые были разработаны для решения олимпиадных задач, часто могут быть использованы в промышленном производстве при создании высоконагруженных систем.
Целью выпускной квалификационной работы является разработка алгоритмов и программ решения олимпиадных задач спортивного программирования. Разработка включает в себя анализ требования, этапы проектирования, реализации и тестирования программных средств.
Алгоритмы, разработанные в рамках выпускной квалификационный работы, можно будет применять для решения задач в различных онлайн соревнованиях или использовать при разработке программ для обработки больших объемов данных.
В ходе выполнения выпускной квалификационной работы разработана библиотека алгоритмом и программ решения олимпиадных задач спортивного программирования.
Проведен анализ алгоритмов решения задач спортивного программирования, рассмотрены задачи спортивного программирования и охарактеризованы алгоритмы их решения. Алгоритмы решения задач спортивного программирования классифицированы. На основе сравнения имеющихся аналогов и требований к заданию сформулирована задача на разработку программного средства, а также определены функциональные и нефункциональные требования к системе.
Для решения поставленной задачи спроектированы и реализованы алгоритмы и структуры данных для решения олимпиадных задач на подотрезках массива, на графах и задач на обработку строк. Необходимые структуры данных представлены в виде классов.
Разработка программных средств проводилась в среде разработки CLion на языке программирования C++. Разработанная программа функционирует, как под управлением операционной системы Linux (Ubuntu 18.04), так и под управлением Windows 10.
Разработанное программное обеспечение протестировано. Выполнено функциональное тестирование, структурное тестирование и модульное тестирование при помощи библиотеки Catch. Все тесты пройдены успешно и в результате тестирования не было выявлено ошибок.
В ходе выполнения выпускной квалификационной работы проведено планирование и оценка бюджета разработки при помощи программы для управления проектами Microsoft Project. Затраты на проект составили 45304 рубля. Время разработки составило 27 рабочих дней.
Таким образом в результате выполнения выпускной квалификационной работы разработаны алгоритмы и программы решения олимпиадных задач спортивного программирования, которые удовлетворяют всем требования технического задания.
