НАУКА и ОБРАЗОВАНИЕ

УДК 004.422.6

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

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

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

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

Рисунок 1 – Фрагмент комбинированной структуры данных дерево-вектор

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

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

Исходными структурами данных являются древовидный список и вектор (рисунок 2). Модели древовидного списка () и вектора () описываются следующим образом:

где

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

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

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

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

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

 - размер элемента данных в байтах,

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

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

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

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

Рисунок 2 – Модели древовидного списка и вектора

Графы  и  имеют общие вершины (, ) и ребра (), что позволяет выполнить операцию объединения графов:

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

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

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

При подсчёте вычислительной сложности необходимо учитывать, что операции доступа можно выполнять над любой из структур данных, входящих в комбинированную структуру (т.к. все они описывают расположение одних и тех же данных в памяти). Однако операции модификации необходимо выполнять над всеми составляющими комбинированной структуры данных. С учётом этого представим множество всех возможных операций над структурами данных  как объединение двух подмножеств – подмножества операций доступа  и подмножества операций модификации . Тогда вычислительная сложность комбинированной структуры данных:

Таким образом, комбинированной структурой данных, полученной в результате объединения двух структур данных, задаваемых моделями , , будет структура данных, описываемая моделью:

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

Литература

1.    К.А. Пасечников, Г.С. Иванова. Модели структур данных для представления объектов задач структурного анализа и синтеза. – Сборник трудов ╧4 молодых учёных, аспирантов и студентов «Информатика и системы управления», - М.: МГТУ им. Баумана, 2006. – 154 с.

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

3.    А. Ахо, Д. Ульман, Д. Хопкрофт. Структуры данных и алгоритмы. – М.:Вильямс, 2003. – 384 с.

4.    Пасечников К.А. Анализ проблемы синтеза оптимальных структур данных для алгоритмов решения комбинаторных задач на графах. . Сборник  трудов #5 молодых учёных, аспирантов и студентов ²Информатика и системы управления в ХХI веке⌡, . М.: МГТУ им. Н.Э. Баумана, 2007. 415 с.

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

6.    Овчинников В.А., Иванова Г.С., Ничушкина Т.Н. Выбор структур данных для представления графов при решении комбинаторно-оптими­за­ци­он­ных задач // Вестник Московского государственного технического университета им. Н.Э. Баумана. Приборостроение. .  2001. . # 2(43). . C. 39-51.

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