Курс за второй семестр. Абстрактные типы данных
Вид материала | Задача |
- Программа дисциплины программирование на языке С++ для направления 080700. 62 «Бизнес-информатика», 131.2kb.
- Методические указания для студентов 1 курса факультета математики, механики и компьютерных, 439.36kb.
- Курс биологи,1 семестр ) фен 26 ч. ((1 курс химики, 2 семестр 2 курс биологи, 2 семестр, 45.56kb.
- Структура программы. Часть Структуры данных. 24. Классификация структур данных. Операции, 41.26kb.
- Курс лекций "Базы данных и субд" Ульянов В. С. Лекция Язык sql. Создание таблиц и ограничений, 146.46kb.
- Borland Turbo Pascal, знать простые основные алгоритмы работы с простыми типами данных, 316.19kb.
- Курс, 1 поток, 5-й семестр лекции (34 часа), экзамен, 52.85kb.
- Программа дисциплины Анализ данных средствами ms excel для направления 080102. 65 Мировая, 121.98kb.
- Крыштановский А. О. Анализ социологических данных, 34.07kb.
- Пояснительная записка, 258.04kb.
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.
GraphXXV
С каждым графом можно связать функцию, ставящую в соответствие каждой паре вершин некоторое ребро (либо его отсутствие). Для этого нужно ввести некоторое неопределённое значение. В самом простом случае интересно лишь наличие, либо отсутствие ребра, т.е. функция вида Graph(i,j)=trueboolean. Это в классической дискретной математике определение графа как отношения или двуместного предиката.
Graph(i,j)=true – существует стрелка из вершины i в вершину j. Отношение соседства из задачи по раскраске – пример именно такого определения графа.
Англия
Это пример неориентированного графа или симметричного отношения.
Франция
Италия
i,j Graph(i,j)=Graph(j,i)
В программировании стандартным способом задания графа является двуместные массивы, обычно булевские. Иной взгляд на диаграммы даёт их понимание как транспортные схемы. Автоматом назовём соответствие вида
Automaton: XFF
Automaton(x,f)=x|, если ребро f ведёт из вершины х в вершину x|. Или, в терминологии теории автоматов, событие f переводит из состояния х в состояние x|.
Путём называется произвольная последовательность элементов из множества F. Функции Graph и Automaton очевидным образом продолжаются на множество всех путей F*. Другая интерпретация (трактовка) элементов множества F – преобразование состояний (процедура). Функция Automaton(x,f)= x| - аналог оператора аппликации – применения функции к аргументу.
Пусть задан некоторый автомат, а также предикаты Вход и Выход.
Вход: XBoolean
Выход: XBoolean
Состояния, на которых эти предикаты верны, называются входными и выходными.
Задача. Для данного автомата и предикатов Вход и Выход определить множество путей их каждого входного состояния некоторое выходное.
Это универсальная спецификация любой
задачи.
Пример: Сортировка массивов.
Множество состояний – множество всех состояний программы.
Вход: произвольное состояние, где Х – выделенная переменная, произвольный массив. Остальные переменные не определены.
Выход: любое состояние, в котором Х – перестановка начального состояния в упорядоченный массив.
Назовём задачу предыдущего вида (универсальный) конечной, если конечно множество состояний автомата (множество вершин графа). Полный перебор пути есть универсальный алгоритм решения любой конечной задачи.
Следствие: программисты не нужны!
Но следствие неверно, поскольку
- существуют бесконечные задачи;
- универсальный алгоритм даёт реально невыполнимые решения.
Деревья
Назовём автомат инициальным, если выделено некоторое начальное состояние Ø такое, что любое другое состояние достижимо из него: xX sF* : (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, или класс всех функций NT.
Дерево позиционное, если на входном алфавите, т.е. на множестве F, зафиксирован некоторый линейный порядок (сравнение). Например, F={0<1} или F={1<0}. Это позволяет нам говорить о старшинстве в одном поколении. Если же это сравнение определяет порядковый тип, то таким же (порядковым) будет и произвольный класс путей в лексикографическом (словарном) порядке.
Упражнение. Определить во введённых нами терминах какой-либо однозначный порядок наследования имущества.
Как сократить перебор с возвратом. Перечисление последовательностей переменной длины
Вернёмся к задаче о раскраске. Идея её проста – перебирать и проверять неполные, незаконченные раскраски, т.е. все последовательности c1…ck, kn, n – число стран. Если неполная раскраска неправильна, то нет смысла перебирать раскраски большей длины, надо искать новый вариант – возврат.