Содержание к диссертации
Введение
1 Исследование процесса алгоритмизации задач структурного синтеза и постановка задачи 10
1.1 Анализ основных этапов процесса решения задачи структурного синтеза 10
1.2 Постановка задачи разработки языка формального описания алгоритмов решения задач структурного синтеза 15
1.3 Автоматическая генерация описаний структур данных 21
1.4 Анализ вычислительной и емкостной сложности алгоритмов 26
Выводы 31
2 Разработка языка описания алгоритмов структурного синтеза и транслятора с него 33
2.1 Абстракции объектов языка формального описания алгоритмов решения задач структурного синтеза , 33
2.2 Анализ алгоритмов решения задач на графах и определение совокупности операций над абстракциями, используемыми для их описания 35
2.3 Определение синтаксиса и семантики конструкций языка 37
2.4 Выбор механизма (способа) трансляции 54
2.5 Преобразование контекстно-свободной грамматики языка формального описания 57
Выводы . 72
3 Разработка средств оценки и классификация способов снижения вычислительной сложности алгоритмов 73
3.1 Оценка вычислительной сложности по описанию на языке и разработка анализатора 73
3.2 Оценка временной сложности с учетом реализации множеств 81
3.3 Классификация способов снижения вычислительной сложности и А выработка рекомендаций по их применению 88
Выводы 92
4 Описание автоматизированной системы разработки алгоритмов и примеры ее использования 94
4.1. Структура автоматизированной системы разработки алгоритмов 95
4.2 Разработка транслятора 99
4.3 Разработка макрогенератора описаний абстракций объектов 103
4.4 Методика разработки алгоритмов с использованием средств автоматизации 104
4.5 Пример - последовательный алгоритм разрезания гиперграфа схемы.». 108
4.6 Пример - уравновешенная двоичная свертка без учета связности 117
Выводы 124
Выводы 125
Список литературы
- Постановка задачи разработки языка формального описания алгоритмов решения задач структурного синтеза
- Анализ алгоритмов решения задач на графах и определение совокупности операций над абстракциями, используемыми для их описания
- Оценка временной сложности с учетом реализации множеств
- Разработка макрогенератора описаний абстракций объектов
Введение к работе
Актуальность. Задачи структурного синтеза решаются при разработке структуры практически любых объектов на всех этапах проектирования. К этому типу задач относятся, например, многие задачи проектирования ЭВМ, телекоммуникационных систем и сетей, а также задачи оптимизации транспортных потоков, причем количество подобных задач постоянно увеличивается, С развитием прикладных и фундаментальных наук задачи, связанные с исследованием и синтезом структур, ставятся, например, в таких далеких от техники областях, как химия и биология.
*
В большинстве случаев задачи структурного синтеза - это задачи большой размерности (более 50 тыс. элементов), кроме того, многие из них принадлежат к классу задач с экспоненциальной оценкой вычислительной сложности [7, 8, 9, 17, 19, 26, 27, 28], точное решение которых невозможно даже на современных ЭВМ по причине неприемлемых временных затрат. В настоящее время для решения таких Ч задач используют приближенные методы и алгоритмы, которые требуют различных вычислительных ресурсов и обеспечивают разную точность решения.
Решение задачи структурного синтеза - трудоемкий процесс, предполагающий исследование свойств исходного объекта и результата проектирования и построение адекватной математической модели, обычно графовой. По результатам исследования определяют последовательность операций преобразования модели исходного объекта в модель результата проектирования. Построив последовательность операций, разработчик должен выполнить анализ эффективности разработанного алгоритма на основании оценок вычислительной и емкостной сложностей.
При получении недостаточно эффективного алгоритма процесс
проектирования приходится повторять, пока не будет получен требуемый результат
- алгоритм, позволяющий за приемлемое время и при заданных ограничениях на
объем используемой оперативной памяти получить удовлетворительный по
Ф точности результат решения конкретной задачи структурного синтеза. После этого
*ь необходимо выбрать структуры данных для представления используемых моделей и
5 реализовать эти операции на выбранном универсальном языке программирования, что с учетом сложности реализации графовых моделей, также является процессом, требующим больших трудозатрат, как на написание программы, так и на тестирование и отладку последней.
Широкое распространение, многообразие постановок задач структурного синтеза и высокая трудоемкость разработки алгоритмов решения этих задач делают актуальной автоматизацию процесса разработки алгоритмов их решения. Это подтверждается увеличившимся интересом к разработке и исследованию алгоритмов решения задач структурного синтеза в отечественной и иностранной литературе [2, 7, 8,27,29,37,39,40].
*
Автоматизировать творческий процесс разработки моделей, метода решения задачи и формального описания алгоритма невозможно- Однако при получении и исследовании моделей и алгоритмов разработчик оперирует понятиями и терминами теории графов, теории множеств и математической логики. Создание на этой основе Ц специализированного языка описания алгоритмов и данных позволит автоматизировать разработку алгоритмов на этом уровне представления.
В процессе разработки языка необходимо определить и уточнить его синтаксис и семантику. Строгое формальное описание алгоритма на специализированном языке обеспечивает также возможность автоматизации процесса составления программы на универсальном языке. Следовательно, необходимо также разработать эффективный способ трансляции описания а алгоритма в программу на универсальном языке.
Вычислительная и емкостная сложность алгоритма существенно зависят от
используемых структур данных. Отсюда возникает проблема выбора представления
графовых моделей в виде структур данных. Целесообразно разрешить разработчику
описывать требуемые реализации, следовательно, необходимо решить задачу
автоматической генерации описаний структур данных на универсальном языке по
метаописанию на языке описания алгоритмов.
ф Поскольку после получения алгоритма необходимо выполнять оценку
* вычислительной и емкостной сложности полученных преобразований, на основе
которой может проводиться его доработка, актуальной является проблема создания методики автоматического получения оценок и средств ее реализации. Более того, наличие языка описания алгоритмов позволяет поставить задачу оценки не только вычислительной, но и временной сложности программы, что позволит уточнить результаты оценок.
На данный момент в рамках единой системы не существует программной поддержки указанных средств автоматизации процесса решения задач структурного синтеза- Создание подобной универсальной системы позволит существенно упростить разработку и анализ алгоритмов решения задач структурного синтеза, предоставляя разработчику алгоритмов возможность реализации, оценки и исследования отдельных методов и алгоритмов с учетом затрат памяти и времени на их выполнение.
Цель работы — создание средств автоматизации процесса решения задач структурного синтеза, предоставляющих возможность реализации и исследования разрабатываемых алгоритмов с точки зрения потребляемых ресурсов.
Для достижения указанной цели в работе поставлены и решены следующие задачи:
Анализ процесса разработки алгоритмов и определение комплекса средств автоматизации.
Определение синтаксиса и семантики языка формального описания алгоритмов и разработка транслятора с него.
Обеспечение автоматической генерации описаний выбранных структур данных и реализации операций над ними.
Анализ методов оценки вычислительной и емкостной сложности алгоритмов и разработка методики автоматического получения соответствующих оценок,
Создание программной системы разработки и анализа алгоритмов. Методы исследований. При решении задач были использованы: методы
теории графов, теории множеств, математической логики. Методика оценки вычислительной сложности базируется на методе Д-карт, ориентированном на
7 структурный подход в программировании. При разработке языка используются теория формальных языков и методы грамматического разбора. Научная новизна работы.
Определены этапы разработки алгоритмов решения задач структурного синтеза, подлежащие автоматизации.
В результате анализа алгоритмов решения широкого круга задач структурного синтеза выявлена совокупность операций преобразования математических моделей объектов.
Предложены синтаксис и семантика языка формального описания алгоритмов для раздела описаний данных и операторов,
Выбран эффективный способ разбора предложений языка, обеспечивающий в дальнейшем автоматическое получение оценок потребления ресурсов вычислительной машины.
Разработана методика автоматизированной оценки вычислительной сложности алгоритмов, что позволило получать количественный критерий для исследования качества полученных алгоритмов.
Предложена методика разработки алгоритмов решения задач структурного синтеза.
Практическая ценность работы. По результатам проведенных исследований создана система автоматизированной разработки алгоритмов, которая включает библиотеки шаблонов описаний классов абстракций, модули синтаксического и семантического анализаторов и ряд рабочих модулей, позволяющих выполнять ввод, модификацию текста алгоритма и структур данных, модуль анализатора вычислительной и емкостной сложности для получения профиля программы и соответствующих оценок, а также окно приложения для просмотра графиков этих оценок. Данная система позволяет выполнять разработку алгоритмов решения задач структурного синтеза и получать оценки потребления ресурсов вычислительной машины.
Апробация работы. Основные положения диссертационной работы обсуждались на Студенческой научной конференции «Информатика и системы
управления в XXI веке» (г. Москва 2003), Международной научно-технической конференции «Гражданская авиация на современном этапе развития науки, техники # и общества» (г. Москва 2003), Первой международной научно-технической конференции «Аэрокосмические технологии» (Москва-Реутов 2004).
Реализация и внедрение. Теоретические и практические результаты работы, полученные автором, нашли применение для решения задачи синтеза схемы "DACT* реляционной базы данных "УА(У* в Информационном центре Управления внутренних дел Восточного административного округа г. Москвы и анализа структуры предприятия ОАО «Гидрометприбор». Документы, подтверждающие внедрение, приведены в приложении.
Публикации. По результатам диссертационной работы автором опубликовано 7 работ.
Объем и структура диссертации* Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, приложения, занимающих ы 133 страницы текста, в том числе 20 рисунков и 21 таблиц на 53 страницах, список использованной литературы из 51 наименований на 5 страницах.
Содержание работы. Во введении обоснована актуальность темы диссертации, сформулированы основные задачи и научные результаты, дано краткое содержание глав.
В первой главе выполнен анализ процесса разработки алгоритмов решения задач структурного синтеза и выявлены задачи, которые необходимо решить при Л создании средств автоматизации. К ним относятся задачи разработки специализированного языка и транслятора с него, макрогенератора описаний структур данных, методики автоматизированного анализа вычислительной сложности и создания на базе этого автоматизированной системы разработки алгоритмов.
Во второй главе определен набор операций над абстракциями объектов и их
связь с базовыми конструкциями языка. Представлены окончательный синтаксис и
0 семантика языка формального описания, разработанные на базе анализа синтаксиса
t* и семантики псевдоязыков, используемых при описании алгоритмов решения задач
9 структурного синтеза в литературе различными авторами- В основном такие псевдоязыки представляют собой объединение Паскале-подобных конструкций с символами теории множеств, математической логики. Синтаксис языка был приведен к грамматике операторного предшествования, а соответствующий распознаватель реализует восходящий детерминированный анализ слева направо.
В третьей главе разработана методика автоматизированной оценки вычислительной сложности алгоритма. Определено, что профиль программы целесообразно строить на этапе трансляции, поскольку в процессе разбора получаются данные об элементарных операциях и количестве их повторений. Наличие языка формального описания алгоритмов позволило поставить также задачу оценки временной сложности программы, что дает возможность уточнить результаты. В работе выполнен анализ способов снижения вычислительной сложности алгоритмов, описанных в литературе, который показал, что эти способы связаны с типом операции- На основе сопоставления способов снижения сложностей группам операций алгоритмов разработана методика снижения вычислительной сложности, для применения которой система предлагает специальную информацию.
В четвертой главе представлена архитектура универсальной системы разработки и анализа алгоритмов. Основными компонентами системы являются: специализированный текстовый редактор; генератор классов, реализующих структуры данных; транслятор с языка описаний алгоритмов на язык Delphi Pascal; анализатор вычислительной сложности; анализатор емкостной и временной сложности. Представлена методика работы пользователя с использованием предлагаемых средств автоматизации. Выполнена разработка последовательного алгоритма разрезания гиперграфа и алгоритма уравновешенной двоичной свертки. Выбор этих алгоритмов обусловлен вниманием, которое уделяется им в литературе и соответствующей степени их проработки, а также возможностью оценить эффективность работы системы в случае их разработки с использованием предлагаемых средств.
Постановка задачи разработки языка формального описания алгоритмов решения задач структурного синтеза
Автоматизация разработки и анализа алгоритмов подразумевает наличие его формального описания. В настоящее время для формализованного представления алгоритма используются псевдоязыки, близкие по синтаксическим конструкциям к языкам программирования, подобным Алголу, Паскалю, Си [1, 4, 7]. С точки зрения степени формализации и наличия дополнительных операций, применяемых в псевдоязыках, по сравнению с указанными универсальными языками высокого уровня можно выделить следующие (РисЛ.2): - псевдоязыки., в которых допускаются неформальные описания действий и ограниченно применяются операции над множествами [1, 4, 7]; - псевдоязыки без неформальных описаний действий с ограниченным использованием операций над множествами и с применением формально описанных операций над стеками и очередями [30]; - псевдоязыки, в которых не допускаются неформальные описания, более широко применяются операции над множествами и математической логики и ограниченно - операции над графами [29]; - псевдоязык, являющийся композицией конструкций языка Pascal и операторов над абстрактными типами данных; в качестве таких операторов выступают имена процедур, реализующих па языке Pascal операции, например над множествами или операции просмотра структуры графа [2]; - нотация, построенная на базе операций над множествами, операций математической логики (в том числе исчисления предикатов) и операций функциональных отношений, определенных на множествах, представляюших граф, Нотация не использует неформальных описаний действий и переходов [8]. Ограниченно операции над множествами
С Псевдоязык описания алгоритмов призван обеспечить разработчику возможность оперировать понятиями и терминами теории графов, теории множеств и математической логики, т.е. непосредственно базовыми понятиями моделей предметной области комбинаторно-оптимизационных задам структурного синтеза. Это дает возможность представить алгоритм в достаточно сжатой и более наглядной по сравнению с неформальным описанием форме, что облегчает его понимание и анализ. Такое представление позволяет также упростить неавтоматизированный переход от алгоритма к его записи на выбранном языке программирования, т.е. непосредственно написание программы. Подобных формальных языков до настоящего времени не существовало. Наиболее близкими аналогами являются пакет MaphCad, который не позволяет создавать программы, и библиотеки функций, предлагаемые различными авторами и реализующие операции над множествами» но не обеспечивающие достаточной степени наглядности описаний,
К основным задачам, решаемым на этапе разработки такого специализированного языка формального описания, относятся: построение спецификации и обоснование синтаксиса языка, а также определение его семантики.
Поскольку, алгоритм решения задач структурного синтеза представляет собой набор операций, применяемых к определенным структурам данных в заданной последовательности, разрабатываемый язык должен принадлежать к группе языков, поддерживающих процедурную декомпозицию.
Для реализации языка на некоторой вычислительной машине необходимо осуществить выбор эффективного метода грамматического разбора и разработать программу-транслятор, переводящую программу на специализированном языке в функционально-эквивалентную программу на выбранном языке, поддерживающем объектно-ориентированное программирование. Возможны два варианта перевода с такого специализированного языка: на машинный язык или промежуточный язык. Использование объектно-ориентированного промежуточного языка позволит существенно упростить разработку транслятора, поскольку операции специализированного языка, выполняемые над абстракциями объектов, ставятся в соответствие методам классов объектов или подпрограммам библиотек универсального языка высокого уровня. Кроме того, используя компилятор такого универсального языка и получив впоследствии программу-результат на ассемблере, пользователь получает возможность выполнить многоуровневую оптимизацию программы. В качестве промежуточного языка был выбран Delphi Pascal, что обусловлено достаточной мощностью и хорошими технологическими характеристиками языка.
Под языком программирования [31] понимают систему обозначений, позволяющую описывать алгоритмы и структуры данных предметной области задачи. Известно, что различия между языками программирования, заключаются не в том, что решение каких-то задач возможно при использовании только определенных языков, а сводятся к тому, насколько эффективно могут быть решены те или иные задачи на разных языках. Язык формального описания алгоритмов на графах должен быть ориентирован на разработку и реализацию алгоритмов решения задач структурного синтеза.
Анализ алгоритмов решения задач на графах и определение совокупности операций над абстракциями, используемыми для их описания
Практическая реализация алгоритма решения задачи структурного синтеза в виде программы на специализированном языке связана с некоторой модификацией его исходного формального описания. Для записи раздела операторов программы на специализированном языке необходимо определить набор операций преобразования исходной графовой модели в модель результата и указать их связь с базовыми конструкциями языка, а в случае необходимости и соглашения по их обозначению. Для выявления совокупности необходимых операций был рассмотрен широкий круг комбинаторно-оптимизационных задач структурного синтеза [1, 2, 3, 4, 5, 6 7, 8, 15, 16,17,23,29,48].
Как показал анализ решение этих задач при проектировании ЭВМ и систем заключается в преобразовании графа, являющегося моделью исходного описания объекта проектирования, в граф результата, либо в получении последнего па основе исходной модели. Преобразование исходной модели и/или генерация графа результата по ней предполагают выполнение следующих основных операций: разбиение множества вершин и/или ребер графа на подмножества (задача декомпозиции/композиции); установление однозначного или взаимно однозначного соответствия между элементами множеств (задачи идентификации, назначения, позиционирования); определение подмножеств, которые обладают заданными свойствами и имеют требуемые характеристики (задачи коммутации, исследования структур графов и др.).
Все перечисленные операции можно реализовать посредством базовых операций над множествами, приведенных в таблице 3, Данная совокупность операций преобразования математических моделей объектов позволяет формализовать выбранный метод решения задачи в виде формального описания алгоритма. Термины и обозначения символов операций данной группы в специализированном языке формального описания были выбраны так, чтобы соответствовать применяемым в теории множеств и математической логике. В качестве исходных данных для написания программы рассматриваются формальное описание алгоритма и выбранные разработчиком абстракции объектов данных, используемые для отображения математических моделей объектов, что полностью соответствует структуре программы, состоящей из разделов описаний и операторов. Однако на этапе представления графовых моделей исходного объекта и результата проектирования для уточнения связей между отдельными элементами используют конкретные структуры данных, отображающие выбранные абстракции в память ЭВМ
В [2, 3, 5, 7, 23, 48] описано большинство структур данных, которые известны и теоретически исследованы на данный момент. Для физического уровня реализации характерно четкое разделение базовых структур данных на векторные (последовательное представление) и списковые (связанное). Такие схемы отображения данных в памяти имеют свои достоинства и недостатки, которые по-щ разному проявляются в алгоритмах решения конкретных задач. При этом способы реализации операций, определенные на этих структурах, будут существенно отличаться- От выбранной схемы представления графовой модели в значительной мере зависит вычислительная и емкостная сложности алгоритма, характеризующие целесообразность выбора структур данных. Очевидно, что множество операций» выполняемых над объектом в алгоритме решения задачи, определяет выбор ее абстрактного типа и физической реализации,
Оценка временной сложности с учетом реализации множеств
Точность получаемой оценки потребления ресурсов вычислители зависит от глубины аналюа операций, выполняемых над абстракциями также степени детализации и іфорабщш алгоритма решения ззд описание алгоритма имеет более высокую степень деталюа юя&чателя Ері рам мы, задачу но ъектов, а рмальное % шзздии достигаете ца этапе реализации алгоритма средствами специализированного ИЬШІ, когда на и -ьытсе формального ОЇШСШШЇ определена последовательность элементарных операций пршбрнжшания исходных объектов и условии в зявмет мости от которых пну вышхчнзштем.
Предельная оценка вычислительной сложности представляет собой оценку с точностью до константы. Основанием для использования подобного рода оценок является тот факт, что большинство задач структурного синтеза имеют большую размерность входа. Однако при небольшой размерности входа члены более низкого порядка по сравнению с общей сложностью могут оказывать существенное влияние на результирующую оценку. И, таким образом, при реализации алгоритмов, выгодных с точки зрения оценки вычислительной сложности, их реальные затраты времени вычислительной машины могут оказаться значительными. В этом случае для исследования и анализа алгоритма решения задач структурного синтеза целесообразно использовать оценки временной сложности. Как отмечалось ранее, автоматическое получение таких оценок основывается на предварительном подсчете времени выполнения базовых операций над абстракциями объектов.
Оценка временной сложности операций над множествами расчитывается в два этапа,
1, Выполняется компиляция метода класса или подпрограммы библиотеки языка высокого уровня Delphi Pascal реализующих базовую операцию на языке формального описания, в последовательность машинных команд.
2, По полученному на предыдущем шаге исполняемому ассемблерному коду и таблицам времен выполнения машинных команд микропроцессора оценивается количество тактов, требуемых для выполнения операции над множествами (таблица 13).
Расчет таких оценок был выполен вручную с использованием СРСЛокна среды разработки Delphi Pascal, предоставляющего возможность обработки команд S3 ассемблера, получаемых на этапе отладки путем дизассемблирования машинного кода библиотеки поддержки абстрактных типов данных. Оценки получены для ф процессора 80586, с использованием таблицы времен выполнения команд ассемблера [38], причем во всех случаях для таких операторов даны минимально возможные скорости.
В таблице 15 представлены оценки вычислительной и временной сложностей, полученные для базовых операций, выполняемых над абстракциями объектов с учетом их реализации в памяти вычислительной машины.
Автоматическая оценка временной сложности алгоритма выполняется по результатам трансляции программы на языке формального описания с использованием профиля программы G, представляющего собой набор счетчиков частоты повторения всех операций а), выполняемых над абстракциями объектов. По матрице оценок временной сложности выполнения операторов (7(таблица 15), учитывающих способ отображения объекта в память вычислительной машины, а также по профилю оценивается количество тактов, требуемых для работы алгоритма [50]: - для /-ой структуры данных: 0і =С[ТаЬЩ.81_Туре]хА\ 3-6) - для алгоритма в целом: п _ Aw (3 7) /=1 где C [Table[f]StJType] - вектор, задающий оценки временной сложности выполнения совокупности базовых операций для структуры данных, имеющей St_Type отображение в памяти вычислительной машины.
Из таблицы 16 видно, что получаемая в данном случае оценка вычислительной сложности - это оценка сверху, т.е. «в худшем» случае, если исходные данные являются худшими из возможных. Применение подобного рода оценок является вполне оправданным, поскольку данная оценка - это оценка с некоторым запасом,
Многие из задач структурного синтеза относятся к классу JVP-полных [5, 7, 8, 17, 18, 19, 26, 39]. Поэтому особую роль приобретает анализ алгоритмов с точки зрения возможности снижения их вычислительной сложности при допустимой емкостной.
Анализ показал, что операции алгоритма решения задач структурного синтеза можно разбить на следующие группы.
1. Операции преобразования модели. Наиболее часто встречающиеся в алгоритмах операции над графами [8, 29]: удаление вершины xtsX; удаление ребраиує U\ добавление вершины хг- и инцидентного ей ребра и/, добавление вершины xs в гиперграф; добавление ребра Uj в гиперграф; стягивание вершин и в вершину Xjfi стягивание ребра ы еС/, инцидентного вершинам xt и х/, подразбиение ребра UjtU, инцидентного вершинам xt и xj
2. Операции определения множества компонент модели (граф исходного или текущего состояния объекта), формирующих возможное множество решений на данном шаге (например, определение на данном шаге преобразования множества вершин, инцидентных ребру и/. ritj=XjCiX).
3 Операции вычисления критериальных оценок (например, для последовательного алгоритма разрезания гиперграфа схемы - число внешних выводов после включения вершины xt определяется, как 5О=50 ДУ/-ДЇ7 ).
4. Операции определения допустимости преобразования модели и операции определения необходимости изменения значения критериальных оценок (например, в алгоритме Прима на каждом шаге к построенному дереву присоединяется ребро минимального веса для которого усв=0).
5. Операции выбора альтернативы, т.е. компоненты модели графа, определяющей вершину дерева решения (например, для алгоритма уравновешенной ДВОИЧНОЙ СВерТКИ ЭЛемеНТ Дерева СВерКИ формируется ИЗ ВерШИН Xk и хг по критерию з{хь9 xr)=max{SijeS}).
При разработке формального описания алгоритмов решения задач структурного синтеза с целью повышения эффективности алгоритма серьезное внимание следует уделить выбору метода решения задачи, определяющему способ преобразования исходной графовой модели, расчету значений критериальных оценок и выбору способа представления графовых моделей. Реализация подобного рода рекомендаций в виде того или иного приема снижения вычислительной сложности зависит от метода решения задачи и характеристик исходного графа. В литературе встречаются следующие способы снижения вычислительной k сложности алгоритмов [1, 4, 8]:
Разработка макрогенератора описаний абстракций объектов
Основные атрибуты абстрактных типов определены в 2,3, программисту в данном случае предоставляется возможность работы с абстракциями объектов на основе списка определенных для такого класса операций, посредством которых можно манипулировать объектами. Все, что требуется знать пользователю при использовании абстрактного типа - это его спецификация; детали реализации скрыты (инкапсулированы), чтобы не отвлекать пользователя от разработки алгоритма.
Для поддержания абстракции данных при реализации была использована объектно-ориентированная модель программирования. Это позволило строить сложные объекты данных, как расширения более простых, используя преимущества этой языковой модели, такие как наследование, полиморфизм, наполнение, композиция. Абстрактные структуры данных, отличающиеся типами полей, включенными в структуру, моделируются шаблоном класса, определяющим правила построения класса. Таким образом, для поддержания абстракций реализованы шаблоны вектора, множества, кортежа и т.д.
На этапе макрогенерации (Рис.4.7) формируется описание класса на основе общего определения базового класса абстракции (шаблона) с учетом заданных атрибутов, описывающих компоненты структуры данных. При этом, используя ф определение общего типа и циклически подставляя в него конкретные значения параметров (тип и имя компонента), генерируется объявление класса и объекта данного типа. Результатом работы макрогенератора является модуль, содержащий описание каждой абстракции, заданной разработчиком алгоритма, что является не достаточно эффективным, поскольку эквивалентный абстракции класс формируется для каждого объявления объекта. Однако такая реализация поддержки абстракций предоставляет возможность обращения к полям класса по именам соответствующих # компонентов, что упрощает программу, являющуюся результатом трансляции на і универсальном языке. Переопределение типа в процессе выполнения невозможно, поэтому все операции по конкретизации типа компонента выполняются на этапе трансляции.
Последовательность этапов процесса разработки алгоритмов решения задач структурного синтеза представлена в 1Л, В соответствии с этой схемой пользователь начинает работу с системой после получения формального описания алгоритма.
Работа включает следующие этапы:
1. Используя текстовый редактор универсальной системы разработки алгоритмов, пользователь осуществляет кодирование текста программы, используя общепринятую математическую символику теории множеств, математической логики и теории графов. На данном этапе программа рассматривается как следствие эквивалентных преобразований последовательности операций, выполняемых в алгоритме над абстракциями объектов, в конструкции специализированного языка формального описания. А поскольку каждая абстракция объекта или переменная, встречаемая в программе, должна быть предварительно описана, пользователь первоначально осуществляет ввод или редактирование уже имеющегося раздела описаний. Такое предварительное описание является достаточно строгим, что повышает надежность разрабатываемой программы. Затем пользователь выполняет кодирование раздела операторов, фактически представляющего собой блок исполняемых инструкций.
2. После подготовки текста программы разработчик алгоритмов переходит к этапу отладки и коррекции возможных ошибок. Если в программе на этапе разбора не обнаружено лексических, синтаксических и семантических ошибок, то выдается сообщение об успешном завершении работы. В противном случае, если распознаватель обнаружил ошибку, он прекращает дальнейшие действия и анализирует диагностическое сообщение с информацией о причинах ошибки и указанием номера строки, при анализе которой она была обнаружена. Такая организация позволяет эффективно выполнить отладку программы и локализовать в ней возможные ошибки, добившись, таким образом, ее правильной работы.
3. После того, как получена правильная с точки зрения разбора программа, выполняется оценка вычислительной сложности, как функции от размерности входа, и расчет матрицы повторяемости операций над абстракциями объектов. Если полученные оценки вычислительной сложности алгоритма неприемлемы, пользователь должен выполнить анализ программы с использованием рекомендаций, приведенных в 3.4 и попытаться повысить эффективность алгоритма. Таким образом, при недопустимых значениях оценки выполняется возврат; в случае возможности модификации алгоритма - на этап реализации с внесением соответствующих изменений, в противном случае - на этап выбора или разработки ф метода решения задачи структурного синтеза,
4- На основании полученных на предыдущем шаге данных о повторяемости операций выполняется исследование возможных вариантов отображения структур данных в память вычислительной машины, в результате которого разработчик алгоритмов выбирает соответствующее представление для физического уровня реализации,
