close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
На правах рукописи
ЕВСЕЕВА Юлия Игоревна
РАЗРАБОТКА МАТЕМАТИЧЕСКОГО
И АЛГОРИТМИЧЕСКОГО ОБЕСПЕЧЕНИЯ
ДЛЯ СИСТЕМЫ СТРУКТУРНО-ПАРАМЕТРИЧЕСКОГО
СИНТЕЗА ТРЕХМЕРНЫХ АДАПТИВНЫХ ПРИЛОЖЕНИЙ
Специальность 05.13.01 – Системный анализ, управление
и обработка информации (в технике и технологиях)
Автореферат
диссертации на соискание ученой степени
кандидата технических наук
ПЕНЗА 2016
Работа выполнена в ФГБОУ ВО «Пензенский государственный университет».
Научный руководитель –
доктор технических наук, доцент
Бождай Александр Сергеевич
Официальные оппоненты:
Кравец Алла Григорьевна,
доктор технических наук, доцент,
ФГБОУ ВО «Волгоградский государственный
технический университет», кафедра
«Системы автоматизированного
проектирования и поискового
конструирования», профессор кафедры;
Курейчик Виктор Михайлович,
доктор технических наук, профессор,
ФГБОУ ВО «Южный федеральный
университет», кафедра «Дискретная
математика и методы оптимизации»,
заведующий кафедрой
Ведущая организация –
АНОО ВО «Воронежский институт
высоких технологий», г. Воронеж
Защита диссертации состоится 16 февраля 2017 г., в ____ часов, на заседании диссертационного совета Д 212.186.04 в ФГБОУ ВО «Пензенский государственный университет» по адресу: 440026, г. Пенза, ул. Красная, 40.
С диссертацией можно ознакомиться в библиотеке ФГБОУ ВО «Пензенский государственный университет» и на сайте http://dissov.pnzgu.ru/
ecspertiza/Tehnicheskie_nauki/evseeva
Автореферат разослан «___» _______ 20__ г.
Ученый секретарь
диссертационного совета
Косников Юрий Николаевич
2
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Проблема оперативной разработки сложных адаптивных систем обладает в настоящее время особой актуальностью. В сфере программного
обеспечения адаптивные системы охватывают широкий класс приложений,
включая компьютерные тренажеры, интеллектуальные симуляторы, среды
имитационного моделирования, системы виртуальной реальности и др. Такие приложения должны, с одной стороны, обеспечивать высокую детализацию и реалистичность графических данных, с другой – обладать свойствами структурной и поведенческой изменчивости без перекомпиляции
исходного кода.
Как правило, сферы применения трехмерных адаптивных приложений (ТРАП) подвержены стремительным динамическим изменениям. Следовательно, модели изменчивости, заложенные в основу адаптивных программ, должны обеспечивать быструю и эффективную самоадаптацию
приложения непосредственно в ходе его функционирования. Характерными примерами подобных приложений являются следующие типы программных систем:
– авиа- и космические симуляторы для обучения пилотов, где наряду
с обычными функциями авиатренажеров должны обеспечиваться многоконтурные адаптивные обратные связи, на основе которых приложение
может самоусложняться (предоставлять пилоту либо новые функции, либо
детализировать уже имеющиеся), усложнять пилотные ситуации и задания
в зависимости от текущих навыков пилота, моделировать стрессовые условия полета за счет постоянного изменения условий полетного сеанса;
– среды виртуальной реальности для моделирования хода хирургических операций и медицинских исследований;
– системы имитационного моделирования для проведения виртуальных испытаний сложного технического устройства при изменяемых свойствах среды функционирования.
Отличительной особенностью перечисленных программных систем
является необходимость автоматической идентификации текущего состояния объекта (пилота, хирурга, испытываемого технического устройства)
с последующим изменением состояния самой системы.
Методологические аспекты разработки подобных систем представлены в работах А. И. Белоусова, С. Б. Ткачева, С. В. Акимова, В. М. Одрина,
С. С. Картавова, G. R. Cano, D. S. Batory, K. Czarnecky, G. Gallo, M. Laguna,
K. C. Kang, L. Shen. Решением задач повышения эффективности разработки
и функционирования интерактивных программных систем занимались
В. В. Мыльников, А. О. Матлин, А. П. Бабенко, В. Е. Шукшунов, М. Е. Зубов, Н. И. Вавилова, О. О. Варламов, K. Dongsun, S. Britain, C. Hogg,
A. L. Wang, M. B. Carvalho, M. Fasli и многие другие. Однако до сих пор
многие проблемы, связанные с оперативностью разработки и увеличением
длительности жизненного цикла адаптивных приложений, остаются нерешенными.
3
Таким образом, задача разработки методов и алгоритмов структурнопараметрического синтеза ТРАП приобретает особую научно-практическую актуальность. Ее успешное решение позволит:
– сократить временные и ресурсные затраты на разработку приложения;
– увеличить продолжительность жизненного цикла программной системы и время ее непрерывного функционирования;
– привлечь к разработке адаптивных программ специалистов из различных предметных областей, не обладающих специальными навыками
разработки программного обеспечения;
– повысить реалистичность и сложность моделируемых процессов
и систем.
Основной научной проблемой диссертационной работы выступает
исследование системных связей и закономерностей функционирования
адаптивных программных систем с целью повышения их эффективности
и длительности жизненного цикла.
Цели и задачи исследования. Цель диссертационной работы заключается в повышении эффективности создания и функционирования ТРАП за
счет применения разработанного математического и алгоритмического обеспечения системы структурно-параметрического синтеза адаптивных приложений. Для достижения цели были поставлены и решены следующие задачи:
– исследована предметная область, связанная с созданием и применением адаптивных программных систем, существующих методов и инструментальных средств структурно-параметрического синтеза адаптивных
приложений;
– разработана математическая модель изменчивости адаптивных приложений, позволяющая задавать множества допустимых системных конфигураций и правила перехода между ними в структурированной форме,
удобной для последующей обработки;
– разработан алгоритм верификации системных конфигураций, созданных с использованием предложенной модели изменчивости;
– разработан алгоритм автоматического ситуационного выбора системных конфигураций адаптивного приложения в реальном времени;
- на основе предложенной модели изменчивости и алгоритмов разработан метод структурно-параметрического синтеза адаптивных программных систем, позволяющий автоматизировать процесс проектирования интерактивных графических приложений с расширенным жизненным
циклом;
- разработан прототип автоматизированной системы структурнопараметрического синтеза ТРАП, выполнена его апробация и экспериментальное обоснование достигнутого экономического эффекта.
Объектом исследования диссертационной работы являются системные связи и закономерности функционирования адаптивных программных
систем.
Предметом исследования является математическое и алгоритмическое обеспечение структурно-параметрического синтеза ТРАП.
4
Методы исследований. Для решения поставленной задачи применялись методы системного анализа, моделирования изменчивости систем,
теории графов и гиперграфов, объектно-ориентированного проектирования, методологии UML.
Научная новизна результатов исследования заключается в следующем:
1. Впервые предложена математическая гиперграфовая модель изменчивости трехмерных адаптивных приложений, базирующаяся на теоретико-множественном представлении объектов характеристического моделирования. Модель позволяет описать структуру, системные связи
и функциональный состав адаптивной системы и обеспечивает возможность алгоритмизации основных процессов изменчивости без перекомпиляции исходного кода.
2. Впервые предложен алгоритм верификации системных конфигураций адаптивного приложения на основе трехмерной графики, использующий формальный аппарат гиперграфового представления диаграммы
характеристик. Алгоритм позволяет автоматически находить и исправлять
ошибки в описании структуры, поведения и системных связей программного приложения на уровне его предметной области.
3. Разработан алгоритм автоматического ситуационного выбора системных конфигураций в процессе выполнения адаптивного приложения,
который в отличие от известных использует трехконтурную систему обратных связей, регулирующих текущее состояние приложения в зависимости от действий пользователя, состояния среды выполнения и доступных
аппаратных ресурсов.
4. Предложен метод структурно-параметрического синтеза адаптивных программных систем, основанный на гиперграфовом подходе к формализации диаграмм характеристик и выбору системных пользовательских
конфигураций. Метод позволяет автоматизировать процесс разработки интерактивных графических приложений в различных предметных областях,
существенно сократив при этом временные и ресурсные затраты.
Практическая значимость работы. Предложенное математическое
и алгоритмическое обеспечение успешно реализовано в качестве компонентов автоматизированной программной системы, позволяющей разрабатывать адаптивные программные приложения в различных областях.
Практические результаты диссертационного исследования могут быть использованы в центрах подготовки специалистов с применением виртуальных тренажеров; для создания обучающего программного обеспечения
специального назначения; в центрах медицинских исследований и т.д.
В диссертационной работе приведены практические рекомендации по
применению разработанного прототипа системы, описаны основные этапы
создания типового адаптивного приложения.
Практическая значимость работы подтверждается актом внедрения,
свидетельством о государственной регистрации программы для ЭВМ,
5
а также дипломом победителя программы «У.М.Н.И.К.» осенней сессии
2015 г. Кроме того, результаты диссертационного исследования были использованы при выполнении научного проекта № 15-07-01553 РФФИ.
Достоверность и обоснованность результатов подтверждается корректным использованием и практической реализацией разработанного математического и алгоритмического аппарата, а также экспериментальной
проверкой прототипа системы при создании приложений различными категориями пользователей.
Соответствие паспорту специальности. Работа выполнена в соответствии с паспортом специальности ВАК РФ 05.13.01 – Системный анализ, управление и обработка информации (по отраслям), пункты 5, 7 и 8.
На защиту выносятся:
1) математическая модель изменчивости трехмерного адаптивного
приложения;
2) алгоритм верификации системных конфигураций адаптивной программной системы;
3) алгоритм автоматического ситуационного выбора системных конфигураций приложения в процессе выполнения;
4) метод структурно-параметрического синтеза адаптивных программных систем, основанный на гиперграфовом подходе к формализации
диаграмм характеристик и выбору системных конфигураций;
5) прототип автоматизированной системы синтеза трехмерных адаптивных приложений.
Апробация работы. Результаты научно-исследовательской работы
обсуждались на следующих конференциях: XVII Международной научнометодической конференции «Университетское образование», посвященной
70-летию Пензенского государственного университета (Пенза, 2013);
XI Всероссийской конференции молодых ученых, аспирантов и студентов
«Информационные технологии, системный анализ и управление» (Таганрог, 2013); XII Международной научно-методической конференции «Инновации в науке, образовании и бизнесе» (Пенза, 2014); XII Международной
научно-технической конференции «Новые информационные технологии
и системы» (Пенза, 2015); I Международной научно-технической конференции «Creativity in Intelligent Technologies and Data Science First
Conference» (Волгоград, 2015).
Публикации. По материалам диссертационного исследования опубликовано 18 печатных работ, в том числе 6 – в журналах, рекомендованных
ВАК РФ, 1 – в издании, индексируемом в Scopus; получено 1 свидетельство
об официальной регистрации программы для ЭВМ.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, библиографического списка из 133 наименований и 3 приложений. Работа содержит 44 рисунка и 6 таблиц. Общий объем работы – 140 страниц.
6
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении приведены сведения об актуальности работы, основных
целях и задачах исследования, научной новизне и практических результатах.
В первой главе приведен обзор современного состояния технологий
создания и применения графических адаптивных систем, а также основных
инструментальных средств автоматизации разработки приложений данного
типа. Указаны достоинства и недостатки существующих инструментов.
Приводится обоснование необходимости разработки усовершенствованного математического и алгоритмического аппарата.
Глава содержит описание существующих подходов к разработке адаптивных программных систем, использующих графическое представление данных. Отдельно рассмотрены методы создания адаптивного программного
обеспечения (в частности адаптивных компьютерных игр) и виртуальных тренажеров, поскольку приложения данных типов представляют собой частные
случаи адаптивных приложений. Однако существующие способы разработки
программного обеспечения недостаточно эффективны для проектирования
адаптивных трехмерных графических программных систем непрерывного
жизненного цикла, работающих в условиях высокодинамичной окружающей
среды и под управлением пользователей с разным уровнем компетенций
и технической оснащенности. Математическое описание алгоритмов функционирования, геометрических моделей и поведенческих стратегий для таких
систем пока недостаточно проработано и требует серьезного усовершенствования.
Проведен анализ методов структурно-параметрического синтеза программных систем, а также обзор инструментальных средств, которые могут
быть использованы для разработки адаптивных приложений. Было выделено
два основных типа таких средств – универсальные и специализированные.
Специализированные средства разработки могут быть использованы только
для построения узкого класса подобных приложений. С помощью универсальных средств возможно построение сложных программ при отсутствии ограничений на предметную область, однако их использование требует значительных
ресурсозатрат. Приложения, разрабатываемые с помощью систем обоих типов,
обладают коротким жизненным циклом и требуют перекомпиляции исходного
кода при выпуске обновленных версий.
Для решения перечисленных проблем было предложено новое
системно-методологическое решение, обеспечивающее процесс структурнопараметрического синтеза ТРАП на основе интеграции технологии моделирования изменчивости, теории гиперграфов и методов визуального проектирования программного обеспечения.
Во второй главе рассмотрены основные вопросы, связанные с разработкой методов и моделей структурно-параметрического синтеза адаптивного программного обеспечения. Дано обоснование применения методов характеристического моделирования для определения структуры программной
системы, задания связей и зависимостей между отдельными ее компонента-
7
ми, а также для описания ее адаптивного поведения в процессе выполнения.
Определено описание общей структуры программы в форме диаграммы характеристик, а также в форме ориентированного гиперграфа (аналогичного по
семантике диаграмме характеристик); представлена математическая модель
изменчивости адаптивной программной системы, использующей возможности трехмерной графики. Одним из центральных понятий предлагаемого подхода является понятие общей структуры ТРАП. Данное понятие обозначает
набор основных компонентов (программных функций, моделей, параметров)
программной системы и взаимосвязей между ними. Согласно предлагаемому
методу структурно-параметрического синтеза общая структура системы изначально определяется в формате модели характеристик, в частности, ее визуального отображения – диаграммы характеристик. Диаграмма характеристик представляет собой усовершенствованное И/ИЛИ-дерево, вершинами
которого являются компоненты адаптивной программы. Ребра данного дерева
определяют отношения между характеристиками.
Для обеспечения возможности автоматизации дальнейшей работы
с общей структурой производится ее преобразование в форму ориентированного гиперграфа. Данное представление диаграммы характеристик удобно
тем, что все возможные типы существующих в ней отношений будут иметь
унифицированное описание – в форме ориентированного гиперребра. Такое
ребро будет связывать отдельные множества вершин, каждая из которых соответствует характеристике диаграммы.
На рисунке 1 представлена диаграмма характеристик, описывающая
типовое адаптивное приложение, и ориентированный гиперграф, полученный
на основе диаграммы.
Предлагается следующая математическая модель изменчивости ТРАП:
M  ( F,S, X ) ,
где F – гиперграфовое представление общей структуры приложения, изначально заданной в форме диаграммы характеристик; S  {S1 , S 2 , S 3 , ..., S k } –
множество конфигураций диаграммы, каждая из которых представляет собой
описание одного состояния адаптивной системы (подграф исходного гиперграфа); X – матрица переходов между состояниями адаптивной программной
системы.
Описание общей структуры приложения в виде ориентированного гиперграфа (или F-графа) будет иметь вид
F  ( N,E ,  , ) ,
где N  {n1 , n 2 , n3 ,..., n n } – конечное множество вершин, каждая
из
которых
представляет
собой
характеристику
диаграммы;
E  {E1, E2 , E3 , ..., Em}, Ei  N  i  1, ..., m  | H (Ei ) |  qi  T (Ei )  1 – множество ребер гиперграфа, каждое из которых имеет собственное головное множество (множество вершин, в которые «входит» гиперребро) H ( E i ) мощностью qi , и хвостовое множество (множество вершин, из которых «исходит»
8
гиперребро) T ( E i ) мощностью, равной 1;   N – вершина, представляющая
корневую характеристику диаграммы;   E  M , M  N  N – функция маркировки, которая присваивает значение мощности mv (Ei )  (min,max)  M ,
здесь M – конечное множество значений мощности модели характеристик;
N – конечное множество вершин гиперграфа, каждому ориентированному
гиперребру E i , так что min,max  Ζ min  0, max  0, min  max  max  qi,
(Z – множество целых чисел). Значение мощности – это пара из минимального и максимального количества вершин головного множества гиперребра, которые могут быть включены в конфигурацию диаграммы характеристик с соответствующим гиперграфом.
а)
б)
Рисунок 1 – Диаграмма характеристик (а) и соответствующий гиперграф (б)
Матрица переходов X состоит из элементов xij , каждый из которых
является интервалом [a;b) либо пустым множеством , причем  xij  
и  xij  [0;) , j = 1, ..., k , i – фиксированное значение. Из состояния p
9
возможен переход в состояние q , если показатель, отвечающий за работу
пользователя с программой, C  x pq . Если x pq  , то перейти из состояния p в состояние q невозможно.
Метод структурно-параметрического синтеза ТРАП, базирующийся
на гиперграфовом подходе к формализации диаграмм характеристик, включает
в себя следующие этапы:
1. Этап морфологического анализа системы. В ходе выполнения данного этапа разрабатывается общая структура программной системы в формате
диаграммы характеристик, определяется пространство параметров элементов
диаграммы.
2. Этап теоретико-множественного преобразования структуры системы. Результатом выполнения данного этапа является гиперграфовое представление полученной на предыдущем этапе общей структуры адаптивной
программной системы.
3. Этап генерации состояний системы. Результатом выполнения данного этапа является множество конфигураций исходной диаграммы характеристик. В процессе разработки программной системы пользователем вручную
определяются необходимые структурные конфигурации, являющиеся базовыми для синтезируемой структуры программы. В процессе выполнения
на основе имеющейся целевой функции формируются производные промежуточные конфигурации. Данный процесс является частью более широкого
процесса адаптации в ходе выполнения программной системы.
4. Этап верификации системных конфигураций. Основное назначение
данного этапа – поиск и исправление ошибок в системных конфигурациях,
описывающих отдельные состояния адаптивной программной системы.
5. Этап определения взаимосвязей между состояниями. Результатом
выполнения данного этапа является матрица переходов.
В главе рассмотрена более подробно процедура генерации промежуточных состояний адаптивной программной системы. Пусть X , Y – два состояния программы, которым соответствуют одноименные непустые множества вершин гиперграфа, представляющего общую структуру ТРАП.
Введем понятие расстояния между состояниями системы
X Y
D( X , Y )  1 
.
max( X , Y )
Введенное понятие расстояния можно интерпретировать следующим
образом: чем больше у состояний X и Y общих вершин, тем ближе данные
состояния друг к другу; если состояния содержат одни и те же вершины,
то расстояние между ними равно нулю; если состояния не содержат ни одной
общей вершины, то расстояние между ними равно единице.
Пусть требуется сгенерировать состояние Z , промежуточное по отношению к X и Y . Тогда для данного состояния должно выполняться следующее условие:
10
D( X , Y )
.
2
Таким образом, состояние Z будет находиться «между» состояниями
X и Y на одинаковом расстоянии от них, равном половине расстояния между
X и Y . Такое состояние можно получить, если взять, например, половину
вершин из состояния X, а другую половину – из состояния Y.
Если требуется сгенерировать N  1 последовательных промежуточных состояний Zi , i  1, 2, ..., N , то для данных состояний должны выполняться условия
i
 D( X , Y ),
