Программирование на языке Пролог для искусственного интеллекта




Упражнения



Упражнения

Определите отношение

        список( Объект)

для распознавания случаев, когда Объект является стандартным прологовским списком.

Посмотреть ответ

    Определите отношение принадлежности к списку, используя систему обозначений, введенную в этой разделе: "затем - ничего_не_делать".

Посмотреть ответ

    Определите отношение

        преобр( СтандСпис, Спис)

для преобразования списков из стандартного представления в систему "затем-ничего_не_делать". Например:

        преобр( [а, b], а затем b затем ничего_не_делать)

Посмотреть ответ

    Обобщите отношение преобр на случай произвольного альтернативного представления списков. Конкретное представление задается символом, обозначающим пустой список, и функтором для соединения головы с хвостом. В отношении преобр придется добавить два новых аргумента:

        преобр( СтандСпис, Спис, Функтор, ПустСпис)

Примеры применения этого отношения:

        ?-  пpeoбp( [а, b], L, затем, ничего_не_делать).

        L = а затем b затем ничего_не_делать

        ?-  преобр( [а, b, с], L, +, 0).

        L = а+(b+(с+0) )

Посмотреть ответ

    Сортировка списков
2.    Сортировка списков

Сортировка применяется очень часто. Список можно отсортировать (упорядочить), если между его элементами определено отношение порядка. Для удобства изложения мы будем использовать отношение порядка

        больше( X, Y)

означающее, что Х больше, чем Y, независимо от того, что мы в действительности понимаем под "больше, чем". Если элементами списка являются числа, то отношение больше будет, вероятно, определено как

        больше( X, Y) := Х > Y.

Если же элементы списка - атомы, то отношение больше может соответствовать алфавитному порядку между ними.

Пусть

        сорт( Спис, УпорСпис)

обозначает отношение, в котором Спис - некоторый список, а УпорСпис - это список, составленный из тех же элементов, но упорядоченный по возрастанию в соответствия с отношением больше. Мы построим три определения этого отношения на Прологе, основанные на трех различных идеях о механизме сортировки. Вот первая идея:

line();

Для того, чтобы упорядочить список Спис, необходимо:

  • Найти в Спис два смежных элемента Х и Y, таких, что больше( X, Y), и поменять Х и Y местами, получив тем самым новый список Спис1; затем отсортировать Спис1.
  • Если в Спис нет ни одной пары смежных элементов Х и Y, таких, что больше( X, Y), то считать, что Спис уже отсортирован.
line();

Мы переставили местами 2 элемента X и Y, расположенные в списке "не в том порядке", с целью приблизить список к своему упорядоченному состоянию. Имеется в виду, что после достаточно большого числа перестановок все элементы списка будут расположены в правильном порядке. Описанный принцип сортировки принято называть методом пузырька, поэтому соответствующая прологовская процедура будет называться пузырек.

        пузырек( Спис, УпорСпис) :-
                перест( Спис, Спис1),  !,
                 % Полезная перестановка ?
                пузырек( Спис1, УпорСпис).

        пузырек( УпорСпис, УпорСпис).
                                        % Если нет, то список уже упорядочен

        перест( [Х, Y | Остаток], [Y, Х ) Остаток] ):-
                                    % Перестановка первых двух элементов
                больше( X, Y).

        перест( [Z | Остаток], [Z | Остаток1] ):-
                перест( Остаток, Остаток1).
        % Перестановка в
хвосте

Еще один простой алгоритм сортировки называется сортировкой со вставками. Он основан на следующей идее:

line();

Для того, чтобы упорядочить непустой список  L = [X | Хв],  необходимо:

(1)        Упорядочить хвост  Хв   списка  L.

(2)        Вставить голову  Х  списка  L  в упорядоченный хвост, поместив ее в такое место, чтобы получившийся список остался упорядоченным. Список отсортирован.

line();

Этот алгоритм транслируется в следующую процедуру вставсорт на Прологе:

        вставсорт([ ], [ ]).

        вставсорт( [X | Хв], УпорСпис) :-
                вставсорт( Хв, УпорХв),
                    % Сортировка хвоста
                встав( X, УпорХв, УпорСпис).
                                                        % Вставить Х на нужное место









Начало  Назад  Вперед



Книжный магазин