автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Индуктивный синтез алгоритмов на основе аксиоматических теорий постановок задач

На правахрущщси

ГУТОРОВ Дмитрий Анатольевич

ИНДУКТИВНЫЙ СИНТЕЗ АЛГОРИТМОВ НА ОСНОВЕ АКСИОМАТИЧЕСКИХ ТЕОРИЙ ПОСТАНОВОК ЗАДАЧ

05.13.01 - Системный анализ, управление и обработка информации

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

- з ДЕК 2009

Москва-2009

003486984

Работа выполнена на кафедре Концептуального анализа и проектирования Московского физико-технического института (государственного университета)

Научный руководитель: кандидат технических наук, доцент

Капустян Виктор Михайлович

Официальные оппоненты: доктор физико-математических наук,

профессор

Непейвода Николай Николаевич

доктор физико-математических наук, доцент

Новосельцев Виталий Борисович

Ведущая организация: Научно-исследовательский институт

информационных технологий Правительства Москвы

Защита состоится 14 декабря 2009 года в 11 часов на заседании диссертационного совета Д 002.086.02 Института системного анализа РАН по адресу: 117312, Москва, проспект 60-летая Октября, 9.

С диссертацией можно ознакомиться в библиотеке Института системного анализа РАН.

Автореферат разослан «13» ноября 2009 года.

Ученый се!фетарь диссертационного совета:

доктор технических наук, профессор

А.ИЛропой

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

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

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

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

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

Разработчики указывают на типичные проблемы, часто сопровождающие проектирование крупных информационных систем:

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

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

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

Экспертами предлагаются следующие принципы проектирования больших информационных систем:

о Построение архитектуры (модели) предметной области, о Выделение основных функций системы, их декомпозиция, о Отделение основных функций от инфраструктурных, о Автоматизация процесса синтеза программ.

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

Современное состояние методов проектирования не позволяет разработчикам в полной мере владеть функционалом своих продуктов: функционал настолько сложен и разветвлен, что члены команд разработчиков полностью владеют лишь его часть (что является следствием применения методологий проектирования, таких как ШРО (Hierarchical Input Processing Output) и др.). Это является одной из причин размещения у внешних контрагентов заказов на проведение работ по комплексному исследованию собственных систем и сопоставительному анализу с системами конкурентов.

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

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

К настоящему времени сложились определенные подходы к автоматизации процесса разработки программ путем их синтеза:

1. Дедуктивный синтез (логический вывод) - программа извлекается из доказательств теорем.

2. Индуктивный синтез (синтез программ по примерам) - извлечение программы из примеров путем обобщения, выявления последовательностей, прогрессий и т.д.

3. Трансформационный синтез (трансляция) - поэтапное преобразование спецификации, заданной на языке высокого уровня, в программный код на языке более низкого уровня.

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

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

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

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

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

В работе были поставлены следующие задачи:

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

теоретико-множественный анализ прецедентов решений задач с формированием аксиоматических теорий прецедентов;

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

- разработка метода формирования аксиоматической теории для теоретико-множественного описания типологии постановок задач;

- разработка метода синтеза алгоритмов решения задач, описанных в типологии;

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

Научная новизна

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

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

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

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

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

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

3) Средство автоматизации процедуры синтеза сложных алгоритмов протопи! экспертной системы в области алгоритмов.

Апробация работы

Результаты работы докладывались и обсуждались на следующих конференциях и научных семинарах: VI Всероссийская школа-семинар молодых ученых «Управление большими системами», Международный симпозиум «Надежность и качество» (Пенза, 2009); X Международная научно-техническая конференция "Теоретические и прикладные вопросы современных информационных технологий" (Улан-Удэ, 2009), Межвузовская научная конференция «Системное Программирование. Интеллектуальные Системы. Обеспечение Качества - 2009» (Екатеринбург, 2009), 47-я, 48-я, 51-я научные конференции МФТИ (Долгопрудный, 2004-2005, 2008), научный семинар Отдела имитационных систем и исследования

