Файл: Учебные пособия по логическому и функциональ ному программированию В. М. Зюзькова. В пособие внесены изменения в 2020 г.pdf

3.
ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
Почти все наши ошибки, в сущности, языково-
го характера. Мы сами создаем себе трудно-
сти, неточно описывая факты. Так, например,
разные вещи мы называем одинаково и,
наоборот, даем разные определения одному и
тому же.
Олдос Хаксли
3.1. Контроль обучения
В процессе дистантного обучения дисциплине "Логическое программи- рование" студент должен выполнить три контрольных задания, курсовую ра- боту и обучение заканчивается выполнением компьютерной экзаменационной работы. Контрольные задания представлены ниже и состоят каждое из двух задач, требующих составить программы на Прологе. Составленные и отла- женные программы (обязательно с комментариями) студент по мере освоения логического программирования периодически пересылает по электронной почте диспетчеру центра дистантного обучения, который в свою очередь пе- ресылает их лектору. Лектор проверяет программы и при правильном выпол- нении программы студент получает подтверждение о том, что они зачтены.
Если программа составлена неправильно, студент получает от лектора тек- стовый файл, в котором содержится описание ошибок программы.
3.2. Инсталляция SWI-Prolog'а
Интерпретатор с языка Пролог представлен в виде упакованного файла pl.arj. SWI-Prolog работает в среде Windows (3.11 или 95); для его установки на компьютере достаточно распаковать файл pl.arj вместе со всеми хранящи- мися в этом файле каталогами. Запустите файл pl.exe из каталога pl\bin и вы войдете в интерпретатор. Пролог выдает приглашение "?-" и ждет вашего ввода.
Чтобы набирать программы, надо воспользоваться каким-либо внеш- ним текстовым редактором (SWI-Prolog не имеет собственного редактора).
Например, вы можете пользоваться стандартной программой Notepad ("блок- нот"). Набранные программы сохраняйте в виде текстовых файлов с расши- рением pl (но можно и расширение txt) в рабочем каталоге. По умолчанию рабочим каталогом будет pl\bin, но вы можете это изменить: для этого со- здайте ярлык для pl.exe и измените рабочий каталог в свойствах этого ярлыка.
Чтобы загрузить программу из файла c:\pl\work\name.pl, находясь в среде ин- терпретатора, вы должны в ответ на приглашение "?-" набрать имя файла в квадратных скобках

15
?- [name]. если установлен рабочий каталог - pl\work, или набрать имя файла с полным путем к нему,
?-['c:\pl\work\name.pl']. если установлен другой рабочий каталог. Отметим следующую особенность работы в SWI-Prolog с блокнотом. После набора текста программы обяза- тельно перейдите курсором на новую строчку, иначе SWI-Prolog при загрузке файла с программой выдаст ошибку "неожиданный конец файла".
3.3. Первое контрольное задание
Задание состоит из двух задач, в которых требуется составить програм- мы на Прологе для написания простых предикатов. При составлении про- грамм (если не оговорено противное) можно использовать все встроенные предикаты Пролога. Тексты всех программ, если вы мыслите в духе логиче- ского программирования, получаются небольшие.
SWI-Prolog не имеет стандартного help'а для Windows, для этого ис- пользуется предикат help. Вызов help(<имя предиката>) выдает на экран ин- формацию об этом предикате. Вызов help(7) выдает на экран список всех встроенных предикатов с комментариями. Текстовый файл руководства по
SWI-Prolog - pl\library\manual. Отладку предикатов можно осуществлять с помощью предиката трассировки trace(<имя предиката>), трассировка преди- ката отключается - trace(<имя предиката>, -all).
Пример задания с решением
Задача 1
Постройте предикат position_max(+L, -M, -N), который в списке L находит максимальное значение M и порядковый номер N этого значения.
Задача 2
Определите умножение целых чисел через сложение и вычитание.
Решение
Задача 1
Будем использовать метод накапливающего параметра. Для этого введем вспомогательный предикат position_max(+List, +I, +M0, +N0, -M, -N), где I равен номеру рассматриваемого элемента в исходном списке, M0 - текущее значение максимума, N0 - позиция текущего максимума. position_max([X|T],M,N):- position_max(T,1,X,1,M,N). position_max([],_,M,N,M,N).

16 position_max([A|T],I,X,_,M,N):-
A>X,
K is I+1, position_max(T,K,A,K,M,N). position_max([A|T],I,X,Y,M,N):-
A= K is I+1, position_max(T,K,X,Y,M,N).
?- position_max([3,2,5,1,4,3],M,N).
M = 5
N = 3
Yes
Задача 2
Определим предикат p(+X,+Y,?R), где X и Y сомножители, R - произведение.
Делаем рекурсию по второму аргументу предиката, используя рекурсивное определение X*Y=X*(Y-1)+X. p(X,0,0). p(X,Y,R):- Y>0,
Y1 is Y-1, p(X,Y1,R1),
R is R1+X. p(X,Y,R):- Y<0,
Y1 is -Y, p(X,Y1,R).
Варианты заданий
Вариант 1 1. Определите возведение в целую степень через умножение и деление.
2. Напишите предикат p(+L, -N) - истинный тогда и только тогда, когда N - предпоследний элемент списка L, имеющего не менее двух элементов.
Вариант 2 1. Напишите предикат p(+X, +N, -L) - истинный тогда и только тогда, когда L
- список из N раз повторенных элементов X.

