Деревья
<<  Баобаб - дерево долгожитель Сувениры «цветы из дерева»  >>
3.Бинарные деревья
3.Бинарные деревья
Дерево на Рис
Дерево на Рис
Моделирование принадлежности множеству
Моделирование принадлежности множеству
Картинки из презентации «3.Бинарные деревья» к уроку окружающего мира на тему «Деревья»

Автор: nik. Чтобы познакомиться с картинкой полного размера, нажмите на её эскиз. Чтобы можно было использовать все картинки для урока окружающего мира, скачайте бесплатно презентацию «3.Бинарные деревья.ppt» со всеми картинками в zip-архиве размером 392 КБ.

3.Бинарные деревья

содержание презентации «3.Бинарные деревья.ppt»
Сл Текст Сл Текст
13.Бинарные деревья. ПРЕДСТАВЛЕНИЕ 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, Т). 12L 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) - не выход. Во втором
упорядоченным. утверждении делается попытка найти путь в
61. Х меньше,чем К. В этом случае нужно северном направлении, т.е. согласовать
добавить Х к Лд, чтобы получить левое целевое утверждение путь(а(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
http://900igr.net/kartinka/okruzhajuschij-mir/3.binarnye-derevja-238279.html
cсылка на страницу

3.Бинарные деревья

другие презентации на тему «3.Бинарные деревья»

«Резьба по дереву» - Разновидности резьбы. Виды геометрической резьбы. Разделочных досок. Сквозная (прорезная). Мастера украшали не только избы, ни и всю домашнюю утварь. Домовая. Скульптурная. Для России более характерны узоры, преимущественно состоящие из треугольников. Рельефная. Плосковыемчатая. Двухгранно-выемочная Трёхгранно-выемочная Четырёхгранно-выемочная Скобчатая.

«Листья деревьев осенью» - Лист засыхает и отмирает. Умирающий лист меняет свой цвет. Дерево засыпает до весны. И.Бунин. Вода не может проникнуть в лист. Хлорофилл находится в растениях повсюду, но главным образом в листьях. Угадай, с какого дерева лист? Хлорофилл – зеленый пигмент, преобладающий у растений. Вокруг ножки листа нарастает пробковый слой.

«Станки по дереву» - Копировальное устройство позволяет изготавливать большое количество одинаковых деталей. Строгальные станки. В данной группе оборудования представлены циркулярные и торцовочные станки. Круглопильные станки. Токарные станки по дереву. Презентация по технологии. Станки по дереву. Ленточные пилы по дереву.

«Роспись по дереву» - Применяемая техника – капелька, усик, штрих, спираль, листок. Применяемая техника – капелька, листок, дуга, штриховка, усик. Технология выполнения – самая многоэтапная по сравнению с другими видами росписей по дереву. Сложился к началу 19 в. в низовьях р. Мезени, селе Палащелье Архангельской обл. Мезенская роспись.

«Деревья и листья» - Деревья бывают хвойные и лиственные. Самые распространённые лиственные деревья. Дуб. Липа. Берёза. Деревья и листья. Мы встречаем деревья повсюду. Тополь.

«Деревья кустарники травы» - Разнообразие растений. Чем травы отличаются от деревьев и кустарников? План исследования: Чем кустарники отличаются от деревьев и трав? Разнообразно влияние растений на человека. Растения живут повсюду: на лугах, в лесах, степях, в горах, в морях и океанах. В лесу растения располагаются ярусами: деревья, кустарники, травы.

Деревья

11 презентаций о деревьях
Урок

Окружающий мир

79 тем
Картинки