ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ И ЭКСПЕРТНЫЕ СИСТЕМЫ (Зюзьков)

Первое контрольное задание

Задание состоит из 5 задач, в которых требуется составить программы на Прологе. Первые две задачи требуют запрограммировать простые предикаты. Следующие две - требуют написать простые программы. В последней задаче требуется составить более сложную программу на Прологе (как правило, требуется определить несколько предикатов). При составлении программ (если не оговорено противное) можно использовать все встроенные предикаты Пролога. Тексты всех программ, если вы мыслите в духе логического программирования, получаются небольшие.
SWI-Prolog не имеет стандартного help'а для Windows, для этого используется предикат help. Вызов help(<имя предиката>) выдает на экран информацию об этом предикате. Вызов help(7) выдает на экран список всех встроенных предикатов с комментариями. Текстовый файл руководства по SWI-Prolog - pl\library\manual. Отладку предикатов можно осуществлять с помощью предиката трассировки trace(<имя предиката>), трассировка предиката отключается - trace(<имя предиката>, -all).

Пример задания с решением
Задача 1
Постройте предикат position_max(+L, -M, -N), который в списке L находит максимальное значение M и порядковый номер N этого значения.

Задача 2
Определите умножение целых чисел через сложение и вычитание.

Задача 3
Сортировка списка простым обменом (по возрастанию).

Задача 4
Пусть бинарное дерево задается рекурсивной структурой tree(<левое поддерево>,<корень>,<правое поддерево>) и пустое дерево задано термом nil. Составьте программу subtree(+S, +T), определяющую, является ли S поддеревом T.

Задача 5a
Определим операторы:
:- op( 100, fy, ~).
:- op( 110, xfy, &).
:- op( 120, xfy, v).
Булева формула есть терм, определяемый следующим образом: константы true и false - булевы формулы; если X и Y - булевы формулы, то и X v Y, X & Y, ~X - булевы формулы, здесь v и & - бинарные инфиксные операторы дизъюнкции и конъюнкции, а ~ - унарный оператор отрицания.
Напишите программу, распознающую логические формулы в конъюнктивной нормальной форме, т.е. формулы, являющиеся конъюнкцией дизъюнкций литералов, где литерал - атомарная формула или ее отрицание.

Задача 5b
Напишите предикат p(+N, -L) - истинный тогда и только тогда, когда список L содержит все последовательности (списки) из N нулей, единиц и двоек, в которых никакая цифра не повторяется два раза подряд (нет куска вида XX).


Второе контрольное задание

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

Логические задачи

Отец и два сына
Отец, два его сына и лодка находятся по одну сторону реки. Отец весит 80 кг, сыновья - по 40 кг. Как переправить эту семью на другую сторону, если лодка выдерживает только 80 кг?
Указания к решению. Различные состояния этой задачи задаются информацией, на каком берегу находятся лодка, отец, первый сын и второй сын. Поэтому структура state(Father,Son1,Son2,Boat) полностью описывает состояние. Возможные значение каждого аргумента: атомы west (западный берег) и east (восточный берег). Начальное состояние: state(east,east,east,east). Конечное состояние: state(west,west,west,west).

Миссионеры и людоеды
Три миссионера и три людоеда находятся по одну сторону реки, через которую они хотят переправиться. В их распоряжении имеется лодка, которая может выдержать вес только двух человек. Кроме того, если в какой-то момент число людоедов станет больше числа миссионеров, миссионеры будут съедены независимо от того, на каком берегу реки это случится.
Указания к решению. Различные состояния этой задачи однозначно задаются информацией, на каком берегу находятся лодка и сколько миссионеров и людоедов на этом же берегу.
Поэтому структура
state(ЛокализацияЛодки,
ЧислоМиссионеровНаТомБерегуГдеЛодка,
ЧислоЛюдоедовНаТомБерегуГдеЛодка)
полностью описывает состояние. Допустимые состояния для решения задачи - это те, когда людоеды не могут съесть миссионеров ни на том берегу, где лодка, ни на противоположном,
Возможные значение первого аргумента: атомы west (западный берег) и east (восточный берег). Возможные значения остальных аргументов: 0, 1, 2 или 3.
Начальное состояние: state(east,3, 3). Конечное состояние: state(west,3,3).

