3506 ФУНКЦИОНАЛЬНОЕ И ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Рабочая программа

Цели и задачи дисциплины

Целью изучения дисциплины являются получение студентами базовых знаний по логическому программированию и приобретение навыков составления и отладки программ на языке логического программирования для решения задач представления и использования знаний о предметной области.  Полученные знания должны использоваться при изучении других дисциплин, таких как “Системы искусственного интеллекта”, ”Проектирование интеллектуальных систем”, а также при выполнении расчётных заданий,  курсовых работ и дипломной работы по этим дисциплинам.

Требования к уровню освоения содержания дисциплины

Студенты должны хорошо усвоить следующие понятия:

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

Студенты должны уметь:

  • описать предметную область с помощью программы на Прологе;
  • отладить программу в программной среде для ряда запросов.

Содержание дисциплины

Представление знаний с помощью фактов и правил. Структура программы. Утверждения: факты, правила, вопросы. Константы и переменные.

Общая схема выполнения программы: сопоставление с образцом, унификация аргументов, процесс возврата (бектрекинг).

Арифметические и операторные выражения. Ввод и вывод термов. Работа с файлами.

Управление выполнением программы. Организация разветвляющихся процессов. Организация повторяющихся процессов.  Встроенные предикаты fail, repeat. Организация получения всего множества решений. Преобразование базы знаний с помощью встроенных предикатов.

Рекурсия. Виды рекурсий: восходящая рекурсия, нисходящая рекурсия. Управление возвратом с помощью  отсечения.

Списки. Ввод-вывод списков. Голова и хвост списка. Операции со списками. Представление информации с помощью списков. Сортировка списков.

Строки. Представление строк в виде списков кодов символов. Преобразование строк. Операции со строками. Ввод и вывод строк на терминал и в файл.

Структура. Определение структуры. Обработка информации в структурах. Создание структур и работа с компонентами структур. Примеры использования языка логического программирования для решения задач искусственного интеллекта.

Лабораторный практикум

  1. Описание предметной области с помощью программы на Прологе.
  2. Общая схема выполнения программы на языке Пролог.
  3. 3. Арифметические выражения. Ввод и вывод термов. Обработка файлов.
  4. Управление выполнением программы с помощью предикатов fail и repeat.
  5. Рекурсия.
  6. Списки.
  7. Литеры, атомы и строки.

Содержание тем контрольной работы

Контрольная работа включает ряд теоретических и практических вопросов по следующим темам.

  1. Описание предметной области с помощью программы на Прологе.
  2. Общая схема выполнения программы на языке Пролог.
  3. Управление выполнением программы с помощью предикатов fail и repeat.
  4. Рекурсия.
  5. Списки.

Методические указания к контрольной работе

Перед выполнением работы необходимо изучить теоретический материал,   изложенный ниже   и    в [1-7], разобрать приведенные примеры по темам и ответить на контрольные вопросы.

Контрольная работа состоит из выполнения по каждой теме  контрольных заданий под номером KV, указанным преподавателем  или совпадающим с номером в журнале KV. Каждое задание содержит две части: теоретическую и практическую. Теоретическая -  предполагает ответ на контрольный вопрос, номер которого определяется по формуле N=KV mod NV, где NV – число вопросов по теме. Практическая – написание и отладку программы на языке Пролог; отчет по второй части должен содержать задание, текст программы и протокол решения с полученными результатами.

1.  ОПИСАНИЕ  ПРЕДМЕТНОЙ   ОБЛАСТИ   С   ПОМОЩЬЮ  ПРОГРАММЫ НА ПРОЛОГЕ

Пролог - это язык программирования, предназначенный для представления и использования знаний о некоторой предметной области. Под предметной областью будем понимать множество рассматриваемых объектов и совокупность знаний о них. Любую взаимосвязь между объектами и (или) их свойствами назовем отношением. Так, например, для предметной области "Студенческая группа" характерными объектами будут студент, его фамилия, имя, отчество, номер группы, наименование факультета, номер специальности, курс обучения, изучаемые дисциплины, оценки, полученные на экзаменах, размер стипендии и т.д. Связи между конкретным студентом и номером группы, между его оценками и размером стипендии, между номером группы и факультетом, специальностью, курсом обучения будут являться отношениями. Таким образом, Предметная область – это объекты и отношения.

Объекты могут быть объединены в классы, обладающие определенными свойствами. Элементы этих классов являются конкретными объектами предметной области. Для представления конкретного объекта в программе на Прологе  используется константа. Константа – это число или символическое имя объекта.

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

Символическое имя (атом) - это:

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

Например: table1, stock_5, r5z, 'студент', 'машина', 'меню', 'Закон', 'список аргументов'.

Для описания в программе некоторого объекта, принадлежащего определенному классу, используется  переменная. Переменная в программе представляется своим именем. Имя переменной в Прологе  - это цепочка латинских букв или цифр, начинающихся с прописной латинской буквы или символа подчеркивания. Примеры имен переменных: D, Leda, X, Y, Lokon, V2 и т. д.

Чтобы описать отношение, необходимо указать его имя и перечислить либо классы объектов, либо конкретные объекты, связываемые этим отношением:

<имя отношения>(<имя объекта1>,<имя объекта2>,…,<имя объекта n>).

