Логич-кое и функ-ное программ-ние_УМП. Учебные пособия по логическому и функциональ ному программированию В. М. Зюзькова. В пособие внесены изменения в 2020 г
 Скачать 2.34 Mb.
|
Вариант 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, то эйлеров путь всегда начинается в одной из таких вершин. |