16. Представления графов в Прологе.

Для представления графов в языке Пролог можно использовать три способа:

1. Использование факта языка Пролог для описания дуг или рёбер графа.

2. Использование списка или структуры данных для объединения двух списков: списка вершин и списка рёбер.

3. Использование списка списков: каждый подсписок в качестве головы содержит вершину графа, а в качестве хвоста - список смежных вершин.

Две самые распространённые операции, которые выполняются над графами:

· Поиск пути между двумя вершинами;

· Поиск в графе подграфа, который обладает некоторыми заданными свойствами.

17. Как Пролог-система отвечает на вопросы пользователя.

В данном разделе приводится неформальное объяснение того, как пролог-система отвечает на вопросы.

Вопрос к системе — это всегда последовательность, состоящая из одной или нескольких целей. Для того, чтобы ответить на вопрос, система пытается достичь всех целей. Что значит достичь цели? Достичь цели — это значит показать, что утверждения, содержащиеся в вопросе, истинны в предположении, что все отношения программы истинны. Другими словами, достичь цели - это значит показать, что она логически следует из фактов и правил программы. Если вопрос содержит переменные, система должна к тому же найти конкретные объекты, которые (будучи подставленными вместо переменных) обеспечивают достижение цели. Найденные конкретизации сообщаются пользователю. Если для некоторой конкретизации система не в состоянии вывести цель из остальных предложений программы, то ее ответом на вопрос будет "нет".

Таким образом, подходящей интерпретацией пролог-программы в математических терминах будет следующая: пролог-система рассматривает факты и правила в качестве множества аксиом, а вопрос пользователя — как теорему; затем она пытается доказать эту теорему, т.е. показать, что ее можно логически вывести из аксиом.

18. S-выражения Лиспа. Примеры.

В языке Лисп как для вызова функций, так и для записи выражений принята единообразная форма записи, при которой имя функции и ее аргументы записываются внутри скобок. Общий формат записи следующий:

(name_function arg_1 arg_2 … arg_n), где

name_function – имя функции;

arg_I – аргументы.

Такая форма записи называется S-выражением.

Таким же образом записываются арифметические выражения, например, (+ 2 3), (- 4 3), (* x (+ y z)), etc.

Характерной особенностью S-выражения является наличие скобок. Действительно, их количество и местоположение влияет на смысл и результат S-выражения. Кроме скобок в любом S-выражении имеются элементы, называемые атомами. Различают два типа атомов: символьные и числовые. Символьный атом состоит обычно из букв, но может содержать и другие символы (числа, символ подчеркивания), но обязательно должен содержать хотя бы один символ, отличающий его от числа. Символьный атом нельзя расчленять на составляющие символы. Единственная операция, допустимая над символами – операция сравнения. Числовой атом является последовательностью цифр, возможно следующих за знаком.

S-выражение может состоять из произвольной смеси символьных и числовых атомов. Простейшая форма S-выражения – атом.

Формы S-выражений:

• один атом

• список атомов

• список с подсписками

QUOTE или ' - блокирует вычисление значения S-выражения.