Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Введение

приложение пользователь программирование интерфейс

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

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

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

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



1. Постановка задачи

1.1 Общее описание разрабатываемого приложения

приложение пользователь программирование интерфейс

Возможности визуализатора необходимо определить заранее. Приложение планируется применять в учебном процессе, и поэтому оно должно удовлетворять необходимым требованиям.

Определим минимум требований к визуализатору алгоритмов:

1) визуализация самых распространенных алгоритмов сортировки;

2) комментирование выполняемых действий;

3) удобный и несложный пользовательский интерфейс.

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

1.2 Актуальность приложения

Для любого хорошего специалиста по программированию важно знать алгоритмы и уметь ими пользоваться. Алгоритм в программировании - это понятная и точная последовательность действий. Согласно популярной книге Кормена «Алгоритмы: построение и анализ», алгоритм (англ. - algorithm) - это любая корректно определенная вычислительная процедура, на вход (англ. - input) которой подается некоторая величина или набор величин, и результатом выполнения которой является выходная (англ. - output) величина или набор значений [2]. Другими словами, алгоритмы - это определенный маршрут, по которому следует двигаться для перемещения из точки А в точку Б.

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

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

Обучение алгоритмизации происходит и в высших учебных заведениях. Алгоритмизация входит в состав основ программирования.

Целями разрабатываемого визуализатора алгоритмов являются:

1) использование программы в высшем учебном заведении для учащихся по дисциплине алгоритмизация и основы программирования

2) упрощение понимания работы алгоритмов

3) повышение наглядности рассматриваемого материала

4) повышение интереса студентов к изучению алгоритмов



2. Анализ существующих систем визуализации

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

1) Визуализатор пирамидальной сортировки СПбГУ ИТМО. При визуализации на экране отображаются состояние массива, пирамида и комментарий к выполняемому действию. Ввод исходных данных не предусмотрен. Алгоритм трассируется только в прямом направлении. Скриншот примера работы программы представлен на рисунке 1.1:

Рисунок 1.1. Визуализатор пирамидальной сортировки СПбГУ ИТМО (Казаков М.А.)

2) Во время работы визуализатора колледжа Хоп (США) отображается код программы, подсвечивается текущий оператор, но производимые действия не комментируются. Ввод исходных данных невозможен. Трассировка алгоритма возможна только в прямом направлении.

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

4) В системе Jeliot университета в Йоэнсуу приведены только визуализаторы пузырьковой и быстрой сортировок. При выполнении алгоритмов отображается вычисление выражений, подсвечивается текущий оператор. Пользовательский ввод исходных данных возможен. Трассировка алгоритма в обратном направлении не предусмотрена.

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



3. Техническое предложение

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

Для разработки нужно выбрать язык программирования, на котором будет написано приложение. Рассмотрим самые распространенные из объектно-ориентированных языков: Java и C++.

С++ сохраняет наибольшую совместимость с С. Java, на первый взгляд, сохраняет подобие С и С++, но в действительности отличается от них: из языка удалено большое число синтаксических средств, объявленных необязательными. В результате программы на Java бывают более громоздки по сравнению с их аналогами на С++. Сборщик мусора Java требует системных ресурсов, что снижает эффективность выполнения программ. С++ позволяет использовать принцип «захват ресурсов путем инициализации» (RAII), при котором ресурсы ассоциированы с объектом и автоматически освобождаются при разрушении объекта (например, std:vector и std:iostream). В Java есть четко определенные стандарты на ввод-вывод, графику, геометрию, диалог, доступ к базам данных и прочим типовым приложениям. С++ в этом отношении более свободен [3]. Исходя из выше перечисленного, выбор был остановлен на языке С++.

Для программирования нужна определенная среда разработки. Сравним наиболее используемые среды: Visual Studio, XCode и IntelliJ IDEA.

Microsoft Visual Studio поддерживает программирование на Basic, C++, C#, позволяет создавать и подключать сторонние дополнения и различные SDK. В основном приложения, разработанные на VS, написаны под операционную систему Windows, но возможности современных версий этой среды позволяют расширить функционал до кроссплатформенного состояния.

Xcode - интегрированная среда разработки программного обеспечения под macOS и iOS. Пакет Xcode поддерживает языки C, C++, Swift, Java, AppleScript, Python и другие. Основным недостатком является стабильность среды, вынуждающая вносить дополнительные изменения в свои проекты после выхода очередной версии. Кроме того, для программирования на XCode необходимо иметь соответствующее оборудование на macOS.

IntelliJ IDEA позволяет создавать программы на языках Java, JavaScript, Python, Ruby, Groovy и других. Из недостатков данной среды хорошо выделяется производительность. Время выполнения компиляции, перекомпиляции и тестирования значительно велико, по сравнению с выше указанными средами.