17 2. Напишите предикат p(+L, -S) - истинный тогда и только тогда, когда S - список списков элементов списка L, например, p([a, b, c],[[a], [b], [c]]) - исти- на.
Вариант 3 1. Напишите предикат p(+L, -S) - истинный тогда и только тогда, когда L - список списков, а S - список, объединяющий все эти списки в один.
2. Напишите предикат p(+L, -S) - истинный тогда и только тогда, когда спи- сок S есть циклическая перестановка элементов списка L, например, p([f, g, h, j], [g, h, j, f]) -истина.
Вариант 4 1. Напишите предикат p(+X, +N, +V, -L) - истинный тогда и только тогда, ко- гда список L получается после добавления X на N-е место в список V.
2. Напишите предикат p(+N, +V, -L) - истинный тогда и только тогда, когда список L получается после удаления N-го элемента из списка V.
Вариант 5 1. Напишите предикат p(+V, -L) - истинный тогда и только тогда, когда спи- сок L получается после удаления всех повторных вхождений элементов в список V, например, p([a, b, c, d, d, a], [a, b, c, d]) - истина.
2. Напишите предикат p(+V, -L) - истинный тогда и только тогда, когда спи- сок L получается после удаления из списка V всех элементов, стоящих на четных местах, например, p([1, 2, 3, 4, 5, 6], [1, 3, 5]) - истина.
Вариант 6 1. Напишите предикат p(+V, +X, -L) - истинный тогда и только тогда, когда список L получается из списка V после удаления всех вхождений X на всех уровнях, например, p([1, [2, 3, [1]], [3, 1]], 1, [[2, 3, []], [3]]) - истина.
2. Напишите обобщение предиката member, когда ищется элемент на всех уровнях в списке.
Вариант 7 1. Определите предикат p(+U, +V, -L) - истинный тогда и только тогда, когда список L есть список всех элементов списка U, не содержащихся в списке V.
2. Определите предикат p(+U, +V, -L) - истинный тогда и только тогда, когда
L - список всех элементов, содержащихся либо в списке U, либо в списке V, но не одновременно в U и V.
Вариант 8 1. Определите предикат p(+V, -L) - истинный тогда и только тогда, когда L - список всех элементов списка V, встречающихся в нем более одного раза.

18 2. Напишите предикат subst(+V, +X, +Y, -L) - истинный тогда и только тогда, когда список L получается после замены всех вхождений элемента X в списке
V на элемент Y.
Вариант 9 1. Напишите предикат p(+V, -L) - истинный тогда и только тогда, когда спи- сок L получается из списка V после удаления всех повторяющихся элементов, т. е. из списка получается множество.
2. Напишите предикат exists(+P, +L), который проверяет "Существует ли эле- мент списка L, удовлетворяющий предикату P?"
Вариант 10 1. Напишите предикат all(+P, +L), который проверяет "Для всех ли элементов списка L выполняется предикат P? "
2. Напишите предикат filter(+V, +P, -L) - истинный тогда и только тогда, ко- гда список L есть список всех элементов из списка V, удовлетворяющих пре- дикату P ("фильтрация" списка).
Вариант 11 1.
Используя предикаты "родитель"(Родитель, Отпрыск), "женщи- на"(Человек), "мужчина"(Человек) и "супруги"(Жена, Муж), определите от- ношения теща, шурин и зять.
2. Башня из кубиков может быть описана совокупностью фактов вида "на"(Кубик1, Кубик2), которые истинны, если Кубик1 поставлен на Кубик2.
Определите предикат "выше"(Кубик1, Кубик2), который истинен, если Ку- бик1 расположен на башне выше, чем Кубик2. (Указание: "выше" является транзитивным замыканием отношения "на".)
Вариант 12 1. Напишите предикат gcd(+A,+B,-D) - истинный тогда и только тогда, когда
D -наибольший общий делитель двух целых положительных чисел A и B.
2. Напишите программу для отношения double(+List, -ListList), в котором каждый элемент списка List удваивается в списке ListList, например, double([1,2,3],[1,1,2,2,3,2]) выполнено.
Вариант 13 1. Напишите новую версию предиката length(+L, -N), в котором при подсчете количества элементов списка не учитывается пустой список. К при- меру, для списка [a,b,c,d,e] новая версия процедуры должна сообщить, что длина списка равна пяти, а для списка [a,[],c,d,[]] эта процедура должна да- вать длину, равную трем.
2. Пусть имеется список структур "client":
[client(a,29,3),client(b,29,6),client(c,40,2)].

