Задача о кратчайшем пути. Алгоритм Дейкстры

Кому интересно – Брал все в папке 9. Экстремальные задачи на графах и пдф 1.Храмова на 8 и 9 странице.

Совет: Так как это вопрос со звездочкой, то я бы посоветовал прочитатьеще пдф файл в той же папке 2.Алгоритм Дейкстры там все подробней расписано.

54. *Алгоритм Форда-Беллмана.

Кому интересно – Брал все в папке 9. Экстремальные задачи на графах и пдф 1.Храмова на 17 и 18 странице.

55. Свободные деревья. Ориентированные (корневые) деревья. Корневые упорядоченные деревья.

Вопрос 56: Прямой порядок обхода дерева.

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

При прохождении в прямом порядке (т.е. при прямом упорядочивании) узлов дерева Т сначала посещается корень п, затем узлы поддерева T₁ далее все узлы поддерева Т₂, и т.д. Последними посещаются узлы поддерева T_k.

Вопрос 57: Бинарные деревья. Типы БД: выровненные, полные, сбалансированные. Обходы бинарных деревьев.

Бинарное (двоичное) дерево (binary tree) - это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причем для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значение данного узла.

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

Типы:

Выровненное

Бинарное дерево называется выровненным, если все листья находятся на одном (последнем) уровне. В выровненном дереве все ветви имеют одну длину, равную высоте дерева, однако выровненное дерево не всегда является эффективным деревом сортировки.

Полное

Бинарное дерево называется заполненным, если все узлы, степень которых меньше 2, располагаются на одном или двух последних уровнях. Другими словами, в заполненном дереве Т все ярусы D(r,i), кроме, может быть, последнего, заполнены.

Сбалансированное

(Бинарное) дерево называется подровненным деревом, или АВЛ-деревом (Адельсои-Вельский и Лаидис, 1962), или сбалансированным по высоте деревом, если для любого узла высоты левого и правого поддеревьев различаются не более чем на 1.

Обходы

1. Обход бинарного дерева в прямом порядке:

а) Обработать корень (например, вывести в выходную последовательность его имя);

b) Обойти левое поддерево корня в прямом порядке;

c) Обойти правое поддерево корня в прямом порядке.

Обход приведённого бинарного дерева в прямом порядке даст: ABCDEFGH.

2. Обход бинарного дерева в обратном порядке:

a) Обойти левое поддерево корня в обратном порядке;

b) Обработать корень;

c) Обойти правое поддерево корня в обратном порядке.

Обход приведённого бинарного дерева в обратном порядке даст: CBEDAGFH.

3. Обход в бинарного дерева в концевом порядке:

а) Обойти левое поддерево корня в концевом порядке;

b) Обойти правое поддерево корня в концевом порядке.

c) Обработать корень;

Обход приведённого бинарного дерева в концевом порядке даст: CEDBGHFA.

Вопрос 58: Представление свободных деревьев кодом Прюфера.

Возьмем какое-нибудь дерево с n вершинами, помеченными различными

числами от 1 до n. Мы сопоставим дереву последовательность длины n-2 из букв x1; x2; …;xn. Последовательность строится индуктивно. Возьмем

в дереве лист с минимальным номером и возьмем в качестве первой буквы

последовательности x с индексом, равным номеру вершины, с которой этот

лист соединен. Затем удалим выбранный лист. Второй буквой будет x с ин-

дексом, равным номеру вершины, с которой соединен минимальный лист в

оставшемся дереве. Этот лист тоже удалим, и будем повторять эту опера-

цию до тех пор, пока не останется дерево из двух вершин (ребро). Получим

как раз последовательность букв длины n-2.

Последовательность удаления вершин в дереве с помеченными вершинами и соответствующая этому дереву последовательность букв – его код Прюфера.

Вопрос 59: Представление упорядоченных деревьев.

Всякое свободное дерево можно ориентировать, назначив один из узлов корнем. Всякое ордерево можно произвольно упорядочить. Всякое упорядоченное дерево можно представить бинарным деревом, проведя правую связь к старшему брату, а левую — к младшему сыну.

Диаграммы упорядоченного и соответствующего ему бинарного деревьев

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

Вопрос 60: Способы кодирования бинарных деревьев: списочные структуры, упакованные массивы, польская запись.

Кодирование списком. Одна ячейка списка – 3 значения: 1)указатель на сам узел, 2) указатель на левый узел, 3) указатель на правый узел. Таким образом, объем памяти n=3p. Очень удобно восстанавливать исходное упорядоченное дерево.

Упакованные массивы. Все узлы располагаются в массиве, так что все узлы поддерева данного узла располагаются вслед за этим узлом. Вместе с каждым узлом хранится индекс узла, который является последним узлом поддерева данного узла. Дерево Т обычно определяется следующим образом: Т: array [l..p] of record i: info, k: l..p end record. Для этого представления n(р) = 2р.

Польская запись. Первый элемент – указатель на узел, второй – условный код: 0 – нет потомков, 1 – есть левый потомок, 2- есть правый потомок, 3 – есть оба потомка. Наиболее компактная запись, так как тройка в двоичном коде – это 11. Поэтому общий объем памяти n<=2p. Но ходить по такому дереву сложнее, чем при кодировании списком. Это удобная запись именно для бинарных деревьев.

61.Булевы функции
булева функция – это функция, и аргументы и значение которой принадлежит множеству { 0, 1 }.

Произвольная булева функция задается одним из трех способов: матричным (табличным), геометрическим и аналитическим.При матричном способе булева функция f (х1,...,хn) задается таблицей истинности, в левой части которой представлены все возможные двоичные наборы длины n, а в правой указывается значение функции на этих наборах.

При геометрическом способе булева функция f (х1,..., хn) задается с помощью n-мерного куба. В геометрическом смысле каждый двоичный набор у = <y1, y2,...,yn> yi E {0,1} есть n-мерный вектор, определяющий точку n-мерпого пространства. Исходя из этого, все множество наборов, на которых определена функция n переменных, представляется вершинами n-мерного куба. Отмечая точками вершины куба, в которых функция принимает единичное (либо нулевое) значение, получим геометрическое представление функции.
При аналитическом способе булева функция задается формулами, т. е. аналитическими выражениями, построенными на основе операций булевой алгебры.

Замена переменных и суперпозиция
Пусть f(x1, x2,..., xn) - заданная функция алгебры логики. Будем говорить, что функция j(y1, y2,..., yn) получена операцией замены переменных из функции f(x1, x2,..., xn), если осуществлена подстановка переменных

Пусть имеется функция f(x₁, x₂,..., x_n) и функци ,

тогда функцию

будем называть суперпозицией функции f(x₁, x₂,..., x_n) и функций

Другими словами: пусть F = { fj } - набор функций алгебры логики, не обязательно конечный. Функция f называется суперпозицией функций из множества F или функцией над F, если она получена из функции

путем замены одной или нескольких ее переменных функциями из множества F.

Булева функция y=f(x1,x2... xn) существенно зависит от переменной xk, если существует такой набор значений a1,a2... ak-1, ak+1, ak+2... an, что f(a1,a2... ak-1, 0, ak+1, ak+2... an) ≠ f(a1, a2... ak-1, 1, ak+1, ak+2... an).
В этом случае xk называют существенной переменной

Переменная является несущественной, если ее изменение не изменяет значения функции.