Ввиду более обширного количества возможностей Visual Studio и наибольшей свободы в программировании на С++ выбор был сделан именно на нем.

3.2 Выбор 3D-движка

Современные технологии позволяют применять в приложениях трехмерную графику. Для реализации трехмерного визуализатора алгоритмов сортировок требуется движок, работающий с 3D-графикой. Рассмотрим наиболее распространенные из них: Unreal Engine 4, Ogre3D и JMonkey Engine.

Все перечисленные движки имеют полную совместимость с операционными системами Windows, Linux и Mac, поддержку OpenGL и Direct3D, возможность разработки под мобильные платформы. Полностью открытым исходным кодом обладают только Ogre3D и JMonkey. У Unreal Engine код более закрытый. Такая задумка нацелена на принуждение к использованию продуктов этой компании для разработки на данном движке. Также применение приложений, разработанных на Unreal Engine, в коммерческих целях возможно только с перечислением некоторых процентов с выручки за продукт. Для сравнения, программы, написанные на Ogre и JMonkey, разрешается свободно использовать с любой целью. Основное различие JMonkey Engine и Ogre3D в том, что основой первого является язык программирования Java, а второго - С++.

Для выбора 3D-движка был подобран ряд критериев, необходимых для разработки визуализатора алгоритмов. Соответствие движков критериям отображено в таблице 3.1.

Таблица 3.1. Сравнение 3D-движков

Критерий\Движки	Unreal Engine 4	Ogre3D	JMonkey Engine
Совместимость с Windows	+	+	+
Разработка на С++	+	+	-
Совместимость с Visual Studio	+	+	-
Открытый исходный код	-	+	+
Свободное коммерческое использование	-	+	+

По итогам сравнения для разработки был выбран движок Ogre3D.

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

Движок представляет собой объектно-ориентированный фреймворк, который включает все части процесса рендеринга в объектной модели.

С объектно-ориентированным подходом к рендерингу геометрии необходимость во взаимодействии с ней напрямую совершенно отпадает.

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

Для манипуляции объектами в библиотеке используются интуитивно понятные методы, в отличие от обычного 3D API, в котором, например, для вращения объекта нужно добиться правильной трансформации матрицы, вместо просто вызова метода с указанием оси вращения и градусов (радиан) [4].

Список возможностей Ogre3D очень велик, и регулярно пополняется новыми фреймворками, классами и методами. Полный перечень средств, используемых в данном движке, перечислен на официальном сайте [4].



4. Разработка приложения

4.1 Архитектура приложения

Проектирование архитектуры приложения является сложной задачей. При её решении необходимо учитывать такие требования к программе, как удобство разработки и сопровождение, надежность, быстродействие. Кроме этого важным свойством архитектуры является понятность или простота. Еще итальянский художник, учёный и изобретатель Леонардо да Винчи говорил: «Простота - это то, что труднее всего на свете; это крайний предел опытности и последнее усилие гения».

Работа разрабатываемого приложения состоит из следующих этапов:

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

2) менеджер алгоритмов считывает выбранный алгоритм и формирует для него список операций, проводимых при выполнении сортировки

3) собранный список операций запоминается визуализатором

4) когда алгоритм сформирован, пользователь переключает шаги сортировки

5) визуализатор анимирует каждый шаг в трехмерной сцене

Блок-схема работы приложения представлена на рисунке 4.1:



Рисунок 4.1. Блок-схема работы приложения

Структурная схема приложения представлена на рисунке 4.2:

Рисунок 4.2. Структурная схема работы визуализатора

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

Отдельным классом оформлен менеджер алгоритмов Algo. Он содержит метод, считывающий идентификатор алгоритма, методы-составители списка операций, методы вставки операции в список.

Пользовательский интерфейс описан в классе GUI. Для разработки использовалась библиотека CEGUI. Выбор интерфейсной библиотеки аргументирован ее полной совместимостью с движком Ogre3D.

Также был создан класс Convert, состоящий из методов, которые конвертируют передаваемые данные в требуемый формат.

Диаграмма классов изображена на рисунке 4.3:

Рисунок 4.3. Диаграмма классов приложения

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



4.2 Настройка сцены и 3D-моделей

Исходный массив чисел будет отображаться в виде кубических объектов (параллелепипедов). Пользователь, вводя последовательность чисел, задает высоту этих объектов. Параллелепипеды на сцене рисуются встроенными в Ogre фигурами Cube.mesh. Далее они заливаются текстурой синего цвета. При построении массива на экране объекты растягиваются в соответствии с заданными значениями элемента.

Сущности нужно отображать на поверхности. Для этого необходимо при построении сцены создать абстрактную плоскость и покрыть ее материалом. По умолчанию поверхность заливается текстурой серого асфальта. Через интерфейс пользователь может выбирать и менять текстуру заливки плоскости. Материалы для поверхности разрабатывались вручную, их настройки устанавливались во встроенном в Ogre скрипте Examples.material.