19
Первым аргументом каждой структуры служит имя клиента, вторым - суточ- ный тариф, а третьим - количество дней, на которое взята автомашина.
Напишите правило, позволяющее вычислить итоговую сумму оплаты, объ- единяющую выплаты всех клиентов, данные о которых содержатся в списке.
Вариант 14 1. Опишите процедуру для предиката расщепить/4, которая берет список це- лых чисел L1 и целое число N и выдает списки L2 и L3 такие, что числа из исходного списка, меньшие, чем N, помещаются в список L2, а остальные - в список L3.
2. Напишите предикат для вычисления чисел Фибоначчи, используя метод накапливающего параметра.
Вариант 15 1. Напишите предикат digits(+N, -L) - истинный тогда и только тогда, когда L
- список цифр натурального числа N.
2. Напишите предикат summa_digits(+N, -S) - истинный тогда и только тогда, когда S - сумма цифр натурального числа N.
3.4. Второе контрольное задание
Задание состоит из двух задач, в которых требуется составить програм- мы на Прологе для написания простых программ. При составлении программ
(если не оговорено противное) можно использовать все встроенные предика- ты Пролога. Тексты всех программ, если вы мыслите в духе логического про- граммирования, получаются небольшие.
Пример задания с решением
Задача 1
Сортировка списка простым обменом (по возрастанию).
Задача 2
Пусть бинарное дерево задается рекурсивной структурой tree(<левое подде- рево>,<корень>,<правое поддерево>) и пустое дерево задано термом nil.
Составьте программу subtree(+S, +T), определяющую, является ли S поддере- вом T.
Решение
Задача 1
Заданный список L сортируется по следующему алгоритму:
(1) если L содержит два соседних элемента, нарушающих требуемое упоря- дочение, то эти элементы меняются местами, после чего к полученному спис- ку применяется этот же алгоритм;

20
(2) если в L не встречается ни одной неупорядоченной пары соседних эле- ментов, то список L отсортирован и тем самым является искомым списком.
Предикат ord(+L) проверяет является ли список L отсортированным. ord([]). ord([_]). ord([X,Y|T]):-
X =< Y, ord([Y|T]). change(L,L):- ord(L),!. change(L,S):- append(L1,[X,Y|L2],L),
X>Y,!, append(L1,[Y,X|L2],Z), change(Z,S).
Отсечения в данном случае ликвидируют многочисленные правильные отве- ты.
Задача 2
Для решения используется очевидная рекурсия. subtree(X, X). subtree(X, tree(L,_,_)):- subtree(X,L). subtree(X,tree(_,_,R)):- subtree(X,R).
Варианты заданий
Вариант 1 1. Напишите предикат, аналогичный предикату subst (см. первое контрольное задание, вариант 8, задача 2), но производящий взаимную замену X на Y, т.е.
X->Y, Y->X.
2. Напишите предикат, который определяет, является ли данное натуральное число простым.
Воспользуйтесь более общей задачей: ispr(N, M) - "Число N не делится ни на одно число большее или равное M и меньшее N".
Имеем ispr(N, M) -истинно, во-первых, если N = M, и, во-вторых, если ис- тинно ispr(N,M+1) и N не делится на M.

21
Вариант 2 1. Сортировка списка простой вставкой (по возрастанию).
2. Сортировка списка простым выбором (по возрастанию).
Вариант 3 1. Напишите предикат p(+L, -N) - истинный тогда и только тогда, когда N - количество различных элементов списка L.
2. Напишите предикат p(+X, +Y, -Z) - истинный тогда и только тогда, когда Z есть "пересечение" списков X и Y, т.е. список, содержащий их общие элемен- ты, причем кратность каждого элемента в списке Z равняется минимуму из его кратностей в списках X и Y.
Вариант 4 1. Запрограммируйте предикат p(+A,+B), распознающий, можно ли получить список элементов A из списка элементов B посредством вычеркивания неко- торых элементов.
Алгоритм: Если A - пустой список, то ответом будет "да". В противном слу- чае нужно посмотреть, не пуст ли список B. Если это так, то ответом будет "нет". Иначе нужно сравнить первый элемент списка A с первым элементом списка B. Если они совпадают, то надо снова применить тот же алгоритм к остатку списка A и остатку списка B. В противном случае нужно снова при- менить тот же алгоритм к исходному списку A и остатку списка B.
2. Напишите предикат p(+X, +Y, +L) - истинный тогда и только тогда, когда
X и Y являются соседними элементами списка L.
Вариант 5.
1. Определите отношение sum_tree(+TreeOfInteger, -Sum), выполненное, если число Sum равно сумме целых чисел, являющихся вершинами дерева
TreeOfInteger.
2. Определим операторы:
:- op( 100, fy, ).
:- op( 110, xfy, &).
:- op( 120, xfy, v).
Булева формула есть терм, определяемый следующим образом: константы true и false - булевы формулы; если X и Y - булевы формулы, то и X v Y, X &
Y, X - булевы формулы, здесь v и & - бинарные инфиксные операторы дизъюнкции и конъюнкции, а - унарный оператор отрицания. Напишите предикат p(+T), определяющий, является ли данный терм T булевой форму- лой.

