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

• Автор: Иванова, Галина Сергеевна
• Шифр специальности: 05.13.11
• Научная степень: Докторская
• Год защиты: 2007
• Место защиты: Москва
• Количество страниц: 416 с. : ил.

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

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

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

1.3. А 1ЛЛИЗ РОЦЕССА И РАЗРАБОТКА МНОГОУРОВНЕВОЙ СХЕМЫ РЕАЛИЗАЦИИ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ СТРУКТУРНОГО анализа и синтеза

1.4. Проблемы поэтапного описания и реализации алгоритмов

РЕШЕНИЯ ЗАДАЧ СТРУКТУРНОГО АНАЛИЗА И СИНТЕЗА НА Г РАФАХ

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

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

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

1.4.5.1 риведение алгоритмов к структурному виду

1.4.6. Разработка моделей алгоритма и данных.
ВЫВОДЫ ПО ГЛАВЕ
2. АНАЛИЗ АЛГОРИТМОВ И ДАННЫХ И ПОСТРОЕНИЕ ИХ
МОДЕЛЕЙ
2.1. Модели объектов задач структурного анализа и синтеза
2.2. Способы задания моделей объектов
2.3. Информационнологическая модель алгоритма.
2.4. Модели с труктурных конструкций, структурного алгоритма
и их свойства.
2.5. Модели базовых структур данных и их свойства.
2.6. Модели многоуровневых и комбинированных структур данных
д
Выводы НО ГЛАВЕ 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. Разделение потока управления в точке слияния, за которой следует оператор ветвления
3.5.0. Изменение последовательности ветвления потоков
управления Г .
3.5.7. Вынесение оператора изменения данных из ветвления или изменение данных до выхода из цикла 7.
3.5.8. Внесение оператора изменения данных в ветвление или проверка условия выхода из цикла до изменения данных
3.6. Виды НАРУШЕНИЯ СТРУКТУРНОСТИ И ИХ УСТРАНЕНИЕ С ИСПОЛЬЗОВАНИЕМ ЭЛЕМЕНТАРНЫХ СТРУКТУРИРУЮЩИХ ПРЕОБРАЗОВАНИЙ.
3.6.1. Условие выхода из цикла в одной из ветвей ветвления, непосредственно следующее за началом ветвления Н1.
3.6.2. Условие выхода из цикла в одной из ветвей ветвления, отделенное от начала ветвления вершиной изменения данных
3.6.3. Пересечение ветвлений вершина слияния непосредственно следует за вершиной ветвления ИЗ
3.6.4. ересечение ветвлений вершина ветвления отделена от вершины слияния 4.
3.6.5. Пересечение ветвления и цикла, являющееся следствием неверной последовательности вершин слияния
3.6.6. Пересечение ветвления и цикла наличие дополнительных
входе в в ци к л
3.6.7. Дополнительные выходы из цикла два выхода из цикла
подряд Н7.
3.6.8. Дополнительные выходы из цикла два выхода из цикла
не подряд 8.
3.6.9. Условие выхода из цикла в середине тела цикла Н9.
3.7. Разработка оригма структуризации.
Выводы ПО ГЛАВЕ 3.
4. МАТЕМАТИЧЕСКИЕ ОСНОВЫ И ЛИНГВИСТИЧЕСКИЕ СРЕДСТВА РАЗРАБОТКИ И АНАЛИЗА АЛГОРИТМОВ
4.1. Определение совокупности операций над графовыми моделями.
4.2. Определение совокупности абстракций и множества операций НАД ИМИ ДЛЯ ЯЗЫКА 1 ИСАИ ИЯ АЛГОРИТМА НА УРОВНЕ МНОЖЕСТВ.
4.3. Синтаксис языка формального описания алгоритмов в оперл дях над множествами и выбор способа построения его распознавателя .
4.4. Синтаксис и семантика языка формального описания алгоритмов в операциях над графами.
4.5. Автоматизация анализа вычислительной, временной и емкостной сложности алгоритма
4.6. Выбор оптимально о способа прбдставле ия графовой модели множествами
4.7. Синтез комбинированных структур данных для прбдставле ия ГРАФОВЫХ МОДЕЛЕЙ.
4.8. Синтез решающих правил для оптимизирующих преобразований алгоритма
4.9. Методика проектирования и анализа алгоритмов решения
ЗАДАЧ СТРУКТУРНОГО А I АЛ ИЗ А И СИНТЕЗА.
Выводы по главе 4.
5. РЕАЛИЗАЦИЯ И ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ СИСТЕМЫ РАЗРАБОТКИ АЛГОРИТМОВ.
5.1. Программное обеспечение системы разработки алгоритмов
5.2. Экспериментальное исследование приведения алгоритмов к структурному виду
5.3. РОВЕРКА РАБОТОСПОСОБНОСТИ И ОЦЕНКА КАЧЕСТВА ПРОГРАММ, ПОЛУЧЕННЫХ С ПОМОЩЬЮ СОЗДАННОЙ СИСТЕМЫ.
5.4. ИССЛЕДОВАНИЕ ЗАВИСИМОСТИ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ
АЛГ ОРИТМОВ ДЕКОМПОЗИЦИИ ОТ СТРУКТУР ДАННЫХ.
5.5. Исследование эффективности огп имизирующих
ПРЕОБРАЗОВАНИЙ.
ВЫВОДЫ ПО ГЛАВЕ 5.
СПИСОК ЛИТЕРАТУРЫ.
ПРИЛОЖЕНИЯ
ВВЕДЕНИЕ


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