Глава 11. Программные проекты на прологе

В этой главе рассматривается перечень программных проектов, которые вы могли бы попытаться осуществить для развития навыков программирования на Прологе. Некоторые из этих проектов довольно просты, зато другие вполне могут быть предложены в качестве «курсовой работы» в рамках учебного курса по Прологу. Более простые проекты следует использовать как дополнение к упражнениям, приведенным в предыдущих главах. В целом при перечислении проектов мы не придерживались какого-то определенного порядка, хотя те из них, что содержатся в разд. 11.2, в большей мере допускают расширения, содержат вызов честолюбию, но и требуют некоторой подготовки или знакомства с литературой по различным вопросам искусственного интеллекта и информатики. Небольшая часть проектов требует знаний из определенных разделов науки, поэтому если вы не специалист в области математической физики, то не отчаивайтесь, если не сможете написать программу дифференцирования трехмерных векторных полей.

Целая подборка Пролог-программ опубликована в отчете Coehlo H., Cotta J. С, Pereira L. M. How to solve it with Prolog, Laboratorio Nacional de Engenharia Civil, Lisbon, Portugal. В нем содержится свыше ста небольших примеров, задач и упражнений из таких областей как вывод умозаключений на основе базы данных, естественный язык, символьное решение уравнений, и т. д. Этот отчет по своему характеру не рассчитан на использование для обучения, поэтому приведенные в нем Пролог-программы снабжены лишь краткими пояснениями.

11.1. Простые проекты

1.Определить предикат лин для «линеаризации» списка путем построения нового списка, не содержащего списков в качестве элементов, но включающего все атомы исходного списка. Например, следующее целевое утверждение будет согласовано с базой данных:

?- лин([а,[b,с],[[d],[],е]], [a,b,c,d,e]).

Существует по меньшей мере шесть различных способов написания этой программы.

2. Составить программу для вычисления интервала (в днях) между двумя датами, заданными в формате День-Месяц, считая что обе они относятся к одному и тому же невисокосному году. Заметим, что '-' это просто инфиксная форма задания 2-х местного функтора. Например, следующее целевое утверждение будет согласовано с базой данных:

интервал(3-март, 7-апрель, 35).

3. В главе 7 приведены сведения, достаточные для составления программ дифференцирования и упрощения арифметических выражений. Усовершенствуйте эти программы так, чтобы они могли обрабатывать выражения с тригонометрическими функциями и, если есть желание, с операциями дифференциальной геометрии, такими как div, grad и rot.

4. Написать программу, осуществляющую символическое отрицание выражения исчисления высказываний. Это выражение строится из атомов, одноместного функтора not и двухместных функторов and (и), or (или) и implies (импликация). Задать соответствующие описания операторов для этих функторов. Выражение, являющееся результатом отрицания, должно быть представлено в простейшей форме, когда not применяется только к атомам. Например, отрицание выражения

р implies (q and not r)

должно выглядеть следующим образом: р and (not q or r)

5. Частотный словарь – это перечень слов, встречающихся в данном тексте, выписанный в алфавитном порядке с указанием числа вхождений каждого слова в тексте. Написать программу составления частотного словаря по списку слов, представленных в виде строк Пролога. Учтите, что строки – это списки кодов ASCII.

6. Написать программу, воспринимающую простые английские предложения, имеющие следующий формат

На основе ранее введенных предложений программа должна выдавать соответствующий ответ (yes (да), no (нет), ok (принято), unknown (неизвестно)). Например,

John is a man.

ok

A man is a person.

ok

Is John a person?

yes

Is Mary a person?

unknown

Каждое предложение должно транслироваться в утверждение Пролога, которое затем в зависимости от его характера, либо помещается в базу данных, либо выполняется как целевое. Так, результаты трансляции предложений приведенного выше примера выглядят следующим образом:

man(john).

person(X):- man(X).?- person (john).?- person(mary).

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

беседа:- repeat, read (Предложение), анализ(Предложение, Утверждение), ответ(Утверждение), Утверждение = stop.

7. Альфа-бета (α-β) алгоритм – это один из методов обхода дерева игры, который упоминается во многих книгах по искусственному интеллекту. Реализуйте альфа-бета алгоритм на Прологе.

8. Задача об N-ферзях также широко распространена в литературе по программированию. Реализовать программу нахождения всех способов размещения 4 ферзей на шахматной доске размером 4?4, причем так, чтобы ни один ферзь не угрожал другому. Один из возможных подходов состоит в создании генератора перестановок, который затем проверяет каждую перестановку, чтобы убедиться, что все ферзи размещены правильно.

9. Написать программу, которая переписывает выражение исчисления высказываний (см. задачу 4), заменяя все вхождения and, or, implies и not единственной связкой nand. Определение связки nand задается следующим тождеством

(α nand β)⌉≡(α∧β)

10. Один из способов представления целых положительных чисел состоит в том, чтобы представлять их в виде термов Пролога с использованием целого числа 0 и функтора S с одним аргументом. Так, число 0 представляет само себя, 1 представляется как S(0), 2 как S(S(0)) и т. д. (каждое число представляется в виде функтора S примененного к представлению числа, на единицу меньшего, чем данное). Написать определение стандартных арифметических операций: сложение, умножение и вычитание, использующих указанное представление чисел. Например, нужно определить предикат plus который действует следующим образом:

?- plus(s(s(0)),s(s(s(0))),X)

X=s(s(s(s(s(0)))))

(2+3=5). Для вычитания нужно ввести соглашение о том, что делать, когда результат операции не является положительным целым числом. Определите также предикат «меньше чем». Какие аргументы нужно конкретизировать, чтобы ваши определения работали правильно? Что произойдет, если этого не сделать? Как это соотносится со стандартными арифметическими операциями Пролога? Попытайтесь определить более сложные арифметические операции, такие как деление нацело и извлечение квадратного корня.