22
Вариант 6 1. Встроенный предикат functor(+Term, ?Functor, ?Arity) определяет для за- данного составного терма Term его функтор Functor и местность Arity.
Встроенный предикат arg(+N, +Term, ?Value) определяет для целого числа N и заданного составного терма Term его N-ый аргумент Value.
Определите предикаты functor1 и arg1 - аналоги предикатов functor и arg через предикат univ (=..)
2. Напишите предикат range(?M, ?N, ?L), истинный тогда и только тогда, ко- гда L - список целых чисел, расположенных между M и N включительно
(предикат должен допускать различное использование, когда не менее двух из трех аргументов конкретизованы).
(Указание. Используйте предикаты var(+X) и nonvar(+X)).
Вариант 7 1. Напишите вариант программы plus(?X, ?Y, ?Z), пригодный для сложения, вычитания и разбиения чисел на слагаемые.
(Указание. Используйте для порождения чисел встроенный предикат between(+Low, +High, ?Value), который порождает все целые числа от нижней границы Low до верхней границы High.)
2. Напишите программу вычисления целочисленного квадратного корня из натурального числа N, определяемого как число I, такое, что I*I  N, но
(I+1)*(I+1) > N . Используйте определение предиката between/3 для генериро- вания последовательности натуральных чисел с помощью механизма возвра- тов.
Вариант 8 1. Напишите новую версию процедуры "предок", которая вырабатывает спи- сок представителей всех промежуточных поколений, располагающихся меж- ду предком и потомком. Предположим, например, что Генри является отцом
Джека, Джек - отцом Ричарда, Ричард - отцом Чарльза, а Чарльз - отцом
Джейн. При запросе о том, является ли Генри предком Джейн, должен выдаваться список, характеризующий родственную связь этих людей, кон- кретно: [джек, ричард, чарльз].
2. Определите предикат p(+V, +N, -L) - истинный тогда и только тогда, когда
L - список элементов списка V, встречающихся в нем не менее N раз. Про- верьте работу этого предиката на примере [a, a, b, a, c, b, c, a, b, b, d, a, b] для
N=1,2,5,0.

23
3.5. Третье контрольное задание
Задание состоит из двух задач, в которых требуется составить более сложные программы на Прологе (как правило, требуется определить несколь- ко предикатов). При составлении программы (если не оговорено противное) можно использовать все встроенные предикаты Пролога. Текст программы, если вы мыслите в духе логического программирования и используете рекур- сию, получается небольшой.
Пример задания с решением
Задача 1
Определим операторы:
:- op( 100, fy, ).
:- op( 110, xfy, &).
:- op( 120, xfy, v).
Булева формула есть терм, определяемый следующим образом: константы true и false - булевы формулы; если X и Y - булевы формулы, то и X v Y, X &
Y, X - булевы формулы, здесь v и & - бинарные инфиксные операторы дизъюнкции и конъюнкции, а - унарный оператор отрицания.
Напишите программу, распознающую логические формулы в конъюнктивной нормальной форме, т.е. формулы, являющиеся конъюнкцией дизъюнкций ли- тералов, где литерал - атомарная формула или ее отрицание.
Задача 2
Напишите предикат p(+N, -L) - истинный тогда и только тогда, когда список
L содержит все последовательности (списки) из N нулей, единиц и двоек, в которых никакая цифра не повторяется два раза подряд (нет куска вида XX).
Решение
Задача 1
Из определения операций видно, что конъюнкция и дизъюнкция являются право ассоциативными, т. е. запрос
?- X & Y & Z = A & B приводит к унификации X = A, Y & Z = B.
Определим два вспомогательных предиката literal(X) и dis(X), которые прове- ряют является ли X литералом и элементарной дизъюнкцией соответственно. literal(true). literal(false). literal( X):- literal(X).

24 dis(X):- literal(X). dis(X v Y):- literal(X), dis(Y). con(X):- dis(X). con(X & Y):- dis(X), con(Y).
?- con( true & ( false v true v false) & true).
Yes
Задача 2 p(1,[[0],[1],[2]]). p(N,R):- N>1,
N1 is N-1, p(N1,R1), t(R1,R). t([],[]). t([X|T],Z):- t(T,R1), s(X,R), append(R,R1,Z). s([0|T],[[1,0|T],[2,0|T]]). s([1|T],[[0,1T],[2,1|T]]). s([2|T],[[0,2|T],[1,2|T]]).

