3.Бинарные деревья |
Деревья | ||
<< Баобаб - дерево долгожитель | Сувениры «цветы из дерева» >> |
![]() 3.Бинарные деревья |
![]() Дерево на Рис |
![]() Моделирование принадлежности множеству |
Автор: nik. Чтобы познакомиться с картинкой полного размера, нажмите на её эскиз. Чтобы можно было использовать все картинки для урока окружающего мира, скачайте бесплатно презентацию «3.Бинарные деревья.ppt» со всеми картинками в zip-архиве размером 392 КБ.
Сл | Текст | Сл | Текст |
1 | 3.Бинарные деревья. ПРЕДСТАВЛЕНИЕ | 8 | попытка доказательства целевого |
БИНАРНЫХ ДЕРЕВЬЕВ Бинарное дерево | утверждения меньше(2, 2) заканчивается | ||
определяется рекурсивно как имеющее левое | неудачей. | ||
поддерево, корень и правое поддерево. | 9 | Такой процесс согласования целевого | |
Левое и правое поддеревья сами являются | утверждения путем прямого продвижения по | ||
бинарными деревьями. На Рис. 2 показан | программе мы называем прямой трассировкой | ||
пример бинарного дерева. Рис. 2. Бинарное | (forward tracking). Даже если целевое | ||
дерево. Такие деревья можно представить | утверждение согласовано, с помощью прямой | ||
термами вида бд(Лд, К, Пд), где Лд - левое | трассировки мы можем попытаться получить | ||
поддерево, К - корень, а Пд - правое | другие варианты его доказательства, т.е. | ||
поддерево. Дл” обозначения пустого | вновь согласовать целевое утверждение. | ||
бинарного дерева будем использовать атом | Пролог производит доказательство | ||
nil. Бинарное дерево на рис.5.2.1 имеет | конъюнкции целевых утверждений слева | ||
левое поддерево. | направо. При этом может встретиться | ||
2 | бд(бд(nil, d, nil), b, бд(nil, е, | целевое утверждение, согласовать которое | |
nil)) правое поддерево бд(nil,с, nil) и | не удается. Если такое случается, то | ||
записывается целиком как бд(бд(бд(nil,d, | происходит смещение влево до тех пор, пока | ||
nil), b, бд(nil,е, nil)), а, бд(nil, с, | не будет найдено целевое утверждение, | ||
nil)). ПРЕДСТАВЛЕНИЕ МНОЖЕСТВ С ПОМОЩЬЮ | которое может быть вновь согласовано, или | ||
БИНАРНЫХ ДЕРЕВЬЕВ Описание множеств в виде | не будут ис черпаны все предшествующие | ||
списков позволяет использовать для | целевые утверждения. Если слева нет | ||
множеств целевое утверждение принадлежит, | целевых утверждений, то конъюнкцию целевых | ||
определенное ранее для списков. Однако для | утверждений согласовать нельзя. Однако, | ||
множеств, состоящих из большого числа | если предшествующее целевое утверждениг | ||
элементов, списковые целевые утверждения | может быть согласовано вновь, Пролог | ||
становятся неэффективными. Рассмотрим, | возобновляет процесс доказательства | ||
например, как целевое утверждение | целевых утверждений слева направо, начиная | ||
принадлежит (см. предыдущий разд.) | со следующего справа целевого утверждения. | ||
позволяет моделировать принадлежность | Описанный процесс смещения влево для | ||
множеству. Пусть L - список, описывающий | повторного согласования целевого | ||
множество из первых 1024 натуральных | утверждения и возвращения вправо носит | ||
чисел. Тогда при ответе на запрос ?- | название механизма возврата. Пример: | ||
принадлежит(3000, b). Прологу придется | задача поиска пути в лабиринте В качестве | ||
проверить все 1024 числа, прежде чем | примера использования механизма возврата | ||
заключить, что такого числа нет: нет | напишем процедуру для поиска пути в | ||
Представление множества бинарным деревом | лабиринте. Лабиринт представлен фактами | ||
позволяет добиться лучшего результата. При | вида: стена(I, J) для позиции в I-м ряду и | ||
этом бинарное дерево должно быть | J-й колонке, где есть стена | ||
упорядочено таким образом, чтобы любой | отсутств_стена(I, J) для позиции в I-м | ||
элемент в левом поддереве был меньше, чем | ряду и J-й колонке, где нет стены выход | ||
значение корня, а любой элемент в правом | (I, J) для позиции в 1-м ряду и J-й | ||
поддереве — больше. Поскольку мы | колонке, являющейся выходом Рассмотрим | ||
определили поддерево как бинарное дерево, | небольшой лабиринт: | ||
такое упорядочение применяется по всем | 10 | Последний ряд лабиринта описывается | |
поддеревьям. На Рис. 3 приведен пример | фактами: стена(4,1). стена(4,3). | ||
упорядоченного бинарного дерева. | стена(4,4). отсутств_стена(4,2). Если | ||
3 | Дерево на Рис. 2 является | задана исходная позиция, путь к выходу | |
неупорядоченным. Рис. 3. Упорядоченное | можно найти следующим образом. Граничное | ||
бинарное дерево. Обратите внимание, что | условие: Если исходная позиция является | ||
упорядочение приводит не к единственному | выходом, то путь найден. Рекурсивные | ||
варианту представления множества с помощью | условия: Ищем путь из исходной позиции в | ||
дерева. Например, на Рис. 4 изображено то | северном направлении. Если пути нет, идем | ||
же множество, что и на Рис. 3. Будем | на юг. Если пути нет, идем на запад. Если | ||
называть линейным представление такого | нельзя, идем на восток. Если соседняя | ||
вида, как на Рис. 4, и сбалансированным - | позиция на севере (юге, западе, востоке) | ||
такое, как на Рис. 3. | является стеной, то нет смысла искать путь | ||
4 | Моделирование принадлежности | из начальной позиции к выходу. Чтобы не | |
множеству. Имея множество, описанное | ходить кругами, будем вести список | ||
бинарным деревом, мы можем моделировать | позиций, в которых мы побывали. | ||
принадлежность множеству с помощью | 11 | Изложенному способу решения задачи | |
целевого утверждения принадлежит_дереву. | соответствует процедура путь: она ищет | ||
При этом используется оператор @<, | путь (второй аргумент) к выходу из | ||
выражающий отношение “меньше, чем”, и | некоторой позиции (первый аргумент). | ||
оператор @>, выражающий отношение | Третьим аргументом является список | ||
“больше, чем”. /* Граничное условие: Х | позиций, где мы побывали. /* Терм a(I, J) | ||
принадлежит /* дереву, если Х является | представляет позицию в /* I-м ряду и J-й | ||
корнем. принадлежит_дереву(Х, бд(Лд, Х, | колонке. /* Нашли путь ? путь(а(I, | ||
Пд)), /* Рекурсивные условия /* Х | J),[а(I, J)], Были) :- выход(I, J). /* | ||
принадлежит дереву, если Х больше /* | Пытаемся идти на север путь(а(I, J),[а(I, | ||
значении корня и находится в правом /* | J) | Р], Были) :- К is I-1, можем_идти(a | ||
поддереве: Рис. 4. Линейное представление. | (K, J), Были), путь(а(I, J) ,Р, [a(K, J) | | ||
5 | принадлсжит_дереву(Х, бд(Лд, У, Пд)) | Были]). /* Пытаемся идти на юг путь(а(I, | |
:- X@Y, припадлежит_дереву(Х, Пд). /* Х | J),[а(I, J) | Р], Были) :- К is I+1, | ||
принадлежит дереву, если Х меньше /* | можем_идти(a (K, J), Были), путь(а(I, J) | ||
значения корня и находится в левом /* | ,Р, [a(K, J) | Были]). /* Пытаемся идти на | ||
поддереве: принадлежит_дереву(Х, бд(Лд ,У | запад путь(а (I, J), [a (I, J) | P], Были) | ||
,Пд)) :-X@Y, принадлежит_дереву(Х, Лд). | :- L is J-1, можем_идти(а(I, L), Были), | ||
Если множество из первых 1024 чисел | путь(а(I, L), Р, [а(I, L)| Были]). /* | ||
описать с помощью сбалансированного | Пытаемся идти на восток путь(а (I, J), [a | ||
бинарного дерева Т, то при ответе на | (I, J) | P], Были) :-. | ||
запрос ?- принадлежит_дереву(3000, Т). | 12 | L is J+1, можем_идти(а(I, L), Были), | |
Пролог сравнит число 3000 не более чем с | путь(а(I, L), Р, [а(I, L)| Были]). /* в | ||
11 элементами множества. прежде чем | позицию a(I, J) можно попасть при /* | ||
ответит: нет Конечно, если Т имеет | условии, что там нет стены и мы /* не | ||
линейное представление, то потребуется | побывали в ней прежде можем_идти(а(I, J)), | ||
сравнение 3000 с 1024 элементами | Были) :- отсутств_стена(I, J), not | ||
множества. Построение бинарного дерева. | (принадлежит (a (I, J), Были)). Для того | ||
Задача создания упорядоченного бинарного | чтобы понять, каким образом процедура ищет | ||
дерева при добавлении элемента Х к другому | путь к выходу, рассмотрим процесс | ||
упорядоченному бинарному дереву | согласования запроса с описанием | ||
формулируется следующим образом: Граничное | лабиринта, описанного выше: ?-путь(а(4,2), | ||
условие: Добавление Х к nil дает бд(nil, | Р, [а(4.2)]). Выходом из лабиринта | ||
Х, nil). Рекурсивные условия: При | является позиция выход (3,1). Выбор | ||
добавлении Х к бд(Лд, К, Пд) нужно | первого утверждения не приводит к | ||
рассмотреть два случая, чтобы быть | согласованию целевого утверждения, | ||
уверенным, что результирующее дерево будет | поскольку а (4,2) - не выход. Во втором | ||
упорядоченным. | утверждении делается попытка найти путь в | ||
6 | 1. Х меньше,чем К. В этом случае нужно | северном направлении, т.е. согласовать | |
добавить Х к Лд, чтобы получить левое | целевое утверждение путь(а(3, 2), Р2, | ||
поддерево. Правое поддерево равно Пд, а | [а(3, 2), а(4, 2)]). Целевое утверждение | ||
значение корня результирующего дерева | не удается согласовать с первым | ||
равно К. 2. Х больше, чем К. В таком | утверждением путь(а(3, 2), Р2, [а(3, 2), | ||
случае нужно добавить Х к Пд, чтобы | а(4, 2)]) так как а (3,2) не является | ||
получить правое поддерево. Левое поддерево | выходом. Во втором утверждении | ||
равно Лд, а значение корня - К. Такой | предпринимается попытка найти путь, | ||
формулировке задачи соответствует | двигаясь на север, т.е. согласовать | ||
программа: /* Граничное условие: | целевое утверждение путь(а(2,2), РЗ, [а(2, | ||
включ_бд(nil, Х, бд(nil, Х, nil)). /* | 2), а(3, 2), а(4, 2)]). | ||
Рекурсивные условия: /*(1) включ_бд(бд(Лд, | 13 | Ни одно из утверждений не может | |
К, Пд), Х, бд(Лднов, К, Пд)) :- Х@К, | согласовать путь(а(2, 2), РЗ, [а(2, 2), | ||
включ_бд(Лд,Х,Лднов). /*(2) | а(3, 2), а(4, 2)]). Первое утверждение - | ||
включ_бд(бд(Лд, К, Пд), Х, бд(Лд, К, | потому, что а (2, 2) не является выходом, | ||
Пднов)) :- Х@К, включ_бд(Пд, Х, Пднов). На | второе - потому, что северная позиция | ||
запрос ?- включ_бд(nil, d, Т1), | является стеной, третье утверждение - | ||
включ_бд(Т1, а, Т2). будут получены | потому, что в южной позиции мы уже | ||
значения Т1=бд(nil, d, nil) Т2=бд(бд(nil, | побывали, а четвертое и пятое утверждения | ||
а, nil), d, nil) Процедуру включ_бд() | - потому, что западная и восточная границы | ||
можно использовать для построения | - это стены. Неудача в согласовании | ||
упорядоченного дерева из списка: | путь(а(2, 2), РЗ, [а(2, 2), а(3, 2), а(4, | ||
7 | /* Граничное условие: | 2)]) заставляет Пролог-систему вернуться в | |
список_в_дерево([], nil). /* Рекурсивное | ту точку, где было выбрано второе | ||
условие: список_в_дерево([Н | Т], Бд) :- | утверждение при попытке согласовать | ||
список_в_дерево(Т, Бд2), включ_бд(Н, Бд2, | путь(а(3, 2), Р2, [а(3, 2), а(4, 2)]). | ||
Бд). Заметим, что включ_бд не обеспечивает | Решение пересматривается и выбирается | ||
построения сбалансированного дерева. | третье утверждение. В третьем утверждении | ||
Однако существуют алгоритмы, гарантирующие | осуществляется попытка найти путь, | ||
такое построение. Механизм возврата и | двигаясь на юг, но она оказывается | ||
процедурная семантика При согласовании | неудачной, поскольку мы уже побывали в | ||
целевого утверждения в Прологе | позиции а (4, 2). Тогда, чтобы согласовать | ||
используется метод, известный под | путь(а(3, 2), Р2, [а(3, 2), а(4, 2)]), | ||
названием механизма возврата. В этой главе | выбирается четвертое утверждение. Мы | ||
мы показываем, в каких случаях применяется | успешно находим путь, двигаясь в западном | ||
механизм возврата, как он работает и как | направлении к позиции а(3,1), которая и | ||
им пользоваться. Описывается декларативная | является выходом. Рекурсия сворачивается, | ||
и процедурная семантика процедур Пролога. | и в результате получается путь Р=[а(4, | ||
Завершается глава обсуждением вопросов | 2),а(3, 2), а(3,1)] другие | ||
эффективности. Механизм возврата При | решения(да/нет)? да Других решений нет | ||
попытке согласования целевого утверждения | Альтернативный путь [a(4,2), a(3,2), | ||
Пролог выбирает первое из тех утверждений, | a(2,2), a(3,2), a(3,1)] мы получить не | ||
голова которых сопоставима с целевым | можем, потому что не разрешается дважды | ||
утверждением. Если удастся согласовать | бывать в одной и той же позиции. Описанная | ||
тело утверждения, то целевое утверждение | процедура не обязательно находит | ||
согласовано. Если нет, то Пролог переходит | кратчайший путь к выходу. Кратчайший путь | ||
к следующему утверждению, голова которого | можно найти, генерируя альтернативные пути | ||
сопоставима с целевым утверждением, и так | с помощью вызова состояния неудачи и | ||
далее до тех пор, пока целевое утверждение | запоминая кратчайший из них. | ||
не будет согласовано или не будет | 14 | Лекция4.4:Элементы нечеткой логики. | |
доказано, что оно не согласуется с базой | Как известно, классическая логика | ||
данных. | оперирует только с двумя значениями: | ||
8 | В качестве примера рассмотрим | истина и ложь. Однако этими двумя | |
утверждения: меньше(X.Y) :- XY, write(X), | значениями довольно сложно представить | ||
write ('меньше, чем'),write(Y). | (можно, но громоздко) большое количество | ||
меньше(Х.У) :- XY, write(Y), write | реальных задач. Поэтому для их решения был | ||
('меньше, 4CM'),write(X). Целевое | разработан специальный математический | ||
утверждение ?- меньше (5, 2). | аппарат, называемый нечеткой логикой. | ||
сопоставляется с головой первого | Основным отличием нечеткой логики от | ||
утверждения при Х=5 и У=2. Однако не | классической, как явствует из названия, | ||
удается согласовать первый член конъюнкции | является наличие не только двух | ||
в теле утверждения X<Y. Значит, Пролог | классических состояний (значений), но и | ||
нс может использовать первое утверждение | промежуточных: F = {0…1} Соответственно, | ||
для согласования целевого утверждения | вводятся расширения базовых операций | ||
меньше(5, 2). Тогда Пролог переходит к | логического умножения, сложения и | ||
следующему утверждению, голова которого | отрицания (сравните с соответствующими | ||
сопоставима с целевым утверждением. В | операциями теории вероятностей): Как можно | ||
нашем случае это второе утверждение. При | легко заметить, при использовании только | ||
значениях переменных Х=5 и Y=2 тело | классических состояний (ложь-0, истина-1) | ||
утверждения согласуется. Целевое | мы приходим с классическим законам логики. | ||
утверждение меньше(5,2) доказано, и Пролог | Нечеткое логическое управление может | ||
выдает сообщение “2 меньше, чем 5”. Запрос | использоваться, чтобы осуществлять | ||
?-меньше (2, 2). сопоставляется с головой | разнообразные интеллектуальные функции, в | ||
первого утверждения, но тело утверждения | самых разнообразных электронных товарах и | ||
согласовать не удается. Затем происходит | домашних приборах, к авто электронике, | ||
сопоставление с головой второго | управлению производственными процессами и | ||
утверждения, но согласовать тело | автоматизации. | ||
опять-таки оказывается невозможно. Поэтому | |||
3.Бинарные деревья.ppt |
«Резьба по дереву» - Разновидности резьбы. Виды геометрической резьбы. Разделочных досок. Сквозная (прорезная). Мастера украшали не только избы, ни и всю домашнюю утварь. Домовая. Скульптурная. Для России более характерны узоры, преимущественно состоящие из треугольников. Рельефная. Плосковыемчатая. Двухгранно-выемочная Трёхгранно-выемочная Четырёхгранно-выемочная Скобчатая.
«Листья деревьев осенью» - Лист засыхает и отмирает. Умирающий лист меняет свой цвет. Дерево засыпает до весны. И.Бунин. Вода не может проникнуть в лист. Хлорофилл находится в растениях повсюду, но главным образом в листьях. Угадай, с какого дерева лист? Хлорофилл – зеленый пигмент, преобладающий у растений. Вокруг ножки листа нарастает пробковый слой.
«Станки по дереву» - Копировальное устройство позволяет изготавливать большое количество одинаковых деталей. Строгальные станки. В данной группе оборудования представлены циркулярные и торцовочные станки. Круглопильные станки. Токарные станки по дереву. Презентация по технологии. Станки по дереву. Ленточные пилы по дереву.
«Роспись по дереву» - Применяемая техника – капелька, усик, штрих, спираль, листок. Применяемая техника – капелька, листок, дуга, штриховка, усик. Технология выполнения – самая многоэтапная по сравнению с другими видами росписей по дереву. Сложился к началу 19 в. в низовьях р. Мезени, селе Палащелье Архангельской обл. Мезенская роспись.
«Деревья и листья» - Деревья бывают хвойные и лиственные. Самые распространённые лиственные деревья. Дуб. Липа. Берёза. Деревья и листья. Мы встречаем деревья повсюду. Тополь.
«Деревья кустарники травы» - Разнообразие растений. Чем травы отличаются от деревьев и кустарников? План исследования: Чем кустарники отличаются от деревьев и трав? Разнообразно влияние растений на человека. Растения живут повсюду: на лугах, в лесах, степях, в горах, в морях и океанах. В лесу растения располагаются ярусами: деревья, кустарники, травы.