Отношение характеризуется именем и числом аргументов. Число аргументов равно числу классов объектов, связанных этим отношением. Для описания отношений в программе на Прологе используются предикаты. Предикат – это логическая функция  от n аргументов, имеющая только два значения «истина» и «ложь». Синтаксис предиката:

<имя предиката>(<аргумент1>,< аргумент 2>,…,< аргумент n>).

При описании отношения имя предиката совпадает с именем отношения, а аргументы предиката – это связываемые отношением объекты. Если описываемое предикатом отношение имеет место в предметной области, то предикат принимает значение «истина», если оно несправедливо для данной предметной области, то значение предиката «ложь».

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

<заголовок>.

или

<заголовок>:- <тело>.,

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

Тело утверждения состоит либо из одного предиката, либо из списка предикатов, перечисленных через запятую. Каждый предикат описывает какое-либо отношение. Знак «:-» соответствует слову  «если». Утверждение читается так: «отношение, стоящее в заголовке будет истинным, если истинны все предикаты (отношения), находящиеся в теле утверждения».  Совокупность утверждений образует программу на языке Пролог.

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

1.1. Факты

Все утверждения программы на Прологе делятся на факты, правила и вопросы. Факты отражают текущее состояние предметной области и содержат конкретную информацию. Факты всегда истинны и соответствуют простым безусловным высказываниям. Они описывают истинные в предметной области отношения (истинные предикаты). Рассмотрим пример описания меню в ресторане. Объекты предметной области - это блюда, которые можно съесть в ресторане, а одним из возможных видов отношений является классификация всех блюд на закуски, вторые мясные или рыбные блюда и десерты. Меню представляет собой небольшую базу знаний, которая записывается в виде последовательности фактов следующим образом:

/* МЕНЮ */

/* Определение отношения закуска */

'закуска'('артишоки_в_белом_соусе').

'закуска'('трюфели_в_шампанском').

'закуска'('салат_с_яйцом').

/* Определение отношения мясо */

'мясо'('говяжье_жаркое').

'мясо'('цыпленок_в_липовом_цвете').

/* Определение отношения рыба */

'рыба'('окунь_во_фритюре').

'рыба'('фаршированный_судак').

/* Определение отношения десерт */

'десерт'('грушевое_мороженое').

'десерт'('земляника_со_взбитыми_сливками').

'десерт'('дыня_сюрприз').

Эти факты вводят одновременно объекты и их классификацию (отношения). Например, факт 'закуска'('салат_с_яйцом') показывает, что салат с яйцом является закуской.

1.2. Правила работы в интерпретаторе Пролога

Интерпретатор может работать в следующих режимах:

  • в режиме ввода программы из файла в буфер или вывода ее из буфера в файл (режим "Ввода/Вывода"). Ввод/вывод программы из файла осуществляется обычным способом, как во всех современных программных системах через меню  «Файл», «Открыть» и «Сохранить как…»;
  • в режиме редактирования: в нем можно как создавать новые программы, так и корректировать уже имеющиеся (режим "Редактирование");
  • в режиме пополнения и обновления базы знаний, в котором осуществляется проверка программы на корректность и запись ее утверждений в базу знаний (БЗ) [режим "Пополнение или обновление БЗ"(Reconsult)];
  • в режиме консультации, когда пользователь вводит вопросы к БЗ (режим "Консультация").

С этими  режимами познакомимся на примере программы меню.

1.3 Вопросы или целевые утверждения

Вернемся к нашей программе. Пусть проверенная программа заполнила базу знаний, и вы находитесь в режиме "Консультация" и задаете вопросы типа:

?-'закуска'('салат с яйцом').            ?-'закуска'('салат из помидор').

yes                                                         no

При получении вопроса (целевого утверждения) интерпретатор начинает выполнять программу. Суть выполнения состоит в поиске в базе знаний заголовка утверждения, соответствующего вопросу. Если такое утверждение (факт)  есть, то на экране появляется ответ "yes" (да). Если  нет, как в случае вопроса "?-'закуска'('салат из помидор').", то на экране появляется отрицательный ответ "no"(нет).

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

1.4. Переменные

Продолжим работу с "Меню". Предположим, что мы хотим получить информацию обо всех закусках. В этом случае мы, естественно, задали бы вопрос: "Какие блюда являются закусками?" или более формализованно: "Существуют ли те блюда (объекты) X, которые являются закусками?" Здесь имя X обозначает не какой-то конкретный объект, а любой, принадлежащий некоторому множеству (может быть пустому) объектов, обладающих свойством быть закуской и которые нужно найти в меню. В этом случае говорят, что X есть переменная.

На Прологе вопрос о закусках записывается так:

?-'закуска'(X).

Интерпретатор ответит:

X='артишоки в белом соусе' ->

и затем будет ждать дальнейших указаний. Если в этой ситуации нажать на терминале клавишу <Enter>, показывая тем самым, что вы удовлетворены полученным ответом, то Пролог прекратит дальнейший поиск. Если вместо этого нажать клавишу <;> (и вслед за ней клавишу <Enter>), то Пролог продолжит поиск и выдаст новые ответы.

?-'закуска'(X).

X='артишоки в белом соусе’®;

X='трюфели в шампанском’®;

X='салат с яйцом’®;

no

Все эти ответы содержат множество тех значений переменной X, при которых утверждение 'закуска'(X) истинно.