1   2   3   4   5   6

Варианты заданий
Вариант 1 1. Напишите предикат p(+N, +K, -L) - истинный тогда и только тогда, когда L
- список всех последовательностей (списков) длины K из чисел 1,2,...,N.
2. Напишите предикат p(+N, -L) - истинный тогда и только тогда, когда спи- сок L содержит все последовательности (списки) из N нулей и единиц, в которых никакая цифра не повторяется три раза подряд (нет куска вида XXX).

25
Вариант 2 1. Определите отношение ordered(+Tree), выполненное, если дерево Tree яв- ляется упорядоченным деревом целых чисел, т. е. число, стоящее в любой вершине дерева, больше любого элемента в левом поддереве и меньше любо- го элемента в правом поддереве. Определение структуры "дерево" см. раздел "Второе контрольное задание".
Указание. Можно использовать вспомогательные предикаты ordered_left(+X,
+Tree) и ordered_right(+X, +Tree), которые проверяют, что X меньше (боль- ше) всех чисел в вершинах левого (правого) поддерева дерева Tree и дерево
Tree - упорядочено.
2. Определим операторы:
:- op( 100, fy, ).
:- op( 110, xfy, &).
:- op( 120, xfy, v).
Булева формула есть терм, определяемый следующим образом: константы true и false - булевы формулы; если X и Y - булевы формулы, то и X v Y, X &
Y, X - булевы формулы, здесь v и & - бинарные инфиксные операторы дизъюнкции и конъюнкции, а - унарный оператор отрицания.
Напишите программу, распознающую логические формулы в дизъюнктивной нормальной форме, т.е. формулы, являющиеся дизъюнкцией конъюнкций ли- тералов, где литерал - атомарная формула или ее отрицание.
Вариант 3 1. Определим операторы:
:- op( 100, fy, ).
:- op( 110, xfy, &).
:- op( 120, xfy, v).
Булева формула есть терм, определяемый следующим образом: константы true и false - булевы формулы; если X и Y - булевы формулы, то и X v Y,
X & Y, X - булевы формулы, здесь v и & - бинарные инфиксные операторы дизъюнкции и конъюнкции, а - унарный оператор отрицания.
Напишите программу, задающую отношение negation_inward(+F1,-F2), кото- рое выполнено, если логическая формула F2 получается из логической фор- мулы F1 внесением всех операторов отрицания внутрь конъюнкций и дизъ- юнкций.
Вариант 4 1. Определите предикат occurances(+Sub,+Term,-N), истинный, если число N равно числу вхождений подтерма Sub в терм Term. Предполагается, что терм
Term не содержит переменных.
2. Разработайте программу "Советник по транспорту". Выберите либо сеть,

26 состоящую из городов, либо транспортную сеть маршрутов поездов или авто- бусов в пределах одного города. Вы должны информировать систему о том, откуда и куда Вы собираетесь добраться, а система должна выдавать реко- мендации о том, какими поездами, автобусами, самолетами и т. д. Вам следу- ет воспользоваться, чтобы добраться до пункта назначения.
Вариант 5 1. Напишите предикат p(+S, -L), который переводит предложение S, пред- ставленное строкой, в список атомов L. Например, p('gfrtyre hjnki <> pi 876 h',
[ gfrtyre, hjnki, '<>', pi, 876,h]) выполнено. Указание. Воспользуйтесь предика- том name/2.
2. Множественное число большинства английских существительных получа- ется путем добавления буквы "s" к форме единственного числа. Но если су- ществительное заканчивается буквой "y", следующей за согласной, множе- ственное число образуется путем замены буквы "y" на сочетание "ies"; если же существительное заканчивается буквой "o", следующей за согласной, множественное число образуется путем добавления сочетания "es". Напишите утверждения для предиката множественное_число/2, которые задают все эти правила. Указание. Воспользуйтесь предикатом name/2.
Вариант 6 1. Простейшая система кодирования сообщений заключается в замене каждой буквы сообщения на букву, находящуюся на N-й по отношению к ней пози- ции в алфавите. Например, для N=2 буква "a" заменяется на "c", буква "y" на "a" и т.д. Зная, что коды ASCII букв от "a" до "z" изменяются от 97 до 122, напишите процедуру для предиката шифратор/3, который берет шифруемое слово и целое число и выдает слово, представляющее шифр данного слова, полученный с помощью указанного метода.
Указание. Воспользуйтесь предикатом name/2.
2. Напишите предикат предшествует/2, который берет два атома в качестве своих аргументов и успешно согласуется, если первый из них в лексико- графическом порядке предшествует второму.
Указание. Воспользуйтесь предикатом name/2.
Вариант 7 1. Одним из примеров использования предиката name/2 может служить гене- рация новых атомов для представления вновь вводимых объектов, например, abc1, abc2, abc3 и т.д. Эти имена характеризуются тем, что все они состоят из корня, определяющего тип именуемого объекта, и целочисленного суффикса для различения объектов одного типа. Напишите программу новое_имя(+X, -Y). Последовательность имен создается с помощью возвра- тов. Указание. Воспользуйтесь предикатом int_to_atom(+N,-X), который кон- вертирует натуральное число N в атом X.

