1. Исходные тексты программ на языке Пролог.
2. Наборы тестовых данных и результаты работы программ.
3. Перечень и анализ ошибок.
4. Выводы по работе.
Методические указания к занятию №4.
Бинарные деревья
2.1 Цель СРСП
1. Научиться описывать рекурсивные типы данных.
2. Выработать навыки представления структур в виде дерева.
1. Решить задачу соответствующего варианта.
2. Подобрать тестовые данные и протестировать программу на компьютере.
3. Составить отчет о проделанной работе.
Задание и методические рекомендации
Типы данных являются рекурсивными, если они допускают, чтобы в его структуре данных была рекурсия.
Примером рекурсивного типа данных является бинарное дерево. Бинарное дерево либо пусто, либо состоит из следующих трех частей:
- корень;
- левое поддерево;
- правое поддерево.
Где левое и правое поддеревья сами являются бинарными деревьями. Таким образом, рекурсивность бинарного дерева заложена уже в его определении.
Бинарное дерево упорядочено, если в нем все вершины левого поддерева меньше корня, все вершины правого поддерева больше корня, и оба поддерева также упорядочены. Такое дерево называется бинарным справочником. Преимущество упорядочивания состоит в том, что для поиска некоторого объекта в бинарном справочнике достаточно просмотреть не более одного поддерева.
Стоит заметить, что поиск в двоичном справочнике наиболее эффективен для сбалансированного дерева, то есть дерева, в котором два поддерева содержат примерно равное количество элементов. Если же дерево полностью разбалансировано, то поиск в нем так же неэффективен, как и поиск в списке.
Опишем предикаты для создания и модификации бинарного дерева. Бинарное дерево задается с помощью функтора
tree(K, LeftT, RightT),
где К – элемент, находящийся в вершине; LeftT и RightT – левое и правое поддерево соответственно.
create_tree(A, tree(A, empty, empty)). % создание дерева
insert_left(X, tree(A, _, B), tree(A, X, B)). % включение элемента данных A, как левого поддерева B
insert_right(X, tree(A, B, _), tree(A, B, X)). % включение элемента данных A, как правого поддерева B
Для обхода бинарного дерева «сверху вниз» опишем предикат:
up_to_down(tree(X, LTr, RTr), Xs) :- up_to_down(Ltr, Ls), up_to_down(RTr, Rs), append([X|Ls], Rs, Xs).
up_to_down(empty, []).
append – это процедура append(LeftList, RightList, ListRes), где ListRes является результатом слияния списков LeftList, RightList.
Аналогичным образом можно описать процедуру обхода дерева «снизу вверх», «слева направо».
Фрагмент программы печатает все элементы, проходя его «в глубину».
show_tree(nil).
show_tree(tree(X,Left,Right)):-write(X),show_tree(Left), show_tree(Right).
1. Составить программу, которая решает задачи соответствующего варианта.
2. Предусмотреть в программе возможности автоматического ввода/вывода деревьев.
3. Подобрать тестовые данные, проверяющие работу программы.
4. Провести анализ ошибок и полученных результатов, составить отчет о проделанной работе.
1. Подсчитать длину максимального пути и выдать его трассировку.
2. Выдать метки всех вершин с их кратностями.
3. Построить деревянное покрытие графа.
4. Выделить метку вершины дерева, имеющую наибольшее число вхождений.
5. В указанном ярусе дерева добавить вершину с указанной меткой.
6. Составить программу, реализующую сортировку линейного числового списка на основе бинарного отсортированного дерева.
7. Проверить дерево на изоморфизм.
8. Для связного графа построить деревянное покрытие, начиная с указанной вершины.
9. Выделить в дереве все поддеревья с указанной меткой.
10. Реализовать обход дерева в ширину с выдачей меток.
11. Удалить вершину с указанной меткой, в случае отсутствия указанной метки выдать сообщение о невозможности удаления.
12. Реализовать обход дерева в глубину с выдачей меток.
13. Реализовать поиск в дереве данного поддерева.
14. Подсчитать количество вхождений в дерево данной метки.
15. Выделить в дереве максимальное поддерево с заданной меткой.
16. Подсчитать количество вершин дерева. Выдать наиболее длинный путь дерева.
17. Подсчитать в дереве количество совпадающих вершин.
18. Выдать элемент бинарного дерева, который имеет в нем наибольшее число вхождений.
19. Сравнить два дерева на изоморфизм.
20. Построить дерево по алгебраическому выражению.
1. Исходные тексты программ на языке Пролог.
2. Наборы тестовых данных и результаты работы программ.
3. Перечень и анализ ошибок.
4. Выводы по работе.
Методические указания к занятию №5.
Работа с динамическими базами данных
Ознакомиться с реализацией динамических баз данных в языке Пролог.
Изучить лекционный материал.
1. Решить задачу соответствующего варианта.
2. Подобрать тестовые данные и протестировать программу на компьютере.
3. Составить отчет о проделанной работе.
Задание и методические рекомендации
Реляционная модель данных предполагает, что база данных – это есть описание некоторого множества отношений. Пролог-программу можно рассматривать как такую базу данных, здесь отношения между данными представлены в виде фактов и правил. В Прологе есть специальные средства для модифицирования этой базы данных, то есть добавлять и удалять новые отношения из файла. Для этих целей служат встроенные предикаты [1, 5]:
consult(F) – все предложения, содержащиеся в файле будут использоваться Пролог-машиной для достижения целей.
reconsult(F) – если в файле есть предложения, касающиеся отношений, которые уже были определены ранее, старые отношения заменяются на новые из файла.
assert(C) – добавляет предложение C из базы данных.
retract(C) – удаляет предложение C из базы данных.
asserta(C) – помещает предложение C в начале базы данных.
assertz(C) – помещает предложение C в конце базы данных.
see(F) – делает файл F текущим входным потоком.
tell(F) – файл становиться текущим выходным потоком.
seen – закрывает текущий входной поток.
told – закрывает текущий выходной поток.
Программа добавляет и удаляет из базы данных новый факт.
add :- write('Введите имя мужчины: '),
read_string(S),
assertz(man(S)).
out :- write('Список имен мужчин:\n'),
man(S),write(S),nl.
del :- write('Введите имя мужчины: '),
read_string(S),
retractall(man(S)).
main :- consult('db.pro'),add,out,del,out.
Файл db.pro первоначально содержит следующие факты:
man(oleg).
woman(zina).
man(alexandr).
man(petr).
1. Составить программу, которая решает задачу соответствующего варианта.
2. Подобрать тестовые данные, проверяющие работу программы.
3. Провести анализ ошибок и полученных результатов, составить отчет о проделанной работе.
1. Исходные тексты программ на языке Пролог.
2. Наборы тестовых данных и результаты работы программ.
3. Перечень и анализ ошибок.
4. Выводы по работе.
Методические указания к занятию №6
Использование возможностей логического сервера AMZI! Prolog в среде Delphi
1. Научиться использовать Пролог в Delphi приложениях.
2. Выработать навыки использования Пролога в DELPHI приложениях.
Изучить материал по теме «Компонент LSEngine»
1. Решить задачу соответствующего варианта.
2. Подобрать тестовые данные и протестировать программу на компьютере.
3. Составить отчет о проделанной работе.
Задание и методические рекомендации
Amzi! Prolog не предоставляет достаточно удобного интерфейса для работы с базой данных. Но возможности языка Amzi! Prolog можно использовать и в других языках и средах программирования, например Borland Delphi. В состав пакета Amzi! Prolog входит компонент, написанный для использования в Delphi (LSEngine). С помощью свойств и методов этого компонента разработчик приложения может производить запросы к откомпилированной базе данных Пролога.
Для работы с базой данных на Прологе в среде Delphi данный компонент необходимо поместить на форму приложения.
Этот компонент содержит большое количество методов, позволяющих производить запросы, модифицировать динамическую базу данных, работать с потоками и т.п. Ниже приведены часто используемые процедуры и функции для работы с компонентом LSEngine.
Процедуры для подключения Пролога к приложению
procedure Init(xplname: String);– инициализация базы;
procedure InitLS(xplname: String); – инициализация базы;
procedure InitLSXP(p: pointer);– инициализация базы;
procedure InitLSX; – инициализация базы;
procedure AddLSX(lsxname: String); – добавление базы;
procedure AddPred(pname: String; parity: TArity; pfunc: TExtPred); – добавление предиката;
procedure InitPreds(PIptr: TPredInitPtr);– инициализация предиката;
procedure Load(xplname: String);– чтение базы из файла;
procedure LoadXPL(xplname: String);– чтение базы из файла;
function Main: Boolean;– доказательство главной цели;
procedure Reset;– сброс базы;
procedure Close;– закрытие базы;
procedure CloseLS;– закрытие базы.
Функции и параметры предикатов
procedure GetParm(n: integer; dt: TDType; p: pointer);– получение параметра;
function GetPStrParm(n: integer): string;– получение строкового параметра;