Другие журналы
|
научное издание МГТУ им. Н.Э. БауманаНАУКА и ОБРАЗОВАНИЕИздатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211. ISSN 1994-0408
Абстракции и базовые операции специализированного языка описания алгоритмов решения задач структурного анализа и синтеза
# 12, декабрь 2013 DOI: 10.7463/1213.0656686
Файл статьи:
Ivanova_P.pdf
(309.92Кб)
УДК 004.3 +519.1 Россия, МГТУ им. Н.Э. Баумана
ВведениеБольшая размерность и экспоненциальная вычислительная сложность решения большинства задач структурного анализа и синтеза предполагает, что программную реализацию этих алгоритмов необходимо осуществлять с использованием всех возможных способов сокращения времени их выполнения. Это требует глубокой проработки алгоритмов и текстов проектируемых программ. Количество работ, в которых разрабатываются и анализируются новые алгоритмы решения новых и старых задач рассматриваемого класса, последние 25 лет не уменьшается. Среди последних публикаций на эту тему следует назвать работы [1-7]. Однако по-прежнему разработка, исследование и оптимизация, как самих алгоритмов решения задач структурного анализа и синтеза, так и написанных по ним программ – сложная и трудоемкая задача. 1 Обоснование необходимости разработки специализированного языкаПрограммы решения задач структурного анализа и синтеза можно реализовывать на различных языках. Как правило, для этого используют универсальные языки высокого уровня, предполагающие процедурную или объектную декомпозицию. В таких языках операции над графами реализуются операциями над сложными структурами данных, такими как массивы, матрицы, списки. Однако размеры и сложность исходных текстов программ указанного класса при подобном уровне детализации таковы, что не позволяют разработчику сосредоточиться на поиске более эффективных с точки зрения вычислительной сложности алгоритмов и способов уменьшения времени выполнения реализующих их программ. Использование же языков, основанных на иных принципах декомпозиции, сопряжено с дополнительными трудностями. Так, например, при реализации программы, выполняющей операции над графами, на языке функционального программирования Haskel [8], разработчик должен абстрагироваться от выполняемых над объектами задачи проектных операций и оперировать математическими абстракциями, напрямую не связанными с абстракциями, которые представляют объекты решаемых задач, т.е. графами. При этом также сложно концентрироваться на снижении времени выполнения программы. Для сокращения сроков разработки и улучшения качества программ решений задач структурного анализа и синтеза на универсальных языках неоднократно предлагались и библиотеки подпрограмм, реализующие основные алгоритмы на графах, и объектные библиотеки для представления, изображения графов и реализации некоторых операций и алгоритмов над ними. Наибольший интерес из известных библиотек представляют: библиотека LEDA (Library of Efficient Data types and Algorithms) [9], разработанная в Институте Информатики Макса Планка (ФРГ), и библиотека GTL (Graph Template Library), созданная в Университете Паскаля (Франция) [10]. Однако на практике использование указанных и им подобных библиотек ограничено, поскольку они рассчитаны в основном на обыкновенные графы (не учитывают мульти-, гипер- и ультраграфов), и потому используют, как основное, представление графов через отношение смежности вершин. В то же время большинство разработчиков алгоритмов решения задач структурного анализа и синтеза в своих работах используют псевдоязыки. Как правило, нотация этих псевдоязыков представляет собой комбинацию математической записи операций над множествами и Паскале-подобных управляющих конструкций [11-13]. Указанные нотации обеспечивают компактную запись сложных алгоритмов, понятны разработчикам алгоритмов и позволяют сосредоточиться на оптимизации последних. В связи с вышесказанным целесообразным является создание специализированного языка с понятным разработчикам алгоритмов синтаксисом. Такой язык должен позволить: · использовать для представления моделей структур не только отношение смежности вершина-вершина, но и отношение инцидентности вершина-ребро и/или ребро-вершина, а потому обеспечит преобразование не только графов, но и гипер- и ультраграфов; · описывать алгоритмы в терминах абстракций, используемых при решении задач структурного анализа и синтеза математических моделей, что в десятки раз сократит объем кода исходной программы и время ее разработки, обеспечивая возможность быстрой реализации и сравнения нескольких программ для выбора варианта с лучшими временными характеристиками. Создание нового специализированного языка с традиционной схемой компиляции «исходный код на разрабатываемом языке – объектный код на машинном языке», особенно с учетом требования максимально возможной оптимизации кода – сложная задача, решение которой потребует много сил и времени. Однако трудоемкость разработки компилятора можно снизить на несколько порядков, если выполнять трансляцию не в машинный код, а на один из существующих объектных универсальных языков программирования высокого уровня, компилятор которого уже реализует известные способы оптимизации получаемого машинного кода. Тогда схема преобразования будет выглядеть так: «исходный код на разрабатываемом языке – исходный код на универсальном языке программирования – объектный код на машинном языке». Анализ уже существующих алгоритмов решения задач структурного анализа и синтеза, показывает, что помимо увеличения степени наглядности программы, а также ускорения ее разработки, специализированные язык должен обеспечивать: · выбор представления графовой модели (простые и взвешенные матрицы смежности, матрицы инцидентности, простые и взвешенные отображения по соответствующим отношениям и т.д.), поскольку для различных задач и размерностей исследуемых структур применяют различные варианты представлений; · замену структур данных для хранения представлений графов без изменения текста программы, что позволит выбрать вариант, обеспечивающий минимальное время выполнения программы [14]; · автоматическое или автоматизированное применение оптимизирующих преобразований уровня операций над множествами, в том числе указанных в [15]. Кроме того следует создать средства автоматической оценки вычислительной и емкостной сложности программы по ее тексту на специализированном языке и обеспечить наглядное сравнение временных и емкостных характеристик разных программ, решающих одну и ту же задачу. 2 Выявление базовых абстракций языка описания алгоритмов решения задач структурного анализа и синтезаК первоочередным задачам, решаемым при разработке формального языка программирования, относят построение спецификации и обоснование синтаксиса языка, а также определение его семантики. И синтаксис и семантика языка при этом должны базироваться на основных абстракциях языка и совокупности операций над ними. Анализ алгоритмов решения задач структурного анализа и синтеза [1-7, 11-13] показывает, что основной абстракцией языка должно служить «множество». Данная абстракция в рассматриваемой предметной области широко используется для представления графовых моделей структур: ориентированных и неориентированных графов, мультиграфов, гиперграфов и ультраграфов. Соответственно почти все преобразования графовых моделей реализуются как преобразование соответствующих множеств вершин и ребер и/или их отображений. Поскольку разрабатываемый язык описания алгоритмов является специализированным и предназначен для решения задач структурного анализа и синтеза, для множеств вершин и ребер всегда существуют универсумы, т.е. все возможные элементы этих множеств известны и их количество ограничено. Элементом множества в этом случае является число (номер узла, вершины, дуги или ребра), соответствующее номеру описания этого элемента в универсуме. Помимо множеств совокупность абстракций, используемых для представления графовых моделей, должна включать [16]: мультимножества – для представления отображений «вершины-вершины» мультиграфов, а также гипер- и ультраграфов с повторением вершин в ребре, кортежи – для задания ребер с отношением порядка в ориентированном гиперграфе и ультраграфе, а также путей и цепей, вектора – для хранения весов элементов графовых моделей и матрицы – для задания матриц смежности и инцидентности. Причем в отличие от принятого в программировании представления перечисленных выше абстракций, как структурных типов данных, в данном случае абстракции целесообразно рассматривать, как базовые типы, поскольку это позволит организовать их эффективную реализацию [14]. Остальные используемые при описании алгоритмов абстракции, такие как множество множеств, вектор векторов и т. п., будем рассматривать как сложные, т.е. построенные из базовых. Это позволит применять для их обработки те же операции, что и для базовых абстракций, но с учетом того, что элементами сложных абстракций являются другие абстракции. Следует также иметь в виду, что элементы любой поддерживаемой на данном уровне абстракции в конкретной задаче могут иметь один или более весов различных типов (целые, вещественные и булевские). Для представления базовых абстракций языка, включающих элементарные компоненты, такие как элементы множества, в программе должен использоваться определяемый программистом тип данных. При описании этого типа должны быть заданы следующие атрибуты. 1. Количество компонентов, которое определяет размерность входа задачи и используется при выделении необходимой памяти и на этапе анализа для получения оценок эффективности алгоритма. 2. Тип каждого компонента, определяющий объем памяти, который отводится под компонент, и множество возможных операций над ним. 3. Имена, используемые для доступа к конкретным компонентам. 4. Для всех абстракций кроме универсума следует также указывать отношение к другим абстракциям, что позволит проверять совместимость типов для выполнения операций над ними. Для универсума эта информация неактуальна, поскольку физически универсум – это последовательность целых чисел, которая непосредственно в программе, как правило, не обрабатывается. Однако отношение к одному универсуму, например универсуму вершин – позволит проверять корректность выполнения над множествами операции объединения, пересечения и т.п. Синтаксис представления абстракции, включающий указанные атрибуты, следует строить с учетом принятого в математике описания тех же или аналогичных абстракций. Это позволит сделать сложные конструкции описаний более понятными и компактными. Так универсум предлагается описывать конструкцией вида: а множество – конструкцией вида: Описание конструкций в БНФ при этом выглядит следующим образом: Для каждой абстракции необходимо определить множество элементарных и сложных операций. Элементарные операции должны быть реализованы в языке непосредственно, а сложные – через элементарные (возможно – в виде подпрограмм). 3 Определение совокупности операций над абстракциями языка решения задач структурного анализа и синтеза3.1 Математические операцииИз совокупности операций на множествах, определенных в математике, в алгоритмах рассматриваемой предметной области используются: · проверка вхождения элемента во множество; · определение мощности множества; · проверка эквивалентности (и не эквивалентности) двух множеств; · проверка вхождения (строгого и нестрогого) одного множества в другое; · пересечение множеств; · объединение множеств (объединение множества и элемента); · конкатенация множеств (конкатенация множества и элемента); · дополнение одного множества до другого (дополнение множества до элемента); · симметрическая разность множеств; · абсолютное дополнение множества до универсума. Операции над мультимножествами в математике встречаются существенно реже, но обычно предполагают, что операции над множествами применимы к мультимножествам. Однако, элементы мультимножества, помимо n-арного отношения вхождения Rn, связаны еще и n-арным отношением кратности Qn. Следовательно, помимо множественных операций, над мультимножествами в языке должны быть определены специфические операции, связанные с отношением кратности: · определение базового множества мультимножества; · определение количества повторений элемента мультимножества. Кортеж в математике определяют как «слово над множеством», т.е. как последовательность или строку, состоящую из элементов множества. Помимо того, что элементы кортежа могут повторяться, как в мультимножествах, они по определению упорядочены, т.е. на них дополнительно наложено отношение порядка или бинарное отношение следования. Соответственно для кортежей должны быть введены операции определения номера элемента в кортеже, замены элемента с указанным номером, добавления (вставки) элемента в заданное место, удаления элемента с заданного места со сдвигом остальных элементов, а также описанные выше операции, связанные с реализующими абстракциями. Операции пересечения, объединения, дополнения, симметрической разности, абсолютного дополнения до универсума, проверки эквивалентности (неэквивалентности), проверки вхождения (строгого и нестрогого) определены для пар множеств (мультимножеств) и, соответственно, их целесообразно рассматривать как сложные, т. е. представимые через элементарные операции над множествами. Эти операции широко используются при описании операций над графовыми моделями, а потому они должны быть определены в языке в виде подпрограмм. В связи с тем, что в программах решения задач структурного анализа и синтеза вектора и матрицы используют в основном для хранения весов вершин и ребер, специфические операции над ними, как правило, не выполняют. Таким образом необходимость реализовывать, например умножение матриц и векторов, отсутствует. 3.2 Операции, связанные с реализацией абстракцийОсновной набор операций над множествами, мультимножествами и кортежами в математике разрабатывался для формулирования условий, а не действий, поэтому для языка описания алгоритмов этих операций недостаточно. Помимо математических операций над указанными абстракциями в языке необходимо также иметь операции, связанные с реализацией этих абстракций в памяти, при которой на элементы множеств и мультимножеств неявно накладывается отношение порядка. Так при представлении линейными структурами данных, элементы множественных абстракций (множества, мультимножества, кортежи) доступны в порядке добавления элементов к абстракции (при использовании стека – обратном порядку добавления элементов). При представлении множественных абстракций характеристическими векторами порядок элементов определяется последовательностью их задания в универсуме. При представлении деревьями – реализованным алгоритмом просмотра вершин дерева (обычно «слева направо»). Необходимость описания действий, проявляется, например, в том, что часто встречающаяся операция поиска элемента с определенными свойствами не может быть заменена операцией проверки принадлежности, потому что результатом операции проверки принадлежности является значение «истина» или «ложь», а результатом поиска элемента должен быть его номер (или адрес) в памяти, который необходим для выполнения дальнейшей обработки этого элемента. Аналогично операция сортировки элементов меняет порядок их просмотра, связанный с физическим размещением этих элементов в памяти. Заменить операцию сортировки описанием того, что элементы множества (мультимножества) должны быть упорядочены также невозможно. Фактически перечисленные выше операции при описании алгоритма выполняются не над множествами или мультимножествами и их элементами, а над абстракциями, реализующими эти понятия в памяти ЭВМ. Соответственно, помимо обычно употребляемых операций над множествами и мультимножествами, необходимо предусмотреть операции чтения и записи элементов по номеру в неявно заданном порядке просмотра, операции поиска заданного элемента по значению, поиска максимального или минимального элемента, сортировки множеств и мультимножеств, а также другие операции, подразумевающие действия с конкретные элементами. Кроме того, необходимо определить операции для взвешенных множественных абстракций, например, операции определения веса конкретного (минимального, максимального или заданного) элемента множества и сортировки множеств в соответствии с указанным весом. Вектора при решении задач структурного анализа и синтеза в отличие от множеств, мультимножеств и кортежей могут содержать не номера элементов графов в соответствующих универсумах, а их веса различных типов или номера и веса одновременно. Элементы вектора находятся только в отношении порядка R, в соответствии с которым каждому из них сопоставлен номер (индекс). Кроме основной операции обращения по номеру для векторов должны быть определены операции поиска элемента с заданными свойствами (максимально, минимального и с заданным значением) и поиска весов соответствующих элементов. Именно наличие указанных операций согласно теории языков программирования позволит говорить о наличии абстракции вектор в языке. Операции вставки и удаления элементов с указанием места обрабатываемого элемента для векторов предусматривать не будем, поскольку при необходимости сопоставлять по номеру элементы множеств, мультимножеств, кортежей и их веса в векторе целесообразно использовать взвешенное множество (мультимножество, кортеж). Элементы матриц, также как и элементы векторов могут хранить номера элементов или веса, а также то и другое вместе. Над ними определены два отношения порядка элементов в строке Ri и в столбце Rj. Поэтому для них также должны быть определены операции обращения по соответствующим номерам, поиска элемента с заданными свойствами (максимально, минимального и с конкретным значением), а также поиска весов указанных элементов. К элементарным операциям модификации для множеств, мультимножеств и кортежей из определенных в теории множеств относятся операции конкатенации и дополнения для случая, когда второе множество состоит из одного элемента, которые осуществляют операции добавления элемента (в конец – для кортежа) и удаления элемента по значению. В эту же группу включим операции записи элемента и веса элемента по номеру. Для множества и мультимножества этих операций достаточно. Для кортежей, элементы которых упорядочены, в качестве элементарных также необходимы операции вставки элемента в указанное место и удаления элемента со сдвигом оставшихся на его место, что обеспечит необходимый порядок элементов при модификации этой структуры. Вектор и матрицу в отличие от кортежа будем считать абстракциями статическими, структура которых в процессе обработки меняться не может, что соответствует обычному использованию указанных абстракций. Следовательно, для них определены только операции записи элемента и веса по номеру. Множество операций модификации для абстракций представлено в таблице 1. Таблица 1 - Операции модификации, определенные для базовых абстракций
К элементарным операциям просмотра соответственно относятся операции: · проверки вхождения элемента во множество (базовое множество – для мультимножеств и кортежей); · определения множества элементов, совпадающих с заданным – для мультимножества и кортежа; · определение следующего и предыдущего элементов – в кортеже (см. таблицу 2). Таблица 2 - Операции просмотра, определенные для множественных абстракций
К операциям определения элементарных характеристик отнесем операции: · определения мощности множества (базового множества для мультимножества и кортежа), длины кортежа (мультимножества); · количества вхождения элемента в мультимножество; · определения номера элемента по его значению, значения по номеру и веса по номеру – для всех абстракций (см. таблицу 3) Таблица 3 - Операции определения элементарных характеристик абстракций уровня множеств
* – для базового множества; ** – ближайшего по порядку просмотра; *** – в неявной последовательности элементов; **** – для обращения к элементу необходимы два номера. Таким образом, совокупность элементарных операций над множествами, мультимножествами и кортежами включает 15 операций. ЗаключениеНа основании выполненных исследований можно утверждать, что целесообразно разработать специализированный язык описания алгоритмов решения задач структурного анализа и синтеза. Язык должен оперировать абстракциями: «множество с заданным универсумом», «мультимножество», «кортеж», «вектор», «матрица». Над этими абстракциями в языке должны быть реализованы как традиционные операции, такие как пересечение множеств или проверка вхождения элемента во множество или мультимножество, так и специальные операции, связанные с использованием перечисленных абстракций в алгоритмах, например, обращение к элементу кортежа по номеру. Применение языка с указанным выше набором абстракций и операций над ними приведет к сокращению времени разработки и реализации алгоритма и позволит реализовать автоматический анализ емкостной и вычислительной сложности по тексту программы на предлагаемом языке и автоматизировать применение оптимизирующих преобразований, позволяющих существенно снизить емкостную и/или вычислительную сложность разрабатываемых программ решения задач структурного анализа и синтеза.
Список литературы 1. Скороходов В.А., Чеботарева А.С. Максимальный поток в сети с циклической зависимостью длительностей прохождения по дугам от времени // Известия высших учебных заведений. Северо-Кавказский регион. Естественные науки. 2011. № 5. С. 23-27. 2. Евстигнеев В.А., Турсунбай К.Ы. О раскраске графов в классе параллельных локальных алгоритмов // Сибирский журнал вычислительной математики. 2011. Т. 14, № 3. С. 231-243. 3. Алгоритмы и методы решения задач составления рисписаний и других экстремальных задач на графах больших размерностей / Е.В. Панкратьев, А.М. Чеповский, Е.А. Черепанов, С.В. Чернышев // Фундаментальная и прикладная математика. 2003. Т. 9, № 1. С. 235-251. 4. Лузгачёв М.В., Самуйлов К.Е. Задача маршрутизации трафика на графе сети MPLS с одноадресными соединениями // Вестник Российского университета дружбы народов. Сер. Математика, информатика, физика. 2009. № 1. С. 23-33. 5. Ейбоженко Д.А. Алгоритм К-кластерной оптимизации для задачи Штейнера на ориентированных графах // Вестник Санкт-Петербургского университета. Сер. 10. Прикладная математика. Информатика. Процессы управления. 2011. № 2. С. 29-39. 6. Соколов Г.В. Анализ алгоритмов автоматической укладки графов на плоскости в рамках задачи визуализации моделей на графах // Вестник Пермского национального исследовательского политехнического университета. Прикладная математика и механика. 2010. № 15. С. 162-171. 7. Титов Ю.П. Применение декомпозиции графа на связные составляющие при работе алгоритмов выбора маршрутов транспортных перевозок // Сборник научных трудов Sworld. 2012. Вып. 2, т. 1. С. 8-12. 8. Бёрд Р. Жемчужины проектирования алгоритмов: функциональный подход. М.: ДМК Пресс, 2013. 330 с. [Bird R. Perls of Function Algorithm Design. Cambridge University Press, 2010]. 9. Mehlhorn K., Naher St.The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press, 1999. 10. Himsolt M. GML: A Portable Graph File Format. TechnicalReport. UniversitatPassau, 1997. 11. Овчинников В.А. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем. М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. 286 c. 12. Кормен Т., Лейзерсон Ч., Риверст Р. Алгоритмы: построение и анализ: пер. с англ. М.: Издательский дом Вильямс, 2006. 955 с. [Cormen T.H., Leiserson C.E., Rivest R.L. IntroductiontoAlgorithms. TheMITPress, 1999.] 13. Ахо А.В., Хопкрофт Д., Ульман Д.Д. Структуры данных и алгоритмы: пер. с англ. М.: Издательский дом Вильямс, 2003. 382 с. [AhoA.V., HopkroftJ.E., UllmanJ.D. DatastructuresandAlgorithms. Addison-WesleyPublishingCompany, 2000.] 14. Пасечников К.А., Иванова Г.С. Синтез оптимальных структур данных для решения задач на графах // Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2008. № 4 (73). C. 29-38. 15. Овчинников В.А., Иванова Г.С., Павлов А.Е. Оценка эффективности оптимизирующих преобразований алгоритмов операций над ультраграфами // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2013. № 1. DOI: 10.7463/0113.0547731 16. Иванова Г.С. Модели объектов задач структурного синтеза. // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2006. № 12. Режим доступа: http://technomag.edu.ru/doc/62361.html (дата обращения 15.09.2013). Публикации с ключевыми словами: структурный синтез, специализированный язык, абстракции языка, операции над абстракциями Публикации со словами: структурный синтез, специализированный язык, абстракции языка, операции над абстракциями Смотри также: Тематические рубрики: Поделиться:
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|