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

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

В работах [3, 4] предложена концепция ассоциативной нейронной среды (АНС) для хранения и обработки информации, в основе которой лежат следующие основные принципы:

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

Линейные списковые структуры отличаются порядком включения, исключения, замены или доступом к элементам данных. Обобщением линейных списков являются массивы. В p-мерном массиве каждый элемент принадлежит p линейным спискам. Эти структуры являются естественно описываемыми в АНС объектами, не требующими дополнительных приемов для их представления на основе определенных в АНС геометрических форматов [4].

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

Многие важные случаи работы с линейными списками требуют адекватности их представления в АНС. Типом решетки, отвечающим основным требованиям адекватности представления списковых структур данных является кубические решетки Z^p. Вопрос адекватности представления треугольных матриц общего вида произвольной размерности (так называемых тетраэдральных массивов) в АНС решается выбором треугольной системы заполнения АНЯ пространства АНС соответствующей размерности с направлениями доступа к ячейкам, совпадающими с осями трансляции при организации этой решетки. Другое представление тетраэдральных массивов может быть осуществлено на решетках Z^p АНС с диагональными направлениями доступа к АНЯ.

Из всех типов структур данных именно для линейных списков и, прежде всего, для многомерных массивов наиболее актуален вопрос их представления на решетках АНС 3-й и меньших размерностей, которые являются физически реализуемыми и визуально представимыми. Например, 4-мерный массив данных, в котором каждый элемент данных принадлежит 4-м линейным спискам, может быть представлен совокупностью 3-мерных геометрических форматов в 3-мерной кубической решетке Z³ с эмуляцией ассоциативных взаимосвязей между АНЯ, обеспечивающих связность, упорядоченность и принадлежность каждого элемента данных 4-м линейным спискам.

Древовидные структуры данных являются одними из наиболее важных нелинейных структур данных. Важным классом деревьев являются бинарные деревья, которые можно определить как конечные множества элементов данных, пустые или, состоящие из корня и двух непересекающихся бинарных деревьев. Деревья общего вида, т.е. r-арные (r - число ветвей > 2) могут быть приведены к виду бинарных деревьев.

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

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

В ряде случаев целесообразно использовать решетки АНС больших, чем 2D, размерностей. Использование для представления деревьев решеток АНС 3-й и больших размерностей позволяет:

• упросить отображение дерева на решетку АНС и виды геометрических форматов для различных видов параллельного доступа к вершинам дерева;
• обеспечить компактность отображения и адекватность представления иерархических взаимосвязей между вершинами разных уровней дерева;
• повысить эффективность осуществления различных видов параллельного доступа и преобразований элементов данных дерева за счет наиболее полного использования свойств решеток АНС, например, за счет использования всех направлений доступа к АНЯ АНС, совпадающих с осями трансляции этих решеток;
• повысить r-арность представляемых деревьев.

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

Для представления и эффективной реализации в АНС различных типов параллельного доступа в древовидных структурах данных предложен новый тип геометрических форматов - иерархических геометрических форматов [4]. Кроме того, в АНС могут быть одновременно размещены несколько деревьев. Причем вершины соответствующих уровней деревьев размещаются в одних и тех же решетках АНС соответствующих размерностей. Это обеспечивает эффективную реализацию быстрых алгоритмов поиска и сортировки для древовидных структур данных в АНС.

1. Метлицкий В.А., Каверзнев В.В. Системы параллельной памяти: Теория, проектирование, применение / Под ред. В.И.Тимохина.- Л., Изд-во Ленинградск. ун-та, 1989.
2. Lawrie D.H, Voga C.R. The Prime Memory System for Array Access // IEEE Trans. on Computers, N5, vol. 31, 1985.
3. Борисов В.В. Ассоциативная нейронная фрактальная среда для прикладных интеллектуальных систем. – Нейрокомпьютер, 1998, № 1-2. - С. 5-11.
4. Борисов В.В. Исследование и разработка многокоординатных ассоциативных запоминающих устройств и среды хранения и обработки информации. – М.: МЭИ, 1997.