автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Синтез оптимальных структур данных для алгоритмов решения комбинаторных задач на графах

На правах рукописи

Пасечников Константин Алексеевич

СИНТЕЗ ОПТИМАЛЬНЫХ СТРУКТУР ДАННЫХ ДЛЯ АЛГОРИТМОВ РЕШЕНИЯ КОМБИНАТОРНЫХ ЗАДАЧ НА ГРАФАХ

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертации на соискание ученой степени кандидата технических наук

Москва - 2009

003469256

Работа выполнена в Московском государственном техническом университете им. Н.Э. Баумана

Научный руководитель:

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

Официальные оппоненты:

доктор технических наук, профессор Жданов Владимир Сергеевич

кандидат технических наук Башмаков Александр Игоревич

Ведущая организация Научно-технический инновацион-

ный центр «ТЕХКОМ»

Защита диссертации состоится «04» июня 2009 г. в 16:00 часов на заседании диссертационного совета Д 212.141.10 в Московском государственном техническом университете им. Н.Э. Баумана по адресу:

105005, 2-я Бауманская ул., д. 5.

Ваши отзывы в двух экземплярах, заверенные печатью, просьба высылать по указанному адресу.

С диссертацией можно ознакомиться в библиотеке Московского государственного технического университета им. Н.Э. Баумана.

Автореферат разослан « » 2009 г.

Ученый секретарь диссертационного совета,

к.т.н., доцент

Иванов С.Р.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы.

Большинство алгоритмов решения задач структурного синтеза на графах являются Л'Р-сложными, а сами объекты особенно применительно к вычислительной технике имеют большую размерность. В настоящее время речь идет о сотнях тысяч компонентов и более - при исследовании и разработке структур аппаратных средств и о тысячах компонентов - для задач, связанных с созданием программного обеспечения. Соответственно время решения многих задач рассматриваемого класса даже на современной технике недопустимо велико.

Исследованиями в области решения задач структурного синтеза, а также проблемами уменьшения вычислительной и емкостной сложности применяемых алгоритмов решения этих задач занимались A.B. Ахо, Т. Кормен, Ч. Лей-зерсон, Р. Риверст, Р. Седжвик, Д. Хопкрофт, В.А. Овчинников, А.И. Петренко и многие другие. В работах перечисленных ученых показано, что вычислительная сложность вариантов реализации алгоритма при использовании различных структур данных для представления графовых моделей может отличаться на несколько порядков.

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

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

В связи с этим синтез оптимальных структур данных для представления графовых моделей является актуальной задачей.

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

Задачи исследований. Для достижения указанной цели потребовалось: Для достижения указанной цели в работе потребовалось:

1. Выполнить анализ существующих структур данных с целью выявления их свойств и классификации основных операций над ними.

2. На основании проведённого анализа разработать модели структур данных, позволяющие оценивать влияние организации данных на ёмкостную и вычислительную сложность алгоритма.

3. Выполнить формальную постановку задачи синтеза оптимальной структуры данных и разработать метод её решения.

4. Разработать способ генерации синтаксически корректных конструкций описаний оптимальных структур данных.

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

6. Выполнить экспериментальную проверку полученных теоретических результатов.

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

Научная новизна работы. В процессе исследования получены следующие новые научные результаты, представляемые на защиту:

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

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

3. Формально определена операция объединения моделей структур данных, позволяющая получать модели комбинированных структур данных и их характеристики из базовых.

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

5. Разработан алгоритм генерации синтаксически корректных конструкций описаний структур данных для синтезированных моделей.

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

Апробация работы. Основные положения работы обсуждались на научно-технической конференции, посвященной 175-летию МГТУ им. Н.Э. Баумана (Москва, 2005), на научной конференции «Информатика и системы управления», проходившей в МГТУ им. Н.Э. Баумана (Москва, 2007).

Реализация и внедрения. Все основные теоретические и практические результаты работы в виде методики и программных средств внедрены в промыш-2

ленность. Они использованы при разработке очередной версии системы защиты Windows-приложений StarForce Protection Builder 5.70 в ООО «Протекшей Тех-нолоджи» (StarForce) и при создании системы анализа и классификации текстов БКФ 2.00 в ЗАО «ИнфоВотч» (дочерняя компания ЗАО «Лаборатория Каспер-ского»).

Публикации. По результатам диссертационной работы автором опубликовано 7 статей.

Объем и структура диссертации. Диссертационная работа включает введение, четыре главы, заключение и список литературы, занимающих 159 страниц текста, в том числе 32 рисунка и 23 таблицы, список использованной литературы из 58 наименований на 6 страницах.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе «Анализ существующих методов синтеза структур данных и постановка задачи» выполнен анализ существующих способов оптимизации структур данных и показана возможность их применения в случае автоматического синтеза структур данных.

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

Проведён анализ существующего оптимизатора языка SETL - единственной на данный момент программной системы, решающей задачу выбора оптимальных структур данных. Анализ оптимизатора выявил 6 существенных недостатков, которые накладывают значительные ограничения на его применение.

