Содержание
- 2. Декларативная семантика программ на языке Пролог. Язык Пролог является не алгоритмическим, а декларативным языком программирования. Пролог⎯программа
- 3. Декларативная семантика программ на языке Пролог. Декларативная семантика программы определяет, что истинно и при каких значениях
- 4. Процедурная семантика программ на языке Пролог. С другой стороны, чтобы определить истинностные значения вопроса, надо произвести
- 5. Процедурная семантика программ на языке Пролог. Процедурная семантика ⎯ это процедура вычисления списка целей на основе
- 6. Процедурная семантика программ на языке Пролог. Назовем эту процедуру именем «Вычислить».
- 7. Процедурная семантика языка Пролог определяет встроенные в Пролог⎯систему механизмы логического вывода. Рассмотрим простейшие механизмы логического вывода.
- 8. Правило совпадения Факты в программе не содержат переменных, а вопрос ⎯ простой и основной. В этом
- 9. Правило обобщения факта Факты в программе не содержат переменные, а вопрос ⎯ простой и неосновной. В
- 10. Правило обобщения факта (Конкретизация переменных) Побочным эффектом доказательства будет конкретизация переменных, входящих в вопрос. Конкретизацией называется
- 11. Вычисление конъюнктивного запроса Процедура поиска ответа на конъюнктивный, неосновной вопрос из программы, состоящей из фактов без
- 12. SWI Prolog Вычислительная модель языка Prolog
- 13. Алгоритм унификации – основа вычислительной модели языка Пролог Унификация (или сопоставление) — основной шаг процесса вычисления
- 14. Правила унификации термов Правило 1. Если термы Т1 и Т2 — константы, то они унифицируются только
- 15. Правила унификации термов Правило 2. Если терм Т1—константа или составной терм, а Т2 — неконкретизированная переменная,
- 16. Правила унификации термов Правило 3. Если термы Т1 и Т2 — неконкретизированные переменные, то их унификация
- 17. Правила унификации термов Правило 4. Если Т1 и Т2 ⎯составные термы, то Т1 и Т2 унифицируются
- 18. Явная операция унификации При выполнении логического вывода скрыто от пользователя выполняется большое число операций унификации, обусловленных
- 19. Примеры унификации термов Пример 1. ?⎯2+1=1+2. no Составные термы 2+1 и 1+2 не сопоставимы, и операция
- 20. Примеры унификации термов Пример 2. ?⎯2+1\=1+2. yes Операция отрицания сопоставления термов 2+1 и 1+2 успешна.
- 21. Примеры унификации термов Пример 2. ?⎯2+X=2+1. X=1 yes Операция сопоставления термов 2+X и 2+1 успешна.
- 22. Общая схема согласования целевых утверждений. Самым общим случаем Пролог⎯программы является программа, включающая как факты, так и
- 23. Общая схема согласования целевых утверждений. Процесс вычисления начинается с некоторого исходного вопроса Q, который в общем
- 24. Общая схема согласования целевых утверждений (продолжение) Допустим, что логическая программа P состоит из фактов и правил,
- 25. Общая схема согласования целевых утверждений (продолжение) 1) Цели запроса обрабатываются слева направо, G1 будет согласовываться первой,
- 26. Общая схема согласования целевых утверждений (продолжение) 2) Предложения программы просматриваются интерпретатором сверху вниз.
- 27. Общая схема согласования целевых утверждений (продолжение) 3) Если цель Gi сопоставима с заголовком правила Hj, то
- 28. Общая схема согласования целевых утверждений (продолжение) Редукцией цели Gi с помощью программы P называется замена цели
- 29. Общая схема согласования целевых утверждений (продолжение) На каждом этапе вычисления существует некоторая конъюнкция целей (или одна
- 30. Общая схема согласования целевых утверждений (продолжение) 4) Если цель Gi сопоставима с фактом, то конкретизируются переменные
- 31. Общая схема согласования целевых утверждений (продолжение) 5) Когда мы таким образом достигнем последней цели в запросе,
- 32. Пример вычисления запроса на основе программы, включающей и факты, и правила. Пусть программа содержит утверждения, приведенные
- 33. Шаг 1 вычисления запроса Для вычисления запроса “? ⎯ dark(X),big(X). “ интерпретатор выполняется следующие действия: Текущая
- 34. Шаг 2 вычисления запроса Шаг 2. Текущая резольвента Q2 является конъюнкцией целей black(X),big(X). Выбираем первую цель
- 35. Шаг 3 вычисления запроса Шаг 3. Текущая резольвента Q3 включает одну цель G31 big(‘кот’). Просматривая программу
- 36. Шаг 4 вычисления запроса Шаг 4. Текущая резольвента Q4=Q2 является конъюнкцией целей black(X),big(X). Выбираем первую цель
- 37. Шаг 5 вычисления запроса Шаг 5. Текущая резольвента Q5=Q1 является конъюнкцией целей dark(X),big(X). Выбираем первую цель
- 38. Шаг 6 вычисления запроса Шаг 6. Текущая резольвента Q5 является конъюнкцией целей brown(X),big(X). Выбираем первую цель
- 39. Шаг 7 вычисления запроса Шаг 7. Текущая резольвента Q6 включает одну цель G61 big(‘медведь’). Просматривая программу
- 40. Дерево поиска Процесс вычисления запроса удобно представить в виде дерева поиска. Дерево поиска ответа на любой
- 41. Дерево поиска Для каждого утверждения программы, заголовок которого унифицируется с выделенной в вершине целью имеется ребро,
- 42. Дерево поиска Лист дерева называется успешной вершиной, если существует подстановка, удовлетворяющая последнюю цель в списке целей.
- 43. Дерево поиска dark(X),big(X). Редукция цели dark(X) black(X), big(X). black(’кот’) {X=’кот’} big(’кот’) {X=’кот’} неуспех brown(X), big(X). brown('медведь')
- 44. Механизм автоматического возврата (backtracing) Когда выполнение программы достигает тупиковой вершины отмеченной словом "неуспех", автоматически происходит возврат
- 45. Механизм автоматического возврата (backtracing) Выполнение алгоритм поиска решения можно представить как обход лабиринта, где на каждой
- 46. Механизм автоматического возврата (backtracing). Понятие маркера. Для того, чтобы представить работу механизма автоматического возврата удобно воспользоваться
- 47. Механизм автоматического возврата (backtracing). Понятие маркера. Для каждой цели в запросе Пролог⎯система создает свой собственный маркер,
- 48. Пример поиска решений с возвратом. Пусть программа «Однокурсники» содержит следующие утверждения: student_course(X,Y):⎯student(X,K1), student(Y,K2),X\=Y,K1=K2. student(‘Иванов’,1). student(‘Петров’,4). student(‘Сидоров’,2).
- 49. Пример поиска решений с возвратом. Пусть требуется согласовать запрос: ?⎯ student_course(X,Y). Этот запрос сопоставим с первым
- 50. Поиск первого решения При просмотре фактов student в программе маркеры будут передвигаться следующим образом: (2) student(‘Иванов’,1).
- 51. Поиск второго решения
- 53. Скачать презентацию