Данная работа посвящена исследованию подходов к тестированию программного обеспечения на основе моделей, а также разработке алгоритма генерации оптимального набора тестов для моделей – графов состояний. Задачи, которые решались в ходе исследования:     1) Формулирование математической постановки для задачи генерации оптимального набора тестов при тестировании на основе моделей.     2) Анализ существующих алгоритмов решения поставленной задачи.     3) Реализация алгоритмов и демонстрация их работы на предоставленных примерах. В результате описанные задачи были решены, но не в полном объёме: для некоторых частных случаев задачи удалось найти и реализовать алгоритмы, позволяющие за приемлемое время получить оптимальный или приближенный к оптимальному набор тестовых сценариев. Для других случаев сделать это пока не удалось.

The subject of the graduate qualification work is «Test suit generation for model-based testing».  This work is devoted to the study of approaches to model-based software testing, as well as the development of an algorithm for generating an optimal set of tests for models represented as state machines. The research set the following goals:     1) Formulating a mathematical statement for the problem of generating an optimal set of tests for model-based testing.     2) Analysis of existing algorithms for solving the problem.     3) Implementation of the algorithms and demonstration of their work on the provided examples. As a result, the described tasks were solved, but not in full: for some special cases of the task, it was possible to find and implement algorithms that allow obtaining an optimal or close to optimal set of test scenarios in a reasonable time. For other cases, this has not yet been done.

• СОДЕРЖАНИЕ
• ВВЕДЕНИЕ
• ГЛАВА 1 ПРОБЛЕМА ГЕНЕРАЦИИ ОПТИМАЛЬНОГО НАБОРА ТЕСТОВЫХ СЦЕНАРИЕВ
  • 1.1 Постановка задачи
  • 1.2 Выводы по первой главе
• ГЛАВА 2 Подходы к решению задачи
  • 2.1 Задача о китайском почтальоне
  • 2.2 Задача о деревенском почтальоне
  • 2.3 k-задача о китайских почтальонах
  • 2.4 k-задача о деревенских почтальонах
  • 2.5 Выводы по второй главе
• ГЛАВА 3 Реализация и сравнение описанных алгоритмов
  • 3.1 Подготовка примеров моделей объектов для демонстрации работы алгоритмов
    • 3.1.1 Пример описания модели
  • 3.2 Алгоритмы для решения задачи китайского почтальона
    • 3.2.1 Сведение к задаче поиска потока минимальной стоимости
    • 3.2.2 Сведение к транспортной задаче
  • 3.3 Алгоритм для решения задачи о деревенском почтальоне
  • 3.4 Алгоритм для k-задачи о китайском почтальоне
  • 3.5 Демонстрация работы реализованных алгоритмов
  • 3.6 Выводы по третьей главе
• ЗАКЛЮЧЕНИЕ
• СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
• ПРИЛОЖЕНИЕ А МОДЕЛИ ТЕСТИРУЕМЫХ ОБЪЕКТОВ
• ПРИЛОЖЕНИЕ Б СГЕНЕРИРОВАННЫЕ ТЕСТОВЫЕ СЦЕНАРИИ ДЛЯ ПРЕДЛОЖЕННЫХ МОДЕЛЕЙ ОБЪЕКТОВ
• ПРИЛОЖЕНИЕ В ПОЛУКОЛЬЦА МАТРИЦ НАБОРОВ МАРШРУТОВ НА ГРАФЕ