Методология и средства разработки алгоритмов решения задач анализа и синтеза структур программного обеспечения и устройств вычислительной техники тема диссертации и автореферата по ВАК РФ 05.13.11, доктор технических наук Иванова, Галина Сергеевна

• Иванова, Галина Сергеевна
• доктор технических наук
• 2007

Оглавление диссертации доктор технических наук Иванова, Галина Сергеевна

ВВЕДЕНИЕ.

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

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

Список литературы диссертационного исследования доктор технических наук Иванова, Галина Сергеевна, 2007 год

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; Телефон:[phone]; фаю: (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, Для телеграмм; Москва, ГРАЧ Гед. [phone] Факс [phone]. УТВЕРЖДАЮ»

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

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

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

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