мама(Саша,Петя)<-!;
мама(Наташа,Ваня)<-!;
мама(Оля,Петя)<-!;
мама(Катя,Даша)<-!;
мама(Люда,Сережа)<-!;
мама(Петя,Костя)<-!;
к базе знаний может быть задан вопрос
?мама(x,Даша); ответ системы Пролог-Д:
x=Kатя ДРУГИХ РЕШЕНИЙ НЕТ.
После нахождения первого решения поиск альтернатив не производится.
Контрольные вопросы и задания
Задание: 1. Составьте базу знаний о своих родственниках с указанием родственных отношений и возраста.
Задание: 2. Составьте программу, которая подсчитывает число людей с одинаковыми именами - тезок среди ваших родственников.
Задание: 3. Составьте программу, которая определит имя самого молодого и самого старого человека среди вашей родни.
Тема3: Рекурсия.
| Содержание лекции | Содержание лабораторного занятия |
| Стратегия управления и механизм вывода в ИИС. Общие методы поиска решений в пространстве состояний: методы перебора, эвристические методы поиска, метод редукции. Дедуктивные методы поиска решений: на основе логики предикатов первого порядка, методом Эрбрана и методом резолюций. Методы поиска решений в больших пространствах состояний. Методы поиска решений в условиях нечеткости: недетерминированность управления выводом | Стратегия управления и механизм вывода в ИИС. Дедуктивные методы поиска решений: на основе логики предикатов первого порядка, методом Эрбрана и методом резолюций. Методы поиска решений в больших пространствах состояний. Методы поиска решений в условиях нечеткости: недетерминированность управления выводом. Рекурсивные правила. Применение рекурсии для описания задач при работе с системами логического программирования |
Задание: Составить базу знаний для своего варианта используя рекурсию. Написать программу иллюстрирующую рекурсию несколькими примерами построения программ на языке Пролог-Д
Исполнение: Написать программу иллюстрирующую рекурсию несколькими примерами построения программ на языке Пролог-Д, как вычислительных, так и логических.
Лабораторная установка: Персональный компьютер с ОС Windows, MS Office, языке Пролог-Д, являющемся учебной версией классического Пролога.
Оценка: Рассматривают содержание нового направления информатики (базы знаний) и особенности его реализации.
Время выполнения работы: 4 часа.
Методические указания
Существует огромное количество задач, в которых отношения между объектами можно определить, только используя сами определяемые соотношения. При этом получаются правила, называемые рекурсивными. Применение рекурсии для описания задач при работе с системами логического программирования широко распространенный прием. Рекурсия будет проиллюстрирована несколькими примерами построения программ, как вычислительных, так и логических. Первым примером будет пример вычисления наибольшего общего делителя (НОД) двух чисел. Предикат, который выполняется, если найден НОД двух данных чисел будет иметь имя нод и три аргумента: числа a,b и значение НОД - c. Для описания вычисления НОД используются следующие соображения. Во-первых, если, а=b, то c=a=b; Во-вторых, если, а>b, то необходимо вычислить НОД для чисел b и a-b; В-третьих, если b>a, то необходимо вычислить НОД для чисел a и b-a. Эти три утверждения естественным образом могут быть записаны на Прологе-Д.:
нод(а,а,а);
нод(а,b,c)<-БОЛЬШЕ(а,b),ВЫЧИТАНИЕ(a,b,d),нод(b,d,c);
нод(а,b,c)<-БОЛЬШЕ(b,а),ВЫЧИТАНИЕ(b,a,d),нод(a,d,c);
ВЫЧИТАНИЕ(X,Y,Z)<-УМНОЖЕНИЕ(1,X,Z,Y);
Если к этой базе знаний задать вопрос:
?нод(10,15,x);
ответ системы Пролог-Д:
x=5 ДРУГИХ РЕШЕНИЙ НЕТ
Предикат нод, определенный выше оказывается обратимым. В качестве второго примера рассматривается задача о вычислении элементов последовательности: 0, 1, 1, 2, 3, 5, 8, 13, 21 ,34, 55, 89, 144,... , известной как последовательность Фибоначчи. Каждый элемент ее определяется следующими правилами:
f0 =0,
f1 =1,
fn =fn-1+fn-2, при n>1
Первая формула соответствует утверждению о том, что значение нулевого элемента последовательности равно нулю. Это можно записать в виде факта: Фиб(0,0);. Вторая строка соответствует утверждению: первый элемент равен 1. На Прологе-Д это можно записать так: Фиб(1,1);. Третья строка представляет собой запись рекурсивного соотношения:
Фиб(N,X)<-БОЛЬШЕ(N,1),ВЫЧИТАНИЕ(N,1,М),
ВЫЧИТАНИЕ(N,2,К), Фиб(М,Y), Фиб(K,Z),
СЛОЖЕНИЕ(Y,Z,X);
ВЫЧИТАНИЕ и СЛОЖЕНИЕ - имена предикатов вычитание и сложение, определяемых с помощью правил:
СЛОЖЕНИЕ(X,Y,Z)<-УМНОЖЕНИЕ(1,X,Y,Z);
ВЫЧИТАНИЕ(X,Y,Z)<-УМНОЖЕНИЕ(1,X,Z,Y);.
Данные предложения представляют собой базу данных на языке Пролог-Д, позволяющую вычислять значения элементов последовательности. B ответ на вопрос:
?Фиб(10,X);
ответ системы Пролог-Д:
x=55 ДРУГИХ РЕШЕНИЙ НЕТ
Необходимо сказать, что такой путь решения данной задачи не самый лучший. Для нахождения N+1 числа Фибоначчи требуется 2* (N+1)-1 рекурсивное обращение. Однако этого можно избежать, если перейти к другой базе знаний, в которой предикат с именем "Фиб" определен как трехарный, то есть имеющий три аргумента, включающий в себя в качестве аргумента значения N-ого и N-1- ого элементов последовательности. Такая база знаний получается в результате перевода на язык Пролог-Д утверждений.
1. 0-ой элемент последовательности есть 0, а (-1) -ый элемент не определен. Фиб(0,x,0);.
Второй аргумент обозначен x. В данном случае значение x может быть любым.
2. 1-й элемент последовательности есть 1, а нулевой-0. Фиб(1,0,1);. 3. N -й член последовательности Фибоначчи определяется через (N-1) -Й член последовательности.
Фиб(N,F,f)<-БОЛЬШЕ(N,1),ВЫЧИТАНИЕ(N,1,M),Фиб (M,Ф,F), СЛОЖЕНИЕ (Ф, F, f);.
Обращение к этой базе знаний будет иметь вид:
?Фиб(10,F,f);.
ответ системы Пролог-Д:
При работе с этой базой знаний для вычисления N - го числа Фибоначчи необходимо всего лишь N рекурсивных обращений. Для системы Пролог-Д характерна особенность, проявляющаяся при работе с рекурсивными программами. В общем случае, порядок предложений в базе знаний не имеет значения. Однако, в нижеследующем примере это не так
родитель(X)<- родитель(Y),отец(Y,Z);
родитель(Коля);
отец(Коля, Петя);
родитель(Петя);
В первом предложении голова имеет то же имя, что и одна из целей - "родитель". В процессе поиска ответа в этой базе знаний будет применено правило: предложение, стоящее первым, будет и применено первым - известное как принцип поиска в глубину. Это приведет к тому, что система будет обращаться только к первому предложению базы знаний и ответ на вопрос ?родитель(Петя); не будет найден никогда. Вместе с тем, небольшое изменение базы знаний, перестановка двух предложений местами, приводит к удачному поиску решения:
родитель(Коля);
родитель(X)<-родитель(Y), отец(Y,X);
отец(Коля, Петя);
?родитель(Петя);.
Неограниченно-повторное обращение к предложению может быть и более замаскированным так, как это получается в примере:
ВЫШЕ(А,В)<-НИЖЕ(В,А);
НИЖЕ(В,А)<-ВЫШЕ(А,В);
ВЫШЕ(Коля, Петя);
?НИЖЕ(Петя, Коля);.
Однако если третье предложение стоит на первом месте, то повторного обращения не произойдет и ответ будет найден. Такая ситуация называется петля. При вычислении элементов последовательности Фибоначчи, может появляться бесконечная петля при исполнении программы. В самом деле, если вопрос имеет вид:
?Фиб(0,x,y);,
то первый возможный результат x =_0, y =1. Далее в попытке отыскать следующее решение возникает бесконечная петля, так как будет отыскиваться Фиб(-1,x,y), Фиб(-2,...),... . Для контроля за подобной ситуацией необходима модификация базы знаний. Первые два предложения должны быть записаны в виде:
Фиб(0,x,1)<-!;
Фиб(1,1,1)<-!;,
тогда при поиске альтернативного решения после получения ответа на вопрос:
?Фиб(0,x,y); x=_0, y =1
будет получен результат:
ДРУГИХ РЕШЕНИЙ НЕТ.
Данный пример иллюстрирует первое возможное использование предиката "отсечение". И еще одно чисто эстетическое предложение. База знаний на Прологе-Д будет выглядеть лучше, если предложения с одинаковыми именами расположены в одном месте. Для сравнения приводится две базы знаний:
1. 2.
мама(Таня, Надя); мама(Таня, Надя);
бабушка(X,Y)<-мама(X,Z), мама(Надя, Катя);
мама(Z,Y), бабушка(X,Y)<-мама(X,Z),
мама(Надя, Катя); мама(Z,Y);.
Контрольные вопросы и задания
Задание:1. Написать на языке Пролог-Д базу знаний, описывающую вычисление факториала.
Задание:2. Написать на языке Пролог-Д базу знаний, описывающую вычисление суммы чисел натурального ряда.
Задание:3. Написать на языке Пролог-Д базу знаний, описывающую вычисление суммы квадратов чисел натурального ряда.
Задание:4. Описать вычисление наименьшего общего кратного.
Задание:5. Описать на Прологе-Д сказку про попа, у которого была собака.
Тема4: Графические возможности. Графика образов.
| Содержание лекции | Содержание лабораторного занятия |
| Трехкомпонентная (зрительная, лингвистическая и сценарная) организация интерфейса пользователя (ИП) ИИС. Влияние новых информационных технологий на реализацию интеллектуального сервиса ИП. Объяснение и обоснование решений в ИИС. Объектный подход к проектированию ИП. Основные этапы технологии проектирования интеллектуальных ИП. Интерфейс эксперта и пользователя. | Трехкомпонентная (зрительная, лингвистическая и сценарная) организация интерфейса пользователя (ИП) ИИС. Влияние новых информационных технологий на реализацию интеллектуального сервиса ИП. Объяснение и обоснование решений в ИИС. Объектный подход к проектированию ИП. Основные этапы технологии проектирования интеллектуальных ИП. Интерфейс эксперта и пользователя. Компьютерной графике, построение изображения на экране. Набор графических примитивов, отображающих графические объекты. Графические встроенные предикаты. |
Задание: Составить базу знаний для своего варианта используя графические возможности. Написать программу, реализующего функции графических возможностей в системе Пролог-Д.