операций Вычислительного центра им. А. А. Дородницына РАН (2009), научный семинар Механико-математического факультета МГУ (2009). Публикации по теме диссертации

По теме диссертации опубликовано 3 статьи (в том числе одна пубдикация в издании, рекомендованном ВАК Минобрнауки России) и 6 докладов на научных конференциях и симпозиумах. Струю-ура и объем диссертации

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Введение

Во введении обоснована актуальность выбранной темы, проведен анализ проблемы. Сформулированы основные задачи и цель работы. Кратко изложено содержание работы и показана ее практическая ценность. Глава 1

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

Для проведения сопоставительного анализа постановок задач и алгоритмов необходимо выразить их в единой форме, для чего были использованы аксиоматические теории. Ключевым компонентом используемого языка описания аксиоматических теорий является понятие родовой структуры, введенной Н.Бурбаки.

Аксиоматическая теория состоит из двух частей: ядра теории и тела теории. Ядро теории - это априорная ее часть. В нее входят 1) базовые понятия, 2) отношения между базовыми понятиями, 3) ограничения на объем базовых понятий и отношений - аксиомы. Тело теории состоит из выводимых из ядра теории понятий. На рис.1 приведена структура аксиоматической теории и пример элементов теории для задачи о максимальном потоке в сети

Структура задачи Структура теории Пример

\ 1) вершины 2) Пропускные способности

Условия задачи Базовые понятия , (Базисные множества)

Вопрос задачи Постановка задачи Отношения (Родрвые структуры) < 1) Дут-связи между вершинами 2) Пропускные способности дуг

Ограничения (Аксиомы) Ядро теории 1) Сеть без циклов . 2) Пропускная способность дат * однозначна Э) одна начальная вершина в сети

Алгоритм решения Выводимые 1 понятия (Термы) Тело теории 1) Каков максимальный поток в сета?

Рис. 1. Структура аксиоматической теории и соответствие элементов задачи и элементов

аксиоматической теории

Представление постановки задачи в виде аксиоматической теории состоит в следующем: условие задачи, задающее модель предметной области, описывается ядром теории, вопрос задачи - в виде попятия из тела теории, что проиллюстрировано в левой части рис. 1.

В используемом теоретико-множественном языке базовые понятия описываются базисными множествами, отношения - родовыми структурами (декартовые произведения базисных множеств), ограничения - аксиомами, наложенными на родовые структуры, выводимые понятия - термами (множествами, выведешплми из родовых структур и базисных множеств). Глава 2

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

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

Обозначения: 1) В - булеан, множество всех подмножеств данного множества; 2) Рг - операция извлечения большой проекции декартового произведения: если А, В, С - множества, то Рг1(АхВхС)=А, Рг2(АхВхС)=В и т.д.; 3) рг - операция извлечения малой проекции элемента декартового произведения: если к — элемент декартового произведения АхВхС, то prl(k)=a, где asA, pr2(k)=b, где ЬеВ и т.д.; 4) card -операция извлечения мощности множества (количества элементов множества); 5) ЕРг - алгебраическая сумма всех элементов большой проекции (если эти элементы являются действительными числами); 6) debool - операция извлечения элемента множества (только для множеств, состоящих из единственного элемента, применяется для изменения типизации).

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

Таблица 1

Имя Логическое выражение Интерпретация

Ядро теории

Базисные множества

XI множество вершин

N1 множество значений пропускных способностей - натуральные числа и бесконечность

Родовые структуры

D1 еВ(Х1хХ1хШ) направленная сеть - множество троек: начальная вершина дуги, конечная вершина дуги, пропускная способность дуги

D2 еВ(Х 1) множество истоков

D3 еВ(Х 1) множество стоков

Аксиомы

Ах1 card(D2)=l аксиома о существовании единственного истока в сети

Ах2 card(D3)=l аксиома о существовании единственного стока в сети

АхЗ D2nD3=0 аксиома о принадлежности истоков и стоков разным множествам вершин