D( Z i , X ) 
( N  1)
( N  1  i)
 D( X , Y ).
D( Z i , Y ) 
(N  1)
Таким образом, промежуточные состояния будут расположены равномерно между состояниями X и Y .
В третьей главе рассматриваются вопросы, связанные с разработкой
алгоритмического и программного обеспечения системы структурно-параметрического синтеза ТРАП.
Поскольку конфигурация общей структурной диаграммы программной
системы определяется как действиями пользователя, так и автоматически, необходима разработка соответствующего алгоритма верификации.
Алгоритм работает с множеством конфигураций S  {S1 , S 2 , S 3 , ..., S k }
и формирует на его основе множество корректных конфигураций
C  {C1 ,C 2 ,C 3 , ..., C k } . В общем виде предлагаемый алгоритм содержит следующие шаги:
1. Расчет корректной конфигурации S1 с использованием процедур добавитьВершину и завершитьКонфигурацию. Вызов процедуры добавитьВершину осуществляется в цикле для каждой вершины s  S1 и формируемой
корректной конфигурации C1 .
2. Цикл по множеству конфигураций S . Выбор очередной конфигурации S i , где i  2, ..., k .
3. Получение множества добавленных в конфигурацию на текущем шаге вершин:
Sплюс  Si  S(i 1) .
4. Получение множества удаленных из конфигурации на текущем шаге
вершин:
Smin  S(i 1)  Si .
5. Вызов в цикле процедуры добавитьВершину для каждой вершины
s  Sплюс и формируемой корректной конфигурации Ci .
D ( Z , Y )  D( Z , X ) 
11
6. Вызов в цикле процедуры удалитьВершину для каждой вершины
s  Smin и формируемой корректной конфигурации Ci .
7. Вызов процедуры завершитьКонфигурацию для формируемой корректной конфигурации Ci .
8. Переход к пункту 2 алгоритма.
Процедура добавитьВершину работает с отдельной вершиной s  Si .
В ходе работы процедура добавляет в конфигурацию рассматриваемую
вершину и вершины, связанные с рассматриваемой отношением включения, а также вершины-родители, предварительно выполнив ряд проверок
на возможность добавления. Таким образом осуществляется формирование
корректного пути из добавляемой вершины в корневую вершину. Алгоритм
процедуры включает следующие шаги:
1. Проверка, включена ли рассматриваемая вершина s  Si в текущую
формируемую конфигурацию Ci . Если нет, то переход к пункту 2 алгоритма, в противном случае – завершение работы процедуры с успешным результатом.
2. Определение множества вершин, требующих отсутствия вершины
s  S i в Ci :
Mut  ( H (e) | e  Em  s  H (e)) \ {s} ,
где E m – множество гиперребер, являющихся отображением отношения
исключения.
3. Если Ci  Mut  , то переход к пункту 4 алгоритма, иначе – завершение работы процедуры с неуспешным результатом.
4. Определение множества гиперребер, в головное множество которых входит рассматриваемая вершина s  Si :
Ne  {e | e  E  s  H (e)} .
5. Если ne  Ne, H (ne)  Ci  Lmax (ne) , то переход к пункту 6 алгоритма, иначе – завершение работы процедуры с неуспешным результатом.
6. Сохранение копий вершин. Добавление рассматриваемой вершины
s  Si в конфигурацию. Определение множества вершин, «зависимых»
от s  Si – вершин-родителей и вершин, связанных с рассматриваемой отношением включения
Dep  ( T (e) | e  E  s  H (e))  ( H (e) | e  E r  T (e)  {s}) ,
где E r – множество гиперребер, являющихся отображением отношения
включения.
7. Цикл по элементам множества зависимых вершин Dep . Получение
очередного элемента d  Dep . Удаление рассматриваемого элемента
из множества Dep . Вызов процедуры добавитьВершину для d . Если вызов
был неуспешен, то переход к пункту 8, иначе – к пункту 9.
12
8. Восстановление исходного множества вершин и завершение работы процедуры с неуспешным результатом.
9. Если Dep  , то переход к пункту 7, иначе – завершение работы
процедуры с успешным результатом.
Процедура удалитьВершину работает с отдельной вершиной s  Si .
В ходе работы процедура удаляет из конфигурации рассматриваемую вершину и вершины-потомки, предварительно выполнив ряд проверок на возможность удаления. Алгоритм процедуры включает следующие шаги:
1. Проверка, включена ли рассматриваемая вершина s  Si в текущую
формируемую конфигурацию Ci . Если да, то переход к пункту 2 алгоритма, в противном случае – завершение работы процедуры с успешным результатом.
2. Получение множества вершин, требующих наличия рассматриваемой вершины s  Si в конфигурации:
Req   T (e) | e  Er  s  H (e) .
3. Если Ci  Req  , то переход к пункту 4 алгоритма, иначе – завершение работы процедуры с неуспешным результатом.
4. Сохранение копий вершин. Удаление рассматриваемой вершины
s  Si из конфигурации. Получение множества дочерних вершин
Dep  H (e) | e  E  T (e) = {s}.
5. Цикл по элементам множества Dep . Получение очередного элемента d  Dep . Удаление рассматриваемого элемента из множества Dep . Вы-
зов процедуры удалитьВершину для d . Если вызов был неуспешен, то переход к пункту 6, иначе – к пункту 7.
6. Восстановление исходного множества вершин и завершение работы процедуры с неуспешным результатом.
7. Если Dep  , то переход к пункту 5 , иначе – завершение работы
процедуры с успешным результатом.
Процедура завершитьКонфигурацию работает с частично сформированной на предыдущих этапах корректной конфигурацией Ci . Основное назначение процедуры – поиск в конфигурации гиперребер, мощность головного множества которых меньше ограничения на минимально допустимую
мощность, и добавление в конфигурацию необходимых вершин. Алгоритм
работы процедуры включает следующие шаги:
1. Цикл по гиперребрам с недостаточной минимальной мощностью.
Если e | e  E  T (e)  Сi  H (e)  Ci  Lmin (e) , то переход к пункту 2,
иначе – завершение работы процедуры с успешным результатом.
2. Получение множества невыбранных головных вершин текущего
гиперребра
F = H (e) \ Ci .
13
3. Получение первого элемента f  F . Сохранение копии конфигурации. Вызов процедуры добавитьВершину для f  F . Если вызов процедуры был неуспешен, то переход к пункту 4, иначе – к пункту 1.
4. Восстановление исходного множества вершин. Удаление рассмотренной вершины из множества F.
5. Если F =  , процедура завершает работу с неуспешным результатом, иначе – переход к пункту 3.
Предложенный алгоритм позволяет исправить все возможные виды
ошибок, которые могут встретиться при составлении (или генерации) описаний состояний программной системы.
Один из основных рассматриваемых вопросов третьей главы – разработка алгоритма автоматического ситуационного выбора системных конфигураций в процессе выполнения приложения. Алгоритм включает в себя следующие шаги:
1. Установка номера текущей конфигурации i  1.
2. Выбор конфигурации Si .
3. Расчет показателя P производительности вычислительной системы:
 PR
 , если PR  PE ,
