- •Программирование и алгоритмические языки. Курс за второй семестр. Абстрактные типы данных.
- •Задача о раскраске.
- •Перечисление последовательностей фиксированной длины.
- •Var I:tСтраны; c:tЦвет;
- •Два взгляда на диаграммы – графы и автоматы.
- •Деревья
- •Как сократить перебор с возвратом. Перечисление последовательностей переменной длины
- •Словарный порядок на последовательностях произвольной длины
- •Статическая реализация стеков.
- •Очереди. Статическая реализация.
- •Статическая реализация деревьев.
- •Автоматы как структуры данных
- •Статическая реализация графов. Проблема фрагментации памяти. Списочные структуры.
- •Общая схема реализации автомата как списка.
- •Обработка кучи.
- •Динамическая реализация абстрактных типов ссылками. Ссылочные типы Паскаля.
- •Ссылочные типы Паскаля. Синтаксис типов.
- •Объявление списочной структуры в Паскале.
- •Реализация стеков.
- •Реализация очередей.
- •Основные операции над списками.
- •Обработка деревьев. Деревья выражений.
- •Поиск атома.
- •Различные объединения типов. Записи типов с вариантами.
- •Создание дерева. Перевод из префиксной записи. Представление записи.
- •Анализ алгоритма вычисления. Дерево как последовательность ветвей.
- •Задача синтаксического анализа.
- •Графы-выражения.
- •Раздельное описание абстрактных типов. Модульное программирование.
- •Проблема с кратным использованием модулей.
- •Деревья как структуры данных.
- •Деревья поиска.
- •Поиск в дереве поиска.
- •Включение в дерево поиска.
- •Другие обходы дерева. Обход в ширину.
- •Рекурсивные процедуры и функции. Примеры применения.
- •Поиск в дереве.
- •Проблемы с семантикой рекурсии.
- •Введение в машинно-ориентированное (ссылочное) программирование. Оператор Goto.
- •Создание новых структурных операторов.
- •Формальная семантика goto и неструктурных программ.
- •Мини-Паскаль.
- •Представление сложных типов. Адресная арифметика.
- •Проблемы реализации ввода-вывода. Идея буферизации.
- •Реализация процедур read и write.
- •Реализация структур управления.
- •Путь наверх. Реализация процедур-подпрограмм.
- •Передача параметров.
- •Сохранение и восстановление значений. Соглашение о связях.
- •Введение в теоретическое программирование. Границы программирования. Принципиальная и практическая неразрешимость.
- •О формальной спецификации. Мир задачи как автомат.
- •Процедуры как функции на множестве состояний. Процедуры как преобразователи предикатов.
- •Универсальные методы решения задач.
О формальной спецификации. Мир задачи как автомат.
Вернёмся к фундаментальному понятию типа данных в качестве модели описания статики и динамики произвольных объектов. Статика описывается множеством состояний, а динамика – множеством операторов.
Мир=<состояния, переменные >
Можно воспринимать такую модель как автомат.
Аппликация: состояние переменные → состояние
Теперь можно специфицировать любую задачу как алгоритм нахождения пути в автомате из некоторого множества начальных состояний в некоторое множества желаемых состояний.
Процедуры как функции на множестве состояний. Процедуры как преобразователи предикатов.
Итак, любая задача может быть сформулирована как определение некоторого оператора (процедуры), который на данном множестве значений (состояний) принимает значения из другого заданного множества. При описании этих множеств нужно использовать либо язык теории множеств, либо логический язык (в силу двойственности языка теории множеств и языка матлогики).
Найти процедуру P такую, что:
{а – произвольный массив}={a=A0 & A0[1..10]real}
P
{a – упорядоченный массив}={a=A1 & i1..9 a[i]a[i+1]}& перестановка (A0,A1)
i1..10 (A1[i]A0) & j1..10 (A0[j]A1)
Постановка спецификации есть функция на множествах состояний. Решение есть процедура, то есть функция на состояние.
Задача поиска. Задан массив…
{a=ANreal} & xReal;
P-?
{xi : x=A[i]}
Любая P, удовлетворяющая этому свойству (находящая значение i с заданным свойством), будет решением.
Вернёмся к нашим обезьянам…
Мир задачи в этом случае описывается в терминах состояния каждого объекта относительно других:
1) Состояние обезьяны относительно комнаты.
Содержательное описание:
- имя переменной: обезьяна ХУ;
- множество значений: {у двери, у окна, в середине}
2) Обезьяна относительно ящика:
- имя переменной: обезьяна Z;
- множество состояний: {на ящике, на полу}
3) Ящик относительно комнаты:
- имя переменной: ящик ХУ;
- множество состояний: {совпадает с множеством значений обезьяна ХУ}
4) Банан относительно обезьяны:
- имя переменной: банан;
- множество значений: {висит, у обезьяны}
Состояние мира задачи определяется совокупностью состояний отдельных объектов, значениями переменных, соответствующих объектам.
Мир в этом случае – 4 переменные:
1) Обезьяна ХУ {у двери, у окна, в середине};
2) Обезьяна Z {на ящике, на полу};
3) Ящик ХУ {у двери, у окна, в середине};
4) Банан {висит, у обезьяны}.
Множество состояний – именованное декартово произведение.
Множество исходных состояний: любое состояние мира, в кот. мир(банан)=висит.
Множество конечных состояний: любое состояние, в кот. мир(банан)=у обезьяны.
Определение задачи заканчивается определением допустимых действий, процедур преобразования состояний.
type wState=record
ОбезьянаХY: tОбезьянаХY;
ОбезьянаZ: tОбезьянаZ;
ЯщикXY: tЯщикХY;
Банан: tБанан;
end;
procedure Схватить(var s:wState);
begin
with s do
if (банан=висит) and (обезьянаXY=середина) and (обезьянаZ=на ящике)
then банан:=у обезьяны;
end;
procedure Залезть(var s:wState);
begin
with s do
if ящикXY=обезьянаXY…
procedure Подвинуть(var s:wState; p1,p2:tОбезьяна);
{Подвинуть ящик из точки p1 в точку p2}
{Очевидно, соответствует более компактному описанию семейства функций}
begin
with s do
begin
if (ящикXY=обезьянаXY) and (обезьянаXY=p1) then
begin
обезьянаXY:=p2;
ящикXY:=p2;
end;
end;
procedure Перейти(var s:wState; p1,p2:обезьянаXY);
{Обезьяна переходить из точки p1 в точку p2}
begin
with s do
if обезьянаXY=p1 then обезьянаXY:=p2;
end;
1) Строго говоря, мы хотим, чтобы спецификация состояний и процедур была не частью программы, но входными данными.
2) Как решать задачу?
Входом должна быть последовательность обращения к процедурам.