Задача об обезьяне и банане
Возле двери комнаты стоит обезьяна. В середине этой комнаты к потолку подвешен банан. Обезьяна голодна и хочет съесть банан, однако она не может дотянуться до него, находясь на полу. Около окна этой же комнаты на полу лежит ящик, которым обезьяна может воспользоваться. Обезьяна может предпринимать следующие действия: ходить по полу, залезать на ящик, двигать ящик (если она уже находится около него) и схватить банан, если она уже стоит на ящике прямо под бананом. Может ли обезьяна добраться до банана?
Указания к решению задачи. Различные состояния задачи можно описать структурой
state(ПоложениеОбезьяныВКомнате, %% значения: дверь, окно, середина
ОбезьянаНаЯщикеИлиНет, %% значения: ящик, пол
ПоложениеЯщикаВКомнате, %% значения: дверь, окно, середина
ИмеетИлиНеИмеетБанан) %% значения: да, нет
Существует 4 типа ходов:
1) схватить банан - если обезьяна на ящике в середине комнаты и банана не имеет;
2) залезть на ящик, если обезьяна находится на полу, рядом с ящиком;
3) подвинуть ящик с одного разрешенного места на другое, если обезьяна на полу рядом с ящиком;
4) перейти по полу с одного разрешенного места на другое.
Начальное состояние: state('дверь','пол','окно','нет'). Конечное состояние: state(_,_,_,'да').

Задача о 8 ферзях
На шахматной доске 8ґ8 надо расставить 8 ферзей, чтобы ни один из ферзей не находился под боем другого.
Указания к решению. Положение одного ферзя на доске задается парой целых чисел от 1 до 8: номера вертикалей и горизонталей. Легко видеть, что каждая вертикаль (как впрочем, и горизонталь) должна содержать по одному ферзю. Поэтому, мы можем экономно задавать положение на доске восьми ферзей списком из 8 чисел, задающих значения только горизонтальной координаты: так, например, список [2,5,7,4,3,6,8] говорит, что первый ферзь стоит на клетке (2, 1), второй - (5, 2), третий - (7, 3) и т. д. Различные состояния решения задачи мы можем представить в виде списка горизонтальных координат уже стоящих на доске ферзей, так, например, список [2] говорит о том, что на доске стоит только один ферзь на клетке (2,1), список [2,5] говорит о том, что на доске два ферзя на клетках (2, 1) и (5,2). Список длиной 8, говорит о том, что расставлены все ферзи.
Теперь нужно определить разрешенные переходы из одного состояния задачи в другое. Для этого надо определить предикат
'не бьет'(НовыйФерзь, ФерзиУжеСтоящиеНаДоске)
Этот предикат легко определить рекурсивно:
"НовыйФерзь не бьет список ферзей [F|T], если он не бьет ферзь F и не бьет список ферзей T".
Начальное состояние: []. Конечное состояние: [_,_,_,_,_,_,_,_].
Поскольку решение этой задачи при поиске выдает последовательность состояний, т.е. список списков, а нас интересует только конечная расстановка, то во втором аргументе предикат solve (см. программу поиска в глубину в лекциях) достаточно конкретизовать только голову списка: solve([],[H|_]).

Задача о волке, козе и капусте
На одном берегу реки находится фермер, волк, коза и капуста. Рядом лодка. Как фермер может переправиться со всем этим "хозяйством" на другой берег? С собой на лодку он может взять только один объект: волка, козу или капусту. Когда он в лодке, на любом из берегов не должна быть "криминальная" ситуация: волк не должен находиться с козой, а коза не должна быть вместе с капустой.
Указания к решению. Различные состояния этой задачи задаются информацией, на каком берегу находятся фермер, волк, коза и капуста, лодка всегда находится там, где фермер. Поэтому структура state(Фермер,Волк,Коза,Капуста) полностью описывает состояние. Возможные значение каждого аргумента: атомы west (западный берег) и east (восточный берег). Начальное состояние: state(east,east,east,east). Конечное состояние: state(west,west,west,west).

