ДонНТУ   Портал магистров

Кустов Максим Николаевич

Факультет компьютерных наук и технологий

Кафедра компьютерной инженерии

Специальность «Инженерия программного обеспечения»

Повышение эффективности алгоритмов генерации программного кода по методологии SADT

Научный руководитель: к.ф-т.н., доц. Дацун Наталья Николаевна

Резюме Биография Реферат Библиотека Ссылки Отчет о поиске Индивидуальный раздел

Реферат по теме выпускной работы

Содержание

• Введение
• 1. Актуальность SADT методологии

                1.1 Общие сведения о языке формальных спецификаций SADT
                1.2 Области применения методологии SADT

• 2. Обзор исследований по теме магистерской работы

                2.1 Современные методы генерации программного кода
                2.2 Инструментарий для реализации
                2.3 Существующая реализация. Инварианты алгоритмов

• Заключение
• Список источников

Введение

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

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

1. Актуальность SADT методологии

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

1.1 Общие сведения о языке формальных спецификаций SADT

SADT (Structured Analysis and Design Technique) завоевал популярность благодаря своим характерным особенностям, а именно:

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

• главной задачей является структурированная, упорядоченная, детальная декомпозиция предмета или предметной области;

• уровень детализации зависит от внешних факторов и не ограничивается особенностями методологии.

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

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

1.2 Области применения методологии SADT

SADT успешно используется в военных, промышленных и коммерческих организациях для решения широкого спектра задач: программное обеспечение телефонных сетей, системная поддержка и диагностика, долгосрочное и стратегическое планирование, автоматизированное производство и проектирование, конфигурация компьютерных систем, обучение персонала, встроенное ПО для оборонных систем,  управление финансами и материально–техническим снабжением и др. Одним, сравнительно новым, применением методологии SADT, является применение SADT как инструмента менеджмента качества [1].

2. Обзор исследований по теме магистерской работы

В настоящее время ведутся исследования, направленные на решение проблем несогласованностью структурных частей;  двусмысленностью, избыточностью (неполнотой) сопровождаемой проектной документации. Сформировалось даже целое научное направление — CASE–технологии (Computer Aided Software Engineering), реализующих выполнение некоторых этапов разработки в автоматическом режиме. По данным некоторых исследований, использование такого подхода позволяет повысить производительность труда при разработке системы, уменьшить материальные затраты, уменьшить сложность и повысить качество проектов [2].

2.1 Современные методы генерации программного кода

В настоящее время индустрия разработки программного обеспечения использует визуальный метод контакта с пользователем, а не текстовый, как это было, например, в при работе в DoS. В связи с этим, важен  вопрос генерации программного кода по графическим моделям (примитивам). Модели можно разделить на два класса: статические и динамические [3].

Основой для статических моделей объектно–ориентированных программ является диаграмма классов. Многие инструментальные средства (Rational Rose) используют именно этот подход — генерируется основа, т.н. скелет, кода по диаграмме классов [3].

Динамические свойства рассматриваемого класса программ лучше всего описать, используя диаграммы состояний (графы переходов). Это обусловлено тем, что любая программа имеет состояния, пусть и не явно выделенные. Существуют средства, которые генерируют программный код по графам переходов. Такие инструменты являются узко специализированными — они производят код на одном (иногда двух) конкретном языке программирования.

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

Результатом этой работы стало инструментальное средство, позволяющее преобразовывать изображение с графов переходов, представленных с помощью редактора MS Visio, в исходные коды программ на различных языках программирования, для которых предварительно были созданы соответствующие шаблоны [3]. Процесс генерации кода был разделён на три этапа: преобразование графа переходов в программное представление, преобразование программного представления в некий общий формат, и непосредственно дальнейшее преобразование из общего формата в программный код.