27 2. Построить программу "сжать", назначение которой - преобразование ан- глийских слов в их "звуковой" код. Этот процесс предусматривает "сжатие" примерно одинаково звучащих слов в одинаковый их код - своего рода, аб- бревиатуру этих слов. Слова "сжимаются" в соответствии со следующими правилами:
- первая буква слова сохраняется;
- все последующие за ней гласные, а также буквы "h", "w" и "y" удаляются;
- сдвоенные буквы заменяются одиночными;
- закодированное слово состоит не более чем из четырех букв, остальные бук- вы удаляются.
Примеры: сжать(barrington, brng) и сжать(llewellyn, ln) - выполнено.
Указание. Воспользуйтесь предикатом name/2.

28
4.
КУРСОВЫЕ РАБОТЫ
Выполнение курсовой работы по логическому программированию ("ло- гическое программирование" понимается в "широком" смысле этого слова) требует решения одной из нижеперечисленных задач и, как результат, созда- ния программы на Прологе или Лиспе и написания пояснительной записки к работе. Созданную программу и пояснительную записку (в электронном ви- де) студент пересылает по электронной почте диспетчеру центра дистантного обучения, который в свою очередь пересылает их лектору. Лектор проверяет программу и пояснительную записку и при правильном выполнении работы студент получает подтверждение о том, что они зачтены. Если программа или записка составлена неправильно, студент получает от лектора текстовый файл, в котором содержится описание ошибок программы и недостатков по- яснительной записки.
Для некоторых курсовых работ вам потребуются некоторые знания из теории графов. В качестве литературы можно использовать любой учебник по дискретной математике, содержащий теорию графов в небольшом объеме.
Например,
Нефедов В. Н., Осипова В. А. Курс дискретной математики. - М.: Изд- во МАИ, 1992.-264 с.
Независимо от того, на каком языке требуется выполнить курсовую ра- боту, на Лиспе или Прологе, представляйте граф в виде двух списков: список вершин и список ребер. Каждое ребро, в свою очередь, есть список из двух вершин.
Следующие два алгоритма для курсовых работ с графами возможно бу- дут полезны.
Алгоритм поиска в глубину в графе для реализации на Лиспе
Функция (depth V,E,x,y,p,end) выдает путь (список вершин):
V - список вершин графа;
E - список ребер; x - стартовая (начальная) вершина, при рекурсивном вызове depth, x - теку- щая вершина, откуда ведется поиск пути; y - список вершин - соседей вершины x; p - накапливаемый путь (накапливающий параметр), в начале поиска - пустой список, вершины накапливаются в обратном пройденному порядке; end - предикат (функциональный аргумент), которому должна удовлетворять целевая (конечная) вершина искомого пути.
If x- целевая вершина , then получаем результат , добавляя к пути p вершину x, else if список y вершин-соседей пуст then ответ = nil else

29 if первая вершина в списке y принадлежит пройденному пути p then вызываем рекурсивно функцию depth для хвоста списка y else if первая вершина в списке y не принадлежит пройденному пути p then вызываем рекурсивно функцию, накапливая параметр p и меняя параметры x и y else вызываем рекурсивно функцию depth для хвоста списка y.
Алгоритм поиска в глубину для Пролога
Описание необходимых предикатов: next(+X, ?Y) - выдает истину тогда и только тогда, когда X и Y - смежные вершины; path(+Start, -Path) - вычисляет путь Path (список вершин в порядке, обратном пройденному) из начальной вершины Start в целевую вершину, удовлетворя- ющую некоторому предикату end; depth(+P, +X, -Path) - предикат, вычисляющий путь Path из стартовой верши- ны в целевую, P - накаливающийся параметр, содержащий уже пройденный путь, прежде чем попасть в вершину X.
Предикат path вычисляется с помощью правила path(Start, Path):- depth([], Start, Path).
Алгоритм для вычисления depth(P, X, Path):
1) если X - целевая вершина, то результатом является путь P, к которому до- бавлена вершина X ;
2) в противном случае находим соседнюю вершину Y для X, которая не вхо- дит в пройденный путь P, добавляем вершину X к пути P и рекурсивно вы- зываем depth.