Ах4 VdeDl (prl(d)#pr2(d)) аксиома об отсутствии петель в сети

Ах5 VEcDl, 3elePrl(E)uPr2(E), 3e2ePrl(Dl\E)u Pr2(Dl\E), HdsDl ((E/0) & (E*D1)) => (((prl(d)=el)&(pr2(d)=e2))v ((prl(d)=e2) & (pr2(d)=el))) аксиома связности сети

Ахб VdleDl, Vd2eDl ((prl(dl)=prl(d2)) & (pr2(dl)=pr2(d2))) => (pr3(dl)= pr3(d2)) аксиома однозначности пропускной способности каждой дуги

Тело теории

Термы

TRI ={ x 6 В (XlxXlxNl) | VkeXl\(D2uD3)) (x={ у 6 XlxXlxNl | VdeDl (prl(d)=prl(y))& (pr2(d)=pr2(y)) & (pr3(d) >pr3(y) >0)}) & (2Pr3{reXlxXlxCl | (rex) & (prl(r)=k)} = ZPr3{reXlxXlxCl | (rex) &(pr2(r)=k)})} все возможные потоки в сети D1 (структура потока соответствует структуре сети, величина потока в дуге не может превышать пропускную способность дуги, сумма потоков, входящих в «промежуточную» вершину сети равна сумме выходящих)

SI = BB (XlxXlxNl) ступень, типизирующая TRI

TR2 ={ x e ß (XlxXlxNl) | BMeTRl, VDeTRl, VGcM, VEcD (Pr 1 (E)=Pr 1 (G)=D2)) & (D2£Prl(D\E)) & (D2£Prl(M\G)) & (!Pr3(G)>EPr3(E)) =>x=M} множество всех максимальных потоков в сети

S2 = BB (XlxXlxNl) ступень, типизирующая TR2

В главе построено 9 аксиоматических теорий для задач из теории потоков и 4 -для задач из теории расписаний. Глава 3

В главе 3 производится построение типологий постановок задач.

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

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

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

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

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

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

Описание задачи в Описание задачи в

отдельной обобщающей

аксиоматической теории аксиоматической теории

Х1 - Вершины __Х1 - Вершины

Х2- Пропускные способности 1 Х2 - Пропускные способности

01 - Множество дуг (сеть) I ) ХЗ-Стоимости

02 - Пропускные способности дуг ' 01 - Множество дуг (сеть)

| | Допустимые значения признака [ Запрещенные значения признака

02 - Пропускные способности дуг

I

03 - Стоимости потоков в дугах

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

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

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

___Таблица 2

№ Наименование признака Более конкретное значение Общее значение

1 Количество истоков в сети единственный исток множество истоков

2 Количество стоков в сети единственный сток множество стоков

3 Наличие внутренних вершин сети отсутствуют присутствуют

№ Наименование признака Более конкретное значение Общее значение

4 Пропускные способности дуг не учитываются (равны бесконечности) равны натуральному числу или бесконечности

5 Пропускные способности вершин не учитываются (равны бесконечности) равны натуральному числу или бесконечности

6 Характер направленности сети направленная ненаправленная

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

8 Стоимости потоков через вершины не учитываются (равны нулю) равны натуральному числу или нулю

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

Здесь рассмотрен пример для задачи о максимальном потоке в сети, сформулированной для разных условий. В данном случае проанализированы были постановки 1, 4, 5 (прецеденты), из которых было получено разнообразие в восьми постановок. Аксиоматическая теория, описывающая условия задачи 1 является наиболее конкретной, а теории, описывающие задачи 6, 7 и 8 - наиболее абстрактными.

Задачу МП в сетях с м * жеством истокф}и/или стс<

-Ш.

-Ш.

_£н1

JЖ.