Помимо плоскости для установки объектов необходимо также создать задний фон. Он будет заливаться встроенными в Ogre текстурами формата SkyBox. Пользователь также имеет возможность выбирать и изменять фон через интерфейс.

4.3 Разработка кода

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

Настройка исходного массива

Реализация основного кода программы производится в классе MainApp. Класс реализован, как наследник от BaseApp, включающего стандартные настройки для показа сцены, определение движковых менеджеров, буферизованный ввод, корректный запуск и завершение приложения.

В MainApp реализован ввод исходного массива чисел, который затем передается в динамические массивы list и listCube. Исходную последовательность задает пользователь, затем программа считывает ее из текстового поля. Массив list, состоящий из переменных класса ListMember, содержит значения исходных чисел и номера сущностей (кубов), которые их изображают. Массив listCube из переменных класса CubeMember содержит сущности (Entity), привязанные к узлам сцены (SceneNode) [4] и, в отличие от предыдущего массива, имеет статическое состояние на протяжении всей работы приложения с одной последовательностью. Члены list же в ходе интерпретации могут перетасовываться. Листинг программы, отвечающий за построение исходного массива (отрывок метода listCreate в MainApp), показан ниже:

vector<int> vecList = ToListInt (gui.listEdit->getText());

listLength = vecList.size();

int *x2 = new int[listLength];

for (int i=0; i<listLength; i++)

{

if (vecList[i]==0) vecList[i] = 1;

x2 [i] = vecList[i];

}

algo.listStart = new int[listLength];

list = new ListMember[listLength];

listCube = new CubeMember[listLength];

createListStart(x2);

createListMember(x2);

createListCube();



Чтобы список операций можно было корректно считывать из текстового поля и передавать в виде вектора, был разработан метод ToListInt в классе Convert. Метод считывает только цифры из строки, иные символы он воспринимает как пробел. В результате ToListInt возвращает вектор типа int, состоящий из исходных чисел. Листинг определения метода ToListInt представлен ниже:

vector<int> vec(0);

bool setNumber = false;

int number = 0;

for (int i=0; i<str.size(); i++)

{

if ((str[i]>='0') && (str[i]<='9'))

{

if (setNumber)

{

number = (number*10) + ToInt (str[i]);

} else {

setNumber = true;

number = ToInt (str[i]);

}

} else {

if (setNumber) vec.push_back(number);

setNumber = false;

}

}

if (setNumber) vec.push_back(number);

if (vec.size()==0) vec.push_back(1);

return vec;



Построение алгоритмов

Построением списков операций алгоритмов сортировки занимается менеджер алгоритмов, он же класс Algo. Класс содержит метод createOperationList, который считывает идентификатор алгоритма и запускает нужный алгоритм сортировки.

В Algo находятся методы-составители списка операций для каждого отдельного алгоритма. При создании списка операции записываются в vector типа string, где первым значением в строке служит символ-идентификатор проводимой операции, вторым - элемент, с которым проводится операция, третьим - другой элемент, который при необходимости также задействован в операции. Также при создании списка операций в отдельный вектор записываются комментарии к выполняемым действиям. Эти комментарии в дальнейшем будут выводиться в интерфейсе для пользователя, чтобы он имел представление о выполняемом действии. Для удобства программирования были добавлены методы вставки нужных значений в вектора (push для вектора операций и pushLog для вектора с комментариями к выполняемым действиям). Пример листинга метода-составителя операций для пузырьковой сортировки показан ниже:

int j = 0;

int buf = 0;

for (int i=0; i<len; i++)

{

for (int k=(len-1); k>i; k-)

{

push («e», k-1, k);

pushLog (ToRU(L «Сравним числа»),

Ogre: StringConverter:toString (l[k]), ToRU (L» и»),

Ogre: StringConverter:toString (l[k-1]));

if (l[k] < l [k-1])

{

push («s», k-1, k);

pushLog (Ogre: StringConverter:toString (l[k]), ToRU (L» <»),

Ogre: StringConverter:toString (l[k-1]),

ToRU (L», поэтому поменяем их местами»));

buf = l[k];

l[k] = l [k-1];

l [k-1] = buf;

pushLog (ToRU(L «Возвратим числа на место»));

} else {

pushLog (Ogre: StringConverter:toString (l[k]), ToRU (L» >=»),

Ogre: StringConverter:toString (l[k-1]),

ToRU (L», поэтому возвращаем их на место»));

}

push («f», k-1, k);

}

}

Для построения нужного алгоритма вызывается метод createSort в основном классе MainApp. Метод просит менеджера алгоритмов Algo собрать список операций для заданного идентификатора алгоритма, запоминает полученный вектор в глобальном векторе operation класса MainApp, пересобирает массив list из элементов ListMember согласно исходной последовательности, расставляет кубические объекты на сцене в начальном порядке.

