Методы программирования. Громов Ю.Ю - 50 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

50
3. Определить последовательность прохождения узлов леса из
упр. 1, если порядок прохождения узлов:
а) прямой; б) обратный; в) концевой.
4. Представьте лес из упр. 1 с помощью последовательного распре-
деления памяти, если порядок прохождения его узлов:
а) прямой; б) фамильный; в) обратный.
8. ИСПОЛЬЗОВАНИЕ ПОНЯТИЯ ДЕРЕВА
ДЛЯ РЕШЕНИЯ ПРИКЛАДНЫХ ЗАДАЧ
Для полной спецификации всякого ориентированного дерева или
леса достаточно связи FATHER (отец), поскольку зная все восходящие
связи можно нарисовать дерево или лес.
Рассмотрим важное практическое приложение, в котором можно
обойтись одними восходящими связями, – алгоритм, решающий задачу
эквивалентности.
Отношением эквивалентности, обозначаемым символом «≡», назы-
вается бинарное отношение между элементами множества М, удовлетво-
ряющее следующим трём свойствам для любых (не обязательно различ-
ных между собой) элементов x, y, z из М:
а) если x ≡ y и y ≡ z, то x ≡ z (транзитивность);
б) если x ≡ y, то y ≡ x (симметричность);
в) x ≡ x (рефлексивность).
Примерами отношений эквивалентности могут служить отношение
«=», отношение сравнимости по модулю m для целых чисел, отношение
подобия между деревьями и др.
Задача эквивалентности состоит в том, что указываются пары экви-
валентных элементов множества М и необходимо установить возмож-
ность доказательства эквивалентности двух определённых элементов из
этого множества.
Пусть множество М = {1, 2, 3, 4, 5, 6, 7, 8, 9} и даны следующие па-
ры эквивалентных элементов:
1 ≡ 5, 6 ≡ 8, 7 ≡ 2, 9 ≡ 8, 3 ≡ 7, 4 ≡ 2, 9 ≡ 3. (36)
Отсюда доказывается, что 2 ≡ 6, поскольку 2 ≡ 7 ≡ 3 ≡ 9 ≡ 8 ≡ 6, но
нельзя доказать, что 1 ≡ 6. В самом деле, пары эквивалентных элементов
из (36) разбивают множество М на два класса эквивалентности:
K
1
= {1, 5} и K
2
= {2, 3, 4, 6, 7, 8, 9}, (37)
такие, что элементы 1 и 6 принадлежат различным классам, а, следова-
тельно, не эквивалентны.

Страницы