Разработка приложения, реализующего метод Флойда

Методология и технология разработки программного продукта. Решение задачи поиска кратчайших путей между всеми парами пунктов назначения, используя алгоритм Флойда. Разработка интерфейса программы, с использованием среды Delphi Borland Developer Studio.

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 26.07.2014
Размер файла 2,0 M

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

· тестирование защиты - проверка защиты, например, от несанкционированного доступа к информации;

· тестирование производительности - определение пропускной способности при заданной конфигурации и нагрузке;

· тестирование требований к памяти - определение реальных потребностей в оперативной и внешней памяти;

· тестирование конфигурации оборудования - проверка работоспособности программного обеспечения на разном оборудовании;

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

· тестирование удобства установки - проверка удобства установки;

· тестирование надежности - проверка надежности с использованием соответствующих математических моделей;

· тестирование восстановления - проверка восстановления программного обеспечения, например системы, включающей базу данных, после сбоев оборудования и программы;

· тестирование удобства обслуживания - проверка средств обслуживания, включенных в программное обеспечение;

· тестирование документации - тщательная проверка документации, например, если документация содержит примеры, то их все необходимо попробовать;

· тестирование процедуры - проверка ручных процессов, предполагаемых в системе.

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

Как правило, для каждого типа программного обеспечения выполняют те виды тестирования, которые являются для него наиболее важными. Так базы данных обязательно тестируют на предельных объемах, а системы реального времени - на предельных нагрузках.

1.5 Описание прикладной задачи

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

Исходной информацией для задачи поиска кратчайших путей является взвешенный граф G = (V, R), содержащий n вершин (|V|= n), в котором каждому ребру графа приписан неотрицательный вес. Граф будем полагать ориентированным, т.е., если из вершины i есть ребро в вершину j, то из этого не следует наличие ребра из j в i. Для поиска минимальных расстояний между всеми парами пунктов назначения Флойд предложил алгоритм. Пусть есть 3 узла I, j и k и заданы расстояния между ними (рис 3). Если выполняется неравенство

dij+djk<dik,

то целесообразно заменить путь i->k путем i->j->k. Такая замена (далее ее будем наз-ть треугольным оператором) выполняется систематически в процессе выполнения алгоритма Флойда.

Рисунок 5

Шаг 0. Определяем начальную матрицу расстояний D0 и матрицу последовательности узлов S0. Диагональные элементы обеих матриц помечаются знаком "_", показывающим, что эти элементы в вычислениях не участвуют. Полагаем k=1.

Основной шаг k. Задаем строку k и столбец k как ведущую строку строку и ведущий столбец. Рассматриваем возможность применения треугольного оператора ко всем элементам dij матрицы Dk-1. Если выполняется неравенство

dij+djk<dik,(i?k,j?k и i?j),

тогда выполняем следующие действия:

1. Создаем матрицу Dk путем замены в матрице Dk-1 элемента dij на сумму dik+ djk.

2. Создаем матрицу Sk путем замены в матрице Sk-1 элемента sij на k. Полагаем k=k+1 и повторяем шаг k.

2. Специальная часть

2.1 Цели разработки

Телефонная компания обслуживает семь удаленных друг от друга районов связанных сетью. Компании необходимо определить наиболее эффективный маршрут для пересылки сообщений между двумя районами.

Рисунок 6. Схема маршрута сети районов

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

· понять математические закономерности конкретного объекта, его структуру, основные свойства и законы развития;

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

· прогнозировать прямые и косвенные последствия реализации;

· заданных способов и форм воздействия;

· обладать наглядным графическим интерфейсом;

· быстро и корректно выполнять расчеты;

· реализовывать данный прикладной метод оптимальным образом;

· легко переносить на различные технологические платформы;

· обеспечивать обработку некорректно введенных данных;

· удовлетворять требованиям простоты, доступности интерфейса.

2.2 Расчет математической модели

Вариант 1

Вариант 2

Вариант 3

2.3 Описание программы

2.3.1 О программе

Данная программа написана в системе Delphi Borland Developer Studio 2006 Borland Developer Studio включает Delphi 2006, C++Builder 2006 и C#Builder2006. Delphi 2006 - десятая версия Delphi, флагманской RAD-среды фирмы Borland.

В Delphi 2006 много новых уровней функциональности. В их число входят как высокоуровневые возможности Application Lifecycle Management (ALM), так и низкоуровневые усовершенствования. Borland в новой версии очень старался сделать акцент на производительности и скорости отклика, о чем свидетельствуют вещи, подобные обновленному менеджеру памяти IDE.

Требования к системе:

процессор Intel Pentium III/M 1,4 ГГц или Pentium IV 1,4 ГГц (минимум) (рекомендуется процессор Intel Pentium III/M с частотой выше 1,4 ГГц или Pentium IV с частотой выше 2 ГГц)

• Microsoft Windows Server 2003 (SP1), Microsoft Windows‚ XP Professional (SP2), Windows 2000 Professional (SP4), Windows 2000 Server (SP4)

• 512 МБ ОЗУ (рекомендуется 1 ГБ или больше)

• 1 ГБ свободного дискового пространства для Delphi for Win32 и Delphi for NET (Без учета пространства, необходимого для дополнительных продуктов сторонних поставщиков).

2.3.2 Алгоритм работы программы

2.3.3 Входные данные

Таблица 2 -Входные данные

Обозначение

Тип данных

Комментарий

a

Array of integer

Расстояние между узлами

CheckBox(x)

Boolean

Начальный узел

CheckBox(y)

Boolean

Конечный узел

2.3.4 Выходные данные

Таблица 3 - Выходные данные

Обозначение

Тип данных

Комментарий

b

Array of integer

Кратчайший путь между отмеченными узлами