Настройка анимаций

При визуализации каждого шага нужно выдвигать и перемещать объекты на сцене на нужное место. Во время анимации шага на сцене меняется положение кубиков, а в коде меняется только массив list. Массив listCube, состоящий из самих кубов, остается в начальном состоянии. Главный плюс такого решения в отсутствии необходимости перерисовывать объекты прямо на сцене. Здесь меняется только численный массив в коде, на сцене лишь изменяются координаты объектов. Следовательно, приложение потребляет меньше оперативной памяти на графическую отрисовку.

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

Ogre: Vector3 vec1 = listCube [list[num1].numCube].node->getPosition();

Ogre: Vector3 vec2 = listCube [list[num2].numCube].node->getPosition();

int point = vec2.x;

while (vec1.x < point)

{

vec1.x += 1;

vec2.x -= 1;

listCube [list[num1].numCube].node->setPosition(vec1);

listCube [list[num2].numCube].node->setPosition(vec2);

}

ListMember buff = list[num1];

list[num1] = list[num2];

list[num2] = buff;

В приложении требуется реализовать, помимо пользовательского переключения шагов алгоритма, автоматический режим визуализации. При включении автоматического переключения шагов запускается таймер в переопределенном движковом методе frameRenderingQueued, который каждые 50 шагов визуализирует следующий шаг. Листинг реализации таймера представлен ниже:

4.4 Проектирование пользовательского интерфейса

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

Разработка элементов интерфейса

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

- кнопку выхода;

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

- переключатели для выбора алгоритма сортировки;

- интерфейс для работы с визуализацией алгоритма (ручное переключение шагов, запуск и приостановление автоматического режима, остановка визуализации и сброс к начальной последовательности);

- поле для отображения комментариев к визуализируемому шагу;

- кнопки для изменения вида сцены (смены положения камеры, изменение текстуры поверхности / фона, отключение теней).

Для настройки интерфейса при построении сцены в основном классе MainApp вызывается метод createGUI класса GUI. Метод устанавливает ресурсы, необходимые для работы интерфейса, подключает используемую графическую схему (в приложении используется стандартная схема TaharezLook пакета CEGUI), создает элементы интерфейса (виджеты) и настраивает их видимость. Все виджеты располагаются на одном листе mySheet. При создании каждого из них вызывается соответствующий метод в классе GUI. Для корректного отображения русских символов на экране реализован метод ToRU в классе Convert.

Взаимодействие пользователя с элементами

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

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

Измерение скорости работы алгоритмов

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

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

Расчет времени производится для эталонного компьютера с частотой 1 ГГц. При расчете времени сортировки учитывается количество операций, проводимых в алгоритме. Считаем, что одна операция равна одному машинному такту. Длительность одного машинного такта обратно пропорциональна тактовой частоте процессора. Следовательно, для выбранного эталонного компьютера время машинного такта составит 1/1 ГГц, что в переводе в секунды равно 1 нс. Листинг реализации расчета скорости работы алгоритмов представлен ниже:

CEGUI: String report = ToRU (L «Скорость работы алгоритмов: \n»);

vector<string> operList;

for (int i=0; i<algo.algoSum; i++)

{

algo.logOn = false;

algo.createOperationList (listLength, i+1);

operList = algo.vec;

report += algo.algoName[i];

report += «-»;

report += ToString (operList.size());

report += ToRU (L» нс \n»);

operList.clear();

}



5. Тестирование

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

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

В текстовое поле для ввода исходной последовательности можно вводить любые символы. Для перевода строки из текстового поля в массив из чисел используется метод ToListInt в классе Convert. Он считывает только цифры, что предохраняет код от попытки использования других символов. Любой символ, не являющийся цифрой, метод считает за пробел. Также, на случай наличия нескольких таких пробелов между числами, в методе имеется флаг setNumber. При значении этой переменной ИСТИНА посимвольно собирается число. При значении ЛОЖЬ полученное число записывается в массив, если оно не было записано до этого, далее происходит ожидание на появление следующего числа в строке. На случай ввода строки без чисел, метод возвращает список с одним элементом равным 1. Если один из элементов списка равен 0, то метод приравнивает его к 1. Такое условие необходимо для корректного отображения кубического объекта, привязанного к элементу, на экране, так как сущность с нулевой высотой будет не видна на сцене.

При вводе больших данных, порядка 500 элементов, списки операций для каждого алгоритма начинают собираться чуть медленнее. На создание алгоритма для таких массивов уходит порядка 1-1,5 секунд. Расчет скорости работы алгоритмов занимает количество времени, примерно большее во столько раз, сколько алгоритмов реализовано в программе. Учитывая, что тестирование проводилось на относительно среднем компьютере, такая скорость работы с большим количеством данных является приемлемой.

