Курс за второй семестр. Абстрактные типы данных

Вид материала

Содержание

Два взгляда на диаграммы – графы и автоматы.
Х – выделенная переменная, произвольный массив. Остальные переменные не определены. Выход: любое состояние, в котором Х
Как сократить перебор с возвратом. Перечисление последовательностей переменной длины

Подобный материал:

1 2 3 4 5 6 7 8

Begin

Кончились:=false;

i:=последняя страна;

c:=раскраска[i];

while not Кончились and (раскраска[i]последний цвет) do

Begin

Раскраска[i]:=первый цвет;

i:=i-1;

кончились:=i=0;

if not Кончились then раскраска[i]:=succ(раскраска[i]);

end;

{Поддерживается быстрое вычисление конъюнкции}

Упражнение. Завершить первый вариант решения задачи.

Привлекательное своей простотой наше решение грешит единственным недостатком – оно неэффективно. Непосредственный выбор структуры данных под алгоритм игнорирует вопросы компактного хранения. Но основная сложность – эффективность по времени. Полный перебор раскрасок даёт (число цветов – число стран) – экспоненциальный алгоритм. Потратится много времени. Такие алгоритмы в программировании считаются практически невыполнимыми за реальное время.

Вопрос: нужно ли было писать такой алгоритм???

Ответ: несомненно, ДА!!!

Правильные программы имеет смысл улучшать. Преобразовывать программы эквивалентно проще, чем писать новые, но основной туш таков: достоинство плохих решений – простые решения универсальны и служат исходной точкой для решения очень широкого круга задач. Теория даёт простые решения.

Два взгляда на диаграммы – графы и автоматы.

Нахождение решений как поиск пути в графе. Полный перебор как универсальный алгоритм.

Графом называется некоторое множество вершин Х, соединённых рёбрами F.

GraphXXV

С каждым графом можно связать функцию, ставящую в соответствие каждой паре вершин некоторое ребро (либо его отсутствие). Для этого нужно ввести некоторое неопределённое значение. В самом простом случае интересно лишь наличие, либо отсутствие ребра, т.е. функция вида Graph(i,j)=trueboolean. Это в классической дискретной математике определение графа как отношения или двуместного предиката.

Graph(i,j)=true – существует стрелка из вершины i в вершину j. Отношение соседства из задачи по раскраске – пример именно такого определения графа.

Англия

Это пример неориентированного графа или симметричного отношения.

 Франция



Италия

i,j Graph(i,j)=Graph(j,i)

В программировании стандартным способом задания графа является двуместные массивы, обычно булевские. Иной взгляд на диаграммы даёт их понимание как транспортные схемы. Автоматом назовём соответствие вида

Automaton: XFF

Automaton(x,f)=x^|, если ребро f ведёт из вершины х в вершину x^|. Или, в терминологии теории автоматов, событие f переводит из состояния х в состояние x^|.

Путём называется произвольная последовательность элементов из множества F. Функции Graph и Automaton очевидным образом продолжаются на множество всех путей F^*. Другая интерпретация (трактовка) элементов множества F – преобразование состояний (процедура). Функция Automaton(x,f)= x^| - аналог оператора аппликации – применения функции к аргументу.

Пусть задан некоторый автомат, а также предикаты Вход и Выход.

Вход: XBoolean

Выход: XBoolean

Состояния, на которых эти предикаты верны, называются входными и выходными.

Задача. Для данного автомата и предикатов Вход и Выход определить множество путей их каждого входного состояния некоторое выходное.

Это универсальная спецификация любой

задачи.

Пример: Сортировка массивов.

Множество состояний – множество всех состояний программы.

Вход: произвольное состояние, где Х – выделенная переменная, произвольный массив. Остальные переменные не определены.

Выход: любое состояние, в котором Х – перестановка начального состояния в упорядоченный массив.

Назовём задачу предыдущего вида (универсальный) конечной, если конечно множество состояний автомата (множество вершин графа). Полный перебор пути есть универсальный алгоритм решения любой конечной задачи.

Следствие: программисты не нужны! 

Но следствие неверно, поскольку

существуют бесконечные задачи;
универсальный алгоритм даёт реально невыполнимые решения.

Деревья

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

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

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

корень

t1 1 t1,t2,t3,…

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

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

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

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

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

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

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

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

Blog