Е.И. Большакова - Практикум на языке программирования Пролог (1109888)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Московский государственный

университет имени М.В.Ломоносова

Факультет вычислительной математики и кибернетики

Большакова Е.И.

Практикум

на языке программирования Пролог

(Методическое пособие)

Москва

1999

УДК 519.68

В данном методическом пособии дается описание заданий практикума на языке программирования Пролог для студентов 4 курса факультета ВМиК МГУ. Задания разработаны в поддержку основных курсов «Математическая логика» и «Искусственный интеллект». Приводятся подробные методические пояснения и рекомендации.

Рецензенты:

доцент Боголюбов Д.П.

научный сотрудник Громыко В.И.

Большакова Е.И. «Практикум на языке программирования Пролог (Методическое пособие )» - М., Издательский отдел факультета ВМиК МГУ (лицензия ЛР №040777 от 23.07.96), 1999.-24 с.

Печатается по решению Редакционно-издательского Совета факультета вычислительной математики и кибернетики МГУ им. М.В.Ломоносова.

ISBN 5-89407-059-7 ã Издательский отдел

факультета вычислительной

математики и кибернетики МГУ

им. М.В.Ломоносова, 1999

ЗАДАНИЕ 1.

ОСНОВЫ ПРОГРАММИРОВАНИЯ НА ЯЗЫКЕ ПРОЛОГ

Постановка задачи

Запрограммировать на языке Пролог следующие 20 предикатов, которые разбиты на 4 группы. При определении этих предикатов указывается условие их истинности.

1. Предикаты для работы со списками

Аргументы L1, L2, L3 обозначают списки, Е - некоторый элемент списка (тип элементов списка произволен), N - порядковый номер элемента в списке.

1. append (L1, L2, L3): список L3 является слиянием (конкатенацией) списков L1 и L2;

2. reverse (L1, L2): L2 - перевернутый список L1;

3. delete_first (E, L1, L2): список L2 получен из L1 исключением первого вхождения в него элемента Е;

4. delete_all (E, L1, L2): L2 - это список L1, из которого удалены все вхождения элемента Е;

5. delete_one (E, L1, L2): L2 - список L1, в котором исключен один элемент Е (исключается какое-то одно вхождение Е в список L1);

6. no_doubles (L1, L2): L2 - это список, являющийся результатом удаления из L1 всех повторяющихся элементов;

7. sublist (L1, L2): L1 - любой подсписок списка L2, т.е. непустой отрезок из подряд идущих элементов L2;

8. number (E, N, L): N - порядковый номер элемента E в списке L;

9. sort (L1, L2): L2 - отсортированный по неубыванию список чисел из L1;

II. Предикаты для работы с множествами

Аргументы М1, М2, М3 обозначают множества, которые представляются в виде списков элементов без повторений, порядок элементов в них несущественен, тип элементов - произволен.

1. subset (М1, М2): множество М1 является подмножеством М2;

2. union (М1, М2, М3): множество М3 - объединение множеств М1 и М2; вместо этого предиката может быть взят предикат

intersection (М1, М2, М3): М3 - пересечение М1 и М2, или subtraction (М1, М2, М3): М3 - разность М1 и М2.

III. Предикаты для работы с бинарными деревьями

Аргументы Т, Т1 и Т2 обозначают деревья, представляемые в виде термов, которые записываются с помощью тернарного функтора

tree (<левое поддерево>, <правое поддерево>, <метка>)

и константы nil (пустое дерево). К примеру,

tree (tree (nil, nil, f), tree (tree(nil, nil, p), tree (nil, nil, r), k))

представляет дерево, изображенное на рис.1. В узлах дерева находятся метки -элементы произвольного скалярного типа (в приведенном примере - символьные атомы).

1. tree_depth (Т, N): N - глубина дерева (т.е. количество ребер в самой длинной ветви дерева);

2. sub_tree (Т1, Т2): дерево Т1 является непустым поддеревом дерева Т2;

3. flatten_tree (Т, L): L - список всех меток-узлов дерева Т («выровненное» дерево);

4. substitute (Т1, V, Т, Т2): Т2 - дерево, полученное заменой всех вхождений элемента V в дереве Т1 на терм Т.

IV. Предикаты для работы с графами

Граф может быть представлен либо явно - в виде одной структуры, либо неявно - набором фактов вида edge (P, R, N), устанавливающих наличие ребра (дуги) между вершинами (узлами) P и R и задающее стоимость N (целое неотрицательное число) этого ребра. При явном способе представления графа он задается термом, включающим в свой состав список ребер и список вершин графа.

Граф, изображенный на рисунке 2, может быть задан неявно фактами

edge(a, c, 8), edge(a, b, 3), edge(c, d, 12), edge(b, d, 0),(e, d, 9),

а в явной форме он может быть задан термом

graph([edge(a, c, 8), edge(a, b, 3), edge(c, d, 12), edge(b, d, 0),edge(e, d, 9)], [a, b, c, d, e]),

где graph - бинарный, а edge - тернарный функторы.

В нижеследующем описании предикатов используется неявный способ задания графа, Х и Y обозначают вершины графа, а L - список вершин.

1. path (Х, Y, L): L - путь без циклов между вершинами Х и Y, т.е. список вершин между этими вершинами;

2. min_path (Х, Y, L): L - путь между вершинами Х и Y, имеющий минимальную стоимость (стоимость пути равна сумме стоимостей входящих в него ребер);

3. short_path (Х, Y, L): L - самый короткий путь между вершинами Х и Y (длина пути равна количеству входящих в него ребер);