Во время переключения шагов скрываются кнопки, которые нельзя нажимать данный момент. Например, при запуске автоматического режима активны только кнопки «Pause» и «Stop», после создания отчета о скорости работы алгоритмов скрывается кнопка «Создать» до тех пор, пока не будет введена другая исходная последовательность. Такой метод необходим, чтобы пользователь не мог сломать работу приложения во время визуализации алгоритма.

При выборе положения камеры она направляется на центральное положение между кубиками на сцене. Если список не построен, то его длина считается равной 0. Данное решение сделано для того, чтобы кнопки изменения камеры были активны в течение всей работы приложения. Выбранное положение запоминается в глобальной переменной cam. Также при построении списка на сцене камера автоматически направляется на центральное положение между кубиками, учитывая значение cam. На случай некорректного направления камеры предусмотрено ручное изменение положения с помощью клавиатуры.

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

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



6. Разработка руководства пользователя

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

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

• - введение;
• - запуск и настройка приложения;
• - работа с исходными данными;
• - работа с алгоритмами (Выбор и визуализация алгоритма, измерение скорости);
• - работа с графикой (Настройка камеры, изменение текстур и теней);
• - об авторах.
• Руководство пользователя включено в пакет, поставляемый с продуктом. В приложении А представлен полный текст руководства.


Заключение

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

Разработанный визуализатор имеет следующие возможности:

- визуализация самых распространенных алгоритмов сортировки (выбором, вставками, пузырьковая, быстрая, сортировка Шелла);

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

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

- пошаговый и автоматический режим выполнения сортировки;

- трассировка алгоритма в прямом и обратном направлении;

- автоматический (случайный) и пользовательский ввод данных;

- измерение скорости работы алгоритмов;

- визуализация алгоритма с применением трехмерной графики;

- удобство сопровождения и модификации приложения.

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

Разработанное приложение удовлетворяет всем предъявленным требованиям. Применение трехмерного визуализатора алгоритмов сортировки позволит повысить интерес студентов к изучаемому материалу.

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

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

Результаты работы над данной выпускной квалификационной работой были представлены на конференциях: Х Ежегодная научная сессия аспирантов и молодых ученых, Молодые исследователи регионам, Вузовская наука - региону. Тезисы докладов опубликованы в сборниках работ.



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

1. Визуализатор алгоритмов с применением трехмерной графики. Костров А.В. В сборнике: Материалы межрегиональной научной конференции Х ежегодной научной сессии аспирантов и молодых ученых. Том 1. 2017. С. 81-85.

2. Кормен Т. Алгоритмы: построение и анализ / Кормен Т., Лейзерсон Ч., Ривест Р. - М.: МЦНМО, 2001. - 960 с.

3. Страуструп Б. Язык программирования С++ / Страуструп Б. - М.: Бином, 2011. - 1136 с.

4. Ogre3D Графический 3D-движок с открытым исходным кодом [Электронный ресурс]: офиц. сайт. - Режим доступа: http://www.ogre3d.org

5. JMonkey Engine [Электронный ресурс]: офиц. сайт - Режим доступа: http://www.jmonkey.org

6. UnrealEngine [Электронный ресурс]: офиц. сайт - Режим доступа: http://www.unrealengine.org

7. Приемы объектно-ориентированного программирования. Паттерны проектирования / Э. Гамма, Р. Хелм, Р. Джонсон, Дж. Влиссиде. - СПб: Питер, 2001. - 368 с.

8. CEGUI [Электронный ресурс]: офиц. сайт - Режим доступа: http://cegui.org

9. Бейзер, Б. Тестирование черного ящика. Технологии функционального тестирования программного обеспечения и систем / Б. Бейзер. - СПб: Питер, 2004. - 320 с.

10. Kerger, F. Ogre 3D 1.7 Beginner's Guide / F. Kerger - Birmingham: Packt Publishing Ltd, 2010 - 300 p.



Приложение 1

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

Введение

Приложение AlgoVisual3D предназначено для изучения алгоритмов сортировки натуральных чисел. Программа разработана с использованием движка Ogre3D.

Возможности программы:

· автоматический / ручной ввод данных;

· автоматический / ручной режимы переключения шагов алгоритма

· визуализация распространенных алгоритмов сортировки (выбором, вставками, пузырьковая, быстрая, Шелла)

· комментирование выполняемых действий

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

· трехмерная графика

· возможность изменения графики на сцене

· смена камеры

Цикл работы программы:

1. Задается исходная последовательность чисел.

2. Выбирается алгоритм сортировки.

3. Программа собирает алгоритм сортировки для визуализации.

4. Переключаются шаги алгоритма, в это время на сцене шаг визуализируется.

