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

На правах рукописи

Иванова Галина Сергеевна

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

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертации на соискание ученой степени доктора технических наук

ООЗОВ584Б

Москва - 2007

003065846

Работа выполнена в Московском государственном техническом университете им Н Э Баумана

Официальные оппоненты

Ведущая организация

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

Жданов Владимир Сергеевич

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

Юркевич Евгений Владимирович

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

Солодовников Игорь Владимирович

Открытое акционерное общество «Научно-исследовательский центр электронной вычислительной техники» (ОАО «НИЦЭВТ»)

Защита диссертации состоится « 1 » ноября 2007 г. в 1430 часов на заседании диссертационного совета Д212141.10в Московском государственном техническом университете им Н.Э Баумана по адресу.

107005,2-я Бауманская ул,д 5

Ваши отзывы в двух экземплярах, заверенные печатью, просьба высылать по указанному адресу

С диссертацией можно ознакомиться в библиотеке Московского государственного технического университета им Н Э Баумана

Автореферат разослан «/fe?» Ce¿-?V~J? 2007 г

Ученый секретарь диссертационного совета, к т н, доцент

Иванов CP

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

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

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

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

• высокую временную сложность - точные алгоритмы решения многих задач данного класса являются М'-сложными, что и при сравнительно небольшой размерности входа (порядка 10г) приводит к недопустимо большому времени выполнения соответствующих программ даже на современных ЭВМ,

• высокую емкостную сложность, как правило, полиномиально зависящую от размерности задачи

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

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

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

Исследованиями в области решения задач структурного анализа и синтеза занимались Р П Базилевич, А М Бершадский, А Н Мелихов, К К Морозов, М И Нечепуренко, Ф А Новиков, В А Овчинников, А И Петренко, А Ахо, Т Кормен, Ч Лейзерсон, Р Риверст, Р Седжвик, С Хидитниеми, Д Хопкрофт и многие другие

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

К средствам автоматизации процесса разработки программ решения задач указанного класса можно отнести ограниченно-применимые язык обработки множеств БЕТЬ и систему «Lambda-Upsllon-Omega», в которой предпринята попытка автоматизации оценки вычислительной сложности, а также некоторые не универсальные библиотеки подпрограмм выполнения часто встречающихся операций над графами, предлагаемые рядом авторов А Ахо, Н Виртом, Р Седжвиком, коллективом под руководством М И Нечепуренко и др

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

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

Задачи исследований. Для достижения указанной цели потребовалось

1 На основе анализа объектов задач структурного анализа и синтеза, их свойств и характеристик определить совокупность математических абстракций, необходимых для представления указанных объектов

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

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

4 Разработать синтаксис и семантику языков описания алгоритмов в операциях над множествами и в операциях над графами, а также трансляторы с них

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

6 Получить совокупность оптимизирующих преобразований алгоритмов на графах и сформулировать соответствующие синтаксические правила

7 Создать методику и средства оценки и снижения вычислительной и емкостной сложности алгоритмов

8 Создать методику и программную систему разработки и анализа эффективности алгоритмов решения задач структурного анализа и синтеза

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

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

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

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

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

4 Определены полные наборы инвариантов моделей структурных конструкций, сформулированы аксиоматика операции свертки уграфов структурных конструкций и теорема о необходимом и достаточном условии структурности алгоритма

5 Формально поставлена задача приведения алгоритмов к структурному виду, разработан и реализован метод ее решения

6 Обоснован синтаксис и определена семантика двух специализированных языков описания алгоритмов решения задач структурного анализа и

синтеза на уровне операций над графовыми моделями и операций над множествами

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

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

Апробация работы. Основные положения работы обсуждались на научно-технической конференции, посвященной 170 лет МГТУ им НЭ Баумана (Москва, 2000), на межвузовской научно-технической конференции МГТУ им НЭ Баумана (Москва, 2003), на Международной научно-технической конференции «Гражданская авиация на современном этапе развития науки, техники и общества» (Москва, 2003), на первой Международной научно-технической конференции, посвященной 90-летию со дня рождения академика В Н Челомея (Москва-Реутов, 2004)

Реализация и внедрения. Все основные теоретические и практические результаты работы в виде методик и программных средств внедрены в промышленность Они использованы при выполнении опытно-конструкторских работ по темам И070406 и И070507 («Метеор-ЗМ-ИКФС-2-МЭ») в НИИ ИСУ МГТУ им Н Э Баумана, работ по договорам № 275/2004 («Разработка Информационной управляющей системы»), № 177/2006 («Разработка информационно-аналитической системы оценки технического состояния, эффективности защиты магистрального газопровода и прогнозирования коррозионного состояния») в ЗАО «РТСофт» и при создании системы управления контентом адаптивных сайтов RBC Contents 5 01 в РБК Софт (РосБизнесКонсалтинг)

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

программирование», «Системное программное обеспечение» и «Автоматизация конструкторского проектирования ЭВМ», а также выполнении курсовых и дипломных проектов

Публикации. По результатам выполненных исследований опубликованы 15 статей, 3 учебника и 1 учебное пособие

Объем и структура диссертации. Диссертационная работа включает введение, пять глав, заключение и список литературы, занимающих 411 страниц текста, в том числе 85 рисунков и 65 таблиц на 119 страницах, список использованной литературы из 115 наименований на 10 страницах

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

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

В первой главе «Определение предметной области и постановка задачи» выполнен анализ известных комбинаторных задач структурного анализа и синтеза, решаемых при проектировании технических и программных средств вычислительной техники

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

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

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

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

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

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

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

Уровень 1

Уровень 2

Уровень 3

Уровень 4

Алгоритм, описанный на уровне графов

Существующие уровни

Алгоритм, описанный на машинном языке

Графы

Трансляция 1

Алгоритм, описанный на уровне множеств Множества

п

Трансляция 2

Алгоритм,

описанный на Структуры

универсальном данных

языке

Компиляция >

Коды данных

Рис. 1. Четырехуровневая схема формального описания алгоритмов и соответствующие представления данных

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

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

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

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

Во второй главе «Анализ алгоритмов и данных и построение их моделей» выполнен анализ характеристик объектов, которые используются при решении задач структурного анализа и синтеза Определено, что структура, на которой можно решать задачи перечисленных типов, полностью характеризуется следующими параметрами

• функциональные свойства компонентов,

• связность компонентов с учетом направления связи и фактора неизвестности или известности порядка их соединения в пределах одной связи,

• топологические свойства компонентов, обуславливающие ограничения на построение соединений,

• метрические параметры компонентов и связей

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

Определен набор и выполнен анализ моделей, используемых для представления объектов, процесса решения и результатов задач структурного анализа и синтеза Установлено соответствие между компонентами объекта и элементами модели при представлении этих моделей с одним и двумя универсумами, связи компонентов объекта сопоставлены отношениям элементов моделей В табл 1 показаны результаты такого сопоставления для связей п элементов с учетом и без учета направления сигналов и с учетом и без учета порядка подключения элементов

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

Таблица 1

Представление связей п компонентов объекта в структурных моделях

Связь Представление в модели с одним универсумом Представление в модели с двумя универсумами

Связь п элементов без учета направления сигналов и порядка подключения (гиперребро) Элемент и-арного симметричного отношения смежности ^ с X" -Х]={х„хк, хг}еЕ, \Х:\=п Множество или мультимножество* из п элементов симметричного бинарного отношения инцидентности ГсХх и = 11хХ-{{хк, ц} е Г}, хк е Хр \ Х} | = и, где Х} - множество вершин, соединенных ребром и,

Связь п элементов, учитывающая порядок их подключения (гипердуга) Элемент я-арного отношения смежности Х/=(.Х„Хк, \Х)\ = п Кортеж из п элементов симметричного бинарного отношения инциденгаосга Г с!хи=ихХ-({хк, и,} е Г), хк е Хр \ Х31 = п, где Х] - множество вершин, соединенных ребром и,

Связь п элементов без учета порядка подключения, но с учетом направления сигналов (ультрадуга) Элемент бинарного отношения смежности на множестве подмножеств х,7хк,т е (Х„Хк) е 1, \х,\+\хк\ =и, х^х,.хь где X, , Хк — множества вершин источников/приемников ребра и. Множество или мультимножество* из п элементов бинарных отношений инцидентности Г, с Хх и, Г2с \JxX-{(х„ щ) е } . {{ир хк) е Г^ }, х, € Х„ хк е Хк, \х,\+\хк\ =п,х]=х,.хк, гдеХ,,Хк-то же, что и слева

Связь и элементов с учетом порядка подключения и направления сигналов (ориентированная ультрадуга) Элемент и-арного отношения смежности с: А!" и элемент бинарного отношения смежности на множестве подмножеств + $ = Й -Х/=(х„ хк, хг) е ^ п, иХ, Ц Хк,т е (Х„Хк)еР2, \Х,\+\Хк\ =п,Х}=Х,.Хк, где Х„ Хк - то же, что и выше Кортеж из п элементов бинарных отношений инцидентности ЦсХх V, Г2с ихХ-({(х„щ) е Г^} . {(ирхк)<= г;», х, £ Х„ хк е Хк, \Х,\+\Хк\ =и, X/ = х,. хк, где Х,,Хк- то же, что и выше

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

G(X, XFX, XRX) или G(X, U, XTU, UTX, XRX), где R = {R4 г = 1,и} — множество отношений между элементами соседних уровней

