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

• Автор: Бакулина, Мария Алексеевна
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Москва
• Количество страниц: 133 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ.
1 ИССЛЕДОВАНИЕ ПРОЦЕССА АЛГОРИТМИЗАЦИИ ЗАДАЧ СТРУКТУРНОГО СИНТЕЗА И ПОСТАНОВКА ЗАДАЧИ.

1.1 Анализ основных этапов процесса решения задачи структурного

синтеза

1.2 Постановка задачи разработки языка формального описания

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

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

1.4 Анализ вычислительной и емкостной сложности алгоритмов

Выводы.

2 РАЗРАБОТКА ЯЗЫКА ОПИСАНИЯ АЛГОРИТМОВ СТРУКТУРНОГО СИНТЕЗА И ТРАНСЛЯТОРА С НЕГО.

2.1 Абстракции объектов языка формального описания алгоритмов
решения задач структурного синтеза.
2.2 Анализ алгоритмов решения задач на графах и определение
совокупности операций над абстракциями, используемыми для их описания.
2.3 Определение синтаксиса и семантики конструкций языка
2.4 Выбор механизма способа трансляции
2.5 Преобразование контекстносвободной грамматики языка
формального описания.
3 РАЗРАБОТКА СРЕДСТВ ОЦЕНКИ И КЛАССИФИКАЦИЯ СПОСОБОВ СНИЖЕНИЯ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ АЛГОРИТМОВ
3.1 Оценка вычислительной сложности по описанию на языке и
разработка анализатора
3.2 Оценка временной сложности с учетом реализации множеств
3.3 Классификация способов снижения вычислительной сложности и
выработка рекомендаций по их применению.
4 ОПИСАНИЕ АВТОМАТИЗИРОВАННОЙ СИСТЕМЫ РАЗРАБОТКИ АЛГОРИТМОВ И ПРИМЕРЫ ЕЕ ИСПОЛЬЗОВАНИЯ.
4.1 Структура автоматизированной системы разработки алгоритмов.
4.2 Разработка транслятора.
4.3 Разработка макрогенератора описаний абстракций объектов.
4.4 Методика разработки алгоритмов с использованием средств
автоматизации
4.5 Пример последовательный алгоритм разрезания гиперграфа схемы.
4.6 Пример уравновешенная двоичная свертка без учета связности
Выводы.
ВЫВОДЫ.
СПИСОК ЛИТЕРАТУРЫ


Наличие языка формального описания алгоритмов позволило поставить также задачу оценки временной сложности программы, что дает возможность уточнить результаты. В работе выполнен анализ способов снижения вычислительной сложности алгоритмов, описанных в литературе, который показал, что эти способы ^ связаны с типом операции. В четвертой главе представлена архитектура универсальной системы разработки и анализа алгоритмов. Основными компонентами системы являются: специализированный текстовый редактор; генератор классов, реализующих структуры данных; транслятор с языка описаний алгоритмов на язык Ое1рЫ Райса1 ф анализатор вычислительной сложности; анализатор емкостной и временной сложности. Представлена методика работы пользователя с использованием предлагаемых средств автоматизации. Выполнена разработка последовательного алгоритма разрезания гиперграфа и алгоритма уравновешенной двоичной свертки. С развитием прикладных и фундаментальных наук комбинаторнооптимизационные задачи структурного синтеза ставятся во многих областях. В области компьютерных систем и сетей это задачи прокладки линий коммуникации, анализа пропускной способности сети, анализа и декомпозиции схем, анализа вычислительной сложности программ, компиляции, распределения памяти, структуризации, создания адаптивных сайтов и многие другие. В связи с этим ф растет интерес к задачам структурного синтеза в нашей и иностранной литературе. Только в последние пять лет появились десятки монографий и учебников, посвященных проблемам решения этих задач. Касьянов, Евстигнеев, Овчинников, Новиков, Асанов, Кормен, Ахо, Седжвик и многие другие наши и зарубежные ученые. Как правило, задачи структурного синтеза - это задачи большой размерности, программы решения которых сложны и даже при современной технике требуют существенных затрат памяти и машинного времени. Решение указанных задач невозможно без их формализации, в работах [4, 7, 8] убедительно показано, что можно избежать многих ошибок, уделяя должное внимание процессу разработки алгоритма. Причем совершенно очевидно, что научный подход в отличие от ® интуитивного целесообразно применять, прежде всего, к программам, работающим со сложными данными большой размерности. В [8] дается определение понятия алгоритма решения задач структурного синтеза и описание процесса ее решения, представляющего собой последовательность итераций. Содержательная постановка и анализ задачи. Выбор математического аппарата формализации задачи. В большинстве случаев, адекватным математическим представлением исходного описания объекта и результата проектирования задач структурного синтеза является графовая модель [7, 8, , , , , , ]. Графовые модели, как математическая абстракция, с требуемой полнотой и правильностью отображают компоненты исследуемых объектов, отношения между ними, их свойства и характеристики. Аппарат теории графов обеспечивает выполнение формальных преобразований модели исходного описания объекта в модель результата, позволяя строить эффективные алгоритмы, удобные для реализации на ЭВМ. Кроме того, аппарат теории графов широко известен и глубоко развит, определены операции на графах, сформулированы теоремы, леммы, описывающие основные свойства графовых моделей, что позволяет использовать при решении задач уже известные результаты, повышая, таким образом, эффективность разработки. Формальная постановка задачи и выбор/разработка метода ее решения. На данном этапе выполняется формализация процесса получения по модели объекта проектирования модели удовлетворяющего заданным ограничениям результата, для которого целевая функция принимает требуемые значения. Получение формальной постановки задачи упрощает выбор или разработку метода ее решения, в значительной степени влияющего на эффективность алгоритма [4, 7, 8]. В ряде случаев [4] выбрать конкретный метод решения задачи на данном этапе не удается и определяется несколько возможных, из которых по ходу разработки алгоритма осуществляется выбор. Создание алгоритмической модели процесса решения. По степени детализации и формализации можно выделить несколько уровней описания процесса решения задачи, к которым предъявляются разные требования.