Родственные отношения на прологе

родственные отношения на прологе

Списки


Списки - одна из наиболее часто употребляемых структур в Прологе. При записи список заключают в квадратные скобки, а элементы списка разделяют запятыми, например,

[слон, лошадь, обезьяна, собака]

Это список из четырех атомов - слон, лошадь, обезьяна, собака.

Элементами списка могут быть любые термы Пролога, т.е. атомы, числа, переменные и составные термы. Это позволяет составлять списки из списков. Пустой список записывается как [].

Вот пример списка с несколько более сложной структурой:

[слон, [ ], X, предок(Х, том), [a,b,c], f(22)]

Первый элемент непустого списка называется головой, а остальная часть списка носит название хвост. У списка, состоящего только из одного элемента головой является этот единственный элемент, а хвостом - пустой список. Обозначение [H|T] используется для представления списка с головой H и хвостом T. Если символ | помещен перед последним термом списка, то это означает, что этот последний терм определяет другой список. Полный список получится, если соединить этот подсписок с последовательностью элементов, расположенных до черты.

В следующем примере 1 - голова списка, а [2, 3, прологе 4, 5] - хвост. Пролог покажет это при помощи сопоставления списка чисел с образцом, состоящим из головы и хвоста.

?- [1, 2, 3, 4, 5] = [Head | Tail].

Head = 1

Tail = [2, 3, 4, 5]

Yes

Здесь Head и Tail - только имена переменных. Мы могли бы использовать X и Y или какие-нибудь другие имена переменных с тем же успехом. Заметим, что хвост списка всегда является списком. Голова, в свою очередь, есть элемент списка. Это относится и ко всем другим элементам, расположенным до вертикальной черты списка, что позволяет выделить, скажем, второй элемент списка.

Пример: Используем анонимные переменные для головы и списка, стоящего после черты, если нам нужен только второй элемент списка:

?- [слон, лошадь, осел, собака] = [_, X | _ ].

X = лошадь

Yes

Рассмотрим несколько процедур обработки списков. Обратите внимание, что все они используют рекурсию, в которой терминальное (базовое) правило использует пустой список.

Пример: Следующий предикат подсчитывает сумму всех элементов списка чисел.

сумма_списка([],0).

сумма_списка([H|T],S):- number(H), сумма_списка(T,S1), S is S1+H.

?- сумма_списка([0,1,7,2,456],X).

X = 466

Yes

Пример: Подсчитаем количество элементов произвольного списка.

колво_элементов([],0). % кол-во элементов пустого списка равно 0

колво_элементов([_|T],S):- колво_элементов (T,S1), S is S1+1.

?- колво_элементов([a,d,[d,t,[t]],s],X).

X = 4

Yes

Пример: Принадлежность элемента списку.

принадлежит(Х,[Х|_]). / любой элемент списка всегда является головой

какого-нибудь подсписка /