30
ВАРИАНТЫ ТЕМ ДЛЯ КУРСОВЫХ РАБОТ
1. Упрощение электрических цепей
Постановка задачи.
Цепь состоит из компонентов только трех видов: резисторов, емкостей и ин- дуктивностей. Преобразовать цепь в более простую, используя упрощающие правила при параллельном и последовательном соединении компонент одно- го вида. Треугольники преобразовывать в звезды. Язык программирования:
SWI-prolog.
Используйте следующее представление предметной области. Структуры r(Номинал), l(Номинал) и c(Номинал) изображают соответственно резистор, индуктивность и емкость с номиналами. Вся цепь представляется в базе дан- ных фактами вида comp(<метка элемента>,
<элемент: резистор, индуктивность или емкость>,
<список узлов элемента>).
Упрощение цепи сводится к изменению базы данных.
2. Программа для алгебраических вычислений
Объекты, с которыми вы будете работать, - это многочлены от одной переменной, представленные в символьном виде с вещественными коэффи- циентами. Многочлены должны изображаться как арифметические выраже- ния, так умножение изображается знаком ‘*’, а возведение в степень - знаком
‘^’. Язык реализации - SWI-Prolog.
Для манипуляций с многочленами нужны некоторые предикаты, чтобы пользователь мог получать ответы на вопросы, на которые не удается отве- тить с помощью традиционных языков программирования. Для этого вам по- надобится обозначать многочлены идентификаторами и хранить в базе дан- ных пару (имя многочлена, сам многочлен). Предикаты выполняют некото- рые операции над своими операндами и помещают результат в качестве зна- чения некоторого имени многочлена.
Список предикатов.
1. Ввести многочлен и записать его под некоторым именем.
2. Образовать алгебраическую сумму (разность, произведение) двух многочленов и записать полученный многочлен под некоторым именем.
3. Возвести данный многочлен в целую степень и результат записать под некоторым именем.
4. Заменить каждое вхождение переменной в многочлене на данный многочлен и результат записать под некоторым именем.
5. Вычислить производную многочлена по переменной и результат за- писать под некоторым именем.
6. Напечатать данный многочлен.

31
Многочлен представлять в виде суммы членов, включающих только операции умножения и возведения в степень. В каждом таком одночлене все константы перемножены и образуют числовой коэффициент (первый сомно- житель), далее идет переменная в некоторой степени. Следует приводить по- добные члены, т. е. объединять одночлены, имеющие одинаковые степени пе- ременной, с соответствующим изменением коэффициентов.
Литература (полезная, но можно без нее обойтись)
1. Уэзерелл Ч. Этюды для программистов: Пер. с англ.-М.: Мир,1982.-
С. 114-120.
2. Стерлинг Л., Шапиро Э. Искусство программирования на языке
ПРОЛОГ.- М.: Мир.- С. 57-61.
Указания. Некоторые фрагменты программы:
% Полиномы хранятся в виде фактов
% pol(+Name, -<список одночленов>).
% Ввод полинома: enter(+Name) enter(X):- write('Введите полином с именем '),write_ln(X), enter(X,[],_). enter(X,S,P):- write_ln('Введите очередной одночлен или end'), read(T),
((T=end,place(X,S,P));
(T \= end, enter(X,[T|S],P))).
% привести подобные во введенном полиноме, упорядочить члены
% загрузить в базу данных place(X,S,P):- merge(S,[],P), retractall(pol(X,_)), assert(pol(X,P)).
% сложение полиномов, представленных списками одночленов merge([],L,L). merge([X|L1],L2,L):- insert(X,L2,L3), merge(L1,L3,L).

32 insert(X,[],[X]). insert(X,[Y|T],[Z|T]):- equal(X,Y,Z),Z \= 0,!. insert(X,[Y|T],T):- equal(X,Y,0),!. insert(X,[Y|T],[X,Y|T]):- low(X,Y). insert(X,[Y|T],[Y|T1]):- not(low(X,Y)), insert(X,T,T1).
/* equal(X,Y,Z) - из двух мономов X, Y при приведении подобных получаем Z low(X,Y) - моном X предшествует моному Y */
% приведение полинома к более "читабельному" виду canon([],0). canon([X],X). canon([X,Y],Y+X). canon([X,Y|T],Z+Y+X):- length(T,M),M>0, canon(T,Z).
% показать полином show(X):- pol(X,P), canon(P,P1), write('Полином с именем '),write_ln(X),write_ln(P1).
% сложение полиномов plus_pol(X,Y,Z):- pol(X,P1), pol(Y,P2), merge(P1,P2,P), retractall(pol(Z,_)), assert(pol(Z,P)), show(Z).
Протокол:
?- enter(a).
Введите полином с именем a
Введите очередной одночлен или end
-8*x^5.