2.4 Тестирование программы

Тестирование - процесс выполнения программы с целью обнаружения ошибок.

Тестирование обеспечивает:

· обнаружение ошибок;

· демонстрацию соответствия функций программы её назначению;

· демонстрацию реализации требований к характеристикам программы.

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

Таблица 4 - Тестирование программы

Тестовый набор

Ожидаемый результат

Полученный результат

Вывод

Начальный узел 1

Конечный узел 7

Путь 7->5->6->1

Расстояние 18

Путь 7->5->6->1

Расстояние 18

Программа работает корректно

Начальный узел 1

Конечный узел 4

Путь 4->5->6->1

Расстояние 26

Путь 4->5->6->

Расстояние 26

Программа работает корректно

Начальный узел 1

Конечный узел 5

Путь 5->6->1

Расстояние 26

Путь 5->6->1

Расстояние 26

Программа работает корректно

Вывод: проведенное тестирование показала, что программа работает корректно.

2.5 Руководство пользователя

Запуск программы осуществляется с помощью файла *.exe. после чего появляется стартовая форма проекта.

Рисунок 7. Стартовая форма

На рисунке изображена форма, которая загружается при старте программы.

Рисунок 8. Расчет

Рисунок 9. Окно "О программе"

Заключение

В ходе разработки курсового проекта были достигнуты следующие задачи:

1. Изучен математический метод алгоритм Флойда-Уоршела;

2. Составлен алгоритм компьютерной модели решения;

3. Создана программа которая:

• реализует данный математический метод оптимальным образом;

• быстро и корректно выполняет расчеты;

• имеет понятный пользователю интерфейс.

Для проверки корректности работы программы были составлены текстовые наборы. Тестирование прошло успешно, что свидетельствует о корректности работы программы. Все расчеты были проведены вручную.

Литература

1. Архангельский А.Я. Object Pascal в Delphi. - СПб.: Бином, 2012.

2. Браун С. Visual Basic 6.0: Учебный курс. - СПб.: Питер, 2010, - 573 с.

3. Васильев А., Андреев А.VBA в Office 2000. - М., 2009.

4. Вишневский П. Длинные строки и динамические массивы в Delphi // RSDN Magazine, № 3, 2012.

5. Галисеев Г.В. Программирование в среде Delphi 7. Самоучитель. - М.: Издательский дом "Вильямс", 2011.

6. Елманова Н., Трепалин С., Тенцер А. - Delphi и технология COM 2010.

7. Лялин В.Е Математические модел, 2012.

8. Парижский С.М.Delphi. Учимся на примерах. 2011.

9. Митчелл К. Керман Программирование и отладка в Delphi: Учебный курс: М.; СПб.; Киев, 2012.

10. Фаронов В.В. Delphi 6: Учебный курс. - СПб.: Питер, 2013.

Размещено на Allbest.ru


Подобные документы

  • Блок-схема алгоритма Флойда. Разработка его псевдокода в программе Microsoft Visual Studio. Программа реализации алгоритмов Беллмана-Форда. Анализ трудоемкости роста функции. Протокол тестирования правильности работы программы по алгоритму Флойда.

    курсовая работа [653,5 K], добавлен 18.02.2013

  • Изучение основных понятий и определений теории графов. Рассмотрение методов нахождения кратчайших путей между фиксированными вершинами. Представление математического и программного обоснования алгоритма Флойда. Приведение примеров применения программы.

    контрольная работа [1,4 M], добавлен 04.07.2011

  • Среда разработки Borland Developer Studio, возможности использования в практике дополнительного обучения. Технологии создания электронных учебно-методических комплексов. Системные требования и установка программы, логическая структура и интерфейс.

    дипломная работа [1,8 M], добавлен 23.04.2015

  • Постановка задач линейного программирования. Примеры экономических задач, сводящихся к задачам линейного программирования. Допустимые и оптимальные решения. Алгоритм Флойда — алгоритм для нахождения кратчайших путей между любыми двумя узлами сети.

    контрольная работа [691,8 K], добавлен 08.09.2010

  • Корректность определения кратчайших путей в графе и рёбра отрицательной длины. Анализ алгоритмов Дейкстры, Беллмана-Форда, Флойда-Уоршелла. Вычисление кратчайших расстояний между всеми парами вершин графа. Топологическая сортировка ориентированного графа.

    презентация [449,3 K], добавлен 19.10.2014

  • Анализ алгоритмов нахождения кратчайших маршрутов в графе без отрицательных циклов: Дейкстры, Беллмана-Форда и Флойда-Уоршалла. Разработка интерфейса программы на языке C++. Доказательство "правильности" работы алгоритма с помощью математической индукции.

    курсовая работа [1,5 M], добавлен 26.07.2013

  • Разработка программного продукта, предназначенного для поиска туров, транспорта, мест проживания и расчета стоимости тура, а так же для работ с клиентской базой туристической фирмы. Тестирование программного продукта в среде Borland Developer Studio 2006.

    курсовая работа [2,5 M], добавлен 08.11.2012

  • Анализ предметной области разрабатываемого программного продукта. Разработка интерфейса пользователя и структурной схемы игровой программы "Крестики-нолики". Отладка и тестирование. Проведение исследования компонентов программной среды Borland Delphi 6.0.

    курсовая работа [660,4 K], добавлен 08.03.2015

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

    отчет по практике [700,5 K], добавлен 24.11.2014

  • Эффективные средства разработки программного обеспечения. Технология визуального проектирования и событийного программирования. Конструирование диалоговых окон и функций обработки событий. Словесный алгоритм и процедуры программы Borland Delphi 7 Studio.

    дипломная работа [660,2 K], добавлен 21.05.2012

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.