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

Тестирование "чёрного ящика" или поведенческое тестирование - стратегия (метод) тестирования функционального поведения объекта (программы, системы) с точки зрения внешнего мира, при котором не используется знание о внутреннем устройстве тестируемого объекта. Под стратегией понимаются систематические методы отбора и создания тестов для тестового набора. Стратегия поведенческого теста исходит из технических требований и их спецификаций. Под "чёрным ящиком" понимается объект исследования, внутреннее устройство которого неизвестно. Понятие "чёрный ящик" предложено У.Р. Эшби. В кибернетике оно позволяет изучать поведение систем, то есть их реакций на разнообразные внешние воздействия и в то же время абстрагироваться от их внутреннего устройства.

Манипулируя только лишь со входами и выходами, можно проводить определенные исследования. На практике всегда возникает вопрос, насколько гомоморфизм "чёрного" ящика отражает адекватность его изучаемой модели, то есть как полно в модели отражаются основные свойства оригинала.

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

В таком случае преобразование называют гомоморфным.

"Чёрный" ящик представляет собой сложную гомоморфную модель кибернетической системы, в которой соблюдается разнообразие. Он только тогда является удовлетворительной моделью системы, когда содержит такое количество информации, которое отражает разнообразие системы. Можно предположить, что чем большее число возмущений действует на входы модели системы, тем большее разнообразие должен иметь регулятор.

В настоящее время известны два вида "чёрных" ящиков. К первому виду относят любой "чёрный" ящик, который может рассматриваться как автомат, называемый конечным или бесконечным. Поведение таких "чёрных" ящиков известно. Ко второму виду относятся такие "чёрные" ящики, поведение которых может быть наблюдаемо только в эксперименте. В таком случае в явной или неявной форме высказывается гипотеза о предсказуемости поведения "чёрного" ящика в вероятностном смысле. Без предварительной гипотезы невозможно любое обобщение, или, как говорят, невозможно сделать индуктивное заключение на основе экспериментов с "чёрным" ящиком. Для обозначения модели "чёрного" ящика Н. Винером предложено понятие "белого" ящика. "Белый" ящик состоит из известных компонентов, то есть известных X, Y, δ, λ. Его содержимое специально подбирается для реализации той же зависимости выхода от входа, что и у соответствующего "чёрного" ящика. В процессе проводимых исследований и при обобщениях, выдвижении гипотез и установления закономерностей возникает необходимость корректировки организации "белого" ящика и смены моделей. В связи с этим при моделировании исследователь должен обязательно многократно обращаться к схеме отношений "чёрный" - "белый" ящик.

"Белый ящик" - тестирование кода на предмет логики работы программы и корректности её работы с точки зрения компилятора того языка, на котором она писалась.

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

Техника "Белого" ящика включает в себя следующие методы тестирования:

·    покрытие операторов;

·        покрытие решений;

·        покрытие условий;

·        покрытие решений и условий;

·        комбинаторное покрытие условий.

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

При тестировании "белого" ящика (англ. white-box testing, также говорят - прозрачного ящика), разработчик теста имеет доступ к исходному коду программ и может писать код, который связан с библиотеками тестируемого ПО. Это типично для юнит-тестирования (англ. unit testing), при котором тестируются только отдельные части системы. Оно обеспечивает то, что компоненты конструкции - работоспособны и устойчивы, до определённой степени.

При тестировании "белого" ящика используются метрики покрытия кода или мутационное тестирование.

При тестировании чёрного ящика, тестировщик имеет доступ к ПО только через те же интерфейсы, что и заказчик или пользователь, либо через внешние интерфейсы, позволяющие другому компьютеру либо другому процессу

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

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

Если "альфа-" и "бета-тестирование" относятся к стадиям до выпуска продукта (а также, неявно, к объёму тестирующего сообщества и ограничениям на методы тестирования), тестирование "белого ящика" и "чёрного ящика" имеет отношение к способам, которыми тестировщик достигает цели.

Бета-тестирование в целом ограничено техникой чёрного ящика (хотя постоянная часть тестировщиков обычно продолжает тестирование белого ящика параллельно бета-тестированию). Таким образом, термин "бета-тестирование" может указывать на состояние программы (ближе к выпуску чем "альфа"), или может указывать на некоторую группу тестировщиков и процесс, выполняемый этой группой. Итак, тестировщик может продолжать работу по тестированию "белого" ящика, хотя ПО уже "в бете" (стадия), но в этом случае он не является частью "бета-тестирования" (группы/процесса).

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

Оценочное тестирование, которое также называют "тестированием системы в целом", включает следующие виды:

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

·    тестирование на предельных объемах - проверка работоспособности программы на максимально больших объемах данных, например, объемах текстов, таблиц, большом количестве файлов и т. п.;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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),

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

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

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

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

.1 Цели разработки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вариант 1

Вариант 2

Вариант 3

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

.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 -Входные данные

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