Задание и методические рекомендации

Типы данных являются рекурсивными, если они допускают, чтобы в его структуре данных была рекурсия.

Примером рекурсивного типа данных является бинарное дерево. Бинарное дерево либо пусто, либо состоит из следующих трех частей:

- корень;

- левое поддерево;

- правое поддерево.

Где левое и правое поддеревья сами являются бинарными деревьями. Таким образом, рекурсивность бинарного дерева заложена уже в его определении.

Бинарное дерево упорядочено, если в нем все вершины левого поддерева меньше корня, все вершины правого поддерева больше корня, и оба поддерева также упорядочены. Такое дерево называется бинарным справочником. Преимущество упорядочивания состоит в том, что для поиска некоторого объекта в бинарном справочнике достаточно просмотреть не более одного поддерева.

Стоит заметить, что поиск в двоичном справочнике наиболее эффективен для сбалансированного дерева, то есть дерева, в котором два поддерева содержат примерно равное количество элементов. Если же дерево полностью разбалансировано, то поиск в нем так же неэффективен, как и поиск в списке.

Опишем предикаты для создания и модификации бинарного дерева. Бинарное дерево задается с помощью функтора

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_righ t(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 приложениях.