Реализация и исследование параллельных алгоритмов для решения задачи О Р-медиане

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное автономное образовательное учреждение
высшего образования

«Южно-Уральский государственный университет»

(национальный исследовательский университет)

Высшая школа электроники и компьютерных наук

Кафедра системного программирования







РАБОТА ПРОВЕРЕНА

Рецензент

<ученая степень, ученое звание>

__________<И.О. Фамилиярецензента>

“___”___________ 2018 г.

ДОПУСТИТЬ К ЗАЩИТЕ

Заведующий кафедрой, д.ф.-м.н., профессор

__________ Л.Б.Соколинский

“___”___________ 2018 г.







реализация и исследование параллельных алгоритмов для решения задачи о p-медиане



ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

ЮУрГУ – 02.03.02.2018.12-005-18781.ВКР







Научный руководитель

к.ф.-м.н., ученое звание>

__________Р.Э. Шангин



Автор работы,
студент группы ВШ ЭКН-402

__________В.О. Дмитриев



Ученый секретарь

(нормоконтролер)

_____________ О.Н. Иванова

“___”___________ 2018 г.











Челябинск-2018

ОГЛАВЛЕНИЕ

	ВВЕДЕНИЕ	3

	1. Актуальность	3

	2. Цель и задачи работы	3

	3. Структура и объём работы	4

	4. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ	5

	5. 1.1 Обзор платформ для построения веб-приложений	5






ВВЕДЕНИЕ

Актуальность

На практике часто появляются ситуации, в которых необходимо наиболеепродуктивноразместить пункты автосервисов на дорогах, различные складские помещения, коммутаторы в телефонной сети, подстанции в электросетях, или, например, просчитать самые выгодные пути для покупки и доставки товара для дальнейшей реализации. Значительная их часть может быть сведена к решению задач дискретного размещения и описана с помощью оптимизационных моделей. Однако, как правило, такие задачи NP-трудны, и их вычислительная сложность не позволяет получить оптимальное решение за приемлемое время. Именно поэтому разработка приближённых методов решения получила особую важность.

Таким образом проблема решения таких задач является актуальной.

Цель и задачи работы

Целью данной работы является исследовать и, в дальнейшем, реализовать алгоритм для решения задачи о p-медиане. Было решено разработать целую систему для упрощения расчёта и вывода конечной информации для пользователя. Эта система должна предоставлять пользователю возможность оперативного поиска нужных точек предприятие-клиент и предприятие-поставщик, внесение в них изменений, сохранения для дальнейшего использования, нахождения оптимальных путей для максимизации своих доходов и прочее.

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

изучить существующие алгоритмы для решения задачи о p-медиане;

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

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

протестировать работу системы.

Структура и объём работы

Работа состоит из введения, четырёх глав, заключения и библиографии. Объём работы составляет СТОЛЬКО-ТО страниц, объём библиографии СТОЛЬКО-ТО источников.

Вглаве «Теоретическая часть» проведён обзор программных средств для разработки системы. Также глава содержит описание алгоритмов для решения задачи о p-медиане.

В главе «Проектирование» описаны функциональные и нефункциональные требования к проектируемой системе. Также в этом разделе рассмотрены проектирование базы данных и системные компоненты.

Главе «Реализация» посвящена реализации системы с использованием фреймворкаDjangoи базы данных MySQL.

В главе«Тестирование» предоставлены результаты тестирования разрабатываемой системы.

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




ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

1.1 Обзор платформ для построения веб-приложений

PHP [].PHP (от английского HypertextPreprocessor) –скриптовый язык программирования общего назначения, который интенсивно применяется для разработки веб-приложений. На сегодняшний момент он поддерживается большим числом хостинг-провайдеров и является одним из самых популярных языков программирования, применяющихся для создания динамических веб-сайтов.

RubyonRails []. Фреймворк, написанный на языке программирования Ruby.Rails предоставляет архитектурный образец Model-Views-Controller (модель-представление-контроллер) для веб-приложений, а также обеспечивает их интеграцию с сервером базы данных и с веб-сервером. Предоставляет механизмы повторного использования, которые позволяют минимизировать дублирование кода в приложениях (принцип Don'trepeatyourself). По умолчанию используются соглашения по конфигурации, которые типичны для большинства приложений (принцип Conventionoverconfiguration). Только в нестандартных случаях требуется явная специфика конфигурации.

ASP.NET []. ActiveServerPages для .NET – это технология, которая применяется для создания веб-приложений и веб-сервисов от компании Майкрософт. Она является основной частью платформы Microsoft .NET и развитием более старой технологии MicrosoftASP. На данный момент последней версией этой технологии является ASPX.NET.

Node.js []. Программная платформа, основанная на движке V8 (транслирующем JavaScript в машинный код), превращающая JavaScriptиз узкоспециального языка программирования в язык общего назначения. Node.jsдобавляет возможность JavaScriptвзаимодействовать с устройствами ввода-вывода через свой API(написанный на C++), подключать другие внешние библиотеки, написанные на разных языках, обеспечивая вызовы к ним из JavaScript-кода. Node.jsприменяется преимущественно на сервере, выполняя роль веб-сервера. В основе Node.js лежит событийно-ориентированное и асинхронное (или реактивное) программирование с неблокирующим вводом/выводом........................