/ ИСТОК у □Мн-во истоковУ^ П)1 исток ]г ОМн-во истоков [5 01 сток (б 01 СТОК (7 РМн«оСТОКОВ (8 амн-востоков

ч. апсв апсв Уапсв X. апсв .

Задачи о МП в сетях с заданными пропускными способностями вершин (ПСВ)

Рис. 3. Типологии задач о максимальном потоке (МП) в сети и отношения между типами: значения существенных признаков задач приведены в овалах, рамки типа и существенные

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

алгоритм решения.

Точно известны алгоритмы решения каждой из восьми постановок, полученные на основе анализа алгоритмов решения для постановок 1, 4, 5.

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

Допустим известно решение задачи 1, описанной в теории 1 - алгоритм 1.

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

Если задача 2 отличается от задачи 1 отсутствием какого-либо ограничения (снята одна или более аксиом), то теория 2 является более общей, чем теория 2 (см. рис.4а). В общем случае алгоритм 1 не применим для задачи 2. Тут возможно два пути: разработка индивидуального алгоритма либо поиск отображения условия задачи 2 в условия задачи 1 с целью решения алгоритмом 1. Такое отображение есть сведение одной задачи к другой (например, задача 5 на рис. 2 сводится к задаче 1 дополнительным построением: вершины с пропускной способностью заменяются на дуги с такой же пропускной способностью).

F(T2)=T1

F - функция сведения Теории 2 к Теории 1 4а) 46)

Рис.4. Назначение сведения: сведение производит взаимнооднозначное отображение модели

из одной теории в другую

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

Это проиллюстрировано рис. 3. Fc.l - функция отображения задач с множеством истоков и стоков к задаче с одним истоком и стоком, Fc»2 - функция обратного отображения. Функция Fc,3 снимает ограничение в виде пропускных способностей вершин сети, а функция Fe,4 производит обратное отображение.

Таким образом, для условия задачи можно записать:

Fei (Усл4)= Усль

где Услд и УсЛ[ - условия задач 4 и 1 соответственно.

Если Рдл,. - функция решения задачи при условии Усл^ то ответом на вопрос задачи при условии Уел] является

0ТВ!= Ралг(УСЛ)).

Соответственно, ответом на вопрос при условии Уац является

ОтВ4=РС,2(Ра.Лг(РС»1(УСЛ4))).

Ответом на вопрос при условии Услаявляется

0ТВ8=РСВ4(|-СВ2(Р^Г(РС61(РСВЗ(УСЛ8))))).

И так далее.

На рис. 5 отображен процесс решения задачи 8. Задача 8 описывается наиболее общей теорией. В процессе решения условия задачи 8 отображаются в условия задачи 4, а затем - в условия задачи 1. При этом происходит постепенная переформулировка условия задачи во все более конкретных теориях. В наиболее конкретной теории 1 находится ответ на вопрос задачи при помощи известного алгоритма. Затем найденный ответ переформулируется сначала в условии задачи 4, а затем - в условии задачи 8.

Задача 8

Рис.5. Отображение условия задачи из теории в теорию в процессе решения.

Глава 4

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

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

Общая аксиоматическая теория (ОАТ) состоит из тех же ключевых элементов, что и обычная теория. Однако для ОАТ определен принцип ее формирования из частных теорий:

1) Набор базисных множеств ОАТ является объединением всех базисных множеств общих теорий.

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

Пример. Поскольку в общей теории описываются не одна, а несколько сетей, то вводится соответствующая родовая структура: D1 еВД(Х1хХ1) - множество сетей: множество множеств пар вершин. Родовые структуры D2e£(Xl) и D3efi(Xl), описывающие множество истоков и множество стоков соответственно, сохраняются в общей теории такими же, как в задаче 1.

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

4) Термы делятся на несколько классов: родовые, аксиоматические и термальные.

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

Пример. В задаче 1 имеются аксиомы Ах1 и Ах2 (см. табл. 1), определяющие наличие единственного истока и единственного стока в сети. В общей теории такие сети опишутся термами 1 и 3 соответственно:

TR1={ х е В (XlxXl) | BxeDl (card(D2nPrl(x))=l) }