{{х';1 ,х\)! x'J1 е X1-1} с К с Х'~1хХ', х'к, х''1-вершины г-го и г-1-го уровня соответственно, Х'к~1- подмножество вершин г-1-го уровня, соответствующее х'к, X', Х'~1 - множества вершин г-го и г- 1-го уровня соответственно, R' - отношение вхождения между вершинами г-1-го и /-го уровней Получены формальные правила, определяющие отображение отношений вершин одного уровня в отношения вершин другого уровня

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

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

А(0,С) = фОВ), где О и С - множества операторов и связей между ними, B={DB, Fq, РВ,Ц- базис алгоритма,

Dfj, Fg, Р[> - символы переменных, функций и предикатов условий, Т— символы типов операторов - операторный базис алгоритма Предложена информационно-логическая модель алгоритма, позволяющая отобразить его компоненты, их отношения и свойства, которые должны быть учтены при решении задач структуризации и автоматического анализа вычислительной сложности разрабатываемых алгоритмов

Модель, состоит из двух частей управляющего графа алгоритма и двудольного графа «оператор-данные»

Так управляющим графом алгоритма (см рис 2, а) является взвешенный граф (см рис 2, б) вида

Оу(<Х, Т, (FB, Рв)>, {<U', L, Е>, U^ }), где X, U - множества вершин и ребер графа,

U', U2 — множества дуг условных и безусловных передач управления, L = {true, false},

Е - множество вероятностей переходов

Начало ^

^ Конец ^

Условные обозначения 0 - терминальный блок, @ - объединенный блок вычисления

@ - обработка данных, условия и ветвления,

@ - слияние потоков управления, О вершина данных Рис. 2. Алгоритм (а), уграф (б) и двудольный граф «оператор-данные» (в)

Сформулированы правила перехода от объекта к модели

1) 0<г>Х,

2) ХК{Т, Х'Я'^в, Х"К'\Рв, Х'иХ"=Х,

3)

4) ТР&и ТГ2 д2Е,

где /?'] , Я" 1, <2\, С>2 ~ однозначные, возможно взаимнооднозначные отображения

Двудольный граф «оператор-данные» (рис 2, в)

00Л(г,У) = С0а({Х,Г},{<^,В>, V2 }),

где X, У и V - подмножества вершин и множество ребер двудольного графа, Vх ,¥2 - подмножества отношений данное-оператор и оператор-данное, В = {Ь\, ¿2}> Ь\ - признак того, что входное данное - аргумент, ¿2 ^ признак того, что входное данное аргументом не является Сформулированы правила перехода от объекта к модели 1) 0<^Х, Б <-» У, причемX п У = 0,1иГ= 2,

\уЛу,>хЛ если У] - входное данное о, <-» х„

2) ук=<

ГУ/с(х,>У])' еслиУ] - выходное данное о, <н> х1

3) У'^В,

где О - множество символов переменных базиса Ив, Дг — однозначное отображение Интегральная модель алгоритма определена как

02, и, У) = Оу и0од Выполненное формальное описание правил перехода от алгоритма к его модели позволяет осуществлять эту операцию автоматически

Построены модели базовых структурных конструкций, определены их свойства и инварианты

1 Модель оператора обработки данных представляет собой одновершинный кусок О0{Х0,и°), такой что

Х°= {хк}, 1(хк) = «обработка данных»,

={й(0,хД й(хк,0)} Формальные признаки данной конструкции \Х°\=1,\и°\ = 2, Р(Х°)=8(Х°)= 1, где ¡{хк) - тип ¿-ой вершины, С,0 - подмножество внешних ребер куска, Р(Х°), 5(Х °) — полустепени исхода и захода куска

2 Модель конструкции следования (см рис 3, а) - простая цепь

Х\иг), такая, что

С\х\и1) -и]3={ й (0, хк\ й ( х*+п, 0)}

Формальные признаки данной конструкции Р(Х') = 5(Х1)=1,

(УXI е X1) (р(х/) = =1 & 1{х/) = «обработка данных»), где Р(Х]), Я(Х1) - полустепени исхода и захода куска О^х'^и'), р(х[), в(XI) - полустепени исхода и захода вершины х/, 1(хк) - тип к- ой вершины

3 Моделью конструкции ветвления (см рис 3, б) является кусок у графа <3 2{Х2,и2), такой что ^={и(0л),а(д;м,0)},

где Хк — вершина начала конструкции ветвления,

Хк+4- вершина конца тела цикла конструкции ветвления

хк+2

хк+3

Хк+2

Хк+3

а б в г

Рис. 3. Модели структурных конструкций а - следование, б - ветвление, в - цикл-пока

Формальные признаки данной конструкции Р(Х2) = Б{Х2) = 1,1(хк) = «вычисление условия», = «слияние», (Г*\хк) = хк+{) & (Кхк+[) ~ «разветвление»), (^(Хк-п) = {хк+2, Хк+з}) & ((Хк+2 =Х/& Хк+3 = ХИ)\/

V (хк+2 = Хк+4 & Хк+3 = X/,) ч(Хк+ 2 =Х/& Хк+3 = Хк+4)) & & {¡(хи) = фсу) = «обработка данных»), где Р(Х2), 5'(Х2) - полу степени исхода и захода куска С2(Х 2, V2), /(хк) - тип к-ой вершины

4 Моделью конструкции цикла (см рис 3, в) является кусок управляющего графа С3(Х3,[/), такой что и]] = {й(0, хк), й (хк,2, 0)},

где хк - вершина начала цикла, Хк+2- вершина конца цикла Формальные признаки данной конструкции

Р{Хг) = 5(х3) = 1, (фсд) = «слияние»), (1(хк+2) = «разветвление»),

(Г*\хк+2) п К1(хк) = хк,з) & (Кхк+ з) = «обработка данных»), (Р*\хк) = хк+\) & (Кхш)= «вычисление условия»),

где Р(Х3), 5(Х3) - полустепени исхода и захода куска С3(Х'\и 3), /(хк) - тип к-ой вершины

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

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

если |Х;|=1,

/ааогЩХ},и,)) = • С;«х„},{"(0,х„), и(х„, 0)}),

1(хп) = «Изменение данных», если | Х} |> 1

Определена аксиоматика этой операции - правила свертки структурных конструкций

/ас1ог{С0) = О№ = в°,

