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

О чем мечтают все программисты? Наверное, чтобы компьютер сам писал за них программы. А если это невозможно, то хотя бы чтобы компьютер максимально помогал в этом нелегком занятии. Цель направления "Технологии программирования" Международной научной лаборатории "Компьютерные технологии" разработка методов, позволяющих автоматизировать процесс проектирования, разработки, тестирования и верификации программного обеспечения.

 

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

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

 

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

Кроме того, эти задачи оптимизации зачастую являются, как минимум, NP-трудными, поэтому для их решения применяются всевозможные метаэвристические алгоритмы, а также методы пропозиционального кодирования на таких языках, как SAT и CSP.

 

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

 

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

 

Конечно-автоматные модели широко применяются на практике при реализации систем управления. Например, в промышленном стандарте IEC 61499 управляющие программы реализуются в виде сетей взаимосвязанных функциональных блоков (рис. 2); базисные функциональные блоки реализуются с помощью конечных автоматов (рис. 3). Одно из направлений исследований – автоматизация генерации автоматных моделей функциональных блоков по примерам поведения и темпоральной спецификации.

network.png

Рис. 2. Фрагмент сети взаимосвязанных функциональных блоков

 
 

ecc.png

Рис. 3. Пример конечного автомата, реализующего базисный функциональный блок

 
 

В рамках программы «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2014 - 2020 годы» проводятся исследования по проектированию, верификации и тестированию кибер-физических систем. В частности, разрабатываются методы генерации формальной модели объекта управления по симуляционной модели (рис. 4). Разрабатываемые методы направлены на повышение надежности ответственных кибер-физических систем за счет формальной верификации в замкнутом цикле.

 

 

Рис. 4. Генерация моделей объекта управления по симуляционной модели

 

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

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

 

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

 

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

 

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

 

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

 

 

 

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