Системные требования:

· Windows XP и выше

· Частота процессора 1 ГГц

· ОЗУ 256 Мб

· Видеокарта с поддержкой 3D

· DirectX 11

1. Запуск и настройка приложения

Запустите exe-файл «AlgoVisual3D» из директории приложения.

В окне настроек выберите «Direct3D9 Rendering Subsystem». При выборе иных систем рендеринга корректность работы приложения не гарантируется.

Для отображения в оконном режиме установите в «Full Screen» значение No. Для полноэкранного режима - Yes.

При наличии нескольких мониторов в «Rendering Device» выберите нужный для показа.

Выберите требуемое разрешение экрана в «Video Mode».

Запустите приложение по кнопке «ОК».

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

Выйти из программы можно по кнопке «Выйти» в левом верхнем углу окна.

2. Работа с исходными данными

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

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

Замечание! Программа считывает только натуральные значения. При вводе нуля он приравнивается к 1. При отсутствии цифр в поле для ввода исходная последовательность приравнивается к списку из одного элемента, равного 1.

Также можно воспользоваться генерацией случайных списков по кнопке «Auto». Генерация случайных чисел производится в диапазоне от 1 до 15 с длиной массива от 3 до 10.

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

Вернуться ко вводу исходных данных можно по кнопке «Поменять числа». При этом кубические объекты, находящиеся на сцене, уничтожатся.

3. Работа с алгоритмами

3.1. Выбор и визуализация алгоритма

После построения списка появляется интерфейс работы с алгоритмами.



Переключение алгоритмов сортировки осуществляется кнопками «<» и «>». Название выбранного алгоритма выводится текстом между кнопками. При их переключении алгоритм для визуализации собирается автоматически.

Ручное переключение шагов алгоритма вперед / назад осуществляется кнопками «next» / «last». Для включения автоматического режима необходимо нажать «play». Чтобы приостановить автоматическую визуализацию алгоритма нужно нажать кнопку «pause». Кнопка «stop» сбрасывает алгоритм к начальному состоянию.

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

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

3.2. Измерение скорости

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

Для раскрытия интерфейса измерения скорости необходимо тапнуть по кнопке «Скорость». Скрыть интерфейс можно аналогичным образом.



В текстовом поле интерфейса для измерения скорости отображается исходная последовательность чисел.

В поле под разделом «Отчет:» записывается отчет о замерах скорости работы алгоритмов. Для создания отчета необходимо нажать кнопку «Создать».

Расчет скорости алгоритмов производится в наносекундах. В расчете учитывается количество выполняемых действий в алгоритме. Считается, что одна выполняемая операция равна одному машинному такту. Период машинного такта рассчитывается по формуле T = 1 / v, где T - период машинного такта, v - частота процессора. Если считать, что компьютер имеет частоту процессора 1 ГГц, то время его одного машинного такта составит 1 нс. В приложении период рассчитывается для эталонного компьютера с частотой 1 ГГц.

4. Работа с графикой

4.1 Настройка камеры

Положение камеры задается кнопками «1-4» в правом верхнем углу экрана. Кнопки доступны в течение всей работы программы. В приложении доступно для изменения 4 положения камеры.



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

Также положение и направление камеры можно изменять вручную клавишами на клавиатуре:

A / D - влево / вправо по x;

Q / E - вниз / вверх по y;

W / S - вперед / назад по z;

J / L - наклон влево / вправо по x;

U / O - наклон вниз / вверх по y;

I / K - наклон вперед / назад по z.

Оси координат на сцене располагаются следующим образом:

4.2 Изменение текстур и теней

Для раскрытия интерфейса изменения графики необходимо нажать по кнопке «Графика». Скрытие интерфейса производится аналогичным образом. Изменение графики доступно в течение всей работы программы.



При переключении фона меняется текстура неба. Выбор производится кнопками «1-3» в соответствующем разделе. При переключении поверхности меняется текстура плоскости, на которой находятся кубические объекты. Выбор также производится кнопками «1-3» в соответствующем разделе. В приложении доступно для выбора 3 текстуры фона неба и 3 текстуры заливки поверхности.

В приложении доступно изменение отображения тени от кубических объектов на сцене. Включение/отключение тени производится кнопками «Тень ON» / «Тень OFF».

Об авторах

Разработчик: Костров Антон Витальевич.

Научный руководитель: Кочкин Дмитрий Валерьевич.

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

За основу взят игровой движок Ogre3D, версия 1.9. Некоторые текстуры частично изменены. Источник www.ogre3d.org.

Интерфейс: CEGUI, версия 0.7.9. Текстуры оригинал. Источник cegui.org.uk.

Коммерческая реализация приложения запрещена.



Приложение 2

Листинг программы

Листинг файла ListMember.h

class ListMember