P   PE
1, если P  P ,

R
E
где PR – производительность ЭВМ, на которой запускается программа;
PE = k · P0 – производительность эталонной ЭВМ; здесь k – коэффициент,
определяемый автором приложения (по умолчанию k  1 ); P0 – производительность ЭВМ, на которой создавалось приложение.
4. Первый этап параметрического синтеза: на основе полученного
коэффициента производительности системы происходит выбор соответствующего уровня детализации трехмерных моделей. На диаграмме характеристик узел, соответствующий трехмерному объекту, может содержать несколько трехмерных моделей разной степени детализации. Данные модели
упорядочены по возрастанию уровня детализации. Если некоторый объект O имеет n уровней детализации (O1 , O2 , ..., On ) , то при визуализации
данного объекта будет выбран вариант Oi , где i   P  x  , x  – целое число, ближайшее к x ,  x   x .
5. Развертывание поддеревьев моделей, функций и параметров. Ожидание завершения состояния.
6. Вычисление показателя работы пользователя с ТРАП. При d  0
формула расчета будет иметь следующий вид:
14
 tнорм d норм 
+


t
d 

,
С=
2
где t – время пребывания системы в текущем состоянии; d – количество
нежелательных пользовательских действий, случившихся при выполнении
состояния; tнорм и d норм – нормальные значения показателей t и d , задаваемые автором приложения для каждой конфигурации. В случае, если
d  0 , формула заменяется на следующую:
  tнорм