/ас1ог{в, е {в\01е,02,0г",03,в№}) = в0",

/ас(ог({С1:} с С'с &Ск<= {С1Р,СЪ! }) = С'"7,

/ааог(Ст,О02 сСж в{С\01р,С2,вг",0\С31'}) = 011',

/ааог(О0 сС!С &С0 е{01,0"\02,С2/\0\0:"7) = 03'7, Сформулирована и доказана теорема о необходимых и достаточных условиях структурности алгоритма

Теорема 1. Алгоритм является структурным тогда и только тогда, когда в результате последовательной факторизации кусков его уграфа, последний можно свести к уграфу

0({хн, хР, хк}, {и(хн, хр), и(хР, хк)}), причем /(.%), д'а-к)= «®» - вершины начала и завершения алгоритма Получена модель структурного алгоритма (?ус(х,£/) = вк € {о1с,с72с,озс,е0},

где С1- =< ,

К

зс = {,сС4с) = С^

_ /--тЗС /~т0^

/

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

Обобщенная модель векторной структуры (см рис 4) - смешанный граф вида

0у{{2АВ,<гАЕ,Г,до >,2У ,2аг},{ЕАВ X ,<ЕЛУ ,1а >,£",£"}),

где \1АВ | = 1,

лу — АУ

для вектора несортированных данных -X = 0, Е = 0, Е =0, причем для характеристического вектора - У = 1/8 (байта),

для вектора сортированных данных -2ЛУ = 0, Е =0,

для вектора адресов —Ху = 0, Еу = 0, еГ= 0, /'' = О, Q0= 0,

для вектора адресов прямого доступа - Ху = 0, Еу= 0,11' = 0, Qo= 0

а б в

Условные обозначения

@ - вершина -»• - дуга, связывающая адреса,

начального адреса, -»- - дуга, связывающая данные,

О - вершина адреса --ребро, связывающее адрес со

элемента, значением элемента

® - вершина данных,

Рис. 4. Модели вектора а- с несортированными элементами, б— с сортированными элементами, в - содержащего адреса

Обобщенная модель списковой структуры (см рис 5)

05({2Ш ,<2АЕ ,Г >,2\2ау},{<ЕА\1а >,<ЕАЕГ >,<Е\\а >, ЕГ.ЕГ})

а б

Рис. 5. Модели списковых структур данных а - линейный односвязный список, б - линейный двусвязный список, в — древовидный список

0¥{{2А\<2А\Г&>Х,2АУ},{Е ,Е ,<Е ,1А >Х,Е }),

_АВ ^Е Л гЖ

где 2 ,2 , 2 , 2 — подмножества начальных вершин, вершин адресов элементов, элементов данных и адресов данных,

—АВ —АЕ —АУ у —У¥

Е ,Е ,Е ,Е ,Е - подмножества ребер (дуг), связывающих вершины указанных выше подмножеств,

<2о - вычислительные сложности выполнения основных операций,

IVМ — объем памяти, необходимый для хранения данных и адреса

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

Модели иерархических и комбинированных структур данных предложено получать как объединение моделей базовых структур, использованных при построении сложной структуры Получены правила перехода от объекта к модели для таких структур данных

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

В третьей главе «Исследование свойств алгоритмов и разработка метода их приведения к структурному виду» получена формальная постановка задачи структуризации, основанная на моделях структурных и неструктурных алгоритмов, что создает предпосылки для ее корректного решения выполнить преобразование

0ун(<Х1,Т>,<и1,Р>)—Ь-*0УС(<Х2,Т>,<и2,Р>)и

сда({<х1,г>,<}^,<г1,с1 »Мег!,?;1 >,<?\,<т?,1%»})—^ —^вдс({<Х2,Г>,<Г2,<^^2,С2 >>},{<у\,Т1 >,<г1,<т2\о32 »})

такое что (Уге/) Ан (Я,) = Ас (8,),

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

5 = {5,/ге/}- множество всех допустимых наборов входных данных задачи, для решения которых предназначен данный алгоритм,

Ан - неструктурная программа, управляющим графом которой является граф в™,

Ас- структурная программа, соответствующая преобразованным графам Сус и Сж:,

при выполнении следующих условий, вытекающих из свойств алгоритмов

[О^ил, и1п\О1^0,

и существует разрезание В куска графа Оус на совокупность кусков В( Сус), удовлетворяющих условиям

(УС,ус е В(вус)) вус Ф 0, (е /,

(VGyc 6 B(Gyc)) (G,yc e GB v G,yc e GBF), UG,yc=Gyc,

(VGyc,Gy^ e B(GVC))(ХГ n= 0 & t/,yC n£/£ = Ц ,+1 &| |= 1), /,i + le/,

(VGyc,G;c eB(Gyc))(X*c nXf = 0 & C/,yc n=0), hj el, j*i±\, или другими словами

factor" (Gyc) = G0F

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

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

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

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

Правило 1. Вершины, кроме вершин слияния и вершин, следующих за вершиной ветвления, нумеруются последовательно

S(xj) = S(x,) +1 Xj е Р*\х,) & tx, e {'начало', 'изменение данных', 'слияние'} & & tXJ е {'изменение данных', 'ветвление', 'конец'},

где Г<'^(х,) - множество вершин, в которые заходят дуги из х,

Следствие. Любой линейный участок простого пути (луч) уграфа -СНщхг, нумерованный по правилу 1, будет S-лучом

Ух„ Xj е СкщХГ & Xj Фхд & х, фхг Xj = ^Чх,) => S(xj) = Six,) + 1

Правило 2. Вершина слияния нумеруется последовательно, если она является первой вершиной цикла или завершает ветвление, обе ветви которого пронумерованы

S(x}) = Six,) +1 X, е F*Xx,) & tx, = 'слияние' &

& [ВCycle{Xj) (х, е Cycle(xj)) v (V xkz Fl(xj))(3

где Cycle(xj) - цикл, проходящий через вершину х,

Следствие 1. Для аранжируемых уграфов все простые пути от начальной вершины Xo - Ch(x0, хк) будут ¿'-путями

V Xj, х, е Ch(xо, Хк) &xj*x,&x,*xk Xj е F*'{x!) => S(Xj) > S(x,)

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

Xj е F"(x,) & х, * х0 & х, * Xj & \/Ch(x0, Xj) е СН(х0, х}) (х, е Ch(x0, х,)) =>

=> S(xj)>S(x,),

где СН(хо, Xj) - множество всех простых путей из начальной вершины в вершину Xj,

Е*'(х,) — <-е прямое отображение вершины х, во множество вершин уграфа

Следствие 3. Все дуги, замыкающие цикл, будут ^-обратными

X[ е F*\Xj) & 3 Ch (xj, х,) (хк е Cycle(xj)& S(xk) = 0) => S(x,) < S(x,)

Правило 3. Последовательно с вершиной ветвления х, нумеруется одна из вершин хрхк& F"(x,), если она принадлежит подмножеству простых циклов, включающих вершины х„ х, и начинающихся в вершине х,., имеющей максимальный номер по сравнению с другими вершинами - входами циклов, а вторая вершина этому подмножеству не принадлежит, или, если такого подмножества не существует и обе вершины - потомки х, еще не нумерованы

S(Xj) = S(x,) +1 F> ](x1) = {xj, xk} & txl = {'ветвление'} & & [(3 {CircleX,{xt)} с {Circle(x,)}) (xrjj e {Circle„} ,xki{ Circle xr\) v v( 3 { CircleX,{x,)} с { Circle(x,) }) {xrrxj e { Circlexr},

xk£ {Circled) & 3(S(Xj),S(Xk))], где {Circle(x,)} — множество простых циклов, включающих вершину х„

{Circlexr(x,)}, {CircleXq(x,)} — множества простых циклов, включающих вершину х, и вершины х,- или xq соответственно,

xr е Xq & S(xr) = max {S(xq)} — входная вершина внутреннего цикла,

xteXt

Хд = \хч еХ & 1(хч) = 'слияние' & = 5,(лт)+1 &хт <£{ С1гс1ехг} } - множество входных вершин циклов

Разработан алгоритм нумерации и определена его вычислительная сложность

Определены синтаксис и семантика языка, который позволяет описывать как структурные, так и неструктурные конструкции в виде последовательности взвешенных терминальных символов (см табл 2)

Таблица 2

Терминальные символы языка описания конструкций алгоритма

№ Название символа Символ Семантика символа Вес символа

1 Изменение данных Последовательность вершин - операторов обработки данных

2 Начало ветвления л Вершины ветвления, если при этом не фиксируется выход из цикла Номер вершины - начала второй ветви

3 Конец ветвления V Вершина слияния прямых потоков —

4 Начало прямой дуги о Разрыв нумерации при завершении первой ветви ветвления Номер вершины слияния, завершающей ветвление

5 Начало цикла .V Вершина слияния прямого и обратного потоков —

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

7 Конец цикла • Разрыв нумерации между последней вершиной цикла и вершиной, следующей за циклом Номер вершины слияния, начинающей цикл

Предложения языка имеют формат

57/' = <Д ]¥, 5> = (<4\, м^, >, <йъ я<12 > <<4/, угш, хм >), где а!{ еЕ = {►, =, л, V, .V, .л, - терминальные символы, в множество которых добавлены символы начала и завершения алгоритма, е 1,| X |— их веса,

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

Сформулированы синтаксические правила языка описания структурных алгоритмов

<Структурный алгоритм> = ► <Следование> Ч <Следование> = <Следование> <Конструкция>|<Конструкция> <Конструкция> = =|

л<Следование> ° <Следование> V | л<Следование>*/| .V .л <Следование> • | .V <Следование> .л • Определено, что грамматика языка описания структурных конструкций относится к классу контекстно-свободных (подклассу грамматик предшествования) Для этого языка построен распознающий автомат с магазинной памятью (см табл 3) и разработан алгоритм программы анализа, что позволило выявлять нарушения структурности алгоритма

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

Таблица 3

Переходы автомата, распознающего структурные алгоритмы _1 Основной распознаватель_

Состоя ние Входные символы

А А V V о • <

0 4-7=1 4- 7=1 Ех Ег 4-7=1 Еъ Е4 Е0

1 4,7=1 4- 7=1 Ех Ег 4-7=1 Еъ Е4 К

2 Рекурсивный распознаватель «Конструкция»

Состоя ние Входные символы

= А ■А V V О • <

0 4-7=1 4-7=1 Е\ Еа 4-7=1 Еъ Е,» Е0

1 4-7=1 4-7=1 Е\ Ег 4-7=1 Ез еа К

X 1Ыисе2 2, Мст Ег 6, Моге Ег Е, Ещ

2 4-7=3 4-7=3 Еъ Ев 4- 7=3 Еп Еъ е9

3 4-7=3 4-7=3 Е\о Ь\Ке(1исе 4- 7=3 4, Мст Ей Е\2

4 4-7=5 4-7=5 Е\ з Е\\ 4- 7=5 Ей Е\в Ец

5 4-7=5 4-7=5 Ещ \yReduce 1^47 4-7=5 Е\9 Ею Егх

Таблица 3 (окончание)

Состоя ние Входные символы

= А •Л V V о # <

6 47=9 4 7=9 7, Move Е22 4 7=9 Е23 Е24 E25

7 4-7=8 4 7=8 Е26 Е21 4 7=8 £28 Е29 Езо

8 47=8 4 7=8 £31 £32 4 7=8 £33 1Y,Reduce \Ещ Е34

9 47=9 4 7=9 10, Move £35 4 7=9 £зб £37 Езг

10 Ез9 Ею Е41 Е42 £43 Е44 t Y,Re- Е45

В таблице использованы следующие условные обозначения

К- конец разбора, Е - состояние ошибки,

47 = <состояние> — рекурсивный вызов распознавателя, справа указан номер состояния после возврата из данного вызова,

Т 7- завершение рекурсивного вызова, следующее состояние определяется значением Y,

Reduce2 — двукратная свертка в нетерминал «Следование»,

Move - операция переноса

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

• условие выхода из цикла в одной из ветвей ветвления, непосредственно следующее за началом ветвления,

• условие выхода из цикла в одной из ветвей ветвления, отделенное от начала ветвления вершиной изменения данных,

• пересечение ветвлений вершина слияния непосредственно следует за вершиной ветвления,

• пересечение ветвлений вершина ветвления отделена от вершины слияния,

• пересечение ветвления и цикла, являющееся следствием неверной последовательности вершин слияния,

• пересечение ветвления и цикла наличие дополнительных входов в цикл,

• дополнительные выходы из цикла два выхода из цикла подряд,

• дополнительные выходы из цикла два выхода из цикла не подряд,

• условие выхода из цикла в середине тела цикла

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

Так для преобразования «Вынесение из конструкции ветвления начала другого ветвления или условия выхода из цикла» получено, что исходный и преобразованный алгоритмы (см рис 6) эквивалентны, если

где Z(m0i) и Z(m02) - множества комбинаций значений данных, при которых происходит передача управления на метки тт или из02, причем события передачи управления на эти метки не совместны,

Рп, Р'п ~ предикаты условий вершин ветвления исходного и результирующего уграфов,

Ьп\, Ъл, е {true, false} - логические переменные, совпадение значений которых с результатами вычисления предикатов условий приводит к осуществлению соответствующих переходов

Рис. 6. Преобразование «Вынесение начала ветвления или условия выхода из цикла из конструкции ветвления»

Откуда определяется предикат ветвления преобразованного фрагмента уграфа

Р'п Ь'п2 = Рп^ Ьп2> если 2 е z0%) p\^b'n2 = false, если zeZ(mm)

Шг Ш\

рп, если (Ъ\2 = bn2)&[z е Z(m0l)], Р„, если (Ъ\2 = bn2)&[z е Z(/w01)], true, если(6'„2 = false)&[z е Z(m02)], false, если (b'n2 = true)&[z e Z(m02)]

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

В четвертой главе «Математические основы и лингвистические средства разработки и анализа алгоритмов» выполнен анализ отношений компонентов графовых моделей и определена совокупность характеристик и элементарных операций над компонентами графовых моделей В табл 4 показаны характеристики, необходимые для полного описания структуры гиперграфов и ультраграфов

Таблица 4

Характеристики элементов графовых моделей

№ Модель Характеристики элементов при различных отношениях между ними

ГХ ги ги впи К„Хи <2Х,ь

1 Гиперграф р(*>) у(и,) Рп(х,) — Я(х,)

2 Ориентированный гиперграф Р(х,) Фу) Рп(х,) ЫитЬег(х,) Ч(х,)

3 Ультраграф Ь{х,) Ъ{х,) у(и,) Ф/) е{и}) е(ч,) е{и}) е(и}) Р„(х.) Р„(х,) Ф-)