TR3={ x e В (XlxXl) | BxsDl (card(D3nPr2(x))=l)}

При этом в общей теории выразимы сети с множество истоков и

множеством стоков - термы 2 и 4 соответственно:

TR2={ хеВ (XlxXl) | 3xeDl (card(D2nPrl(x))*0) }

TR4={ хеВ (XlxXl) 13xeDl (card(D3nPr2(x))*0) }

В общей теории также выразимы и сети без истоков и стоков.

b. Каждый родовой терм являются результатом пересечения некоего набора аксиоматических термов, в результате чего формируется терм, удовлетворяющий как логическим условиям аксиом ОАТ, так и логическим условиям аксиоматических термов. Т.е. получаемый терм является полным аналогом родовой структуры из частной теории (удовлетворяет тем же логическим условиям и содержит тот же набор элементов).

Пример. Для описания условий задач 1-4 сформируем следующие термы: TR101=TRlnTR3 - множество сетей с единственным истоком и единственным стоком;

TR102=TR2nTR3 - множество сетей с множеством истоков и единственным стоком;

TR103=TRlnTR4 - множество сетей с единственным истоком и множеством стоков;

TR104=TR2nTR4 - множество сетей с множеством истоков и множеством стоков.

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

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

Для того чтобы одну и ту же форму логического условия можно было использовать несколько раз, используется терм-функция. Для формирования терм-функции из логического условия терма выделяются множества, которые не являются переменными в логическом условии. Выделенные множества заменяются внешними (для логического условия) переменными, обозначенными следующим образом: Varl, Var2, Var3,... Область значений внешних переменных типа Var задается при объявлении терм-функции:

либо поименным перечислением множеств

TRF21(Varl е {D1,TR1,TR2,TR3,TR4}, Var2e {TR5,TR6,TR7})={. ..}, либо определением ступени, которой должно принадлежать множество: TRF28(Varle£ß (XlxXl), Var2eÄB (XlxNl)) ={...|...}.

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

Терм-функции используются для формирования описания комплексных алгоритмов, составленных из нескольких элементов. Пример такого описания: TRF28(TRF30(TRF38(TRF29(TRF27(TR18))))),

где TRI 8 - некий родовой терм, TRf27 и TRF29 терм-функции, описывающие сведения от общих постановок к более конкретным, TRF38 - терм-функция, описывающая алгоритм решения, TRF28 и TRF30 терм-функции, описывающие обратные сведения к общим постановкам. Глава 5

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

В случае, если несколько отображений производятся по независимым признакам (например, наличие петель в сети является частным случаем наличия циклов, и признаки наличия петель и наличия циклов являются зависимыми) с двумя возможными значениями, то разнообразие различных постановок, к которым можно подобрать решения, равно 2°, где пе{1,2,3...} - количество признаков. Так, анализ пяти постановок задач о максимальном потоке в сети выявил 6 существенных независимых признаков и позволил сформулировать разнообразие, состоящее из 64 постановки и 64 алгоритма.

К условиям задач можно задать другие вопросы, т.е. сформулировать новые постановки задач. Если известны частные случаи решения задач с новыми вопросами, то общее разнообразие алгоритмов становится равным к*2", где ке{1,2,3...} -количество вопросов задач. Так, анализ еще двух задач с вопросами о потоке минимальной стоимости и о кратчайшей цепи позволил сформулировать общее разнообразие в 192 постановки и 192 алгоритма их решения.

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

ЫосДЬге йпИтуэ

Существенные признаки заДач из теории пртрков

г Д» Кояи^еотЬ истоков ■всстйг Ц'"'

; . О ! ИСТОК

; 0Множество истоков •

;• 5. Прапускныз спс^бнсти дуг:..........:

:.: О Бесконечные

Г 0 Положительные целочисленные

.6. Пропускльй сгюсо6нстикй|хииЬ ■ | О Бесконечные ' [: • Щ Положительные целочисленные