Выполнен анализ формального описания структур данных, применяемого в языке АЛГОРИТМ. Показано, что использование предлагаемых моделей структур данных для решения задачи синтеза оптимальной структуры данных неэффективно вследствие высокой сложности последних.

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

Во второй главе «Разработка моделей структур данных» выполнен анализ наиболее часто используемых операций над структурами данными и предложена классификация, позволяющая определить набор операций, который можно

использовать при сравнении двух структур данных по временным параметрам. Этот набор состоит из операций, вычислительная сложность которых не зависит от используемых инструментальных средств (компиляторов и операционных систем) и включает в себя элементарные операции анализа и преобразования.

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

Моделью векторного способа организации данных является смешанный граф (рис. 1). Переход от объекта к модели для вектора выполняется по следующим правилам:

1) Любая структура данных представляет собой описание одного из возможных способов размещения конечного множества данных О в памяти. При этом каждому элементу множества данных ставится во взаимнооднозначное соответствие Р адрес из множества доступных адресов памяти А И,Р с: АхИ. При переходе от объекта к модели поставим во взаимнооднозначное соответствие множеству £) множество вершин графа Хр, а множеству адресов А - множество вершин графа ХА. Поскольку множество Р описывает взаимнооднозначное соответствие между множествами А и Д каждой паре элементов множества Р сопоставляем ребро иАП е ил[).

2) Структура данных кроме полезной информации в виде элементов данных обычно хранит служебную информацию о связях элементов между собой. Элемент данных вместе со служебной информацией назван компонентом структуры данных. Таким образом, можно говорить о наличии множества С компонентов структуры данных и множества 2, определяющего взаимнооднозначное соответствие размещенных элементов данных компонентам структуры Р сРхС. Компонентом вектора будет являться непосредственно элемент данных, а множество связей компонентов F будет представлять собой декартово произведение множества С самого на себя, т. е. F = С х С. Таким образом, каждому компоненту сеС вектора будет взаимнооднозначно соответствовать двухвершинный подграф с одним ребром ¿{<хА,х0 >,иА0)еС, где - граф, описывающий организацию элементов структуры данных.

3) Связи ^ между компонентами структуры данных отобразим, определив однозначное соответствие С С, /гсСхС. Каждой связи компонентов из множества Р сопоставим дугу из множества С//.-.

В результате модель вектора:

где Оу({Х0,< ХА,11 >},{или,1!р}) - смешанный граф, описывающий организацию элементов,

() - множество функций, определяющих вычислительную сложность операций,

5 = { 5,} - множество допустимых операций над структурой данных, <7, (и) — функция оценки вычислительной сложности /'-ой операции, Ь(п) = О - дополнительная ёмкостная сложность структуры данных (функция, определяющая объём памяти, занимаемый вспомогательными элементами структуры данных в зависимости от количества хранимых элементов данных).

и,.

X,

Хп

вершина данных; - вершина адреса;

дуга, связывающая вершины адреса; ребро, связывающее вершину адреса и вершину данных;

Рис. 1. Модель вектора

Построена модель списковой организации данных подразумевающей размещение элементов списка в произвольных свободных участках памяти (см. рис. 2). Сопоставление модели списка с объектом выполняется по таким же правилам, как и в случае вектора, за исключением того, что в случае списка необходимо учитывать явную связь компонентов между собой, для чего добавляются дополнительные конструкции (ХА',Х[)',иАп\ил).

По аналогии с вектором, модель списка будет выглядеть следующим образом:

Щ =< Ди) >

где <75({Х0,Х0,,< Ха/ >,< Ха,,1а >},{иАО,ил[).,иА,и- смешанный граф, описывающий организацию элементов в структуре данных,

£) - множество функций, определяющих вычислительную сложность операций,

Ь(п) = п1л — дополнительная ёмкостная сложность списка.

Полученные модели базовых структур данных позволяют не только описывать организацию элементов данных, но и задавать вычислительные и ёмкостные параметры структур данных, также предложенные модели являются более простыми, чем модели, используемые в языке АЛГОРИТМ, так как они не содержат избыточной, с точки зрения поставленной задачи, информации.

О -

Условные обозначения:

- вершина данных; ^^ - вспомогательная вершина;

- вершина адреса;

— - дуга, связывающая вершины адреса;

- - ребро, связывающее вершину адреса и вершину данных;

— - дуга, связывающая компоненты списка между собой

Рис. 2. Модель односвязного списка

Разработаны модели комбинированных структур данных и определены формальные правила, позволяющие получать комбинированные структуры данных из базовых. Для иллюстрации формальных правил объединения рассмотрим объединение древовидного списка А/, и вектора М2, которые описываются следующим образом:

с, = с(ед)= с({х0,хт,< хА/ >,< хмГ >} ,{ило,илт,иТм), о2=с(х2,и2)=с{{х0,<хА/>},{ило,й7г}\

где С1 ,С2- графы организации элементов древовидного списка и вектора соответственно,

множества функций, определяющих вычислительную сложность операций над исходными структурами данных,

¿1 (п),Ь2(п) - дополнительные объёмы памяти для организации древовидного списка и вектора соответственно,

Х0, ХА~ множество вершин, соответствующих элементам данных и их адресам,

иАВ - множество дуг, отражающих взаимнооднозначное соответствие между элементами данных и их адресами,

> %л\->Vао\ ~ множества вершин и дуг, описывающие дополнительные поля в компонентах древовидного списка,

и¡.-2 - множества дуг, отражающих связи компонентов структуры данных между собой,

{/,' - множество дуг, отражающие связи между полями внутри компонента.

Графы С, и имеют общие вершины (X А, X 0) и ребра (иАВ), что позволяет выполнить операцию объединения этих графов. Результат объединения представлен на рис. 3.

ип

Рис. 3. Результат объединения моделей древовидного списка и

вектора

Модель результирующей структуры данных:

М=< Ь\п)>, _ _

где С* =С7, иС2 =С({Х0,<ХА/>,Хйи<Хм,1А >},{11 А0,и Ат,11 п,и< ,и п}\

Цп) = Ь1 (п) + ¿2 (и),

<2$\ = {?/(") = тт^ДлХ^Дл)]},

&2 = {?/(«) = ?,,. (и)+ <?2;(")}>

6.51 множества функций, определяющих вычислительную сложность

операций анализа и преобразования соответственно.

Разработаны различные варианты объединения структур данных, содержащих указатели, а также предложен способ снижения вычислительной сложности операций преобразования над результирующей структурой, за счёт введения дополнительной связи между компонентами.

Полученные формальные'правила объединения моделей структур данных позволяет синтезировать модели сложных комбинированных структур данных, а также дают возможность автоматически оценивать вычислительную сложность выполнения операций над ними и их емкостную сложность.

Выполнена формальная постановка задачи синтеза оптимальных одноуровневых структур данных. Исходными данными для синтеза оптимальной, с точки зрения вычислительной сложности заданного алгоритма, структуры данных являются:

1) описание множества и размер одного элемента этого множества;

2) совокупность базовых структур данных В = Щ =< >};

3) совокупность операций, выполняемых над множеством, что позволит определить набор операций над данными структуры;

4) количество повторений каждой операции над множеством в алгоритме (множество функций R = {r(n): S -> N});

5) допустимый объем памяти ЕЯ0П(п), который может занимать синтезируемая структура.

Отсюда получена формальная постановка задачи в следующем виде: Найти

Gop, sG:Qz (Gopl) = min{Q^ (G,)/G,. eG}, при

L(Go;>l ) - Loon > L0on =Еооп(П)~п1' >

где

G = {B^B2,BK},

BK={bjUbklbj,bk sB,j*k},B = {B,,B2>B3},

seS

qs=<

здесь G - полное множество возможных вариантов одноуровневых структур данных;

В - полное множество базовых структур данных (см. пункт 2 списка исходных данных);

Вк - множество всех возможных комбинированных структур данных; ps е Р - функция, определяющая количество повторений операции типа seS в зависимости от размера входа задачи;

qs eQ - оценка вычислительной сложности операции типа s над результирующей структурой данных;

fAl\>ch) ~ функция оценки вычислительной сложности операции типаs над комбинированной структурой данных, зависящая от типов объединяемых структур и типа операции.

. В этом случае задача определения оптимальной структуры данных заключается в нахождении такого способа организации элементов данных Gopl, при

котором Qy —» min при выполнении условия L'(Gop,)< Löon.

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

Выполнена формальная постановка задачи синтеза оптимальных двухуровневых структур данных. Исходными данными для синтеза оптимальной двухуровневой структуры данных являются все исходные данные, рассматриваемые при решении задачи синтеза оптимальной одноуровневой структуры данных, а также множество базовых двухуровневых структур данных В 2 = {¿2, =«7„а,!,(#!)>}.

Отсюда получена формальная постановка задачи синтеза оптимальной двухуровневой структуры данных в следующем виде:

Найти G2opreG2:Qz (G^) = min{gz (G2)/G2 eG2}, при

L(G2opl)<Lao„,

Lào„=Eàon(n)-nl" -kl1, где

B^{BX,B2,BK),

G2 = [gj = <b2t,Gl >},b2 eB2,

Gl={b)/b)eB1},

BK = {bj иbk /bj,bk eB,j*k},B = {В„Вг,Вг}, Ôz (G2)=YPs*1s,

SE S

qs=fs(b2k,Gl),

здесь G - множество всех возможных двухуровневых структур данных; В2 - полное множество базовых двухуровневых структур данных; G1 - множество одноуровневых структур данных, включённых в двухуровневую;

В1 - множество всех возможных одноуровневых структур данных; ps е Р - функция, определяющая количество повторений операции типа s e S в зависимости от размера входа задачи;

qs - оценка вычислительной сложности операции типа s над результирующей структурой данных.

В этом случае задача определения оптимальной структуры данных заключается в нахождении такого способа организации элементов G2pl, при котором

—> min при выполнении условия L(G2pt)< Làon.

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