принадпежит(Х,[_|Z) :- принадлежит(Х,Z).

?- принадлежит(седло,[руль,рама,колесо,седло])

Yes

Пример: Выбор n-го элемента списка.

n(1, E, [E|_]).

n(N,E,[_|L]) :- C is N - 1, n(C, E, L).

?- n(3,X,[1,2,3,4,5]).

X = 3

1 solution

Пример: Функция присоединения.

append([ ], L, L).

append([X|Ll], L2, [X|L3]) :- append(Ll,L2,L3).

Функция append позволяет составлять и расчленять список.

?- append([a,b,c], [d,e,f], L)

L = [a,b,c,d,e,f].

?- append(L, [d,e,f|, [a,b,c,d,e,f])

L = [a,b,c].

?- append([a,b,c], L, [a,b,c,d,e,f])

L = [d,e,f].

?- append(Ll, L2, [a,b,c,d])

L1= [], L2= [a,b,c,d]

L1= [a], L2= [b,c,d]

L1= [a,b], L2= [c,d]

L1= [a,b,c], L2= [d]

L1= [a,b,c,d], L2= []

Пример: Поиск наименьшего элемента списка.

меньший([X], X).

меньший([X, Y|Z], R) :- X =< Y, меньший([X|Z], R);

X > Y, меньший([Y|Z], R).

?- меньший([6,5,7,3,2,0],X)

X = 0

Пример: Удаление заданного элемента из списка.

удалить(E, [E | Y], Y).

удалить(E, [X | Y], [X | Z]) :- удалить(E, Y, Z).

?- удалить(7,[1,2,3,7,4,5],Y)

Y= [1,2,3,4,5]

Пример: Сортировка элементов списка.

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

сортировать(L, [M|R]) :- меньший(L, M), удалить(M, L, Q),

сортировать(Q, R),!.

?- сортировать([1,5,2,7,3,4,2,9],X)

X= [1,2,2,3,4,5,7,9]

Пример: Перевод одного списка в другой, согласно словарю.

словарь("I";"я").

словарь("study","изучаю").

словарь("language","язык").

словарь("PROLOG","Пролог").

словарь("in","в").

словарь("the university","университете").

перевести ([], []).

перевести ([С_А|Ф_А], [С_Р|Ф_Р]):- словарь (С_А, С_Р),

перевести (Ф_А, Ф_Р).

?- перевести(["I","study","language","PROLOG","in","the university"],P)

Р = ["Я", "изучаю", "язык", "Пролог", "в", "университете"]

?- перевести(Р, ["Я", "изучаю", "язык", "Пролог", "в", "университете”]).

P = ["I", "study", "language", "PROLOG", "in", "the university"]

Пример: Предикат место/3 успешен, если третий аргумент есть список, полученный вставкой первого аргумента в произвольное место списка, являющимся вторым аргументом.

место(E, L, [E|L]).

место(E, [H|L], [H|Y]):- место(E, L,Y).

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

?- место(1,[2,3],X).

X = [1, 2, 3]

X = [2, 1, 3]

X = [2, 3, 1]

No

?- место(1,L,[2,1,3]).

L = [2, 3]

No

?- место(X,[2,3],[2,1,3]).

X = 1

No

Пример: Разбить список с элементами разделителями (0) на список списков (слов).

parser([],[],[]).

parser([X|Z],D,W) :- parser(Z,D1,W1),(

X \== 0, D = [X|D1], W = W1;

X == 0, D = [], W = [D1|W1]).

concat(Z,W) :- parser(Z,D1,W1), W = [D1|W1].

?- concat([a,s,d,f,0,r,t,e,0,w,d,0,g,h,j,0,r,t],X)

X= a,s,d,f],[r,t,e],[w,d],[g,h,j],[r,t

Пример: Разбить список с элементами разделителями (0) на список списков (слов).

calc([],0,[]).

calc([X|Z],D,W) :- calc(Z,D1,W1),(

X \== 0, D is D1 + 1, W = W1;

X == 0, D = 0, W = [D1|W1]).

conc(Z,W) :- calc(Z,D1,W1), W = [D1|W1].

?- conc([a,s,d,f,0,r,t,e,0,w,d,0,g,h,j,0,r,t],X)

X= [4,3,2,3,2]

Пример: Предикат перестановка/2 дает все перестановки первого аргумента.

перестановка([],[]).

перестановка([H|L],Z):- перестановка(L,Y), место(H,Y,Z).

Пример использования:

?- перестановка([a,b,c],X).

X = [a, b, c]

X = [b, a, c]

X = [b, c, a]

X = [a, c, b]

X = [c, a, b]

X = [c, b, a]

No

И, наконец, приведем правило для печати всех возможных перестановок списка:

все_перестановки(L):- перестановка(L,R), write(R), nl, fail.

Первая подцель предиката вычисляет очередную перестановку, печатает ее и переходит к последней подцели - fail. Эта подцель всегда неуспешна, что заставляет Пролог вернуться к началу правила и продолжить поиск решения. Работа процедуры завершится, когда все перестановки будут исчерпаны:

?- все_перестановки(['маркиза', 'ваши прекрасные глаза',

| 'сулят мне смерть от любви']).

[маркиза, ваши прекрасные глаза, сулят мне смерть от любви]

[ваши прекрасные глаза, маркиза, сулят мне смерть от любви]

[ваши прекрасные глаза, сулят мне смерть от любви, маркиза]

[маркиза, сулят мне смерть от любви, ваши прекрасные глаза]

[сулят мне смерть от любви, маркиза, ваши прекрасные глаза]

[сулят мне смерть от любви, ваши прекрасные глаза, маркиза]

No

^ Часть II. Указания к выполнению контрольной работы

В ходе выполнения курсовой работы студент должен получить практические навыки применения теоретических знаний, полученных на лекционных занятиях.

В работе разбираются следующие теоретические разделы:


  • модель семантической сети

  • продукционная модель

  • способ представления знаний в среде ПРОЛОГ

  • механизм вывода в среде ПРОЛОГ

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

Синтаксис языка ПРОЛОГ требует, чтобы все идентификаторы констант и предикатов начинаются со строчной буквы, а все идентификаторы переменных начинаются с заглавной буквы. В данном методическом пособии для удобства чтения договоримся о другом стиле: идентификаторы, начинающиеся с заглавной или строчной русской буквы, являются константами или предикатами.

План курсовой работы:


  1. Введение. (1..3 стр)

  2. Генеалогическое дерево. (1..2)

  3. Перевод генеалогического дерева в базу фактов. (2..3)

  4. Составление правил искомых родственных связей в базе знаний. (3..5)

  5. Примеры запросов к базе знаний и ее ответов (2..3).

  6. Листинг разработанной базы знаний на языке ПРОЛОГ. (2..3)

  7. Список литературы. (1..2)

Требования к оформлению курсовой работы стандартные (для АГТУ): не менее 15 страниц, основной шрифт абзаца – 13 шрифт “Times”, полуторный межстрочный интервал, отступ слева 10 мм, отступ перед абзацем 6 пт, поля Л:35, П:15, ВиН:20 мм. Нумерация страниц со второй страницы в верхнем правом углу.

  1. Введение


В этом параграфе кратко рассматриваются некоторые исторические и теоретические вопросы и делаются акценты на целях и задачах выполнения данной курсовой работы (раздел 1, «История и перспективы развития языка Пролог»).
  1. ^

    Генеалогическое дерево


Перед началом составления базы знаний необходимо составить генеалогическое дерево и изобразить его на бумаге в виде семантической сети. Личности, объединяемые генеалогическим деревом, могут быть как реальными (Иван Грозный, Петр I, Николай II, Пушкин А.С., и т.п.), так и виртуальными (родословные гномов и т.п. персонажей). Для проверки правильности составления всех правил родственных отношений дерево должно содержать не менее четырех уровней или, говоря языком предметной области, на дереве должны быть прадедушки(прабабушки) и правнуки (правнучки). Для упрощения задания не рекомендуется (но не возбраняется) вводить в генеалогическое дерево личностей порождающих родственные отношения типа «сводный брат» или «сводная сестра». А также личностей порождающих циклические связи, являющимися, например, одновременно «супругой» и «двоюродной сестрой». Пример генеалогического дерева приведен на рис.1.

Рис. 1. Пример генеалогического дерева.

  1. ^

    Перевод генеалогического дерева в базу фактов


В индивидуальном задании студенту для описания базы фактов предлагается минимальный набор родственных отношений. Такими отношениями могут быть как вертикальные связи

отец ( виктор, андрей ). мать ( алла, андрей ).

сын (андрей, виктор). Дочь ( алла, сергей ).

так и горизонтальные связи

муж ( виктор, алла ). Жена ( алла, виктор ).

брат( виктор, света ). сестра ( света, виктор ).

а также унарные отношения

мужчина (виктор). женщина (алла).

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

Индивидуальные задания:


отец/2. мать/2. мужчина/1.

сын/2. дочь/2. мужчина/1.

сын/3. дочь/3.

супруг/2. ребенок/2. мужчина/1

муж/2. сын/2. дочь/2.

родитель/2. женщина/1.

отпрыск/2. мужчина/1.

сестра/2 брат/2. родитель/2.

родители/3. женщина/1.

жена/2. сын/2 дочь/2.

Значками «/1», «/2», «/3» задается арность отношения или, говоря в терминах предметной области, количество личностей в отношении. Например:

  • отношение «мужчина/1» характеризует такой факт как «Виктор является мужчиной» или на ПРОЛОГ мужчина (виктор);

  • отношение «отец/2» характеризует родственной отношение «Виктор отец Андрея» или на ПРОЛОГ отец (виктор, андрей);

  • отношение «сын/3» характеризует родственной отношение «Андрей сын Виктора и Аллы» или на ПРОЛОГ сын (андрей, виктор, алла);

  • отношение «родитель/3» характеризует родственной отношение «Виктор и Алла родители Андрея»
    или на ПРОЛОГ родители (виктор, алла, андрей);

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

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

Затем, все нарисованные отношения необходимо переписать в виде фактов. Необходимым условием правильности перевода семантической сети в факты является соответствие количества стрелок каждого цвета и количества фактов этого отношения. Каждой стрелке должен соответствовать только один факт.

  1. ^

    Составление правил искомых родственных связей в базе знаний


Написать правила для установления родственных связей (всем студентам), таких как:

  • отец, мать, сестра, брат, сын, дочь, муж, жена;

  • двоюродная сестра (кузина), двоюродный брат (кузен), дядя, тетя, племянник, племянница;

  • дедушка, бабушка, прадедушка, прабабушка, внук, внучка, правнук, правнучка;

Задание повышенной трудности (для желающих):

  • кровные (общий предок), сводные брат и сестра, шурин, деверь, золовка, тесть, теща, зять, невестка и т.п. родственные отношения.

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

^ ЕСЛИ есть такой X который является отцом Z

И Z является отцом ИЛИ матерью Y

ТОГДА X является дедом Y.

Затем переписать это же правило на языке ПРОЛОГ:

дед (X,Y) :- отец (X,Z), ( отец (Z,Y) ; мать (Z,Y) ).

В синтаксисе языка ПРОЛОГ это правило будет выглядеть так:

grandfather (X,Y) :- father (X,Z), ( father (Z,Y) ; mother (Z,Y) ).

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

ded (X,Y) :- papa (X,Z), ( papa (Z,Y) ; mama (Z,Y) ).

Заметим, что PIE32 работает с кириллическими идентификаторами, но не всегда корректно, поэтому рекомендуется везде, где можно, применять латиницу.

  1. ^

    Примеры запросов к базе знаний и ее ответов


В этом разделе необходимо привести примеры диалога с созданной экспертной системой. Показать возможные варианты запросов системы и ее ответов. Например:

Запрос: Дед (Олег, Y)

Ответ 1: Y = Юрий

Ответ 2: Y = Юлий

Ответ 3: Y = Инга

Пример сложного составного запроса:

Сестра(X,Y),Сестра(Y,X).

  1. ^

    Листинг разработанной базы знаний


Привести распечатку готовой программы. Шрифт пропорциональный “Courier”

Часть III. Лабораторные работы

Лабораторная работа №1


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

Лабораторная работа №2


  1. Написать программу, которая на запрос реки([“Архангельск”, “Питер”, “Москва”],P) выводила P = [“Северная Двина”, “Нева”, “Яуза”].

  2. Как известно, n! = 123…n. Написать программу для поиска n = 1+2+3+…+n. Обязательно использовать рекурсию.

  3. Написать программу для преобразования списка вида [1997, 1970, 1907, 1979, 1909] к виду [1907, 1909, 1970, 1979, 1997].

  4. На заданный список городов вывести список в порядке убывания количества жителей. Необходимо использовать базу фактов вида
    население(“Москва”,10000).
    Население взять в тысячах.

  5. Написать программу определения времени пути между двумя городами. При описании сети дорог необходимо задавать только один вариант пути (для упрощения задачи), т.е. используется топология дерева, например с вершиной в Москве. Для описания БФ использовать отношение:

дорога(город, город, расстояние, скорость).
^

Лабораторная работа №3


  1. Определить (и напечатать) координаты концов интервала на оси Х, покрываемого максимальным количеством отрезков из списка o1(X1_1,Х2_1), o2(X1_2,Х2_2),...,oN(X1_N,Х2_N).

  2. Даны два списка целых чисел A1,..., AN и B1,..., BN. Cлить эти списки в один, исключить все повторения чисел и упорядочить их по возрастанию.

  3. Для множества точек плоскости p1(X1,Y1), p2(X2,Y2),..., pN(Xn,Yn) найти диаметр и центр минимальной описанной окружности.

  4. В списке символов S1, S2,..., SN найти первое и последнее вхождения указанного символа и исключить все символы между ними.

  5. В списке символов S1, S2,..., SN исключить все последовательности указанного вида, например [a,b,c,d].

  6. В списке символов S1, S2,..., SN найти длину наибольшей последовательности, построенной повторением одного и того же символа. Вывести эту последовательность.

  7. В списке символов S1, S2,..., SN каждую указанную последовательность символов заменить нв другую указанную последовательность.

  8. Из списка символов S1, S2,..., SN исключить все символы между круглыми скобками. Сами скобки тоже должны быть отброшены. Однако, если внутри круглых скобок есть другая пара круглых скобок, то она и содержащиеся в ней символы должны быть сохранены. И так далее рекурсивно. Например, последовательность "ab(c(d(ef(gh)z)fg)r)dd(ik(l))" преобразуется в "ab(d(gh)fg)dd(l)".

  9. В списке символов S1, S2,..., SN подсчитать количество букв в последнем слове, если разделителем между словами является один или несколько пробелов.

  10. В списке символов S1, S2,..., SN подсчитать количество слов, если разделителем между словами является один или несколько пробелов.

  11. Вдоль доски расположены лунки и в каждой лунке лежит шар белого или черного цвета. Одним ходом разрешается менять местами два соседних шара. Добиться того, чтобы в лунках сначала лежали белые, а потом черные шары.

  12. В списке символов S1, S2,..., SN найти число слов, начинающихся с заданной буквы, если разделителем между словами является один или несколько пробелов.

  13. В списке символов S1, S2,..., SN найти длину самого короткого слова, если разделителем между словами является один или несколько пробелов. Вывести это слово.

  14. В списке символов S1, S2,..., SN найти все вхождения указанного слова, если разделителем между словами является один или несколько пробелов.

  15. Вдоль доски расположены лунки и в каждой лунке лежит шар белого, синего или красного цвета. Одним ходом разрешается менять местами два соседних шара. Добиться того, чтобы в лунках сначала лежали белые, затем красные, а потом синие шары.

  16. В списке символов найти число слов с одинаковыми первой и поледеней буквами, если разделителем между словами является один или несколько пробелов. Вывести самое длинное такое слово.

  17. В списке символов S1, S2,..., SN найти среднюю длину слов, если разделителем между словами является один или несколько пробелов. Вывести все слова, имеющие эту длину.

  18. В списке символов S1, S2,..., SТ найти длину самого длинного слова, если разделителем между словами является один или несколько пробелов. Вывести это слово.

  19. Преобразовать список целых чисел A1, А2,..., AN следующим образом:

    • исключить нули,

    • слева записать все положительные числа,

    • справа - все отрицательные.

  20. Каждый элемент списка целых чисел A1, A2,..., AN помножить на квадрат наименьшего элемента и представить этот список в упорядоченном виде.

  21. Из списка целых чисел A1, А2,..., AN исключить все элементы, совпадающие со значением [(A_max + A_min + A_ср) / 3].

  22. Из списка целых чисел исключить все члены, равные целой части от среднего арифметического. Результирующий список представить в упорядоченном виде.

  23. Список целых чисел A1, A2,..., AN оставить без изменений, если он упорядочен по возрастанию или убыванию. В противном случае:

  24. каждый четный элемент списка утроить,

  25. каждый элемент, стоящий на нечетном месте и кратный четырем, удалить.

  26. Список отрезков o1(X1_1,X2_1), o2(X1_2,X2_2),..., oN(X1_N,X2_N) упорядочить и найти отрезки с минимальной и максимальной длиной.

  27. Даны два списка целых чисел A1,..., AN и B1,...,BN найти

    • max(A1BN, A2BN-1,..., ANB1) и

    • min(max(A1,...,AN), min(B1,...,BN)).

  28. В каждой из девяти клеток квадрата 3х3 разместить одно из чисел 1, 2 или 3 так, чтобы сумма чисел, стоящих в каждом вертикальном ряду, в каждом горизонтальном ряду и на каждой главной диагонали равнялась 6.

  29. В квадрате размером 3х3 расставить числа 1, 2, 3, 4, 5, 6, 7, 8 и 9 так, чтобы суммы чисел, стоящих в каждом вертикальном ряду, в каждом горизонтальном ряду и на каждой главной диагонали были равны.

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

    Стол

    Стул

    Шкаф

    Стул

    Кресло

  31. Решить упрощенный вариант головоломки "пятнашки" (поле размером 3х3, номер старшей фишки - 8) для указываемой начальной позиции. ( Лит-ра: Н.Нильсон. Принципы ИИ... )

  32. Для N произвольно заданных костяшек домино необходимо найти все возможные цепочки из этих костяшек длиной N. Если таких цепочек нет, то выдать максимально длинную возможную цепочку.

  33. Для двух произвольно введенных строк символов определить является ли одна из них инвертированной копией другой без учета пробелов.

  34. Для двух произвольно введенных строк символов определить может ли быть одна строка получена из другой перестановкой символов (без учета пробелов).

  35. Для произвольно введенной последовательности целых чисел определить (и напечатать) максимально длинную подпоследовательность чисел, расположенных в возрастающем порядке.

  36. Для произвольно введенной последовательности символов определить содержатся ли в ней все символы указанного слова в той же последовательности, что и в самом слове. Например: последовательность "development" содержит в себе символы слова "dont".

  37. Для двух произвольно введенных последовательностей символов найти слово наибольшей длины, состоящее из символов, имеющихся в каждой последовательности одновременно и встречающихся в них (последовательностях) в том же порядке, что и в слове.

  38. Написать программу, реализующую беспроигрышную стратегию игры "в крестики-нолики" на поле 3х3. Организовать вывод текущей позиции после каждого хода программы и человека.

  39. Для списка пар целых чисел р1(Х1,Y1), p2(X2,Y2),..., pN(XN,YN), рассматриваемых как координаты точек на плоскости, найти и вывести все прямоугольники и квадраты, все четыре вершины которых располагаются в этих точках. Определить фигуру наибольшей площади.

  40. Написать программу шифрации последовательности А нулей и единиц в последовательность В также нулей и единиц, реализующую следующий алгоритм шифрации:

    • b(1) = a(1);

    • b(j) = 1, если a(j) = a(j-1) и b(j) = 0 в противном случае.

Написать также программу дешифрации В в А.

Список литературы


  1. И.Братко. Программирование на языке ПРОЛОГ для искусственного интеллекта: Пер. с англ. – М.:Мир, 1990. – 560с., ил.

  2. Т.А. Гаврилова, В.Ф. Хорошевский, Базы знаний интеллектуальных систем – учебник. СПб.: Питер, 2001. – 384с.: ил.

  3. Ю.И. Рыжиков. Информатика. Лекции и практикум. – СПб.: КОРОНА принт, 2000. – 256с.


Закрыть ... [X]

1.1. Пример программы: родственные отношения / Программирование на Восстановление кожи на сиденьях авто

Родственные отношения на прологе Родственные отношения на прологе Родственные отношения на прологе Родственные отношения на прологе Родственные отношения на прологе Родственные отношения на прологе Родственные отношения на прологе