7-, Стодаость единицы потока в дуге-

: 6. Стоимость единицы потока в вершине

.2..Количество стоко» в сети • .....

: 01 СТОК ...

5 ©Множество стоков

:<-.3*: Нзпрзвленмость сети .......«гг-*............

.•3 Направленная сеть '•■ О Ненаправленная сеть

4. Наличие промехуточньк ьераян • :: О Двусторонняя сеть .

. , . - , „ . „ , .

...Вопросмдзчй -• : ......;; "..' •-•■•• ■■• ■•- - - • ■ '■>) " -

: 0 Какое максимальный поток в сети? . ОКаковпотокминималы+л* стоимости в сети? - О Каково макс«««>ное независимое множество допустимых клеток? •

Родовой терм !ТЯ134 Базовый алгоритм ;ТЯ301

Алгоритм ; ,; Т!^02<Т^2р4(ТР1212СТЯ^111СТО203СТЛ2 Ь

Базисные понятия: •• 1. Множество вершин ; I 2',-Пропускные'способности . .[ 3. Стоимости ;. ; 4. Эффективности ; 5. Метки

■ Отношения : 1. Множество сетей >; 2. Множество истоков Т 3. Множество стоков 1 4. Пропускные способности дуг Г .:. 5. Г^юпускные способности вершин ; 6. Стоимость вд-цы;потока вдуге 1 7. Стоимость ед-цы потока в вершине \ 1 8. Эффективности дуг

; Ограничения '.

; 1. Отсутствие петель в любой сети

:!,С^теза^оритма:

Рис.6. Интерфейс программы, автоматизирующей процедуру синтеза алгоритмов.

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

В Заключении кратко сформулированы основные результаты работы:

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

2) Проведен теоретико-множественный анализ и построены аксиоматические теории для прецедентов решений задач из теории потоков и теории расписаний. Построены две типологии постановок задач, синтезированы алгоритмы для постановок из типологий. Дана количественная оценка многообразию алгоритмов.

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

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

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Гуторов Д.А. Автоматический синтез структуры перенастраиваемого программного комплекса на основе специальной типологии задач// Системы управления и информационные технологии, 2009, 2.1(36). - С.119-122

2. Гуторов Д.А. Один подход к формированию структуры информационных систем: на основе специальной типологии задач. //Десятая Всероссийская научно-техническая конференция. Теоретические и прикладные вопросы современных информационных технологий. Материалы конференции, 2009. Часть I. С.121-124.

3. Гуторов ДА. Построение типологий задач и алгоритмов и использование их для оптимизации процесса проектирования информационных систем. //Международный симпозиум «Надежность и качество». Материалы симпозиума, 2009. Том I. С.200-202.

4. Гуторов Д.А. Автоматический синтез структуры перенастраиваемого программного комплекса на основе специальной типологии задач// Информационные технологии моделирования и управления, 2009, 3(55). -С.410-416

5. Гуторов Д.А. Метод подбора алгоритмов решения задач. Труды 51-й научной конференции МФТИ, 2009. Часть IX. Инновации и высокие технологии. С.48-51.

6. Гуторов Д.А. Представление текста концептуальных схем на языке ХМЬ как этап их операционализации. //Труды 51-й научной конференции МФТИ, 2009. Часть IX. Инновации и высокие технологии. С.51-54.

7. Гуторов Д.А., Гараева Ю.Р. Концептуальная квалификация потоковых сетевых задач выбранного класса. //Процессы и методы обработки задач. М.-2006. С.30-37.

8. Гуторов ДА. Проблема трудоемкости создания новых программных продуктов, использующих в своей основе потоковые сетевые модели. //Труды 48-й научной конференции МФТИ, 2005. С.207-210.

9. Гуторов Д.А., Гараева Ю.Р. Модель абстрактных обменных отношений. //Труды 47-й научной конференции МФТИ, 2004. С.115 .

Подписано в печать: 12.11.2009

Заказ № 3027 Тираж - 100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru