Запрограммировать на языке Пролог следующие 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. В узлах дерева находятся метки -элементы произвольного скалярного типа (в приведенном примере - символьные атомы).
 | |||
|
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 - тернарный функторы.
 | |||||||
| |||||||
| |||||||
|
В нижеследующем описании предикатов используется неявный способ задания графа, Х и 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 - структура, представляющая граф.
