Деревья

Назовём автомат инициальным, если выделено некоторое начальное состояние 0 такое, что любое другое состояние достижимо из него:  xX  sF^* : (Automaton(0,s)=x).

Деревом называется инициальный автомат T, в котором разные пути приводят в разные состояния: s,s^| F^* (T(0,s)T(0,s^|)).

Обычно деревья связывают не только собственно с деревьями, но с генеалогическим древом, что подсказывает терминологию. Начальное состояние – корень, конечное – листья.

корень

t1 t1,t2,t3,…

0 1 Пример бинарного дерева F={0,1}

родители(предки)дети(потомки)

Упражнение. 1) Дать определение дерева на языке теории графов (т.е. в терминах соединения вершин). 2) Дать формальное определение родственной терминологии (родители, дети, дядья, кузены, деды, внуки).

Фундаментальный пример дерева даёт класс всех последовательностей некоторого базового типа T, или класс всех функций NT.

Дерево позиционное, если на входном алфавите, т.е. на множестве F, зафиксирован некоторый линейный порядок (сравнение). Например, F={0<1} или F={1<0}. Это позволяет нам говорить о старшинстве в одном поколении. Если же это сравнение определяет порядковый тип, то таким же (порядковым) будет и произвольный класс путей в лексикографическом (словарном) порядке.

Упражнение. Определить во введённых нами терминах какой-либо однозначный порядок наследования имущества.

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

Вернёмся к задаче о раскраске. Идея её проста – перебирать и проверять неполные, незаконченные раскраски, т.е. все последовательности c₁…c_k, kn, n – число стран. Если неполная раскраска неправильна, то нет смысла перебирать раскраски большей длины, надо искать новый вариант – возврат.

Словарный порядок на последовательностях произвольной длины

c₁…c_k  c₁^|…c^|_L, т.е.  i₀ (c_i0c_i0^| and ii₀ (c_i=c^|_I) or (i (c_i=c_i^|) and k<L)

Технический приём: дополнить меньшее слово фиктивным элементом, например пробелом, наименьшим по определению.

можно:=false;

pаскраска:=Первая раскраска; {<первый цвет>}

while (не кончилась раскраска) do

begin

{Пустая раскраска – последовательность длины 0}

if правильная (раскраска) then if полная (раскраска) then

begin

можно:=true {печать (раскраска)}

else {раскраска правильная, но не полная}

{дополнить} раскраска:=раскраска + первый цвет

else {возврат} раскраска:=succ(раскраска);

end;

end;

Переход к следующей раскраске при новом определении словарного порядка:

1. Выбрасывать все последние значения с конца последовательности до тех пор, пока не выкинем первый элемент, у которого есть следующий. Если такого нет, то раскраска кончилась.

2. Если раскраски не кончились, возвратить следующий за последним, выкинутым в раскраску.

Последовательность, из конца которой можно выкидывать и в конец которой можно добавлять элементы, называется стеком (stack).

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

1. Push ([x:tStack], y:T), х – имя стека, затолкнуть y в стек.

Семантика: x:=x+y (добавление элементов в конец последовательности)

2. Pop ([x:tStack],y:T), x – имя стека, извлечь y из стека.

if x=c₁…c_n then pop=c_n. Длина стека уменьшается на 1: x=c₁…c_n-1.

Попытка взять элемент из пустого стека считается ошибкой.

3. Empty ([x:tStack]):boolean; – стек пуст.

if Empty([x:tStack]){=true} then {длина стека равна нулю}.

4. Характерные для динамических типов операции Create([x:tStack]) и Destroy([x:tStack]) рассмотрим позднее.

Стеки также называют «магазинной» памятью.

Переход к следующей раскраске, если такой нет, то к пустой.

procedure Новая (var раскраска:tStack);

var x:tЦвет;

Begin

pop(stack,x);

while not empty(stack) and (x=последний цвет) do pop(stack,x);

if not empty(stack) then push(succ(x));

End;

Дополнить раскраску=push(stack,первый цвет)

Кончились раскраски – empty(stack)

Упражнение. Завершить реализацию перебора с возвратом, написав процедуру «Правильная».

c₁…c_k+1 – правильная, то c₁…с_k – правильная.

i[1,k] (соседи(c_k,c_k+1))

раскраска(1)раскраска(k+1)

(Выходим за пределы стековых операций).