{

public:

int value; // значение числа

int numCube; // номер сущности

};

Листинг файла CubeMember.h

#include <OgreEntity.h>

#include <OgreSceneManager.h>

class CubeMember

{

public:

CubeMember();

virtual ~CubeMember();

Ogre: Entity* entity; // сущность

Ogre: SceneNode* node; // узел сцены

};

Листинг файла Convert.h

#include <iostream>

#include <CEGUI.h>

using namespace std;



namespace Convert

{

int ToInt (char x);

int Pow (int x, int y); // возведение в степень

vector<int> ToListInt (CEGUI: String str);

CEGUI: String ToString (vector<int> x);

CEGUI: String ToRU (wchar_t strw[]); // convert to ru lang

}

Листинг файла Convert.cpp

#include «Convert.h»

int Convert: ToInt (char x)

{

switch (x)

{

case '1': return 1;

case '2': return 2;

case '3': return 3;

case '4': return 4;

case '5': return 5;

case '6': return 6;

case '7': return 7;

case '8': return 8;

case '9': return 9;

case '0': return 0;

default: break;

}

return 0;

}

int Convert: Pow (int x, int y)

{

int z = 1;

for (int i=0; i<y; i++) z = z*x;

return z;

}

CEGUI: String Convert: ToString (vector<int> x)

{

CEGUI: String str = «»; // create empty string

for (int i=0; i<x.size(); i++)

{

str += ToString (x[i]);

str += «»;

}

return str;

}

vector<int> Convert: ToListInt (CEGUI: String str)

{

vector<int> vec(0);

bool setNumber = false; // истина - собираем число, ложь - некорректные символы

int number = 0; // собираемое число

for (int i=0; i<str.size(); i++)

{

if ((str[i]>='0') && (str[i]<='9'))

{

if (setNumber)

{

number = (number*10) + ToInt (str[i]); // дополнили число

} else {

setNumber = true; // число

number = ToInt (str[i]); // начали собирать число

}

} else {

if (setNumber) vec.push_back(number); // записали собранное число

setNumber = false; // некорректные символы или пробелы

}

}

if (setNumber) vec.push_back(number);

// записали собранное число, если последний символ - цифра

if (vec.size()==0) vec.push_back(1); // если чисел в списке нет

return vec;

}

CEGUI: String Convert: ToRU (wchar_t strw[])

{

CEGUI: String str;

for (int i=0; i<wcslen(strw); i++) str += strw[i];

return str;

}

Листинг файла GUI.h

#include <iostream>

#include «Convert.h»

#include <CEGUI.h>

#include <RendererModules/Ogre/CEGUIOgreRenderer.h> //from 0.8 it's just Ogre/Renderer.h



using namespace std;

using namespace Convert;

class Mygui