4 Ультраграф с упорядоченными вершинами ребра Ь{х,) Ь{х,) Ч«,) Ч«,) е{и}) е{и}) е(и;) е(^) РЛх.) р„(х,) ЫитЬег(х,) Ф.)

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

а = {Ор°мод , Ор°пр , Ор°хар },

где OpGuoд = {+, -, п, и, \, Fací} - символы операций преобразования (добавление и удаление вершин и ребер, пересечение, объединение и дополнение графов, подграфов и их кусков, а также свертка кусков),

Ор°Пр = {Г, Г, Г, F, F, F, F„, ~Rn, R~n, Q„, Qn, QJ - символы определения бинарных, я-арных, симметричных, несимметричных отношений инцидентности Г, смежности F, порядка R и кратности Q, OpGx¡9 = {p,b ,b,v, V , v,p, р , р,р„, р„ , р„,е, е , e,q, q , q, Number, GammaBool, ComponenlNumber, NumberOfComponents} - символы оцределения характеристик элементов по различным отношениям и отображениям

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

Ори = {Орммоя, Ормпр, Орихар},

где Ормиол-{, Set, Set weight, Insert, Delete} - символы операций модификации, возможно, взвешенных множеств, мультимножеств и кортежей,

Ормпр={е (g), Duplicate, Next, Previous}- символы операций просмотра данных тех же типов,

Of/^xаР ={Card, Length, n Duplicate, Number, Get, Get_ weight} — символы операций просмотра характеристик

Определено множество конструкций и предложен синтаксис языка описания алгоритмов на уровне операций над множествами Синтаксические правила основных конструкций языка <Список операторов> = <Помеченный оператор> |

<Список операторов>, <Помеченный оператор> <Помеченный оператор> = <Метка> <Оператор> | <Оператор> <Оператор> = <Составной оператор> | <Присваивание> | <Условный оператор> | <Циют счетный> | <Выборка> | <Безусловный переход> | <Вызов процедуры> <Метка> = # <Целое без знака> безусловный переход> = goto <Метка>

<Условный оператор> =<Логическое выражение> => <Оператор> <Выборка> ={<Элемент-переменная>е<Выражение множественное>/

<Выражение логическое>}| {<Элемент-переменная> / <Выражение логическое>} <Цикл счетный> = <Заголовок цикла> <Оператор> <3аголовок цикла> = <3аголовок счетного цикла> |

(<Заголовок счетного цикла>) & (<Выражение логическое>)

<3аголовок счетного цикла> =

У<Идентификатор>=<Выражение арифметическое>, <Выражение арифметическое >|

\/<Элемент-переменная> е <Выражение множественное> <Элемент-переменная> = <Идентификатор> | <Идентификатор> [<Идентификатор>] | <Идентификатор> [<Идентификатор>, <Идентификатор>] Определено множество дополнительных конструкций, которые необходимо включить в язык описания алгоритмов, чтобы обеспечить описание алгоритмов на уровне операций над графовыми моделями

Сформулированы правила описания графовых моделей и их фрагментов подграфов и кусков, а также наборы множеств для представления всех типов графовых моделей (см табл 5)

Таблица 5

Описание графовых моделей и набор подмножеств их отображений

№ Тип модели Подтип Подмножества отображений

1 Граф и мультиграф а) Неориентированный Undirected XFX={XFX}, UFU = {UFU}, xru=\xfu}, игх= {ufx}

б) Ориентированный Directed XFX= {XFX, XFX}, UFU={ UFU, UFU, UFU, UFU }, xru= {xfu, xfu}, urx={ufx, ufx}

2 Гиперграф а) С неупорядоченными вершинами _ребра Unarranged XFX= {XFX }, UFU = {UFU }, xru= {xfu}, urx= {ufx}

б) С упорядоченными вершинами в ребре Arranged XFX= {XFX } , UFU= {UFU }, xru= {xfu}, UFX= {UVX}

3 Ультраграф а) С неупорядоченными вершинами ребра Unarranged XFX={XFX ,XFX,XFX,XFX }, UFU={ UFU,UFU,UFU, UFU }, xru= {xfu, xfu}, urx= {ufx, ufx}

б) С упорядоченными вершинами в ребре Arranged XFX = { XFX, XFX ,XFX, XFX }, UFU={ UFU, UFU, UFU, UFU }, хги={ xfu,xfu}, urx={ ufx ,ufx ,итх}

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

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

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

Найти вариант представления графовой модели

leJ r¡ = min{rjlye,/}, при L¡ < Laon, где J- количество комбинаций отображений в представлении графовой модели, к

L¡ =£/ - объем памяти для хранения отображений j-ой комбинации пред-i=i

ставления,

К - количество отображений в комбинации,

к ,

г j = a f — количество операций, необходимых для получения недос-

i=i "

тающих образов при j-м варианте представления, f¡ — кратность получения г-го отображения в алгоритме, at¡- количество операций, необходимых дня получения /-го отображения

А'= {Aje A й}

