Постановка задачи. Запрограммировать на языке Пролог следующие 20 предикатов, которые разбиты на 4 группы

Запрограммировать на языке Пролог следующие 20 предикатов, которые разбиты на 4 группы. При определении этих предикатов указывается условие их истинности.

 

I. Предикаты для работы со списками

Аргументы L1, L2, L3 обозначают списки, Е - некоторый элемент списка (тип элементов списка произволен), N - порядковый номер элемента в списке.

 

1. append (L1, L2, L3): список L3 является слиянием (конкатенацией) списков L1 и L2;

2. reverse (L1, L2): L2 - перевернутый список L1;

3. delete_first (E, L1, L2): список L2 получен из L1 исключением первого вхождения в него элемента Е;

4. delete_all (E, L1, L2): L2 - это список L1, из которого удалены все вхождения элемента Е;

5. delete_one (E, L1, L2): L2 - список L1, в котором исключен один элемент Е (исключается какое-то одно вхождение Е в список L1);

6. no_doubles (L1, L2): L2 - это список, являющийся результатом удаления из L1 всех повторяющихся элементов;

7. sublist (L1, L2): L1 - любой подсписок списка L2, т.е. непустой отрезок из подряд идущих элементов L2;

8. number (E, N, L): N - порядковый номер элемента E в списке L;

9. sort (L1, L2): L2 - отсортированный по не убыванию список чисел из L1;

 

II. Предикаты для работы с множествами

Аргументы М1, М2, М3 обозначают множества, которые представляются в виде списков элементов без повторений, порядок элементов в них несущественен, тип элементов - произволен.

 

10. subset (М1, М2): множество М1 является подмножеством М2;

11. union (М1, М2, М3): множество М3 - объединение множеств М1 и М2; вместо этого предиката может быть взят предикат

intersection (М1, М2, М3): М3 - пересечение М1 и М2, или subtraction (М1, М2, М3): М3 - разность М1 и М2.

III. Предикаты для работы с бинарными деревьями

Аргументы Т, Т1 и Т2 обозначают деревья, представляемые в виде термов, которые записываются с помощью тернарного функтора

tree (<левое поддерево>, <правое поддерево>, <метка>)

и константы nil (пустое дерево). К примеру,

tree (tree (nil, nil, f), tree (tree(nil, nil, p), tree (nil, nil, r), k))

представляет дерево, изображенное на рис.1. В узлах дерева находятся метки -элементы произвольного скалярного типа (в приведенном примере - символьные атомы).

 

		Рис. 1

 

 

12. tree_depth (Т, N): N - глубина дерева (т.е. количество ребер в самой длинной ветви дерева);

13. sub_tree (Т1, Т2): дерево Т1 является непустым поддеревом дерева Т2;

14. flatten_tree (Т, L): L - список всех меток-узлов дерева Т («выровненное» дерево);

15. substitute (Т1, V, Т, Т2): Т2 - дерево, полученное заменой всех вхождений элемента V в дереве Т1 на терм Т.

 

IV. Предикаты для работы с графами

Граф может быть представлен либо явно - в виде одной структуры, либо неявно - набором фактов вида edge (P, R, N), устанавливающих наличие ребра (дуги) между вершинами (узлами) P и R и задающее стоимость N (целое неотрицательное число) этого ребра. При явном способе представления графа он задается термом, включающим в свой состав список ребер и список вершин графа.

Граф, изображенный на рисунке 2, может быть задан неявно фактами

edge(a, c, 8), edge(a, b, 3), edge(c, d, 12), edge(b, d, 0),(e, d, 9),

а в явной форме он может быть задан термом

graph([edge(a, c, 8), edge(a, b, 3), edge(c, d, 12), edge(b, d, 0),edge(e, d, 9)], [a, b, c, d, e]),

где graph - бинарный, а e dge - тернарный функторы.

			c
	е
		Рис. 2

 

В нижеследующем описании предикатов используется неявный способ задания графа, Х и Y обозначают вершины графа, а L - список вершин.

 

16. path (Х, Y, L): L - путь без циклов между вершинами Х и Y, т.е. список вершин между этими вершинами;

17. min_path (Х, Y, L): L - путь между вершинами Х и Y, имеющий минимальную стоимость (стоимость пути равна сумме стоимостей входящих в него ребер);

18. short_path (Х, Y, L): L - самый короткий путь между вершинами Х и Y (длина пути равна количеству входящих в него ребер);

19. cyclic: граф является циклическим (т.е. не является деревом);

20. is_connected: граф является связным (т.е. для любых двух его вершин существует связывающий их путь).

 

Замечания:

1) В предикатах 16-19 граф предполагается связным и может содержать циклы;

2) Все вышеописанные предикаты группы IV для явного способа представления графа должны содержать дополнительный аргумент - сам граф, например: path (G, X, Y, L), где G - структура, представляющая граф.