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

Содержание:

Содержание Введение…………………………………………………………………………………………………… 5

1 Анализ
структур данных и алгоритмов их обработки……………………………….. 7 1.1 Алгоритм Дейкстры………………………………………………………………………….. 7

2 Разработка
алгоритмов программного средства……………………………………… 11

3 Выбор языка
программирования…………………………………………………………… 13

4 Программная
реализация структур данных и алгоритмов их обработки….. 15

5 Анализ
сложности разработанных алгоритмов……………………………………….. 16

6 Тестирование
программного средства……………………………………………………. 18

Заключение……………………………………………………………………………………………… 20

Список
использованных источников…………………………………………………………. 21

Приложение А Программный код…………………………………………………………….. 22

Введение:

С каждым годом в
сети Интернет появляется все больше данных, которые необходимо обрабатывать.
Стремительная популяризация социальных сетей, онлайн карт, увеличение
количества IP адресов в сети Интернет. В связи с этим с каждым
годом становится все сложнее обрабатывать информацию, которая увеличивается в
геометрической прогрессии, вне зависимости от роста производительности вычислительных
систем необходимы еще и методы минимизации операций для обработки необходимой
информации, в связи с этим и появилась необходимость в строгой последовательности
действий над представленными данными, для минимизации тактовой сложности.
Последовательность таких действий и называется алгоритмом.

Время является основным
показателем эффективности, который мы используем для оценки алгоритма —
конечно, после тоrо, как мы показа­ ли, что алгоритм дает правильное решение.
Но это не единственная мера эффективности. Следует также учитывать, какое
количество памяти компьютера требуется алгоритму для работы, так как иначе
может оказаться, что он просто не станет работать из-за недостатка памяти в
вашем компьютере или ином устройстве. Другие возможные ресурсы, которые может
использовать алгоритм — это сетевые соединения, дисковые операции и прочее. Одним из ключевых видов алгоритмов являются приближенные
алгоритмы. Приближенные алгоритмы применяются к за­
дачам оптимизации, в которых мы хотим найти наилучшее решение в смысле некоторой
количественной меры. Одним из примеров является поиск наиболее быстрого
маршрута, для которого количественная мера представляет собой время поездки.
Для некоторых за­ дач нет алгоритма, который мог бы найти оптимальное решение
за любое разумное ко­личество времени, но при этом известен приближенный
алгоритм, который за разумное количество времени может найти решение, которое
является почти оптимальным. "Почти оптимальный" обычно означает, что
отличие количественной меры найденного алгорит­мом приближения от таковой для
оптимального решения находится в некоторых извест­ных пределах. Если мы в состоянии
указать эти пределы отличия от оптимального ре­шения, то можем говорить о том,
что корректным решением приближенного алгоритма является любое решение, которое
находится в указанных пределах.

Цель
работы: анализ
структур данных и алгоритмов их обработки,

реализация алгоритмов
обработки данных.

Для достижения цели
работы необходимо решить следующие инженерные задачи:

— рассмотреть концепцию алгоритмической задачи,
рассмотреть и понять область применения данного алгоритма;

— выполнить анализ последовательности действий, который
выполняет алгоритм и теоретически обосновать правильность его работы;

— обосновать актуальность исследования;

— выполнить сравнительный анализ алгоритмов, использующихся
в той же области;

— разработать методику исследования тестирования работоспособности
и сложности алгоритмических вычислений;

— определить требования к разрабатываемой системе
экспериментальных исследований;

— выполнить разработку архитектуры приложения системы
экспериментальных исследований, определить функциональное назначение системы;

— разработать алгоритмы приложения;

— реализовать функционал системы;

— реализовать графическое представления ввода требуемых
данных;

— разработать технологическую документацию;

— выполнить проверку времени алгоритма;

— выполнить анализ результатов эксперимента, сделать выводы,
определить дальнейшие направления развития исследования.

Заключение:

В процессе выполнения курсовой работы анализ структур данных и алгоритмов их
обработки, реализация алгоритмов обработки данных: рассмотрена концепция
алгоритмической задачи, рассмотреть и понять область применения данного алгоритма,
выполнен анализ последовательности действий, который выполняет алгоритм и практически
обосновано правильность его работы, разработана методику исследования тестирования
работоспособности и сложности алгоритмических вычислений, реализовано
графическое представления ввода требуемых данных, выполнен анализ результатов
эксперимента, сделаны выводы, определены дальнейшие направления развития
исследования.

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

Выбраны инструментальные средства разработки программного
обеспечения: PHP, интегрированная среда разработки
PHPStorm, также использовался локальный веб-сервер MAMP PRO.

Определены требования к разрабатываемой системе
экспериментальных исследований.

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

Определена минимальная конфигурация аппаратно-программного
обеспечения для функционирования системы экспериментальных исследований, разработано
руководство программиста, руководство пользователя.

Выполнено планирование эксперимента: определена цель
эксперимента, объект, предмет исследования, границы исследования, описано
используемое оборудование и программное обеспечение, входные, выходные данные,
разработана схема проведения эксперимента. В результате проведения эксперимента
выполнена проверка временной сложности алгоритма Дейкстера.

Таким образом, поставленные задачи выполнены, цель
курсовой работы достигнута.

Фрагмент текста работы:

1 Анализ
структур данных и алгоритмов их обработки

1.1 Алгоритм Дейкстры

Перед тем как рассмотреть сам алгоритм дадим
основные определения, необходимые для понимая принципа работы алгоритма.

Граф – это набор вершин (узлов) и соединяющих
их ребер (дуг). Рисунок. Граф

Направленный граф (ориентированный, орграф) –
это граф, в котором все дуги имеют направления.

Цепь
– это последовательность ребер, соединяющих две вершины(в орграфе – путь).

Цикл – это цепь из какой-то вершины в нее
саму.

Взвешенный граф (сеть) – это граф, в котором
каждому ребру приписывается вес (длина).

Связный граф – это граф, в котором существует
цепь между каждой парой вершин.

Граф называется вершинно k-связным, если
удаление любых(k-1) вершин оставляет граф связным. Рисунок вершинно 3-связный граф

Полный граф – это граф, в котором проведены
все возможные ребра (n вершин → n(n-1)/2 ребер). Рисунок. Полный граф