Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«новосибирский государственный педагогический университет»
Гришаева А.П.
Методическое пособие
по курсу «Основы искусственного интеллекта»
Новосибирск, 2012
|
Удк ббк г |
Печатается по решению Редакционно-издательского совета НГПУ |
Рецензенты:
Городняя Л.В., к.ф-м.н., старший научный сотрудник Института систем информатики имени А.П. Ершова
Жуков А.В., старший преподаватель, ведущий программист Новосибирского государственного педагогического университета
Научный редактор:
Заведующий кафедрой информатики и дискретной математики
Новосибирского государственного педагогического университета
профессор, доктор физико-математических наук
В.Л. Селиванов
Г Гришаева А.П.
Методическое пособие по курсу «Основы искусственного интеллекта» –Новосибирск: Изд. НГПУ, 2011 –с.
В работе описаны рекомендации для выполнения лабораторных работ по системам программирования на языке Турбо-Пролог, Common Lisp и рекомендуемую литературу. Методическое пособие предназначено для студентов педагогических вузов, изучающих логическое и функциональное программирование.
© Новосибирский государственный
педагогический университет, 2012
1. Описание лабораторных работ по языку логического программирования Пролог
Порядок выполнения работ:
· Изучить краткие теоретическое сведения к лабораторной работе.
· Выполнить предложенные задания из практической части.
· Оформить отчет по лабораторной работе, содержащий по каждому выполненному заданию постановку задачи, текст программы и результаты работы.
1.1. Лабораторная работа по теме: «Реализация простейших программ в системе программирования Турбо –Пролог»
Учебные цели: Знакомство с системой программирования Турбо-Пролог. Приобретение умений и навыков pаботы с системой пpи ее настpойке, pазpаботки пpостейших пpогpамм с фактами, pазличными типами данных, внутpенней и внешней целью.
Пролог –зто язык логического программирования (ПРОграммирование в ЛОГике), используемый для представления и манипулирования знаниями в системах искусственного интеллекта. Он был разработан в начале семидесятых годов в университете Марселя (Франция) под руководством А. Колмероэ. В логическом программировании использует механизм доказательства теорем в логике, который позволяет выяснить, является ли противоречивым некоторое множество логических формул. При этом программа рассматривается как набор логических формул, описывающих предметную область, совместно с теоремой, которая должна быть доказана. Логическое программирование избавляет программиста от необходимости определять точную последовательность шагов выполнения вычислений. Пролог является декларативным языком. Программы на этом языке содержат объявления логических взаимосвязей, необходимых для решения задачи. Обозначения, используемые в Прологе для выражения логических взаимосвязей, унаследованы из логики предикатов. Декларативный смысл программы состоит в том, что она определяет, является ли данная цель истинной. Если является, то программа выясняет, при каких значениях переменных эта цель достигается. Процедурный же смысл программы состоит в определении порядка действий, с помощью которых данная цель достигается.
С точки зрения логики предикатов элементарные выражения имеют вид:
P(A1,A2,..,An),
где P –имя предиката;
A1, A2 ,.., An –аргументы.
Программа на языке Пролог представляет собой набор утверждений, составляющих базу фактов и базу правил, к которым допустимо обращение с запросами, касающимися их содержимого. Запросы называются целевыми утверждения. Утверждение языка Пролог –это линейная конструкция из термов, заканчивающаяся точкой. Структура программы в языке Пролог может состоять из нескольких разделов, которые не являются обязательными. К ним относятся разделы:
1. директивы компилятора;
. CONSTANTS для описания констант;
. DOMAINS содержит описания доменов (типов). Раздел применяется только, если в программе используются нестандартные домены;
. DATABASE предназначен для описания предикатов внутренней базы данных;
. PREDICATES содержит описания предикатов. Он применяется, если в программе используются нестандартные предикаты;
6. CLAUSES –раздел предложений,в котором записываются предложения факты и правила вывода;
7. GOAL предназначен для записи внутренний цели (запроса).
Использование директив компилятора дают компилятору дополнительные инструкции по обработке программы. В самом начале программы можно расположить одну или несколько директив компилятора. Директива trace применяется при отладке программы для трассировки. Этот процесс аналогичен пошаговому выполнению программы на языке Паскаль с контролем за изменением значений переменных. В том случае, когда после ключевого слова trace указаны имена предикатов через запятую, то трассировка идет только по этим предикатам. В противном случае – по всем предикатам программы. Во время исполнения программы при включенной трассировке в специальном окне трассировки будет отображаться следующая информация после служебных слов:
Переход от одной подцели к другой вызывается нажатием функциональной клавиши F10. При этом в окне редактирования на выполняющуюся подцель указывает курсор, кроме того, она отображается в окне трассировки с параметрами и дополнительной информацией.
Директива nowarnings используется для подавления предупреждения системы о том, что какая-то переменная встречается в предложении только один раз. Эту директиву стоит использовать только в хорошо отлаженных программах. Как правило, для подавления такого предупреждения ("WARNING: The variable is only used once") достаточно заменить переменную, которая встретилась только один раз, на анонимную переменную.
С помощью директивы include при компиляции в исходный текст можно вставить содержимое некоторого файла. Заметим, что многие директивы компилятора могут быть не только расположены в тексте программы, но и установлены в меню среды разработки Турбо Пролога (Options–Compiler Directives). Значение директивы компилятора, указанное в тексте программы, имеет более высокий приоритет, чем значение, установленное в меню.
При написании программ без разделов DOMAINS, PREDICATES и GOAL действительно можно обойтись, кроме того, можно написать программу и без CLAUSES. К примеру:
GOAL
write (“Введите Ваше имя: ”), readln (Name), write (“Здравствуйте, ”, Name, “!”).
Как правило, программа содержит разделы PREDICATES и CLAUSES.
База фактов в языке Пролог –это последовательность утверждений, описывающих факты предметной области в виде структур, функторами которых являются атомы –имена отношений (предикатные буквы), а компонентами –предметные константы. Каждый факт представляет собой элементарную формулу (предикат) исчисления предикатов первого порядка и является дизъюнктом Хорна, состоящим из одного (положительного) литерала. При описании фактов переменные не используются.
База правил –это совокупность правил в программе в языке Пролог. Правило представляет собой дизьюнкт Хорна, содержащий один положительный и несколько отрицательных литералов, записанный в виде:
<структура-0>:-<структура-1>, ... ,<структура-N>.
Здесь каждая структура представляет собой предикат, областью действия переменных является все правило. Предикат, стоящий слева от атома ":-", называется заголовком правила, все остальные предикаты образуют его тело. Правило может трактоваться следующим образом: предикат, являющийся заголовком правила доказан, если доказан каждый предикат тела правила. В качестве предикатов, составляющих тело правила, могут выступать:
· предикаты, содержащиеся в базе фактов;
· предикаты, совпадающие с заголовком других правил;
· встроенные предикаты.
Встроенный предикат –это предикат, выводимость (согласованность) которого устанавливается непосредственно системой программирования Пролог.
Запрос в языке Пролог –это целевое утверждение, имеющее следующий вид:
<структура-1>, ...,<структура-N>.
Каждая структура представляет собой предикат, возможно, содержащий переменные. Областью действия переменной является все утверждение в целом, т. е. одна и та же переменная в пределах утверждения означает один и тот же объект. Символ "," между предикатами обозначает логическую связку "И", т.е. запрос необходимо рассматривать как требование на поиск в базе фактов и правил информации, удовлетворяющий одновременно всем предикатам целевого утверждения. Предикаты, объединенные связкой "И" в таком запросе, называются подцелями (имея в виду весь запрос целью).
Выполнение запроса в языке Пролог –это процесс доказательства выводимости всех подцелей целевого утверждения методом резолюции с использованием линейной по входу стратегии. Получив запрос, состоящий из нескольких предикатов, интерпретатор выбирает первый в последовательности запроса предикат и, если этот предикат не встроенный, делает попытку согласовать его с утверждениями, составляющими базу фактов и правил. Для этого выполняется сопоставление этого предиката со всеми фактами и заголовками этих правил в простом линейном порядке до тех пор, пока оно не даст положительного результата. Если этого не происходит, ответом на запрос будет "NO". В ходе согласования возможна конкретизация переменных значениями.
В том случае, если в ходе просмотра произошло сравнение с заголовком правила, то тело правила рекурсивно рассматривается в качестве нового целевого утверждения. Удовлетворив один предикат (подцель) запроса, интерпретатор переходит к следующему справа, обрабатывая его аналогичным образом. Запрос считается выполненным после доказательства истинности его последней (крайней справа) подцели. Одной из важнейших особенностей языка Пролог является возможность поиска всех решений. Поиск всех решений достигается посредством использования механизма поиска с возвратом.
Можно сформулировать четыре основных правила поиска с возвратом:
• правило 1: подцели должны быть согласованы по порядку, слева направо;
• правило 2: предложения проверяются в том порядке, в котором они появляются в тексте программы;
• правило 3: когда подцель сопоставляется с заголовком правила, тело этого правила должно быть доказано (тело правила состоит, в свою очередь, из новых подцелей, которые должны быть доказаны);
• правило 4: целевое утверждение считается согласованным, когда соответствующие факты найдены для каждой листьевой вершины дерева целей.
Типы данных в языке Пролог
Домен в языке Пролог определяет множество допустимых значений, которые может принимать объект, принадлежащий к нему. Аналогично другим языкам программирования, в Прологе существует несколько стандартных доменов:
1. integer –целые числа от - 32768 до 32767;
2. real –действительные числа от +1E-307 до +1E308, например,5.457, -65344, 1.25Е23;
. string –строки (любая последовательность символов, заключенная в кавычки);
. char –одиночный символ, заключенный в апострофы;
. symbol –последовательность из не более 250 латинских букв, цифр и символов подчеркивания, которая начинается со строчной буквы или заключена в кавычки (при этом допускается применение заглавных букв и русского алфавита), например, person, a4,"Piter" , "Москва".
Система Турбо-Пролог позволяет пользователю вводить собственные имена типов доменов для указания смысла аргумента предиката. Атомом называют любой набор символов алфавита, заключенный в кавычки, или набор строчных букв и цифр, начинающийся с буквы, к примеру,
"анна", "Alpha", "betta4", alpha, x4.
Атомами не являются наборы:
1 b, #n, a-b
Переменная в языке Пролог –это последовательность букв, цифр и знака "подчеркивание", обязательно начинающаяся с прописной буквы. Имя переменной дается по следующим правилам: имя должно начинаться с заглавной латинской буквы или символа подчеркивания, после которых могут следовать латинские буквы, цифры или символы подчеркивания.
К примеру:
First_list
X
Person
City
Область видимости (лексический диапазон) переменных ограничено одним предложением. Одно и то же имя в предложениях программы обозначают разные переменные. Переменная, не имеющая значения, называется свободной, переменная, имеющая значение –конкретизированной. Переменная может быть конкретизирована каким-либо значением или нет. Конкретизация переменной –это связывание переменной языка Пролог с конкретным значением. Конкретизация переменной обеспечивает возврат искомых значений переменных по запросам. Операция сопоставления заключается в следующем: в Прологе берутся два терма и пытаются сделать их идентичными, подбирая соответствующую конкретизацию переменных в обоих термах. В том случае, если сопоставление завершается успешно, в качестве результата выдает наиболее общую конкретизацию переменных. Принудительно изменить значение переменной, уже получившей значение нельзя. В Прологе отсутствует явно конструкция присваивания. Эту функцию время от времени берет на себя операция равенства. К примеру, цель:
…, X=5, …
Она будет рассматриваться, как сравнение или как присваивание. Это зависит от того, получила ли какое-либо значение переменная X к моменту доказательства этой цели. Если переменная X имеет значение (к примеру, равное 6), то равенство (=) работает как операция сравнение. Если же переменная X свободна (не имеет никакого значения), то операция равенство работает как присваивание. При этом совершенно неважно, слева или справа от знака равенства находится имя переменной. Главное, чтобы переменная в этот момент была свободной. С точки зрения программы на языке Пролог следующие две цели совершенно одинаковы:
…, X=5, …
…, 5=X, …
Важно, чтобы переменная X была свободной. Отсюда следует, что цель будет всегда ложной, если записана в виде:
…, X=X+5, …
Действительно, если переменная X в процессе доказательства цели, связана со значением равным 10, то тождественно ложная цель:
…, 10=10+5, …
Результат будет равен "NO".
Если же переменная X свободна, то нельзя к переменной, не имеющей никакого значения, прибавить 5, и присвоить эту неопределенность той же самой переменной. С целью изменения значения переменной необходимо использовать новое имя, поскольку переменная, которая появляется в тексте программы впервые, считается свободной, и может быть конкретизирована некоторым значением. При этом не важен порядок записи относительно знака "=". Если переменная X конкретизирована некоторым числом, следующие цели выполняются как присваивание:
…, X+5=Y, … …, Y=X+5, …
Существуют в языке Пролог специальные переменные, которые называются анонимными. Их имя состоит только из знака подчеркивания ( _ ). Анонимные переменные используются в случаях доказательства цели, когда значение переменной несущественно, но переменная должна быть указана потому, что аргументы у предикатов позиционные и количество их фиксированно.
К примеру:
predicates
parent (symbol, symbol)
clauses
parent (“Владимир”, “Михаил”).
parent (“Владимир”, “Светлана”).
parent (“Анна”, “Михаил”).
parent (“Анна ”, “ Светлана”).
Факты описывают информацию о родителях и их детях (первый аргумент –имя родителя, второй –имя ребенка). Если использовать внешний запрос:
Goal: parent (Person, Child).
Результаты запроса получим:
Person=Владимир, Child=Михаил
Person=Владимир, Child=Светлана
Person=Анна, Child=Михаил
Person=Анна, Child=Светлана
Solutions
В том случае, когда необходимо узнать только имена родителей без имен детей, к программе можно обратиться с внешним запросом, используя анонимную переменную:
Goal: parent (Person, _).
Решение в данном случае будет иметь следующий вид:
Person=Владимир
Person=Владимир
Person=Анна
Person=Анна
4 Solutions
1.1.2. Общие сведения о системе Турбо Пролог
Запустите файл prolog.exe. После заставки Пролога на экране появятся четыре окна:
Окна служат для ввода и вывода сообщений, команд, директив, программ, результатов. В верхней строке экрана находится главное меню Пролога с режимами (опциями) работы системы и выпадающими меню команд. Познакомьтесь с командами, которые содержатся в выпадающих меню. Для этого последовательно вызовите режимы главного меню:
File, Compile, Option, Setup.
Режимы Edit и Run не имеют подменю. При выборе режима пользуйтесь курсором и клавишей ввода. Для выхода из режима в главное меню нажмите клавишу Esc.
Режимы главного меню предназначены для выполнения следующих функций:
Files –управление файлами, переход в DOS, выход из системы;
Edit –вызов встроенного текстового редактора;
Run –компиляция и запуск программы на выполнение;
Compile –компиляция программ и проектов, состоящих из модулей;
Options –установка параметров компилятора, редактирование
файла с описанием проекта;
Setup –установка параметров среды (размера и цвета окон и др.).
Подменю режима File содержит следующие команды:
Load –загрузка программы для редактирования и выполнения;
Pick –вызов списка семи последних программ;
New file –очистка памяти перед набором новой программы;
Save –запись программы на диск под старым или "дежурным" именем;
Write to –запись программы под задаваемым именем;
Directory –вызов каталога;
Change –изменение рабочего каталога;
DOS shell –временный выход в DOS (возврат по команде Exit);
Quit –выход из системы.
Встроенный редактор Edit используется для набора и ввода исходного текста программы на Прологе и ее редактирования при исправлении допущенных ошибок и внесении необходимых изменений. Он работает с обычными командами перемещения курсора, имеет команды вставки и удаления символов и строк (Ins, Del, Ctrl+N,Ctrl+Y и др.), команды работы с блоками (Ctrl+K B, Ctrl+K K, Ctrl+K C и др.), команды поиска и замены (Ctrl+Q P и др.)
Режим Compile устанавливает различные режимы компиляции исходной программы:
В режиме Options имеется разветвленная система подменю с многочисленными командами для задания:
Режим Setup используется для установки или временного изменения параметров системы Пролог, хранящихся в файле .SYS. Это такие параметры системы:
1.1.3. Практическая часть
Задание 1. Сформулировать и записать на естественном языке:
1. лечит(врач, больных);
2. учится(мой_брат, школа);
. учится(моя_сестра, институт);
. лечит(врач, петров, больной, сидоров);
. кассир(сидоров);
. играл(оркестр,популярная_музыка);
. заблудилась(маша, лес);
. протекла(старая_крыша);
. падают(неосторожные_инспектора, лестница);
. подтачивает(боль, сила, человек);
. не_нужна(расческа, лысый);
. совершают(невнимательные, люди, оплошности);
. не_забывают(внимательные, люди, обещания);
. ходят(разумные, люди, ноги);
. ходят(не_разумные, люди,руки).
Задание 2. Записать на Прологе следующие факты:
1. Золото является ценным.
2. Иванов –студент математического факультета.
. Земля имеет форму шара.
. Писатель пишет книги.
. Ученый занимается наукой.
. Писатель Лев Толстой написал книгу «Война и мир».
. Этот треугольник равносторонний.
. Федор Шаляпин –великий русский певец.
. Чарли Чаплин –великий кинорежиссер, актер, композитор.
. Дом состоит из фундамента, крыши, стен и окон.
. Квадрат гипотенузы равен сумме квадратов катетов.
. Река Волга впадает в Каспийское море.
13. Колумб открыл Америку.
Задание 3. Программа на языке Пролог описывает базу "Овощи и фрукты". Целевое утверждение следующее: необходимо выдать название имеющегося фрукта. Комментарии в программе записываются в скобках /* комментарии */ или в конце строки после знака процента %.
Программа имеет вид:
/* Программа "Овощи и фpукты." */
/* Пpостая пpогpамма с фактами. Цель внутpеняя/внешняя.*/
predicates
fruit(symbol) % В этом разделе точка не ставится.
vegetables(symbol)
clauses
fruit("яблоко"). % В этом разделе точка ставится.
fruit("слива").
fruit("апельсин").
vegetables("капуста").
vegetables("свекла").
goal
fruit(X),write(X),nl. % В этом pазделе точка ставится.
1. Познакомьтесь со структурой программы и содержанием представленных в ней фактов.
2. Наберите текст программы в режиме Edit.
. Выйдите в главное меню нажатием клавиши Esc.
. Вызовите программу на исполнение выбором в главном меню режима Run. Объясните полученный ответ.
. Выйдите в главное меню и вызовите pедактоp с загpуженной в него пpогpаммой. Измените цель в пpогpамме и узнайте, какие имеются овощи и какой ответ выдает система на вопpос типа: fruit("слива").
. Пеpейдите к pаботе с внешней целью. Исключите внутpеннюю цель. В окне диалога (Dialog) последовательно вводите цели. Задайте вопросы о том, является ли фруктом ананас, яблоко. Узнайте, относится ли к овощам капуста. Сформулируйте запрос о каких фруктах и овощах имеются сведения в базе данных.
Сравните ваши записи вопросов для внешней цели с ниже следующими:
Обратите внимание на форму ответов системы и объясните, почему выдан отрицательный ответ на вопрос об ананасе и множественные ответы на вопросы об известных овощах и фруктах.
Задание 4. Создать англо-русский словарь.
Составьте программу по теме "Англо-русский и русско-английский словарь" из 10-20 слов по одной из тем уроков английского языка. Для набора и ввода программы необходимо очистить память. Для этого выберите в главном меню раздел File и выполните имеющуюся в нем команду New file. Затем перейдите в редактор (раздел Edit).
Задание 5. Создать справочник по истории.
Создайте фрагмент учебной информационно-справочной программы по истории "Президенты США". Воспользуйтесь приведенными ниже данными с фамилией, годом рождения, принадлежностью к партии, годами правления, штатом для нескольких президентов США:
Создайте следующие запросы:
1. Когда родился и из какого штата был президент Джонсон?
. Кто из президентов представлял республиканскую партию США?
. В какой период был президентом Никсон?.
Задание 6. Построить базу данных на языке Пролог из следующих взаимосвязанных фактов:
1. Карл у Клары украл кораллы. Клара у Карла украла кларнет.
. У попа была собака. Он ее любил. Она съела кусок мяса. Он ее убил. И в землю закопал. И надпись написал.
Задание 7. Построить базу данных на языке Пролог из следующих фактов:
У мельника было три сына. Мельник оставил наследство. Оно состояло из мельницы, осла и кота. Старший сын взял мельницу. Средний сын взял осла. Младшему сыну дали кота.
Задать к этой базе данных следующие запросы на Прологе:
1. Кто был у мельника?
2. Что оставил мельник?
3. Из чего состояло наследство?
4. Что взял старший сын?
5. Что дали младшему сыну?
Задание 8. Построить базу данных, содержащую сведения о днях рождении друзей и их хобби. Сформулировать запросы.
Оформление отчета
Отчет по работе должен включать исходные тексты выполненных программ и целями, с которыми они работали, и должен содержать:
Вопросы для самоконтроля
1. Сформулируйте определения понятий:
2. Синтаксис чисел, атомов, переменных, структур, предложений, фактов, правил, запросов, комментариев.
3. Структура программы на Прологе.