Рыцари и дамы
На берег реки приезжают 3 рыцаря, каждый со своей дамой. В их распоряжении имеется лодка, способная вместить не более 2-х человек. Как смогут перебраться на другой берег рыцари со своими дамами, если требуется выполнить условие: ни одна дама не может остаться без своего рыцаря в обществе других рыцарей - она тут же подвергается насилию (нравы "рыцарей" не слишком-то изменились с тех пор). Лошади переплывают реку сами, дамы гребут веслами, как и рыцари, лодка может пересекать реку сколько угодно раз.
Указания к решению. Удобно рыцарей обозначать атомами a, b и c и их соответствующих дам тоже теми же атомами. Различные состояния этой задачи задаются информацией, на каком берегу находятся лодка и списком рыцарей и дам, находящихся же на этом берегу. Поэтому структура state(НаКакомБерегуЛодка,
СписокРыцарейНаТомБерегуГдеЛодка,
СписокДамНаТомБерегуГдеЛодка)
полностью описывает состояние. Возможные значение первого аргумента: атомы west (западный берег) и east (восточный берег). Второй и третий аргументы - списки из элементов a, b и c. В этой задаче списки рыцарей и дам нужно рассматривать как множества, т. е. не учитывать порядок перечисления и поэтому воспользоваться специальными предикатами для операций с множествами. Удобно, для отладки, так написать программу, чтобы список рыцарей (а, следовательно, дам) задавался фактом knight([a,b,c]); в этом случае легко будет менять число рыцарей для тестирования.
Начальное состояние: state(east,X,Y), где выполнено условие knight(M) и X и Y равны как множества списку M.
Конечное состояние: state(west, M,M), где выполнено условие knight(M).


Курсовые работы

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

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

Как выполнять курсовую работу и оформлять пояснительную записку
Общие положения
Основные задачи и цели курсового проектирования:
1) приобретение навыков и методов программирования достаточно сложных задач искусственного интеллекта;
2) подготовка к выполнению дипломного проекта.
В курсовой работе должна быть разработана тема в соответствии с заданием, одобренным кафедрой.

Общие требования к построению пояснительной записки (ПЗ)
Структура построения ПЗ
ПЗ к работе должна содержать следующие разделы:
1) титульный лист;
2) реферат;
3) задание на проектирование;
4) содержание;
5) введение;
6) основная часть работы;
7) заключение;
8) список литературы;
9) приложения.

Титульный лист
Титульный лист оформляется согласно ГОСТ 2.105-79, форма титульного листа приведена в приложении 1.

Реферат
Реферат - краткая характеристика работы с точки зрения содержания, назначения, формы и других особенностей. Перечисляются ключевые слова работы, указывается количество страниц и приложений. Реферат размещают на отдельной странице. Заголовком служит слово "Реферат", написанное прописными буквами.

Задание на проектирование
Форма задания заполняется студентом в соответствии с полученным заданием. Форма задания приведена в приложении 2.

Содержание
Содержание включает наименования всех разделов, подразделов
и пунктов, если они имеют наименование, а также список литературы
и приложения с указанием номера страниц, на которых они начинаются. Слово "Содержание" записывается в виде заголовка, симметрично тексту, прописными буквами. Пример оформления содержания приведен в приложении 3.

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

Заключение
Заключение должно содержать краткие выводы по выполненной работе. Также следует указать, чему программист научился на примере этой задачи (на этот вопрос легко ответить, если сформулировать его в виде: "Что я в следующий раз сделаю иначе?").

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

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

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

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

Правила оформления ПЗ к курсовой работе
ПЗ пишется в редакторе MS Word шрифтом Times New Roman, размером 12, на формате A4. Нумерация страниц должна быть сквозной, первой страницей является титульный лист. Номер страницы проставляется вверху посередине. Заголовки разделов пишутся прописными буквами по середине текста. Заголовки подразделов пишутся с абзаца строчными буквами, кроме первой прописной. В заголовке не допускаются переносы слов. Точку в конце заголовка не ставят. Если заголовок состоит из двух предложений, то их разделяют точкой.

Рекомендуемая литература

Основная литература
Братко И. Программирование на языке Пролог для искусственного интеллекта.- М.:Мир,1990.- 560 с.
Стерлинг Л., Шапиро Э. Искусство программирования на языке Пролог.- М.: Мир, 1990. - 235 с.
Логический подход к искусственному интеллекту: от классической логики к логическому программированию: Пер.с франц./Тейз А., Грибомон П., Луи Ж. и др. - М.:Мир,1990.- 432 с.
Лорьер Ж.Л. Системы искусственного интеллекта. М.: Мир,1991.- 568 с.

Дополнительная литература
Малпас Дж. Реляционный язык Пролог и его применение. - М.: Наука, 1990. - 464 с.
Годфруа Ж. Что такое психология.Т.1 - М.:Мир,1992.
Лем С. Сумма технологии -М.:Мир,1968. - 608 с.