Технологии программирования

О чем мечтают все программисты? Конечно, чтобы компьютер сам писал за них программы или максимально помогал в этом нелегком занятии. Множество программных проектов, начиная от ассемблеров, компиляторов и интерпретаторов и заканчивая построителями исполняемого кода по UML-диаграммам, направлены на достижение именно этой цели.

 

Поисковая инженерия программного обеспечения (Search Based Software Engineering) -- способ решения задач, возникающих в процессе производства программного обеспечения, путем сведения их к задачам оптимизации и последующего решения этих задач.

В поисковой инженерии программного обеспечения применяются:

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

 

Построение управляющих программ по спецификации

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

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

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

На рис. 1 представлена модель автопилота на основе конечного автомата, выполняющая "бочку". Автомат представлен в правой части рисунка. Данный автомат построен с помощью муравьиных алгоритмов на основе траекторий нескольких полетов, выполненных людьми в авиасимуляторе.

 

Автоматный автопилот

Рис. 1 - Автопилот на основе конечного автомата

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

 

Генерация тестов с испольхованием эволюционных алгоритмов

Тестирование является одним из самых затратных этапов производства программного обеспечения - по оценке экспертов, на него уходит до 50% времени и более 50% стоимости производства ПО.

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

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

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

 

Построение тестов
Рис. 2 - Графики, иллюстрирующие процесс построения тестов против алгоритма поиска максимального потока

 

 

Информация © 2015-2017 Университет ИТМО
Разработка © 2015 Департамент информационных технологий