33
Введите очередной одночлен или end
9.
Введите очередной одночлен или end
10*x^5.
Введите очередной одночлен или end x^3.
Введите очередной одночлен или end
-7*x^3.
Введите очередной одночлен или end end.
Yes
?- show(a).
Полином с именем a
2 * x ^ 5 + -6 * x ^ 3 + 9
Yes
?-plus_pol(a,a,b).
Полином с именем b
4 * x ^ 5 + -12 * x ^ 3 + 18
Yes
3. Игра "Суммируйте до 20"
Два игрока по очереди называют какое-либо число в интервале от 1 до 3 включительно. Названные числа суммируются, выигрывает тот игрок, сумма чисел после хода которого равна 20. Напишите программу на SWI-Prologе, выигрывающую данную игру на стороне компьютера.
Указания. Используйте запоминающие функции (см. "Курс лекций по логиче- скому программированию"). Напишите программу в таком виде, чтобы ее можно было легко модернизировать для решения более общей задачи. Более общая задача: перед началом игры компьютер спрашивает "Какой список до- пустимых ходов (какие числа можно называть) и какая предельная (выиг- рышная) сумма?"
4. Задача Прима-Краскала (“жадный” алгоритм) на Прологе
Дана плоская страна и в ней n городов. Нужно соединить все города
телефонной связью так, чтобы общая длина телефонных линий была мини-
мальной.
Уточнение задачи. В задаче речь идет о телефонной связи, т. е. подра- зумевается транзитивность связи: если i-й город связан с j-ым, а j-ый с k-ым, то i-й связан с k-ым. Подразумевается также, что телефонные линии могут разветвляться только на телефонной станции, а не в чистом поле.

34
Наконец, требование минимальности (вместе с транзитивностью) означает, что в искомом решении не будет циклов. В терминах теории графов задача
Прима-Краскала выглядит следующим образом:
Дан граф с n вершинами; заданы длины ребер. Найти остовное дерево
минимальной длины.
Как известно, дерево с n вершинами имеет n-1 ребер. Оказывается, каж- дое ребро надо выбирать жадно (лишь бы ни возникали циклы).
Алгоритм Прима-Краскала
(краткое описание)
В цикле n-1 раз делай:
"выбрать самое короткое еще не выбранное ребро при условии, что оно не образует цикл с уже выбранными".
Выбранные таким образом ребра образуют искомое остовное дерево.
Напишите программу для решения задачи Прима-Краскала на SWI-Prologе.
5. Задача Прима-Краскала (“жадный” алгоритм) на Лиспе
Решите задачу Прима-Краскала (см. предыдущую тему) на языке XLisp.
6. Упрощение арифметических выражений
Назовем арифметическим выражением терм, при конструировании ко- торого используются только атомы, числа, скобки и знаки арифметических операций. Напишите программу для упрощения арифметических выражений на SWI-Prologе.
В целом, задача упрощения выражений является достаточно сложной и в каком-то смысле неконкретизованной, т. к. единого верного решения для этой задачи нет. Если арифметическое выражение имеет несколько вариантов более простого представления, то какой из них выбрать в качестве решения?
Это зависит от того, для каких целей нам необходимо упрощение.
Задачу упрощения выражения поставим следующим образом. Необхо- димо найти эквивалентное выражение, форма записи которого является более короткой, чем форма записи исходного выражения. Для упрощения выраже- ний используйте различные рекурсивные "правила переписывания", каждое из которых "упрощает" какое-нибудь подвыражение в исходном выражении.
Правила переписывания должны соответствовать обычным математическим преобразованиям, как-то: приведению подобных и т. п., и представляются правилами Пролога (см. программу "дифференцирование выражений" из кур- са лекций).
Ваша программа должна быть некоторым компромиссом между жела- тельной простотой написания и той сложностью, которой от нее требует по- ставленная задача.

35
Литература (не обязательная): Лорьер Ж.-Л. Системы искусственного интеллекта. - М., Мир, 1991.- С. 129-131, 471.
7. Определение связности графа на Прологе
Напишите программу на SWI-Prologе, определяющую является ли данный неориентированный граф связным.
Указание: запрограммируйте предварительно предикат path(+X,+Y), прове- ряющий, существует ли путь из вершины X в вершину Y.
8. Определение связности графа на Лиспе
Напишите программу на языке XLisp, определяющую, является ли данный неориентированный граф связным.
Указание: запрограммируйте предварительно предикат (path X Y), проверя- ющий, существует ли путь из вершины X в вершину Y.
9. Определение эйлерова пути на Прологе
Напишите программу на SWI-Prologе, определяющую эйлеров путь, начина- ющийся с заданной вершины в неориентированном графе. Путь называется эйлеровым, если проходит через все ребра графа по одному разу. Теорема
Эйлера утверждает, что такой путь всегда существует, если количество вер- шин в графе с нечетной степенью равно 0 или 2. Степень вершины - это ко- личество ребер, которые инцидентны данной вершине. Если количество вер- шин с нечетной степенью равно 2, то эйлеров путь всегда начинается в одной из таких вершин.

1   2   3   4   5   6