Ещё один подход был рассмотрен в работе Кручинина А. Н. Автоматическая генерация программных компонент по высокоуровневым спецификациям. Автор уделяет внимание проблемы качества сгенерированного программного кода, указывает на появление сложного кода, который со временем становится неочевидным и очень трудным для понимания и последующей модификации. Главной целью работы является рассмотрение методов достижения приемлемой локализации программного кода. Предлагается решение проблемы реализации сквозной функциональности. Это позволит уменьшить стоимость внесения изменений в программный код. Работа является продолжением и развитием работ A. Л. Фуксмана, посвященным проблемам рассредоточенности программного коде, а также идей о вертикальном слоении программы.

В этой работе были разработаны методы структуризации программного кода. Для достижения поставленной цели ведется разработка методов применения аспектно-ориентированной парадигмы, не ограниченных исключительно объектно–ориентированными языками, путем разрешения следующих задач: о расширении области применимости точек связывания на не объектно–ориентированные языки; о расширении области применимости аспектов на не объектно–ориентированные языки [4].

 

2.2 Инструментарий для реализации

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

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

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

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

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

 

2.3 Существующая реализация. Инварианты алгоритмов

Подобная программная система была разработана Губанем Б. [5]. Она генеририрует программный код для работы с массивами целых и массивами строк. Были реализованы функции поиска максимального (минимального) значений в массиве и перестановка элементов массива.

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

Автор работы выделял общие части в алгоритмах, т.н. инварианты алгоритмов.

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

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

Следуя рассмотренному принципу, также можно выделить инварианты алгоритмов и построить SADT–диаграммы для других структур данных (файлов прямого и последовательного доступа, строк, деревьев).

Заключение

Проанализировав существующие подходы к автоматической генерации программного кода, выбор остановился на использовании языка формальных спецификация SADT с применением инвариантов алгоритмов. Таким образом, направлением дальнейших исследований будет совершенствование уже существующей реализации такого подхода. Опираясь на работу [5] расширить функциональность для базовых алгоритмов поиска, модификации и удаления элементов. Реализовать работу этих базовых алгоритмов с большим набором основных структур данных языков программирования (матрицы, списки, деревья).

При написании данного реферата магистерская работа еще не завершена. Окончательное завершение: декабрь 2012 года. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанной даты.

Список источников

1. Герман М.В., Галактионов Е.А., Применение методологии структурного анализа и проектирования SADT/IDEF0 как инструмента менеджмента качества. Электронный ресурс. Режим доступа: http://www.hsb.tsu.ru/content.php?id=116
2. Козлинский А.В. CASE–технология: индустриальная разработка систем обработки информации // Компьютерное обозрение. — 1993. — №1.
3. Канжелев С. Ю. Автоматическая генерация кода программ с явным выделением состояний, Software Engineering Conference (Russia) — 2006 (SEC (R) 2006), с. 60–63.
4. Кручинин А. Н. Автоматическая генерация программных компонент по высокоуровневым спецификациям, Ростов–на–Дону, 2006.
5. Губань Б. И., Анализ эффективности алгоритмов генерации кода по технологии SADT, Реферат по теме выпускной работы. Электронный ресурс. Режим доступа: http://masters.donntu.ru/2010/fknt/guban/diss/index.htm
6. Жарихина М.А. Подготовка управляющих программ для станков с ЧПУ / Учебно–научно–производственный журнал Автоматизация и управление в машиностроении, Выпуск №21, — Москва, — 2003.
7. Анисимов Б.П., Котов В.В. Современные методологии структурного анализа и проектирования систем обработки информации / Журнал Программные продукты и системы, Выпуск №2, — Москва, — 1997.
8. Gabrovska K., Smrikarov A. Structural analysis and methods for development of software tool for design and energy simulation of PV–hybrid power supply systems in poultry farms / International Conference on Computer Systems and Technologies CompSysTech, — 2005.
9. Богатырёв М.Ю. Инварианты и симметрии в генетических алгоритмах. — Тула: Тульский государственный университет, 2003. — 8 с.
10. Ross D., Structured Analysis (SA): A Language for Communicating Ideas, IEEE Transactions on Software Engineering, vol. SE–3, N. 1, pp. 16–34. 1, Jan. 1977.