Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Нелинейные информационные структуры

Читайте также:
  1. III. Изменение объема и структуры продукции
  2. V4: Информационные технологии общего назначения
  3. Автоматизированные информационные системы
  4. Автоматизированные информационные системы.
  5. Адаптивные организационные структуры и их виды
  6. Адаптивные структуры управления
  7. Адаптивные структуры управления(проэктная,матричная)Проектная структура.
  8. Анализ ассортимента и структуры продукции 1 страница
  9. Анализ ассортимента и структуры продукции 2 страница
  10. Анализ ассортимента и структуры продукции. Анализ ритмичности производства
  11. Анализ дебиторской и кредиторской задолженности: цели, источники информации, оценка структуры и динамики. Оптимизация расчетов.
  12. Анализ динамики и структуры имущества предприятия и источников его формирования.



Поскольку классификационная компонента представляется посредством графов класса деревьев, то прежде всего следует вспомнить основные положения, касающиеся нелинейных информационных структур. Дерево формально определяют как конечное множество Т, состоящее из одного или более узлов, таких, что: имеется один, специально обозначенный узел, называемый корнем данного дерева. Остальные узлы, исключая корень, содержатся в n ≥ 0 попарно непересекающихся множествах Т1, Т2, …,Тn, каждое из которых в свою очередь является деревом. Деревья Т1, Т2, …,Тn называются поддеревьями данного дерева. Определение рекурсивно, поэтому каждый узел дерева является корнем некоторого поддерева, которое содержится в этом дереве. Число поддеревьев данного узла называют степенью этого узла, а узел с нулевое степенью называют концевым узлом, листом или терминальной вершиной. Уровень узла по отношению к дереву Т определяется следующим образом: говорят, что корень имеет уровень 1, а другие узлы имеют уровень на единицу выше уровня своего корня. На Рис. 4 и Рис. 5 изображены деревья с семью узлами. Корнем дерева является узел А.

 


 

G G

 

D E F F E D

 

B C C B

 

A A

Рис. 4. Пример дерева Рис. 5. Пример симметричного дерева

Дерево на рис. 4 имеет поддеревья {B} и {C, D, E, F, G}. Корнем дерева {C, D, E, F, G} является узел С, имеющий уровень 2 относительно всего дерева. В свою очередь, он имеет три поддерева: {D}, {E}, {F,G} и, следовательно, его степень равна 3. Узлы B, D, E, G являются концевыми узлами. F – единственный узел степени 1, а G – единственный узел уровня 4.

Подразумевается, что все рассматриваемые нами деревья являются упорядоченными, так что деревья, изображённые на Рис. 4 и 5 считаются различными.

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

Деревья могут изображаться другими структурами или, наоборот, служить изображением других логических структур, например, вложенных множеств, вложенных списков, вложенных уступов и т.п. (Рис. 6).

 

H J A

D F B

B C H

E G J

A C

 

(A (B (H) (J))(C (D) (E (G)) (F))) D E

G

Рис. 6. Примеры древовидных структур F

Так всякий прямоугольный массив можно рассматривать как частный случай древовидной структуры. Например, вот два представления матрицы размера 3*4 (Рис. 7):

           
   
 
   
 
 


A[1,1] A[1,2] A[1,3] A[1,4]

A[2,1] A[2,2] A[2,3] A[2,4]

A[3,1] A[3,2] A[3,3] A[3,4]

 

Рис. 7. Представление массива в виде дерева



Другой пример древовидной структуры дают нам алгебраические формулы. Например, формулу a-b*(c/d+e/f) можно изобразить в соответствии с рис. 8.

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

--

a *

b +

/ /

 





Дата добавления: 2015-04-25; Просмотров: 68; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:



studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ip: 54.225.57.89
Генерация страницы за: 0.007 сек.