В третьей главе «Разработка методики синтеза оптимальных структур данных и генерации их описаний» разработан алгоритм решения задачи синтеза оптимальной одноуровневой структуры данных. Результатом данного алгорит-

ма является структура данных с минимальной суммарной вычислительной сложностью для определённого множества операций. Эта структура может быть базовой либо комбинированной, то есть полученной в результате объединения нескольких базовых структур данных.

Показано, что применение комбинированных структур данных, полученных в результате объединения более чем двух базовых структур данных, является нецелесообразным. Это обусловлено тем, что при объединении трёх и более структур наблюдается существенное увеличение вычислительной сложности операций преобразования без какого-либо уменьшения вычислительной сложности операций доступа.

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

Содержательное описание полученного алгоритма синтеза оптимальной одноуровневой структуры данных выглядит следующим образом:

1. Посредством применения операций преобразования к базовым структурам данных из множества В] (множество базовых структур данных) формируем множества В2 (множество базовых структур данных, содержащих указатели на элементы данных) и Вг (множество базовых структур данных, содержащих указатели на элементы данных и дополнительные указатели для связи компонентов в результирующей структуре).

2. Формируем полное множество базовых структур данных, т.е. В = В, и В2 и .

3. Определяем множество решений как совокупность всех возможных объединений всех структур данных из полного множества базовых структур и множества простых базовых структур данных, т.е.

4. Задаём начальные значения для минимальной суммарной вычислительной сложности, текущего множества решений с минимальной суммарной вычислительной сложностью: £)т1п = оо, = 0.