{

public:

Mygui(void);

virtual ~Mygui(void);

virtual CEGUI: Window* createGUI(void); // Постойка интерфейса

virtual void createResourses(void); // группы ресурсов

virtual void createWidgets(void); // widgets

virtual void quitButton(void); // кнопка выхода

virtual void camStaticText(void); // text camera

virtual void camButton1 (void); // кнопка camera 1

virtual void camButton2 (void); // кнопка camera 2

virtual void camButton3 (void); // кнопка camera 3

virtual void camButton4 (void); // кнопка camera 4

virtual void listStaticText(void); // text для ввода исх. последовательности

virtual void listEditBox(void); // поле для ввода исх. последовательности

virtual void listAutoButton(void); // кнопка для создания рандом list

virtual void listOkButton(void); // кнопка для создания исх. последовательности

virtual void algoOffButton(void); // close algo

virtual void algoStaticText(void); // text для algo

virtual void algoNameText(void); // name algo

virtual void algoLButton(void); // algo left

virtual void algoRButton(void); // algo right

virtual void stepStaticText(void); // text для steps

virtual void stepStopButton(void); // кнопка для stop all

virtual void stepPlayButton(void); // кнопка для play auto mode

virtual void stepPauseButton(void); // кнопка для pause auto mode

virtual void stepLastButton(void); // кнопка для last manual mode

virtual void stepNextButton(void); // кнопка для next manual mode

virtual void logStaticText(void); // text

virtual void logList(void); // логирование

virtual void speedButtonOn(void); // кнопка speed on

virtual void speedButtonOff(void); // кнопка speed off

virtual void speedListTextStaticText(void);

virtual void speedListStaticText(void);

virtual void speedReportStaticText(void); // text для report in speed

virtual void speedReportOkButton(void); // create report in speed

virtual void speedReportEditBox(void); // editbox для report in speed

virtual void sceneButtonOn(void); // кнопка scene on

virtual void sceneButtonOff(void); // кнопка scene off

virtual void skyStaticText(void); // text sky

virtual void skyButton1 (void); // кнопка sky 1

virtual void skyButton2 (void); // кнопка sky 2

virtual void skyButton3 (void); // кнопка sky 3

virtual void groundStaticText(void); // text ground

virtual void groundButton1 (void); // кнопка ground 1

virtual void groundButton2 (void); // кнопка ground 2

virtual void groundButton3 (void); // кнопка ground 3

virtual void shadowButtonOn(void); // кнопка shadow on

virtual void shadowButtonOff(void); // кнопка shadow off

virtual void listShow(void); // visible = true - невидимость

virtual void listHide(void); // visible = false

virtual void algoShow(void); // visible = true

virtual void algoHide(void); // visible = false

virtual void sceneShow(void); // scene развернуть

virtual void sceneHide(void); // scene свернуть

virtual void speedShow(void); // speed развернуть

virtual void speedHide(void); // speed свернуть

virtual void stepEnableBegin(void); // enable когда список собрался

virtual void stepEnableEnd(void); // enable когда список закончился

virtual void stepEnablePlay(void); // enable когда нажали плей

virtual void stepEnablePause(void); // enable когда нажали pause

virtual void stepDisable(void); // enable = false

CEGUI: Window *mySheet; // лист для виджетов

CEGUI: Window *quit; // quit Button

CEGUI: Window *camText; // camera text

CEGUI: Window *cam1; // camera Button

CEGUI: Window *cam2; // camera Button

CEGUI: Window *cam3; // camera Button

CEGUI: Window *cam4; // camera Button

CEGUI: Window *listSText; // text для ввода исх. последовательности

CEGUI: Window *listEdit; // поле для ввода исх. последовательности

CEGUI: Window *listAuto; // кнопка для создания рандом list

CEGUI: Window *listOk; // кнопка для создания исх. последовательности

CEGUI: Window *algoOff; // close algo

CEGUI: Window *algoSText; // text для algo

CEGUI: Window *algoText; // name algo

CEGUI: Window *algoL; // algo left

CEGUI: Window *algoR; // algo right

CEGUI: Window *stepSText; // text для steps

CEGUI: Window *stepStop; // stop button

CEGUI: Window *stepPlay; // play button

CEGUI: Window *stepPause; // pause button

CEGUI: Window *stepLast; // last button

CEGUI: Window *stepNext; // next button

CEGUI: Window *logSText; // text

CEGUI: Window *logText; // поле для вывода комментариев (логирование) 1

CEGUI: Window *speedOn; // speed Button

CEGUI: Window *speedOff; // speed Button

CEGUI: Window *speedListText; // text для исх. последовательности in speed

CEGUI: Window *speedList; // text исх. последовательности in speed

CEGUI: Window *speedReportText; // text для отчета in speed

CEGUI: Window *speedReportOk; // button для create отчета in speed

CEGUI: Window *speedReportLog; // log отчета in speed

CEGUI: Window *sceneOn; // scene Button

CEGUI: Window *sceneOff; // scene Button

CEGUI: Window *skyText; // sky text

CEGUI: Window *sky1; // sky Button

CEGUI: Window *sky2; // sky Button

CEGUI: Window *sky3; // sky Button

CEGUI: Window *groundText; // groung text

CEGUI: Window *ground1; // ground Button

CEGUI: Window *ground2; // ground Button

CEGUI: Window *ground3; // ground Button

CEGUI: Window *shadowOn; // shadow Button

CEGUI: Window *shadowOff; // shadow Button

};

Листинг файла GUI.cpp

#include «GUI.h»



CEGUI: Window* Mygui:createGUI(void)

{

createResourses(); // установим группы ресурсов

CEGUI: WindowManager &wmgr = CEGUI: WindowManager:getSingleton();

mySheet = wmgr.createWindow («DefaultWindow», «MySheet»);

createWidgets(); // настраиваем виджеты

sceneHide();

speedHide();

listShow();

algoHide();

stepDisable();

return mySheet;

}

void Mygui:createResourses(void)

{

CEGUI: Imageset:setDefaultResourceGroup («Imagesets»);

CEGUI: Font:setDefaultResourceGroup («Fonts»);

CEGUI: Scheme:setDefaultResourceGroup («Schemes»);

CEGUI: WidgetLookManager:setDefaultResourceGroup («LookNFeel»);

CEGUI: WindowManager:setDefaultResourceGroup («Layouts»);

}

void Mygui:createWidgets(void)

{

quitButton(); // создали кнопку выхода

camStaticText();

camButton1 (); // кнопки камеры

camButton2 (); // кнопки камеры

camButton3 (); // кнопки камеры

camButton4 (); // кнопки камеры

listStaticText();

listEditBox(); // поле для ввода исх. последовательности

listAutoButton();

listOkButton();

algoOffButton();

algoStaticText();

algoNameText();

algoLButton();