4. cyclic : граф является циклическим (т.е. не является деревом);

5. is_connected : граф является связным (т.е. для любых двух его вершин существует связывающий их путь).

Замечания:

1. В предикатах 16-19 граф предполагается связным и может содержать циклы;

2. Все вышеописанные предикаты группы IV для явного способа представления графа должны содержать дополнительный аргумент - сам граф, например: path (G, X, Y, L), где G - структура, представляющая граф.

Требования к программе

Основные требования к программе связаны с особенностями языка Пролог. К числу главных особенностей относится так называемая инвертируемость прологовских предикатов (процедур). В процедурах и функциях большинства операторных языков программирования (Паскаль, Си и др.) фиксируется, какие параметры (аргументы) являются входными (input), какие выходными (output), т.е. фиксируется направление передачи значений этих аргументов. Прологовский же предикат обычно допускает многообразное использование, т.е. один и тот же аргумент может быть как входным (при одних вычислениях), так и выходным (при других вычислениях) - это связано с декларативным пониманием предиката как отношения между объектами. Например, предикат member (E, L), определяемый следующими предложениями

member (E, [E| L]).

member (E, [Z| L]):- member (E, L).

и истинный, если E есть элемент списка L, допускает следующие варианты использования:

?-member (b, [a, b, c]): значения обоих аргументов заданы, результат вычислений есть истинность данного отношения;

?-member (Х, [a, b, c]): задано значение только второго аргумента, результатом вычислений (значение Х) могут быть всевозможные элементы заданного списка;

?-member (b, Y): задан лишь первый аргумент, результат вычислений (Y) - любой список, который можно составить из элементов b.

Зафиксированные направления передачи значений аргументов предиката (внутрь/вовне или input/output) часто называют образцом или прототипом передачи (flow pattern), для его записи используются латинские буквы i и o, а также скобки. Для рассмотренного предиката member соответствующие прототипы записываются так: (i, i), (o, i), (i, o). Таким образом, инвертируемый предикат - это предикат, допускающий несколько образцов передачи.

Другая часто встречающаяся особенность предикатов Пролога - недетерминированность. Предикат называется недетерминированным, если его вычисление может дать более одного решения (результата). Точнее следует говорить о недетерминированности (или детерминированности) вычислений предиката при определенном прототипе передачи значений аргументов. Например, для предиката member недетерминированными являются вычисления при прототипах (o, i) и (i, o).

Перечислим теперь требования к пролог-программе:

1. При программировании и отладке следует определить все возможные прототипы передачи аргументов для всех 20 предикатов программы и поместить в тексте программы рядом с записью каждого предиката строку комментария, содержащую все обнаруженные прототипы. Прототипы, приводящие к недетерминированным вычислениям, необходимо пометить особо.

2. Для недетерминированных предикатов subset, path, short_path, min_path исключить возможность порождения дважды одного и того же результата (решения). Например, недопустимо возникновение дважды одного и того же пути во множестве решений предиката path.

3. Предикаты flatten_tree, short_path, min_path работы с деревьями и графами должны быть запрограммированы эффективно. Для реализации flatten_tree потребуется вместо обычного использовать разностный вариант предиката append или же технику накапливающего параметра; а для реализации предикатов поиска короткого и минимального пути в графе необходим выбор подходящих алгоритмов перебора вершин графа.

4. Для всех предикатов работы с деревьями и графами требуется заготовить тестовые данные, демонстрирующие различные результаты их работы во всех возможных прототипах.

5. При реализации предиката sort допускается любой метод и алгоритм сортировки, кроме метода пузырька: сортировка вставкой (включением), выбором, слиянием, быстрая сортировка и др.

6. Поскольку цель задания - освоение основ логического программирования, то в программе запрещается использовать внелогические предикаты, имеющие побочные эффекты: free, bound, read, assert, retract и другие.

Методические указания

1. При программировании предикатов группы IV следует учесть следующее. Для простейшего, неявного способа задания графа легче запрограммировать предикаты 16-18, однако этот способ не применим для представления несвязных графов и работы с ними. Явное задание графа в виде терма - менее экономный способ, поскольку информация в нем частично дублируется, но он более универсален.

Кроме того, возможны и другие, еще более неэкономные и сложные способы представления графа, облегчающие в то же время его обработку, например, задание графа как списка пар вида

pair(<вершина>, <список вершин, смежных с ней>),

где pair - бинарный функтор. Для графа на рис. 2 таким списком будет

[pair (a, [b, c]), pair(b, [a, d]), pair(c, [a, d]), pair(d, [b, c, e]), pair(e, [d])].

При программировании некоторых предикатов может оказаться полезным перевод графа из одной формы представления в другую.

Ключевой момент при любом способе задания графа - решение, является ли обрабатываемый граф ориентированным или нет (на рис.2 показан неориентированный граф).

1. Несмотря на внешнюю похожесть определений предикатов min_path и short_path их эффективная реализация на Прологе требует применения разных алгоритмов поиска путей, т.е. просмотра (перебора) вершин в графе.

Нахождение минимального по стоимости пути (предикат min_path) предполагает полный просмотр графа и путей в нем. Такой просмотр целесообразно программировать на основе алгоритма поиска вглубь (depth_first_search), поскольку он по сути встроен в пролог-интерпретатор. При поиске вглубь всегда для продолжения просмотра из еще не рассмотренных вершин графа выбирается вершина, наиболее удаленная от начальной вершины (т.е. от которой был начат поиск) [Братко, с.330-335; Стерлинг, с.224-232].

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов книги