+ 1

t

 , если d
С = 
норм  0,
2

  , если d норм  0.
7. Второй этап параметрического синтеза: определение значений параметров, используемых в функциях (ветвь «Параметры» общей структуры
на рисунке 1). Данные параметры могут принадлежать к одному из трех
типов данных – целое число, вещественное число, перечисление. В первых
двух случаях автор должен задать пару граничных значений (xнач , xкон ) ,
в пределах которых параметр может принимать свои значения. В последнем случае автор должен перечислить значения x1 , x2 , ..., xn . Для расчета
параметров необходимо провести вычисление нормализованного показателя Cнорм  [0;1]. Для этого нужно отобразить интервал [0;  ] , которому
принадлежит С , на интервал [0;1] . Это можно сделать, например, с помощью следующего преобразования:
C
 , если C  b,
Снорм =  b
1, если С  b,
где 0  b   – наибольшее значение показателя С , определенное для текущего состояния. Другой возможный вариант преобразования выглядит следующим образом:
Снорм = 1  e kC ,
где k  0 – некоторый коэффициент, позволяющий настроить вид преобразования. После того, как получено нормированное значение показателя работы пользователя с состоянием, вычисляются значения параметров, используемых в следующем состоянии. В случае, если параметр является
целым или вещественным числом, для которого заданы граничные значения (xнач , xкон ) , то значение параметра находится по формуле
x  xнач  Cнорм (xкон  xнач ) .
Если параметр является перечислением, то его значение равно x  xi ,
где i   Cнорм n  ; x  – целое число, ближайшее к x , x   x .
15
8. Если это необходимо, корректировка матрицы переходов с учетом
состояния среды выполнения
X  E X эт ,
где X эт – эталонная (исходная) матрица переходов, задаваемая пользователем для E = 1; E – показатель, определяющий состояние среды выполнения. Данный показатель вычисляется на основании множества значений
показателя С , характеризующих то, как пользователь работал с несколькими последними состояниями программной системы. В случае, если среда
выполнения оказывается слишком сложной для пользователя (значения показателя С по результатам прохождения нескольких последних состояний
являются низкими), происходит уменьшение значения показателя E и, соответственно, сужение диапазонов значений, расположенных в ячейках
матрицы. При усложнении среды выполнения происходит увеличение значения показателя E.
9. Если существует такой интервал xij , что C  xij , то i  j и осуществляется переход к пункту 2 алгоритма. Иначе работа приложения завершается.
Также в главе представлено описание программной реализации системы. Архитектура прототипа системы представлена на рисунке 2.
Рисунок 2 – Архитектура прототипа системы
16
Как видно из рисунка, система состоит из двух подсистем – подсистемы разработки и подсистемы запуска адаптивного приложения. Каждая
из подсистем реализует свой собственный набор модулей, но некоторые
модули (например модуль визуализации) являются общими для обеих подсистем.
Предложенная математическая модель и алгоритмы верификации
реализованы в модуле работы с изменчивостью подсистемы синтеза. Данный модуль включает в себя также два внутренних модуля – модуль работы с моделью характеристик и модуль синтеза структуры ТРАП. Первый
модуль реализует функции задания описания диаграммы характеристик
графическим и текстовым способом, а также алгоритм преобразования диаграммы в гиперграф, описание которого также приведено в главе. Второй
модуль отвечает за создание и верификацию конфигураций составленной
диаграммы.
Помимо модуля работы с изменчивостью, в главе приведено подробное описание таких модулей, как модуль авторизации и учета пользователей, модуль формирования выходных данных, модуль исполнения, модуль
компоновки.
Также в главе приведено описание визуального языка программирования, используемого для написания программных функций. Возможно
расширение базовых возможностей языка за счет подключения дополнительных библиотек.
В четвертой главе приведено описание прототипа системы, реализующего предложенные математические и алгоритмические решения.
На нескольких тестовых примерах, описывающих виртуальные тренажеры в области медицины и передвижной техники, показана работоспособность алгоритма верификации системных пользовательских конфигураций.
На примере реализации методики диагностирования нагляднодейственного интеллекта «Кубики Коса» в форме адаптивного приложения
показана эффективность введенной во второй главе математической модели изменчивости. Приведено пошаговое описание процесса создания адаптивного приложения. Даны методические рекомендации по работе с прототипом системы.
С целью оценки эффективности внедрения системы было проведено
экспериментальное сравнение временных затрат на создание одного адаптивного приложения с использованием системы и без нее. Для разработки
программы без использования системы использовалась технология Windows presentation foundation(WPF). По условиям эксперимента, синтезируемое приложение включало 17 структурных состояний, из которых 8 генерировались в процессе выполнения программы. Сравнительную оценку
можно наглядно представить в виде таблицы 1.
17
Таблица 1– Результаты экспериментальной оценки эффективности синтеза ТРАП
Наименование вида работы
Сложность
ТРАП
Временные затраты
без системы
(часов)
с системой
(часов)
73 500
полигонов
1
1
Разработка модуля визуализации
манипуляции с объектами ТРАП
476 строк кода
20
0
Разработка модуля реализации
адаптивного поведения ТРАП
603 строки кода
26
0
742 строки кода
30
10
347 строк кода
16
4
Описание общей диаграммы
характеристик / разбиение
приложения на компоненты
и определение взаимосвязей
26 узлов, 14 связей
3
1
Описание отдельных состояний
работы ТРАП
17 состояний
(8 промежуточных)
3
1
Описание матрицы переходов /
определение связей
между состояниями
ИТОГО
9 на 9 строк
3
1
102,5
18,5
Подготовка необходимых
трехмерных моделей
Разработка алгоритмической
основы функционирования ТРАП
Разработка интерфейсов
По данным таких рейтинговых агентств, как КИАС и Person Agency,
в среднем один человеко-час специалиста стоит около 600 руб. Тогда в денежном выражении создание подобного адаптивного приложения без применения автоматизированной системы стоит порядка 61 500 руб., а с применением системы – 11 100 руб.
Таким образом, применение автоматизированной системы позволяет
более чем в 5 раз сократить затраты на создание адаптивного приложения.
Для определения степени увеличения жизненного цикла адаптивной
программы за счет применения разработанного математического и алгоритмического обеспечения использовались экспертные оценки. По мнению
экспертов, разработанное алгоритмическое и математическое обеспечение
позволит увеличить жизненный цикл адаптивного приложения на 20 %.
Как видно из проведенных экспериментов, применение разработанных моделей, методов и алгоритмов позволяет существенно снизить затраты на разработку и повысить эффективность функционирования адаптивных программных систем на основе трехмерной графики.
В заключении приведены основные выводы и результаты исследования.
18
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
1. Проведен анализ предметной области, который показал недостаточную эффективность существующих подходов к разработке трехмерных адаптивных приложений по причине высоких ресурсозатрат и короткого жизненного цикла.
2. Впервые предложена математическая гиперграфовая модель изменчивости трехмерных адаптивных приложений, базирующаяся на теоретикомножественном представлении объектов характеристического моделирования.
Модель позволяет описать структуру, системные связи и функциональный состав адаптивной системы и обеспечивает возможность алгоритмизации основных процессов изменчивости без перекомпиляции исходного кода.
3. Впервые предложен алгоритм верификации системных пользовательских конфигураций, использующий формальный аппарат гиперграфового
представления диаграммы характеристик. Алгоритм позволяет автоматически
находить и исправлять ошибки в пользовательском описании структуры, поведения и системных связей адаптивной программы на уровне понятий ее предметной области.
4. Разработан алгоритм автоматического ситуационного выбора системных конфигураций в процессе выполнения приложения, который, в отличие от известных, использует трехконтурную систему обратных связей, регулирующих текущее состояние программы в зависимости от действий
пользователя, состояния среды выполнения и доступных аппаратных ресурсов.
5. Предложен метод структурно-параметрического синтеза адаптивных
программных систем, основанный на гиперграфовом подходе к формализации
диаграмм характеристик и выбору системных конфигураций. Метод позволяет автоматизировать процесс разработки интерактивных графических приложений в различных предметных областях, существенно сократив при
этом временные и ресурсные затраты.
6. Разработан прототип автоматизированной системы структурнопараметрического синтеза адаптивных приложений на основе трехмерной графики, реализующий предложенные методы, модели и алгоритмы.
7. С помощью прототипа системы разработано адаптивное приложение,
демонстрирующее преимущества использования предлагаемых моделей и алгоритмов. Использование предложенного в диссертации математического и алгоритмического аппаратов позволило снизить ресурсозатраты на создание одного адаптивного приложения более чем в 5 раз и увеличить его жизненный
цикл на 20 %.
ОСНОВНЫЕ ПУБЛИКАЦИИ ПО МАТЕРИАЛАМ ДИССЕРТАЦИИ
Публикации в изданиях, рекомендованных ВАК РФ
1. Евсеева, Ю. И. Моделирование изменчивости в виртуальной образовательной среде с помощью методов теории графов и гиперграфов /
Ю. И. Евсеева // Фундаментальные исследования. – 2016. – № 11. –
С. 27–31.
19
2. Евсеева, Ю. И. Метод структурно-параметрического синтеза адаптивных программных компонентов виртуальной образовательной среды /
А. С. Бождай, Ю. И. Евсеева // Известия высших учебных заведений. Поволжский регион. Технические науки. – 2016. – № 3 (39). – С. 85–93.
3. Евсеева, Ю. И. Разработка алгоритма самоорганизации интерактивных программных компонентов виртуальной образовательной среды /
В. И. Волчихин, А. М. Бершадский, А. С. Бождай, Ю. И. Евсеева, А. А. Гудков // Современные наукоемкие технологии. – 2016. – № 11. – С. 15–18.
4. Евсеева, Ю. И. Алгоритм верификации структуры трехмерного
адаптивного приложения / Ю. И. Евсеева // Известия высших учебных заведений. Поволжский регион. Технические науки. – 2015. – № 4 (36). –
С. 5–16.
5. Евсеева, Ю. И. Математическая модель изменчивости адаптивных
графических приложений / А. С. Бождай, Ю. И. Евсеева, А. А. Гудков //
Известия Волгоградского государственного технического университета.
Актуальные проблемы управления, вычислительной техники и информатики в технических системах. – 2015. – № 14 (178). – С. 7–12.
6. Евсеева, Ю. И. Моделирование изменчивости в автоматизированном проектировании адаптивных обучающих программ / А. С. Бождай,
Ю. И. Евсеева // Известия высших учебных заведений. Поволжский
регион. Технические науки. – 2015. – № 1 (33). – С. 5–18.
Публикации в изданиях, индексируемых в SCOPUS
7. Evseeva, J. Variability Modeling in the Automated System for Authoring Intelligent Adaptive Applications on the Basis of Three-Dimensional Graphics / A. Bershadsky, A. Bozhday, A. Gudkov, J. Evseeva, V. Mkrtchian // Creativity in Intelligent Technologies and Data Science First Conference. –
Volgograd, 2015. – P. 149–159. DOI: 10.1007/978-3-319-23766-4_12
Основные публикации в других изданиях
8. Evseeva, J. Development of the System for Authoring Three-Dimensional Learning Applications for Use in E-Learning Environment / J. Evseeva,
A. Bozhday, A. Gudkov // Handbook of Research on Estimation and Control
Techniques in E-Learning Systems / Eds.: V. Mkrttchian, A. Bershadsky,
A. Bozhday, M. Kataev, S. Kataev. – Hershey, PA : IGI Global, 2016. –
P. 410–440. DOI: 10.4018/978-1-4666-9489-7.ch029
9. Евсеева, Ю. И. Средства визуального программирования в автоматизированной системе синтеза трехмерных компьютерных приложений /
А. С. Бождай, Ю. И. Евсеева, А. А. Гудков // Модели, системы, сети в экономике, технике, природе и обществе. – 2014. – № 1 (9). – С. 85–90.
10. Евсеева, Ю. И. Автоматизированная система проектирования интерактивных адаптивных приложений на основе трехмерной графики /
Ю. И. Евсеева // Вестник Пензенского государственного университета. –
2015. – № 4 (12). – С. 118–121.
20
11. Евсеева, Ю. И. Автоматизация процесса структурно-параметрического синтеза трехмерных адаптивных приложений / Ю. И. Евсеева //
Современные научные исследования и инновации. – 2016. – № 5 (61). –
С. 38–40.
12. Евсеева, Ю. И. Применение моделей изменчивости в структурнопараметрическом синтезе трехмерных адаптивных приложений / Ю. И. Евсеева // Современная техника и технологии. – 2016. – № 5 (57). – С. 56–59.
13. Евсеева, Ю. И. Применение моделей изменчивости в разработке
адаптивного обучающего программного обеспечения / Ю. И. Евсеева,
А. А. Гудков // Современные научные исследования и инновации. – 2014. –
№ 9 (41). – С. 64–67.
14. Евсеева, Ю. И. Представление структуры трехмерного адаптивного приложения с помощью модели характеристик / Ю. И. Евсеева // Новые
информационные технологии и системы : сб. науч. ст. XII Междунар. науч.-техн. конф. – Пенза, 2015. – С. 14–15.
15. Евсеева, Ю. И. Методы моделирования изменчивости в интеллектуальных обучающих комплексах / Ю. И. Евсеева // Информационные технологии, системный анализ и управление (ИТСАиУ-2013) : сб. тр. XI Всерос. науч. конф. молодых ученых аспирантов и студентов. – Таганрог,
2013. – Т. 2. – С. 15–18.
16. Евсеева, Ю. И. Автоматизация процесса разработки трехмерных
обучающих систем / Ю. И. Евсеева, А. А. Гудков // Университетское образование : сб. ст. XVII Междунар. науч.-метод. конф. – Пенза, 2013. –
С. 104–106.
17. Евсеева, Ю. И. Модель вариативности семейства программных
продуктов, генерируемых системой синтеза трехмерных обучающих приложений / А. С. Бождай, Ю. И. Евсеева, А. А. Гудков // Инновации в науке,
образовании и бизнесе : материалы XII науч.-метод. конф. – Пенза, 2014. –
С. 54–58.
Свидетельство о государственной регистрации
18. Свид. о гос. рег. программы для ЭВМ № 2016617796. Программа
для создания трехмерных адаптивных приложений / Евсеева Ю. И. – Зарег.
в Реестре программ для ЭВМ Федеральной службы по интеллектуальной
собственности. – 2016 г., 14 июля.
21
Научное издание
ЕВСЕЕВА Юлия Игоревна
РАЗРАБОТКА МАТЕМАТИЧЕСКОГО
И АЛГОРИТМИЧЕСКОГО ОБЕСПЕЧЕНИЯ
ДЛЯ СИСТЕМЫ СТРУКТУРНО-ПАРАМЕТРИЧЕСКОГО СИНТЕЗА
ТРЕХМЕРНЫХ АДАПТИВНЫХ ПРИЛОЖЕНИЙ
Специальность 05.13.01 – Системный анализ, управление
и обработка информации (в технике и технологиях)
Редактор Т. В. Веденеева
Технический редактор Н. В. Иванова
Компьютерная верстка Н. В. Ивановой
Распоряжение № 25/112-2016 от 14.12.2016.
1
Подписано в печать 15.12.2016. Формат 6084 /16.
Усл. печ. л. 1,16. Заказ № 755. Тираж 100.
___________________________________________________
Издательство ПГУ.
440026, Пенза, Красная, 40.
Тел./факс: (8412) 56-47-33; e-mail: iic@pnzgu.ru
22
23
24
1/--страниц
Пожаловаться на содержимое документа