Поскольку количество вариантов представления невелико (/<" < 7 - если рассматриваются табличные способы, К < 15- если рассматриваются аналитические способы víK<72- если рассматриваются и те и другие способы одновременно), поставленная задача может быть решена методом перебора

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

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

<Решающее правило> = <Условие существования> & <Условие целесообразности>& <Условие допустимости> & <Условие локальности>& <3аменяемая строка> —> <3аменяющая строка> Приведены примеры описания синтаксиса заменяемой и заменяющей строк, а также решающих правил оптимизирующих преобразований Так правило исключения лишних вычислений при определении показателей связности, используемое для замены фрагментов вида

V; = 1, п-\ {У 1 = 1+1 ,п (А'-.Л = СагсКТхЩгл Г.;ф]))),

на фрагменты вида

\/г=1,п (У/=/+1,и ($[*/] =0), \/хЩ эЛф] (.?[/,у] = СагЛ(Гх[/] п Г*[у]))),

при условии наличия в описании алгоритма отображения ГХ, где Х- множество вершин гиперграфа, выглядит следующим образом

(осеЛ) & (уеЛ) —» (а =(3),

где а, (3 - строки описания заменяемого и заменяющего фрагментов,

у — строка, определяющая наличие отображения РХ среди исходных данных алгоритма, А — упорядоченное множество строк описания алгоритма Синтаксически заменяемый и заменяющий фрагменты при этом определяются следующим образом <3аменяемый фрагмент> = \/<Индекс1>= 1, <Границал>-1

(Ч^<Индекс2>=<Индекс1>+1 ,<Границаи> (<Матрица> [<Индекс 1 >,<Индекс2>] =

Саг^/(Г< Множество 1 > [<Индекс 1 >]пГ<Множество 1 > [<Индекс2>]))), где <Индекс1>, <Индекс2> - идентификаторы целого типа,

<Границаи> - идентификатор целого типа - размерность множества вершин графа,

<Матрица> — идентификатор матрицы, <Множество1> - идентификатор множества вершин графа <3аменяющий фрагмент> = У<Индекс1>= 1, <Границаи>-1

(\/<Индекс2> = <Индекс1>+1, <Границап>

(<Матрица>[<Индекс1>,<Индекс2>] = 0), \/<Множество1 >[<Индекс2>] э Г <Множество1>[< Индекс 1>]

(<Матрица> [<Индекс 1 >,<Индекс2>] = С«гг/(Г< Множество 1 > [<Индекс1>]пГ<Множество1 >[<Индекс2>]))),

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

Полученные правила составили основу создания автоматического оптимизатора алгоритмов

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

В пятой главе «Реализация и экспериментальные исследования системы разработки алгоритмов» описаны назначение, состав (см рис 7) и функции основных частей системы описания, реализации и анализа алгоритмов решения задач структурного анализа и синтеза (см рис 8) Приведены результаты ее эксплуатации и экспериментальных исследований

Текстовый редактор

Процедура преобразования исходных данных

Процедура преобразования результата

Генератор данных

Структуризатор

Процедура подсчета операций

Проадура выбора способа представления

Оптимизатор

Анализатор сложности алгоритма

Система разработки алгоритмов и решения задач структурного анализа и синтеза

Транслятор

Синтезатор структур данных

Генератор описаний структур данных для графов

Генератор описаний структур данных для множеств

Подсистема обслуживания/ визуализации

Рис. 7. Структура системы разработки алгоритмов и решения задач структурного анализа и синтеза

Система разработки алгоритмов и ре

Jnjxj

@ Файл Помощь

Описание проекта

Редактирование Вид Проект Выполнение Окно

^JeJxJ

Дета создания

Дата изменения

Описание данный

Описание алгоритма

AJstl-WO

611 £006 20.6

10.11.200615:3

DJistl.dec

И роСКТ. dpi

И смешные Донные

'1 ре^уЛЬГЗГОЕ

Комметерки проег.та

□писание данных Описей» Алгоритма

begin

VI =1, р:

vlcX: (i»0=>(Xt:=Xl-t:)i; ni:- card (XI); W* l.nt-1

(im=Z; Й1:=хЩ UI:=Gx№;

Щ

I xli;-xM:

Рис. 8. Интерфейс системы

Программное обеспечение написано на Delphi Раиса! и I is на! С++ и имеет объем - 22000 операторов.

Сформулированы цели экспериментальных исследований, даны характеристики объектов

Экспериментальная проверка программы, реализующей метод структуризации, показала, что структурированная программа сортировки слияниями эквивалентна исходной с точки зрения результатов на всем диапазоне допустимых значений исходных данных Время выполнения этой программы превышает время выполнения исходной при размере входа N = 460000 не более чем на 4 %, что согласуется с общепринятыми нормами

Экспериментальные исследования различных программ решения задач структурного анализа и синтеза показали, что трудоемкость создания программ с использованием системы на порядок ниже трудоемкости создания тех же программ вручную

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

4 Обоснован синтаксис и определена семантика двух специализированных языков описания алгоритмов решения задач структурного синтеза на уровне операций над графовыми моделями и операций над множествами Применение указанных языков позволяет формулировать описание алгоритма с использованием абстракций предметной области и обеспечивает возможность автоматического выполнения частичной оптимизации алгоритма и синтеза оптимальных структур данных

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

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

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

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

Работы по теме диссертации

1 Иванова Г С Формальная постановка задачи структуризации алгоритмов // Вестник Московского государственного технического университета им НЭ Баумана Приборостроение - 2005 -№3(60) - С 64-73

2 Иванова Г С Нумерация вершин управляющего графа для решения задачи его структуризации // Информационные технологии - 2005 -№ 12 -С 48-56

3 Иванова Г С Математические модели структур данных // Информационные технологии - 2006 - № 9 - С 44-52

4 Иванова Г С Модели объектов задач структурного синтеза // Наука и образование Инженерное образование Эл науч издание - 2006 -№ 12 (Номер гос регистрации 0420600025X0053 )

5 Иванова Г С Способы представления структурных моделей // Наука и образование Инженерное образование Эл науч издание — 2007 — № 1 (Номер гос регистрации 0420700025X003 )

6 Иванова Г С Основы программирования Учебник для вузов - M Изд-воМГТУим НЭ Баумана,2004 -416с

7 Иванова Г С , Ничушкина Т H, Пугачев Е К Объектно-ориентированное программирование Учебник для вузов / Под ред Г С Ивановой -M Изд-во МГТУ им H Э Баумана, 2003 - 366 с

8 Иванова Г С Технология программирования Учебник для вузов - M Изд-во МГТУ им НЭ Баумана, 2003 -320 с

9 Овчинников В А, Иванова Г С Информационно-логическая модель алгоритма // Вестник Московского государственного технического университета им H Э Баумана Приборостроение - 2005 — № 2(59) -С 109-121

10 Овчинников В А , Иванова Г С Проектно-исследовательская система решения задач структурного синтеза // Тез докл научно-технической конференции -М,2000 -С 41

11 Овчинников В А , Иванова Г С Способы снижения вычислительной сложности реализации операций над множествами // Научный вестник МГТУ ГА Информатика Прикладная математика - 2002 - № 55 -С 38-42

12 Овчинников В А , Иванова Г С , Ничушкина Т H Выбор структур данных для представления графов при решении комбинаторно-оптимизационных задач // Вестник Московского государственного технического университета им H Э Баумана Приборостроение - 2001 -№2(43) -С 39-51

13 Иванова Г С, Бакулина М А Автоматизация процесса разработки алгоритмов решения задач структурного синтеза на графах // Тез Докл Международной научно-технической конференции - М, 2003 -С 166-167

14 Иванова Г С, Домосканов А А Оптимизация управления динамическим распределением оперативной памяти // Современные информационные технологии Сб докл и сооб Межвузовской юбилейной на-учно-техническойконференции -М,2001 - С 6-13

15 Иванова ГС, Ничушкина ТН Проектирование синхронных интерфейсов интерактивных программных систем // Научный вестник МГТУ ГА Информатика Прикладная математика - 2002 - № 55 -С 33-37

16 Бакулина М А , Иванова Г С Средства автоматизации процесса решения задач структурного синтеза // Аэрокосмические технологии Материалы Первой международной научно-технической конференции, посвященной 90-летию со дня рождения академика В Н Челомея - М , 2004 -С 167-169

17 Иванова Г С, Пасечников К А Макрогенерация описаний структур данных для системы проектирования алгоритмов решения задач структурного синтеза // Современные информационные технологии Сб. трудов каф, посвященный 175-летию МГТУ им НЭ Баумана - М Эликс+, 2004 - С 69-73

18 Иванова Г С , Тихонов Ю В Введение в МПролог Практическое пособие для программистов - М Изд-во МГТУ, 1990 - 152 с

19 Овчинников В А , Иванова Г С , Попов А Ю Применение метода ветвей и границ для решения задачи дихотомического разрезания гиперграфа // Вестник Московского государственного технического университета им Н Э Баумана Приборостроение Информатика — 1999 -№2(34) - С 78-91

Подписано к печати 03 09 07 Заказ № 573 Объем 2,0 печ л Тираж 100 экз Типография МГТУ им Н Э Баумана 105005, Москва, 2-я Бауманская ул, д 5 263-62-01

ВВЕДЕНИЕ.

1. ОПРЕДЕЛЕНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ И ПОСТАНОВКА ЗАДАЧИ.

1.1. Задачи анализа и синтеза структур и области их приложения.

1.2. Объекты задач анализа и синтеза структур и их модели.

1.3. Анализ процесса и разработка многоуровневой схемы реализации алгоритмов решения задач структурного анализа и синтеза.

1.4. Проблемы поэтапного описания и реализации алгоритмов решения задач структурного анализа и синтеза на графах.

1.4.1. Создание языков формального описания алгоритмов на уровнях графов и представляющих их множеств.

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

1.4.3. Разработка средств снижения вычислительной сложности.

1.4.4. Синтез структур данных для представления графовых моделей.

1.4.5. Приведение алгоритмов к структурному виду.

1.4.6. Разработка моделей алгоритма и данных. выводы по главе 1.

2. АНАЛИЗ АЛГОРИТМОВ И ДАННЫХ И ПОСТРОЕНИЕ ИХ

МОДЕЛЕЙ.

2.1. Модели объектов задач структурного анализа и синтеза.

2.2. Способы задания моделей объектов.

2.3. Информационно-логическая модель алгоритма.

2.4. Модели структурных конструкций, структурного алгоритма и их свойства.

2.5. Модели базовых структур данных и их свойства.

2.6. Модели многоуровневых и комбинированных структур данных

Выводы г10 главе 2.

3. ИССЛЕДОВАНИЕ СВОЙСТВ АЛГОРИТМОВ И РАЗРАБОТКА МЕТОДА ИХ ПРИВЕДЕНИЯ К СТРУКТУРНОМУ ВИДУ.

3.1. Формальная постановка задачи структуризации алгоритма.

3.2. Нумерация вершин управляющего графа и определение идентифицирующих признаков конструкций.

3.2.1. Требования к нумерации и анализ известных нумераций.

3.2.2. Выбор модели алгоритма и разработка правил нумерации.

3.2.3. Разработка метода нумерации.

3.2.4. Модель результата и алгоритм нумерации.

3.3. Синтаксис и семантика языка описания конструкций алгоритмов.

3.3.1. Множество терминальных символов.

3.3.2. Определение правил продукции языка описания структурных конструкций.

3.3.3. Распознающий автомат.

3.4. Анализ неструктурных фрагментов описания структуры алгоритма.

3.5. Элементарные структурирующие преобразования алгоритмов и определение условий их эквивалентности.

3.5.1. Инверсия условий передачи управления (П1).

3.5.2. Изменения последовательности слияния потоков управления (П2).

3.5.3. Вынесение начала ветвления или условия выхода из цикла из конструкции ветвления (ИЗ).

3.5.4. Разделение потока управления в точке слияния, за которой следует оператор изменения данных (П4).

3.5.5. Разделение потока управления в точке слияния, за которой следует оператор ветвления (П5).

3.5.6. Изменение последовательности ветвления потоков управления (П6).

3.5.7. Вынесение оператора изменения данных из ветвления или изменение данных до выхода из цикла (П7).

3.5.8. Внесение оператора изменения данных в ветвление или проверка условия выхода из цикла до изменения данных (П8).

3.6. Виды нарушения структурности и их устранение с использованием элементарных структурирующих преобразований.

3.6.1. Условие выхода из цикла в одной из ветвей ветвления, непосредственно следующее за началом ветвления (HI).

3.6.2. Условие выхода из цикла в одной из ветвей ветвления, отделенное от начала ветвления вершиной изменения данных (Н2).

3.6.3. Пересечение ветвлений: вершина слияния непосредственно следует за вершиной ветвления (НЗ).

3.6.4. Пересечение ветвлений: вершина ветвления отделена от вершины слияния (Н4).

3.6.5. Пересечение ветвления и цикла, являющееся следствием неверной последовательности вершин слияния (Н5).

3.6.6. Пересечение ветвления и цикла: наличие дополнительных входов в цикл (Н6).

3.6.7. Дополнительные выходы из цикла: два выхода из цикла подряд (Н7).

3.6.8. Дополнительные выходы из цикла: два выхода из цикла не подряд (Н8).

3.6.9. Условие выхода из цикла в середине тела цикла (Н9).

3.7. Разработка алеоритма структуризации. выводы по главе 3.

4. МАТЕМАТИЧЕСКИЕ ОСНОВЫ И ЛИНГВИСТИЧЕСКИЕ СРЕДСТВА РАЗРАБОТКИ И АНАЛИЗА АЛГОРИТМОВ.

4.1. Определение совокупности операций над графовыми моделями.

4.2. Определение совокупности абстракций и множества операций над ними для языка описания алгоритма на уровне множеств.

4.3. Синтаксис языка формального описания алгоритмов в операциях над множествами и выбор способа построения его распознавателя

4.4. Синтаксис и семантика языка формального описания алгоритмов в операциях над графами.

4.5. Автоматизация анализа вычислительной, временной и емкостной сложности алгоритма.

4.6. Выбор оптимального способа представления графовой модели множествами.

4.7. Синтез комбинированных структур данных для представления графовых моделей.

4.8. Синтез решающих правил для оптимизирующих преобразований алгоритма.

4.9. Методика проектирования и анализа алгоритмов решения задач структурного анализа и синтеза.

Выводы по главе 4.

5. РЕАЛИЗАЦИЯ И ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ СИСТЕМЫ РАЗРАБОТКИ АЛГОРИТМОВ.

5.1. Программное обеспечение системы разработки алгоритмов.

5.2. Экспериментальное исследование приведения алгоритмов к структурному виду.

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

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

5.5. Исследование эффективности оптимизирующих преобразований.

Выводы по главе 5.

ВЫВОДЫ.

Актуальность. К задачам структурного анализа и синтеза относят задачи исследования или определения некоторого варианта структуры объекта, под которой понимают совокупность составляющих его элементов и связей между ними [63]. В качестве моделей объекта и результата в этих задачах обычно используются графы различных типов, позволяющие отображать существенные с точки зрения решаемой задачи отношения между компонентами рассматриваемой структуры.

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

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

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

Рассматриваемые задачи в основном являются NP- полными [1, 7, 44, 56, 61, 62, 64 и др.], что делает время их точного решения даже на современных ЭВМ неприемлемо большим. Причем непрерывное совершенствование технических средств и усложнение современных программных систем приводит к существенному росту размерности входа задач, связанных с анализом и синтезом структур.

Для решения задач данного класса предложено большое количество различных методов и алгоритмов [2, 5-7, 14, 22, 39, 44, 48, 55-58, 61, 64, 73, 7881, 85, 86, 93, 95, 97, 101, 102, 115]. Однако появление новых задач предполагает разработку новых методов и алгоритмов, и, кроме того, в условиях роста размерности входа для уже имеющихся задач, алгоритмы решения которых имеют большую вычислительную сложность, актуальной остается проблема разработки новых приближенных методов и алгоритмов, которые позволят за приемлемое время получать результаты с требуемой точностью.

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

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

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

Широкое распространение, многообразие постановок задач структурного анализа и синтеза и высокая трудоемкость разработки алгоритмов решения этих задач делают актуальной автоматизацию процесса разработки алгоритмов их решения, что также подтверждается увеличившимся интересом к разработке и исследованию алгоритмов решения задач структурного анализа и синтеза в отечественной и иностранной литературе [4, 44, 62, 64, 93, 95, 115 и т. д.].

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

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

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

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

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

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

Основные решаемые задачи. Для достижения указанной цели в работе потребовалось:

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

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

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

4. Разработать синтаксис и семантику языков описания алгоритмов в операциях над множествами и в операциях над графами, а также трансляторы с них.

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

6. Получить совокупность оптимизирующих преобразований алгоритмов на графах и сформулировать соответствующие синтаксические правила.

7. Создать методику и средства оценки и снижения вычислительной и емкостной сложности алгоритмов.

8. Создать методику и программную систему разработки и анализа эффективности алгоритмов решения задач структурного анализа и синтеза.

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

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

1. Предложена многоуровневая схема описания, реализации и оптимизации алгоритмов решения задач структурного анализа и синтеза.

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

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

4. Определены полные наборы инвариантов моделей структурных конструкций, сформулированы аксиоматика операции свертки уграфов структурных конструкций и теорема о необходимом и достаточном условии структурности алгоритма.

5. Формально поставлена задача приведения алгоритмов к структурному виду, разработан и реализован метод ее решения.

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

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

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

Апробация работы. Основные положения работы обсуждались на научно-технической конференции, посвященной 170 лет МГТУ им. Н.Э. Баумана (Москва, 2000), на межвузовской научно-технической конференции МГТУ им. Н.Э. Баумана (Москва, 2003), на Международной научно-технической конференции «Гражданская авиация на современном этапе развития науки, техники и общества» (Москва, 2003), на первой Международной научно-технической конференции, посвященной 90-летию со дня рождения академика В.Н. Челомея (Москва-Реутов, 2004).

Реализация и внедрение. Все основные теоретические и практические результаты работы в виде методик и программных средств внедрены в промышленность. Они использованы при выполнении опытно-конструкторских работ по темам И070406 и И070507 («Метеор-ЗМ-ИКФС-2-МЭ») в НИИ ИСУ МГТУ им. Н.Э. Баумана, работ по договорам № 275/2004 («Разработка Информационной управляющей системы»), № 177/2006 («Разработка информационно-аналитической системы оценки технического состояния, эффективности защиты магистрального газопровода и прогнозирования коррозионного состояния») в ЗАО «РТСофт» и при создании системы управления контентом адаптивных сайтов RBC Contents 5.01 в РБК Софт (РосБизнесКонсалтинг). Кроме этого, разработанные в диссертации Ивановой Г.С. методики, аналитические, лингвистические и программные средства используются при чтении лекций и проведении семинарских занятий по курсам «Алгоритмические языки и программирование», «Системное программное обеспечение» и «Автоматизация конструкторского проектирования ЭВМ», а также выполнении курсовых и дипломных проектов. Документы, подтверждающие внедрение, приведены в приложении.

Публикации. По результатам диссертационной работы автором опубликовано 19 работ: 15 статей, 3 учебника и 1 учебное пособие.

По материалам работы защищена 1 и выполняется еще 2 диссертации на соискание степени кандидата технических наук, защищено 2 магистерских работы.

Объем и структура диссертации. Диссертационная работа включает введение, пять глав, заключение и список литературы, занимающих 411 страниц текста, в том числе 85 рисунков и 65 таблиц на 119 страницах, список использованной литературы из 115 наименований на 10 страницах.

ВЫВОДЫ

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

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

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

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

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

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

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

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

1. Алгоритмы и программы решения задач на графах и сетях / М.И. Не-чипуренко, В.К. Попков, С.М. Майнагашев и др. Новосибирск: Наука. Сиб. отделение, 1990. -515 с.

2. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ Регулярная и хаотическая динамика, 2001.-288 с.

3. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции: Пер. с англ. М.: Мир, 1978. - Т. 1.-611 с.

4. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции: Пер. с англ. M.: Мир, 1978. - Т. 2. - 487 с.

5. Ахо A.B., Хопкрофт Д., Ульман Д.Д. Построение и анализ вычислительных алгоритмов: Пер. с англ. М.: Мир, 1978. - 536 с.

6. Ахо A.B., Хопкрофт Д., Ульман Д.Д. Структуры данных и алгоритмы: Пер. с англ. М.: Издательский дом Вильяме, 2001. - 384 с.

7. Базилевич Р.П. Декомпозиционные и топологические методы автоматизированного конструирования электронных устройств. Львов: Вища школа, 1981. - 168 с.

8. Вениаминов Е.М., Ефимова Е.А. Элементы универсальной алгебры и ее приложений в информатике. М.: Научный мир, 2004. -168 с.

9. Бершадский A.M. Применение графов и гиперграфов для автоматизации конструкторского проектирования РЭА и ЭВА. Саратов: Изд-во Саратовского ун-та, 1983. - 120 с.

10. П.Вирт Н. Алгоритмы+структуры данных=программы: Пер. с англ. -М.: Мир, 1985.-406 с.

11. Глушков В.М. Теория автоматов и формальные преобразования микропрограмм // Кибернетика. 1965. - № 5 (6). - С. 1-10.

12. Глушков В.М., Цейтлин Г.Е., Ющенко E.JI. Алгебра. Языки. Программирование. Киев: Наукова думка, 1978. - 389 с.

13. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов: Пер. с англ. -М.: Мир, 1981.-368 с.

14. Грис. Д. Конструирование компиляторов для цифровых вычислительных машин: Пер. с англ. -М.: Мир, 1975. 544 с.

15. Дал У., Дейкстра Э., Хоор К. Структурное программирование: Пер. с англ. М.: Мир, 1975. - 248 с.

16. Евстигнеев В.А. Применение теории графов в программировании / Под ред. А.П. Ершова. М.: Наука. Гл. ред. физ.-мат. лит., 1985. - 352 с.

17. Ершов А.П. Операторные алгоритмы. III (Об операторных схемах Янова) // Проблемы кибернетики (М.). 1968. - Вып. 20. - С. 25-43.

18. Ершов А. П. Описание основных конструкций программирования // Проблемы кибернетики (М.). 1962. - Вып. 8. - С. 12-31.

19. Ершов А.П. Современное состояние теории схем программ // Проблемы кибернетики (М.). 1973. - Вып. 27 (4). — С. 87-111.

20. Зыков A.A. О некоторых свойствах линейных комплексов // Математический сборник. 1949. - Вып. 2 (24). - С. 163-188.

21. Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учеб. пособие. М.: Лаборатория Базовых Знаний, 2002. - 288 с.

22. Иванова Г.С. Математические модели структур данных // Информационные технологии. 2006. - № 9. - С. 44-52.

23. Иванова Г.С. Модели объектов задач структурного синтеза // Наука и образование. Инженерное образование: Эл. науч. издание. 2006. - № 12. (Номер гос. регистрации 0420600025\0053.)

24. Иванова Г.С. Нумерация вершин управляющего графа для решения задачи его структуризации // Информационные технологии. 2005. - № 12. -С, 48-56.

25. Иванова Г.С. Основы программирования: Учебник для вузов. М.: Изд-во МГТУ им. Н.Э. Баумана, 2004. - 416 с.

26. Иванова Г.С. Способы представления структурных моделей // Наука и образование. Инженерное образование: Эл. науч. издание. 2007. - № 1. (Номер гос. регистрации 0420700025X003.)

27. Иванова Г.С. Технология программирования: Учебник для вузов. -М.: Изд-во МГТУ им. Н.Э. Баумана, 2003. 320 с.

28. Иванова Г.С. Формальная постановка задачи структуризации алгоритмов // Вестник Московского государственного технического университета им. Н.Э. Баумана. Приборостроение. 2005. - № 3(60). - С. 64-73.

29. Иванова Г.С., Бакулина М.А. Автоматизация процесса разработки алгоритмов решения задач структурного синтеза на графах // Тез. докл. Международной научно-технической конференции М., 2003. - С. 166-167.

30. Иванова Г.С., Домосканов A.A. Оптимизация управления динамическим распределением оперативной памяти. // Современные информационные технологии: Сб. докл. и сооб. Межвузовской юбилейной научно-технической конференции.-М., 2001. С. 6-13.

31. Иванова Г.С., Ничушкина Т.Н. Проектирование синхронных интерфейсов интерактивных программных систем. // Научный вестник МГТУ ГА. Информатика. Прикладная математика. 2002. - № 55. - С. 33-37.

32. Иванова Г.С., Ничушкина Т.Н., Пугачев Е.К. Объектно-ориентированное программирование: Учебник для вузов. М.: Изд-во МГТУ им. Н.Э. Баумана, 2003. - 366 с.

33. Иванова Г.С., Тихонов Ю.В. Введение в МПролог: Практическое пособие для программистов. М.: Изд-во МГТУ, 1990. - 152 с.

34. Калужнин JI.A. Что такое математическая логика? М.: Наука. Гл. ред. физ.-мат. лит., 1964. - 150 с.

35. Касперски К. Техника оптимизации программ. Эффективное использование памяти. СПб.: БХВ - Петербург, 2003. - 464 с.

36. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ - Петербург, 2003. - 1104 с.

37. Касьянов В.Н. Оптимизирующие преобразования программ. М.: Наука. Гл. ред. физ.-мат. лит., 1988. - 336 с.

38. Компаниец Р. П., Маньков Е. В., Филатов Н. Е. Системное программирование. Основы построения трансляторов: Уч. пособие. СПб.: Корона принт, 2000. - 256 с.

39. Кнут Д. Искусство программирования для ЭВМ: Пер. с англ. 2-е изд. - М.: Издательский дом Вильяме, 2001. -Т.1 - 720 с.

40. Кнут Д. Искусство программирования для ЭВМ: Пер. с англ. 2-е изд. - М.: Издательский дом Вильяме, 2001. - Т. 3. - 823 с.

41. Компаниец Р.И., Маньков Е.В., Филатов Н.Е. Системное программирование. Основы построения трансляторов. СПб.: Корона принт, 2000. - 320 с.

42. Кормен Т., Лейзерсон Ч., Риверст Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000. - 960 с.

43. Котов В.Е. Введение в теорию схем программ. Новосибирск: Наука, 1978.-256 с.

44. Котов В.Е., Сабельфельд В.К. Теория схем программ. М.: Наука. Гл. ред. физ.-мат. лит., 1991. -248 с.

45. Кофман А. Введение в прикладную комбинаторику. М.: Мир, 1981. -480 с.

46. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.-427 с.

47. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергоатомиздат, 1988. - 480 с.

48. Лавров С.С. Программирование. Математические основы, средства, теория,- СПб.: БХВ-Петербург, 2001. 320 с.

49. Липский В. Комбинаторика для программистов: Пер. с польск. М.: Мир, 1988.-213 с.

50. Лекции по теории графов / В.А. Емеличев, О.И. Мельников, В.И. Сарванов и др. М.: Наука, Гл. ред. физ.-мат. лит., 1990. - 384 с.

51. Майерс Г. Надежность программного обеспечения: Пер. с англ. М.: Мир, 1980.-360 с.

52. Мартынюк В.В. Об изменении порядка выполнения операторов в операторной схеме // ЦВТ и программирование. М.: Советское радио, 1967. -Вып. 2. - С. 67-72.

53. Макконнелл Дж. Основы современных алгоритмов: Пер. с англ. М.: Техносфера, 2004. - 368 с.

54. Мелихов А.Н. Ориентированные графы и конечные автоматы. М.: Наука. Гл. ред. физ.-мат. лит., 1971. - 416 с.

55. Мелихов А.Н., Берштейн Л.С. Гиперграфы в автоматизации проектирования дискретных устройств. Ростов-на-Дону: Из-во Ростовского униве-ситета, 1981. - 112 с.

56. Мелихов А.Н., Берштейн Л.С., Курейчик В.М. Применение графов для проектирования дисретных устройств. М.: Наука, 1974. - 303 с.

57. Мину М. Математическое программирование. Теория и алгоритмы. -М.: Наука, 1990.-488 с.

58. Многоуровневое структурное проектирование программ: Теоретические основы, инструментарий / Е.Л. Ющенко, Г.Е. Цейтлин, В.П. Грицай и др. -М.: Финансы и статистика, 1989. 208 с.

59. Морозов К.К., Одиноков В.Г., Курейчик A.M. Автоматизированное проектирование конструкций радиоэлектронной аппаратуры. М.: Радио и связь, 1983.-280 с.

60. Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2001.-304 с.

61. Норенков И.П. Основы автоматизированного проектирования: Учеб. для вузов. М.: Изд-во МГТУ им. Н.Э. Баумана. - 2000. - 360 с.

62. Овчинников В.А. Автоматизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем: Учеб. для вузов. М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. - 288 с.

63. Овчинников В.А., Иванова Г.С. Информационно-логическая модель алгоритма // Вестник Московского государственного технического университета им. Н.Э. Баумана. Приборостроение. 2005. -№ 2(59). - С. 109-121.

64. Овчинников В.А., Иванова Г.С. Проектно-исследовательская система решения задач структурного синтеза // Тез. докл. научно-технической конференции. М., 2000.-С. 41.

65. Овчинников В.А., Иванова Г.С. Способы снижения вычислительной сложности реализации операций над множествами // Научный вестник МГТУ ГА. Информатика. Прикладная математика. 2002. - № 55. - С. 38-42.

66. Овчинников В.А., Николаев К.В., Попов А.Ю. Исследование вычислительной сложности алгоритмов двоичной свертки схем ЭВМ // Вестник

67. Московского государственного технического университета. Приборостроение. 1997. - № 2. - С. 113-120.

68. Оре О. Теория графов. М.: Наука, 1980. - 336 с.

69. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. -М.: Мир, 1985. 512 с.

70. Пасхавер И.С., Яблочник А.Л. Общая теория статистики / Под ред. М.М. Юзбашева. М.: Финансы и статистика, 1983. - 432 с.

71. Пратт Т., Зелковиц М. Языки программирования: разработка и реализация / Под ред. А. Матросова. СПб.: Питер, 2002. - 688 с.

72. Попов А.Ю. Модели и алгоритмы автоматизированной декомпозиции схем ЭВМ: Дисс. . канд. техн. наук. М., 2004. - 136 с.

73. Проектирование высокопроизводительного процессора обработки графов / С.М. Абрамов, A.B. Кондратьева, В.А. Роганов и др. // Информационные технологии. 2001. - № 3. - С. 7-10.

74. Райли Д. Абстракция и структуры данных: Пер. с англ. М.: Мир, 1993.-752 с.

75. Савельев А.Я., Овчинников В.А. Конструирование ЭВМ и систем: Учебник для вузов. М.: Высшая школа, 1989. - 312 с.

76. Седжвик Р. Фундаментальные алгоритмы на С: Пер. с англ. СПб, ООО ДиаСофт, 2003. - 1136 с.

77. Судоплатов С. В., Овчинникова Е.В. Элементы дискретной математики: Учебник для вузов. М. - Новосибирск: ИНФРА-М - Изд-во НГТУ, 2002.-280 с.

78. Татт У. Теория графов: Пер. с англ. М.: Мир, 1988. - 424 с.

79. Теоретические основы проектирования компиляторов / Ф. Льюис, Р. Розенкранц, Р. Стиринз: Пер. с англ. -М.: Мир, 1979. 654 с.

80. Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. М.: Наука. Гл. ред. физ.-мат. лит., 1987. - 288 с.

81. Харрари Ф. Теория графов: Пер. с англ. М.: Едиториал УРСС, 2003.-296 с.

82. Хидитниеми С., Гудман С. Введение в разработку и анализ вычислительных алгоритмов: Пер. с англ. М. Мир, 1981 г. - 366 с.

83. Цейтлин Г.Е. Формальные аспекты структурного программирования с GOTO // Программирование. 1984. - № 1. - С. 3-16.

84. Цейтлин Г.Е. Формальная трансформация структурированных алгоритмов сортировки // Программирование. 1985. - № 2. - С. 88-100.

85. Янов Ю.И. О логических схемах алгоритмов // Проблемы кибернетики (М.).- 1958. -Вып. 1.-С. 75-109.

86. Ashcroft Е., Manna Z. The translation of GOTO Programs to WHILE Programs // Proc. IFIP Congress 71; Lubljana (Yugoslavia), August 23-28 1971. -Amsterdam, 1972. -V. 1. P. 250-255.

87. Baker B.S. An algorithm for structuring flowfraphs // J. of the ACM. -1977.-V. 24 ,№ i.p. 98-120.

88. Behm C., Jacopini G. Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules // Comm. of ACM. 1966. - V. 9, № 5. - P. 366371.

89. Caldwell A., Kahng A., Markov I. Improved Algorithms for Hypergraph В ¡partitioning // Proc. Asia and South Pacific Design Automation Conf. Tokyo (Japan), 2000.-P. 661-666.

90. Cifuentes C. A structuring Algorithm for Decompilation // Proceedings of the XIX Conf. Latinoamericana de Informatica. Buenos Aries (Argentina), 1993. -P. 267-276.

91. Chang C-C., Cong J., Xie M. Optimality and Scalability of Existing Placement Algorithms // Proc. Asia and South Pacific Design Automation Conf. -Tokyo (Japan), 2003. P. 621-627.

92. Coorer D.C. Behm and Jacopini's reduction of flow charts // Comm. ACM. 1967. - V. 10, № 8. - P. 463-473.

93. Dutt S., Deng W. VLSI Circuit Partitioning by Cluster-Removel Using Interactive Improvement Techniques // Proc. IEEE International Conf. on Computer-Aided Design. San Jose (USA), 1996. - P. 194-200.

94. Earnest C.P., Balke K.G., Anderson J. Analysis of graphs by ordering of nodes // J. ACM. 1972. - Vol. 19, № 1. - P. 23-42.

95. Erosa A.M., Henron L.J. Taming Control Flow: A structured Approach to Elimination GOTO Statements // Proc. IEEE International Conf. on Computer Languages. Toulouse (France), 1994. - P. 229-240.

96. Flajolet Ph., Salvy B., Zimmermen P. Automatic Average-Case Analysis of Algorithms // Theoretical Computer Science. 1991. - Feb. - P. 37-109.

97. Hauck S., Bordello G. An Evaluation of Bipartitioning Techniques // IEEE Transactions of Competer-Aided Design. 1997. - V.16, № 8. - P. 849866.

98. Karypis G., Kumar V. Multilevel k-way partitioning scheme for irregular graphs // J. of Parallel and Distributed Computing. 1998. - № 48 (1). - P. 96129.

99. Kosaraju S.R. Analysis of Structured Programs // J. Computer and System Sci. 1974. - V.9, № 2(3). - P. 232-255.

100. Knuth D.E., Floyd R.W. Notes on avoiding GOTO statements // Inform. Processing Letters. 1971. - № 1. - P. 23-31.

101. Ledgard H.K., Marcotty M.A. Genealogy of Control Structures // Communications ACM. 1975,-V. 18, № 11.-P. 629-639.

102. Martin J.L. Generalized structured programming // AFIPS Conf. Proc. -Chicago, 1974,-V. 43.-P. 665-669.411

103. Mills H.D. Mathematical foundation for structured programming // IBM Tech. Rep. 1972. - V. FSC-72-6012. - P. 34.

104. Peter R. Graph schemata and Recursive Functionalb // Dialectica. -1958.-V.12,- P. 373-388.

105. Peterson W.W., Kasami T., Tokura N. On the capabilities of the WHILE, REPEAT, and EXIT statements // Comm. ACM. 1973. - V. 16, № 8. -P. 503-512.

106. Programming With Sets: An Introduction to SETL / Jacob T. Schwartz, R.B.K. Dewar, E. Dubinsky and etc. New York, 1986. - 127 pp.

107. Ramshaw L. Eliminating goto's while preserving program structure // J. ACM. 1988. - V. 35, № 4. - P. 893-920.

108. Vitter J., Flajolet Ph. Average-Case Analyse of Algorithms and Data Structure // Handbook of Handbook of theoretical computer science: algorithms and complexity. 1991. - Vol. A. - P. 431 -524.

109. Williams M.H. Generating structured flow diagrams: the nature of un-structuredness // Computer. 1977. - V. 20, № 1. - P.45-50.

110. Williams M.H., Chen G. Restructuring Pascal programs containing goto statements// The Computer Journal. 1985. - V. 28, № 2. - P. 134-137.

111. Yang X., Choi B., Sarrafzadeh M. Routability Driven White Space Allocation for Fixed-Diie Standart-Cell Placement // Proc. International Symposium on Physical Design. Del Mar (USA), 2002. - P. 42-49.- СРЕДСТВА и СИСТЕМЫ АВТОМАТИЗАЦИИ

112. Закрытое акционерное общество "РТСофт"

113. Ген.директор «РТСофт» д.т.н. Синенко О.В.1. АКТо внедрении результатов диссертационной работы к.т.н. доцента кафедры "Компьютерные системы и сети" МГТУ им.Н.Э. Баумана Ивановой Г.С.

114. Зам.Генерального директора по проектному бизнесу Л^д С.А.Андрианов ifeim

115. Технический Директор ББ АИУС Куцевич H.A.1. Ко4--!xSs-ож1. РБК СОФТ

116. Адрес: 117393, Москва, уя. Профсоюзная, 78; Е-лиі!; in!o:@t!A.o!iiu; Телефон:(095)363-1111; фаю: (0951363-1125; www.fDcsoH.ru

117. Основные теоретические результаты диссертационной работы Ивановой Г.С. использованы при разработке математической модели адаптивного Интернет-сайта, как новой оригинальной составляющей, реально

118. Лингвистические средства реализации и анализа алгоритмов, разработанные в диссертационной работе Ивановой Г.С., включены в проект очередной версии системы управления контентом RBC Contents 5,01.

119. На базе системы управления контентом RBC Contents предыдущих версий компанией РБК СОФТ реализовано более 600 сайтов, из которых не менее 20 кольца сайтов.

120. Ожидаемый экономический эффект от внедрения положений диссертационной работы Ивановой Г.С. может составить не мене 200 000 рублей на один адаптивный Интернет-сайт.

121. Данный акт не может служить основанием для финансовых претензии.используемой в проектах РБК СОФТ, модели кольца сайтов.

122. Генеральный директор ЗАО «РБ.КХОФТ»1. А.В. Кузовкинл

123. Практическое применение разработанной системы позволило на 30-40 % сократить время разработки алгоритмического и программного обеспечения блока обработки сигналов и управления многофункциональной РДС и блока управления бортового Фурье-спектрометра,

124. Начальник отдела НИИ ИСУ МГТУ им. Н.Э. Баумана, к.т.н., Ст. научный сотрудник

125. A.C. Романовский С.Ю. Чухров

126. МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ имени Н. Э. Баумана

127. Факультет Информатика и системы управления

128. J07005, Москва, 2-я Бауманская ул., 5 Телекс 417661, Для телеграмм; Москва, ГРАЧ Гед. (095) 267-65-37 Факс (095) 267-79-851. УТВЕРЖДАЮ»

129. Руководитель НУК ИСУ ; К4ГТУ ;ще Г1. В.А. Матвеев 2007 г.1. АКТоб использовании результатов диссертационной работы к.т.н. доцента кафедры «Компьютерные системы и сети» МГ'ТУ им. Н.Э. Баумана Ивановой Г'.С,

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

131. Заведующий кафедрой «Компьютерные системы и сети» д.т.п. профессор \-------"" В.В. Сюзев

132. Заместитель заведующего кафедрой по учебной работе 7к.т.н. доцент /^Гу^---;.^-- А.М. Губарь