5. Для V/;- еЛ,/* =< С,£),£(«)> выполняем:

5.1 .Определяем суммарную вычислительную сложность:

•вг =!»)*<

5.2.Проверяем условие:

Если условие выполняется, то переходим к п. 5.3, иначе - к п. 5.

5.3.Если установлено ограничение на максимальный размер непрерывного блока, т.е. т оо, то проверяем условие:

т^/ыоск(П>Пп, ах/')>

где /Ыоск - функция, возвращающая максимальный размер непрерывного блока для заданной структуры данных при определённом количестве элементов и размере одного элемента.

Если условие не выполняется, то переходим к п. 5, иначе - к п. 5.4.

5.4.Проверяем условие: Edon(n)>L(n)+nlv

Если условие не выполняется, значит, данная структура данных не удовлетворяет ограничению по ёмкостной сложности, переходим на п. 5, иначе-к п. 5.5.

5.5.Проверяем условие:

Q-Z =ömi„-

Если условие выполняется, то переходим к п. 5.7, иначе - к п. 5.6. 5.6.0чищаем множество решений с минимальной суммарной вычислительной сложностью: *min=0.

5.7.Включаем rt в Rmjn:

^min = Rmin U ri и возвращаемся к пункту 5.

6. Проверяем условие: Ämi „=0.

Если условие выполняется, значит, подобрать структуру данных, соответствующую заданным ограничениям, не удалось. Переходим на п. 9. Если условие не выполняется, переходим на п. 7.

7. Ищем структуру данных с минимальной дополнительной ёмкостной сложностью, для которой одновременно выполняется условие:

Mm*=ri eÄmin :£,■(«)-> min.

8. Запускаем процедуру генерации описания структуры данных.

9. Конец работы алгоритма.

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

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

Предложенные процедуры макрогенерации описаний структур данных на основании шаблонов обеспечивают простоту внесения изменений в описания базовых структур данных (без необходимости перекомпиляции), а также высокую скорость работы макрогенератора (см. рис. 4).

Разработан алгоритм генерации описания комбинированных структур данных.

Для задачи синтеза оптимальной двухуровневой структуры данных предложен способ сокращения размера множества решений с 6 * 1010 до 2 * I О3 вариантов, что позволило использовать метод полного перебора. Сокращение стало возможным за счёт использования свойства двухуровневых структур данных, которое заключается в том, что любую операцию над двухуровневой структурой данных можно представить в виде совокупности операций над одноуровневыми структурами, входящими в состав двухуровневой.

Разработан алгоритм синтеза оптимальных двухуровневых структур данных.

Разработан алгоритм генерации описания двухуровневой структуры. Согласно данному алгоритму, генерация выполняется за два этапа. На первом этапе генерируются описания всех вспомогательных одноуровневых структур, входящих в состав двухуровневой. На втором этапе генерируется класс самой двухуровневой структуры данных.

Входные данные

Дескриптор типа элемента данных

Имя структуры, имя элемента данных и т.д.

Библиотека базовых структур данных

Метаданные

Шаблон класса первой структуры данных

Метаданные

Шаблон класса второй структуры данных

Макрогенератор

Библиотека N

комбинированных

структур данных

Метаданные

Шаблон класса

комбинированной

структуры данных

ч /

Результат

Класс комбинированной структуры данных

Класс первой структуры данных

Класс второй структуры данных

Рис. 4. Генерация описания комбинированной одноуровневой структуры

данных

В четвертой главе «Экспериментальные исследования полученных результатов» описаны назначение, состав и функции системы синтеза оптималь-

ных структур данных (см. рис. 5). Программное обеспечение написано на языках Delphi Pascal и С# и имеет объем ~ 15000 строк.

Система синтеза

оптимальных структур данных

L.

Модуль ввода/вывода данных

Библиотеки шаблонов| структур данных |

Процедура преобразования \ входных данных

Макрогенератор ! описаний структур! данных

| | Библиотека г] шаблонов базовых ; : ! структур данных i

; i Библиотека ¡J шаблонов одноуровневых | структур данных

! Модули синтеза ■ оптимальных | структур данных 1

_I

! ! Модуль синтеза ! | одноуровневых | | структур данных

| | Модуль синтеза Ц двухуровневых : структур данных |

Библиотека шаблонов двухуровневых структур данных

Рис. 5. Структура системы синтеза оптимальных структур данных

Приведены результаты эксплуатации системы и экспериментальных исследований. Сформулированы цели экспериментальных исследований, даны характеристики объектов.

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

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

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

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

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

По результатам исследования показано, что структуры данных, оптимальные для одного набора входных данных могут быть неоптимальными для другого. Для выбранного алгоритма и заданного ограничения на размер входа задачи, это различие несущественно, так как изменение времени решения задачи в данном случае составляет менее 1 секунды, при погрешности измерения 0,04 с.

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

Целями исследования зависимости вычислительной сложности алгоритма лингвистического анализа текста от структур данных являлись анализ работоспособности модуля синтеза оптимальных одноуровневых структур данных и определение эффекта от применения оптимальных одноуровневых структур данных.

В качестве объекта исследования был использован алгоритм лингвистического анализа текста, который применяется в продукте Traffic Monitor компании Info Watch для решения задачи детектирования конфиденциальной информации в заданном электронном тексте. По результатам исследования показано, что использование оптимальных структур данных позволило ускорить работу программы в среднем на 14%, при этом наиболее заметно снизилось время обработки больших текстов - на 44%.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Для представления простых структур разработаны модели базовых структур данных, позволяющие оценивать вычислительную сложность базовых операций и емкостную сложность исследуемой структуры, а также обладающие меньшей избыточностью по сравнению с моделями, разработанными для языка АЛГОРИТМ.

2. Поскольку в алгоритмах решения задач на графах используются также многоуровневые структуры данных, были определены и сформулированы правила перехода от объекта к модели для многоуровневых и комбинированных структур данных, а также определены расчетные соотношения для оценки вы-

числительной и емкостной сложности таких структур по построенным моделям.

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

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

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

Теоретические результаты работы доведены до практической реализации в виде системы синтеза оптимальных структур данных для алгоритмов решения комбинаторных задач на графах. Экспериментальная проверка и эксплуатация системы подтвердили результаты теоретических исследований и основные научные положения, а также показали эффективность предложенных моделей, способов и средств. Так, практическое применение системы при создании программно-аппаратного комплекса БКФ 2.00 в компании Info Watch позволило сократить время обработки больших электронных текстов на 44% и уменьшить стоимость аппаратной составляющей комплекса на 10%. Также применение оптимальных структур данных при разработке очередной версии системы защиты Protection Builder 5.70 в компании «Протекшей Технолоджи» позволило увеличить скорость защиты приложений в среднем на 20%.

Работы по теме диссертации

1. Иванова Г.С, Пасечников К.А. Макрогенерация описаний структур данных для системы проектирования алгоритмов решения задач структурного синтеза // Современные информационные технологии: Сб. трудов каф., посвященный 175-летию МГТУ им. Н.Э. Баумана. - М.: Эликс+, 2004. - С. 69-73.

2. Пасечников К.А. Анализ проблемы синтеза оптимальных структур данных для алгоритмов решения комбинаторных задач на графах.

// Информатика и системы управления в XXI веке: Сб. трудов молодых учёных, аспирантов и студентов МГТУ им. Н.Э. Баумана. - 2007. -№5.-С. 118-124.

3. Пасечников К.А., Иванова Г.С. Модели структур данных для представления объектов задач структурного анализа и синтеза. // Информатика

и системы управления: Сб. трудов молодых учёных, аспирантов и студентов МГТУ им. Баумана. - 2006. - №4. - С. 45-48.

4. Пасечников К.А., Иванова Г.С. Генерация оптимальных структур данных для алгоритмов решения комбинаторных задач на графах. // Аэрокосмические технологии: Труды Всероссийских и Международной научно-технических конференций. - М., 2008. - С. 112-115.

5. Пасечников К.А. Генерация комбинированных структур данных

// Наука и образование. Инженерное образование: Эл. науч. издание. -2008. -№11. (Номер гос. регистрации 0420900025)

6. Пасечников К.А. Модели структур данных с векторной, списковой и древовидной организацией элементов // Наука и образование. Инженерное образование: Эл. науч. издание. - 2008. - № 10. (Номер гос. регистрации 0420900025)

7. Пасечников К.А., Иванова Г.С. Синтез оптимальных структур данных для решения задач на графах // Вестник Московского государственного технического университета им. Н.Э. Баумана. Приборостроение. -2008. - № 4(73). - С. 29-38.

Подписано к печати 23.04.09. Заказ №301 Объем 1,0 печ.л. Тираж 100 экз. Типография МГТУ им. Н.Э. Баумана 105005, Москва, 2-я Бауманская ул., д.5 263-62-01

ВВЕДЕНИЕ.

1. АНАЛИЗ СУЩЕСТВУЮЩИХ МЕТОДОВ СИНТЕЗА СТРУКТУР ДАННЫХ И ПОСТАНОВКА ЗАДАЧИ.

1.1. Анализ существующих методов оптимизации структур данных

1.1.1. Языки сверхвысокого уровня и абстрактные типы данных.

1.1.2. Специализация структур данных.

1.1.3. Оптимизация структур данных, использующих указатели.

1.1.4. Оптимизация структур данных с большим количеством элементов.

1.2. Анализ методов автоматического выбора оптимальных структур данных.

1.3. Анализ существующих формальных описаний структур данных

1.4. Постановка задачи синтеза оптимальных структур данных.

Выводы по главе 1.

2. РАЗРАБОТКА МОДЕЛЕЙ СТРУКТУР ДАННЫХ.

2.1. Анализ операций над структурами данных.

2.2. Модели базовых одноуровневых структур данных.

2.3. Модели комбинированных одноуровневых структур данных.

2.4. Формальная постановка задачи синтеза одноуровневой структуры данных.

2.5. Модели базовых двухуровневых структур данных.

2.6. Формальная постановка задачи синтеза двухуровневой структуры данных.

Выводы по главе 2.

3. РАЗРАБОТКА МЕТОДИКИ СИНТЕЗА ОПТИМАЛЬНЫХ СТРУКТУР ДАННЫХ И ГЕНЕРАЦИИ ИХ ОПИСАНИЙ.

3.1. Синтез комбинированных одноуровневых структур данных.

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

3.1.2. Входные данные и способы их представления.

3.1.3. Способ задания функций одного переменного.

3.1.4. Реализация операции объединения структур данных.

3.1.5. Генерация описания одноуровневой структуры данных.

3.2. Синтез многоуровневых структур данных.

3.2.1. Разработка алгоритма синтеза двухуровневой структуры.

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

Выводы по главе 3.

4. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ.

4.1. Программное обеспечение системы синтеза оптимальных структур данных.

4.2. Исследование зависимости вычислительной сложности реализации алгоритма уравновешенной двоичной свертки от структур данных.

4.3. Исследование зависимости вычислительной сложности алгоритма неуравновешенной двоичной свертки от свойств входных данных

4.4. Исследование зависимости вычислительной сложности алгоритма лингвистического анализа текста от структур данных.

Выводы по главе 4.

ВЫВОДЫ.

Актуальность. К задачам структурного анализа и синтеза относят задачи исследования или определения некоторого варианта структуры объекта, под которой понимают совокупность составляющих его элементов и связей между ними [19]. В качестве моделей объекта и результата в этих задачах обычно используются графы различных типов, позволяющие отображать существенные с точки зрения решаемой задачи отношения между компонентами рассматриваемой структуры.

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

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

Вычислительная сложность вариантов реализации алгоритма при использовании различных структур данных может отличаться на несколько порядков. Данная задача, т.е. задача синтеза оптимальных структур данных, является самостоятельной научной проблемой, актуальной для многих научно-технических направлений. На данный момент существуют системы, которые решают лишь задачу выбора оптимальной структуры данных [32, 49, 51], в то время как формальной постановки задачи синтеза до сих пор не было получено.

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

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

Основные решаемые задачи. Для достижения указанной цели в работе потребовалось:

1. Выполнить анализ существующих структур данных с целью выявления Pix свойств и классификации основных операций над ними.

2. На основании проведённого анализа разработать модели структур данных, позволяющие оценивать влияние организации данных на ёмкостную и вычислительную сложность.

3. Выполнить формальную постановку задачи синтеза оптимальной структуры данных и разработать метод её решения.

4. Разработать способ генерации синтаксически корректных конструкций описаний оптимальных структур данных.

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

6. Выполнить экспериментальную проверку полученных теоретических результатов.

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

Научная новизна работы. В процессе исследования получены следующие новые научные результаты, представляемые на защиту:

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

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

3. Формально определена операция объединения моделей структур данных, позволяющая получать модели комбинированных структур данных и их характеристики из базовых.

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

5. Разработан алгоритм генерации синтаксически корректных конструкций описаний структур данных для синтезированных моделей.

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

Апробация работы. Основные положения работы обсуждались на научно-технической конференции, посвященной 175-летию МГТУ им. Н.Э. Баумана (Москва, 2005), на научной конференции «Информатика и системы управления», проходившей в МГТУ им. Н.Э. Баумана (Москва, 2007).

Реализация и внедрение. Все основные теоретические и практические результаты работы в виде методик и программных средств внедрены в промышленность. Они использованы при разработке очередной версии системы защиты Windows-приложений StarForce Protection Builder 5.70 в ООО «Протекшей Технолоджи» (StarForce) и при создании системы анализа и классификации текстов БКФ 2.00 в ЗАО «ИнфоВотч» (дочерняя компания ЗАО «Лаборатория Касперского»). Документы, подтверждающие внедрение, приведены в приложении.

Публикации. По результатам диссертационной работы автором опубликовано 7 статей.

Объем и структура диссертации. Диссертационная работа включает введение, четыре главы, заключение и список литературы, занимающих 159 страниц текста, в том числе 32 рисунка и 23 таблицы, список использованной литературы из 58 наименований на 6 страницах.

ВЫВОДЫ

1. Для представления простых структур разработаны модели базовых структур данных, позволяющие оценивать вычислительную сложность базовых операций и емкостную сложность исследуемой структуры, а также обладающие меньшей избыточностью по сравнению с моделями, предложенными В [13].

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

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

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

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

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

1. Архангельский А. Я. Программирование в Delphi 7. — М.: Бином-Пресс, 2003.- 1152 с.

2. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции: Пер. с англ. М.: Мир, 1978. - Т. 1.-611 с.

3. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции: Пер. с англ. М.: Мир, 1978. - Т. 2. - 487 с.

4. Ахо A.B., Хопкрофт Д., Ульман Д.Д. Построение и анализ вычислительных алгоритмов: Пер. с англ. М.: Мир, 1978. - 536 с.

5. Ахо A.B., Хопкрофт Д., Ульман Д.Д. Структуры данных и алгоритмы: Пер. с англ. М.: Издательский дом Вильяме, 2001. - 384 с.

6. Вирт Н. Алгоритмы+структуры данных=программы: Пер. с англ. М.: Мир, 1985.-406 с.

7. Гамма Э., Хелм Р., Джонсон Р. Приемы объектно-ориентированного проектирования. Паттерны проектирования. — М.: Питер, 2006, 368 с.

8. Грис. Д. Конструирование компиляторов для цифровых вычислительных машин: Пер. с англ. М.: Мир, 1975. - 544 с.

9. Иванова Г.С., Домосканов A.A. Оптимизация управления динамическим распределением оперативной памяти. // Современные информационные технологии: Сб. докл. и сооб. Межвузовской юбилейной научно-технической конференции. М., 2001. - С. 6-13.

10. П.Иванова Г.С. Математические модели структур данных // Информационные технологии. 2006. - № 9. — С. 44-52.

11. Иванова Г.С. Модели объектов задач структурного синтеза // Наука и образование. Инженерное образование: Эл. науч. издание. 2006. — № 12. (Номер гос. регистрации 0420600025\0053.)

12. Иванова Г.С. Методология и средства разработки алгоритмов решения задач анализа и синтеза структур программного обеспечения и устройств вычисли-тельной техники: Дисс. докт. техн. наук. М., 2007. - 416 с.

13. Н.Иванова Г.С. Способы представления структурных моделей // Наука и образование. Инженерное образование: Эл. науч. издание. 2007. - № 1. (Номер гос. регистрации 0420700025\003.)

14. Иванова Г.С. Технология программирования: Учебник для вузов. -М.: Изд-во МГТУ им. Н.Э. Баумана, 2003. 320 с.

15. Касперски К. Техника оптимизации программ. Эффективное использование памяти. СПб.: БХВ - Петербург, 2003. - 464 с.

16. Кормен Т., Лейзерсон Ч., Риверст Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000. - 960 с.

17. Макконнелл Дж. Основы современных алгоритмов: Пер. с англ. М.: Техносфера, 2004. - 368 с.

18. Норенков И.П. Основы автоматизированного проектирования: Учеб. для вузов. М.: Изд-во МГТУ им. Н.Э. Баумана. - 2000. - 360 с.

19. Овчинников В.А. Автоматизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем: Учеб. для вузов. — М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. 288 с.

20. Пасечников К.А., Иванова Г.С. Модели структур данных для представления объектов задач структурного анализа и синтеза. // Информатика и системы управления: Сб. трудов молодых учёных, аспирантов и студентов МГТУ им. Баумана. 2006. - №4. - С. 45-48.

21. Пасечников К.А., Иванова Г.С. Генерация оптимальных структур данных для алгоритмов решения комбинаторных задач на графах. // Аэрокосмические технологии: Труды Всероссийских и Международной научно-технических конференций. М., 2008. - С. 112-115.

22. Пасечников К.А. Генерация комбинированных структур данных

23. Наука и образование. Инженерное образование: Эл. науч. издание. 2008. -№11. (Номер гос. регистрации 0420900025)

24. Пасечников К.А., Иванова Г.С. Синтез оптимальных структур данных для решения задач на графах // Вестник Московского государственного технического университета им. Н.Э. Баумана. Приборостроение. 2008. - № 4(73).-С. 29-38.

25. Пасечников К.А. Модели структур данных с векторной, списковой и древовидной организацией элементов // Наука и образование. Инженерное образование: Эл. науч. издание. 2008. - № 10. (Номер гос. ре-гистрации 0420900025)

26. Райли Д. Абстракция и структуры данных: Пер. с англ. М.: Мир, 1993.-752 с.

27. Рихтер Дж. Программирование на платформе Microsoft .NET Framework. M.: Издательско-торговый дом "Русская редакция", 2003. — 512 с.

28. Рихтер Дж. Windows для профессионалов: создание эффективных \Ут32-приложений с учетом специфики 64-разрядной версии Windows. M.: Издательско-торговый дом "Русская редакция", 2001. - 752 с.

29. Соломон, Д. Внутреннее устройство Microsoft Windows 2000. Мастер-класс. M.: Издательско-торговый дом "Русская редакция", 2001. - 992 с.

30. Cai J., Façon Ph. Type analysis and data structure selection // Constructing Programs from Specifications / B. Moller. North-Holland, 1991. - P. 124-164.

31. Chase D., Wegman M., Zadek F. Analysis of pointers and structures

32. Proceedings of the SIGPLAN '90 Conference on Program Language Design and Implementation. New York, 1990. - P. 296-310.

33. Childs D.L. Feasibility of a set-theoretical data structure a general structure based on a reconstituted definition of relation // IFIP Cong. - Michigan, 1968. - 123 p.

34. Cook W. Object-oriented programming versus abstract data types // Proceedings of REX Workshop School on the Foundations of Object-Oriented Languages. London, 1990.-P. 151-178.

35. Freudenberger S., Schwartz J. Experience with the SETL Optimizer // Abstract in TOPLAS 5(1). New York, 1983. - P. 26-45.

36. Guttag J. J. Abstract data types and the development of data structures // Communications of the ACM. New York, 1977. - V. 20. - P. 396-404.

37. Hoare C. A. R. Proof of correctness of data representations // Acta Information-New York, 1972.-V.l P. 271-281.

38. Hummel J., Hendren L. J., Nicolau A. Abstract description of pointer data structures: An approach for improving the analysis and optimization of imperative programs // ACM Letters on Programming Languages and Systems. New York, 1992.-P. 243-260.

39. Jones N.D. An introduction to partial evaluation // ACM Computing Surveys. New York, 1996. - V. 28. - P. 480-503.

40. Jones N.D., Muchnick. S.S. Flow analysis and optimization of LISP-Iike structures // ACM SIGPLAN Notices. New York, 1981. - P. 343-359.

41. Kant E. The selection of efficient implementations for a high-level language // Proceedings of the 1977 symposium on Artificial intelligence and programming languages. New York, 1977. - P. 140-146.

42. Lattner C. Macroscopic Data Structure Analysis and Optimization : Ph.D. Thesis, Computer Science Dept., University of Illinois. — Urbana-Champaign, 2005.-225 p.

43. Liskov B. Data Abstraction and Hierarchy // ACM SIGPLAN Notices. -New York, 1987. V.23.-P. 17-34.

44. Liskov B., Zilles N. Programming with abstract data types. // SIGPLAN Notices. New York, 1974. - V.9. - P. 50-59.

45. Low J. R. Automatic Data Structure Selection: An Example and Overview // Communications of the ACM. -New York, 1978. V. 21. - P.376-385.

46. Park J. G., Park M. S. Using Indexed Data Structures for Program Specialization // Internet Computing Lab., Department of Computer Science and Engu-neering, Korea University. Seoul (Korea), 2001. — P. 61-69.

47. Schonberg E., Schwartz J. Automatic data structure selection in SETL

48. Conference record of the 6th annual ACM symposium on principles of programming languages. San Antonio (Texas), 1979. - P. 197-210.

49. Schwartz J. Automatic and semiautomatic optimization of SETL // Proceedings of the ACM SIGPLAN symposium on Very high level languages. New York, 1974.-P. 42-49.

50. Schwartz, J. Automatic data structure choice in a language of very high level // CACM 18. New York, 1975. - V.12. - P. 722-728.

51. Schwartz J., Dubinsky E. Programming With Sets: An Introduction to SETL. New York, 1986. - 127 p.

52. Snyder. K. The SETL2 programming language: Technical Report 490, Courant Institute of Mathematical Sciences. New York, 1990. - P. 44-53.

53. Standish T. A. Data structures: An axiomatic approach // Communications of the ACM. New York, 1977. - V.20. - P. 396-404.

54. Tenenbaum A. Program efficiency and data structures // ACM SIGCSE Bulletin. New York, 1977. - V. 9. - P. 21-27.

55. Truong D. N., Bodin F. Improving cache behavior of dynamically allocated data structures // Proceedings of the International Conference on Parallel Architectures and Compilation Techniques. Paris, 1998. - P. 322-329.

56. Wegbreit B. Goal-directed program transformation // IEEE Transactions on Software Engineering SE. New York, 1976. - P.69-79.

57. Zilles S. Abstract specifications for data types // IBM Res. Lab. San Jose (California), 1975.-P.453-479.