Методические рекомендации по срсп и срс самостоятельная работа студентов под руководством преподавателя

Методические рекомендации по СРСП и СРС

САМОСТОЯТЕЛЬНАЯ РАБОТА СТУДЕНТОВ ПОД РУКОВОДСТВОМ ПРЕПОДАВАТЕЛЯ

Интеллектуальные системы можно разбить на два класса: общего назначения и специализированные. При разработке и реализации интеллектуальных систем эффективно используются языки логического и функционального программирования, что позволяет обеспечить их высокую эффективность. Экспертные системы как одна из разновидностей интеллектуальных систем, использующих технологию инженерии знаний, получили наиболее широкое распространение на практике. К экспертным системам отнесены как собственно экспертные системы, решающие задачи в конкретной предметной области, так и оболочки экспертных систем.

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

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

Уровень знания проверяется на экзамене, умения и навыки - по результатам выполнения лабораторных и практических работ.

Разделы и темы для изучения

№ п/п	Номер раздела, тема дисциплины	Цель и содержание занятия	Результаты работы	Формы контроля выполнения	час
Занятие №1	Ознакомление с оболочкой AMZI! Prolog. Изучение основ программирования на языке Пролог. Отношения между данными	Формирование у студентов представления о возможностях программы	Изобразить граф, иллюстрирующий описываемые родственные отношения. Составить программу, которая описывает родственные отношения.	Составить отчет о выполнении исследовательской работы в MSWord	5
Занятие №2	Исследование использования рекурсивных правил и структурированных данных	Формирование у студентов представления об использовании рекурсивных правил и структурированных данных	Выполнить задачи согласно варианту. Подобрать тестовые данные и оформить отчет.	Составить отчет о выполнении исследовательской работы в MSWord	5
Занятие №3	Исследование работы со списками	Формирование у студентов представления работе со списками	Реализовать набор функций для обработки списков, используя возможности языка: Решить дополнительные задачи согласно варианту, используя построенные функции.	Составить отчет о выполнении исследовательской работы в MSWord	5
Занятие №4	Исследование работы с бинарными деревьями	Формирование у студентов представления о работе с бинарными деревьями	Составить программу, которая решает задачи соответствующего варианта. Предусмотреть в программе возможности автоматического ввода/вывода деревьев.	Составить отчет о выполнении исследовательской работы в MSWord	5
Занятие №5	Исследование работы с динамическими базами данных	Формирование у студентов представления о работе с динамическими базами данных	Выполнить задание	Составить отчет о выполнении исследовательской работы в MSWord	5
Занятие №6	Исследование использования возможностей логического сервера AMZI! Prolog в среде Delphi	Формирование у студентов представления об использования возможностей логического сервера AMZI! Prolog в среде Delphi	Составить программу, которая отображает все данные практической работы № 1 на форме DELPHI приложения. Подобрать тестовые данные, проверяющие работу программы.	Составить отчет о выполнении исследовательской работы в MSWord	5

Введение

Осознание того, что вычисление – часть случайного логического вывода привело к возникновению логического программирования [4], первая реализация которого была осуществлена в семидесятые годы в виде системы Пролог [1, 2, 9]. Суть идеи – представить в качестве программы формальное описание предметной области, а затем сформулировать необходимую для решения задачу в виде цели или утверждения. Построение же решения этой задачи в виде вывода в этой системе предложить самой машине . Последнее возможно, поскольку нужный алгоритм решения (поиска) осуществляется решателем, строящим вывод по определенной стратегии [3, 8]. При такой постановке основная задача программиста сводится к описанию предметной области в виде системы логических формул и отношений на них, которые с достаточной степенью полноты описывают задачу. Этот подход стал возможен благодаря тому, что были получены достаточно эффективные методы автоматического поиска доказательств [8].

Проиллюстрируем вышесказанное, воспользовавшись исчислением высказываний [8]. Дадим формальное описание предметной области
:

F1 : Если жарко и сыро, то будет дождь .

F2 : Если сыро, то жарко база знаний

F3 : сейчас сыро

Воспользуемся обозначениями:

Р – жарко, Q – сыро, R – будет дождь,

тогда

F1 =PÙQ®R

F2 =Q®P формальное описание базы знаний

F3 : Q

и зададимся вопросом-целью:

будет ли дождь?

Решим поставленную задачу, воспользовавшись правилом вывода modus ponens: A , A ® B => B (если верно А и A®B, то верно и B). Тогда Q , Q ® P => P, т. е. верно P.

Но тогда QÙP, QÙP ® R => R, т.е. верно R. То есть, поставленная задача решена, ответ – будет дождь.

Отметим, что в основу логического программирования положена логика исчисления предикатов первого порядка. Опишем с ее помощью базу знаний, определяющую понятие натурального числа. Воспользуемся следующими предикатами:

E
(x
,
y
) – числа x
и y
равны между собой

f
(x
) – число, следующее за числом x

g
(x
) – число, предшествующее числу x

1. За каждым числом существует другое

А
("х
)(($у
)(Е(у
, f
(x
)))Ù"z
)(E(z
, f
(x
)))®E(y
,
z
)

2. Нуль является крайним числом

А ~ ($x
)(E(0, f
(x
)))

3. Существует один предыдущий элемент для всех чисел кроме нуля.

А ("х
)(~E(x
,0)®(($y
)(E(y
, g
(x
))Ù("z
)(E(z
, g
(z
)) ® E(y
, z
)))

Использование правила вывода modus ponens позволяет показать возможность достижения цели – доказательства теорем. На практике обычно используется более эффективные с точки зрения вывода методы доказательства теорем.

Один из таких методов – метод резолюции [3] – позволяет реализовать на практике концепцию логического программирования, согласно которой вычислительная программа может быть записана при помощи логических формул, играющих роль аксиом, а её вычисление представлено в виде доказательства формулы-запроса.

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

Правило резолюций в простейшем случае имеет вид

ØA, A ® B => ØB,

результат называется резольвентой
, а само правило modus
tollens
.

Для доказательства выводимости некоторой формулы G из формул F1
, F2
, ..., Fn
,
достаточно доказать истинность формулы F1
Ù F2
... Ù Fn
® G.

Теорема. F1
Ù F2
... Ù Fn
® G <=> F1
Ù F2
... Ù Fn
Ù Ø G – противоречиво

То есть для доказательства G достаточно опровергнуть ØG. Это так называемое доказательство от противного или reductio ad absurdum.

Логическое программирование является описательным (декларативным). В нем используются утверждения трех видов: факты, правила, вопросы. Воспользуемся примером Пролог-программы, приведенной в работе [3]

вор(питер).

любит(мэри, шоколад).

любит(мэри, вино)

любит(питер, деньги).

любит(питер, X) :- любит(X, вино).

может_похитить(X, Y) :- вор(X), любит(X, Y).

и опишем работу интерпретатора для цели

? может_похитить(питер, X).

то есть вопрос «что может похитить Питер?».

Интерпретатор отыщет последнее правило программы и унифицирует цель с его левой частью, при этом

X = питер, а Y = Z,

вместо старой цели появятся две новые подцели:

? вор(питер), любит(питер, Z).

Первая подцель достижима, поскольку она унифицируется с фактом в программе: вор(питер).

Вторая подцель: любит(питер, Z) будет унифицирована с фактом любит(питер, деньги), при этом

Z = деньги.

Поскольку и эта цель достижима, интерпретатор выдаст ответ Y = деньги. То есть Питер может_похитить деньги.

Интерпретатор продолжит поиск других целей и расторгнет унификацию цели любит(питер, X) с фактом любит(питер, деньги). Взамен этого цель любит(питер, X) будет унифицирована с правой частью правила, расположенного в пятой строке программы. Эта унификация означает, что X = Z и вместо старой цели любит(питер, X) будет выставлена цель любит(Z, вино), поскольку X = Z. Эта цель будет достигнута, поскольку она унифицируется с фактом, находящимся в третьей строке – любит(мэри, вино). В результате Z = мэри и интерпретатор выдаст ещё один ответ Z = мэри, то есть питер может_похитить мэри.

В заключение отметим, что Пролог позволяет решать задачи, относящиеся к искусственному интеллекту:

- общение с ЭВМ на естественном языке;

- формальные вычисления;

- написание компиляторов;

- работа с базами данных;

- экспертные системы и другие.

Методические указания к занятию
№ 1

Ознакомление с оболочкой AMZI Prolog. Изучение основ программирования на языке Пролог. Отношения между данными

Цель СРСП

1. Изучить основы синтаксиса языка Пролог.

2.Выработать навыки работы с интерактивной системой AMZI! Prolog.

3. Научиться оформлять отношения между данными на языке Пролог на примере родственных отношений между членами семьи.

Задание для подготовки к работе

Изучить лекционный материал и основные понятия настоящей лабораторной работы.

Порядок выполнения работы

1. Изучить основные команды и возможности системы AMZI! Prolog.

2. Отработать команды в системе AMZI! Prolog.

3. Выполнить контрольный пример.

4. Создать в системе AMZI! Prolog программу, которая описывает родственные отношения между членами семьи.

5. Составить отчет о проделанной работе.

Методические рекомендации

Язык программирования Пролог базируется на ограниченном наборе механизмов, включающих в себя сопоставление образцов, древовидное представление структур данных и автоматический возврат. Этот небольшой набор образует удивительно мощный и гибкий программный аппарат.

Программирование на Прологе – программирование в терминах логики. Программы на Прологе записываются в декларативном стиле, это означает что выполнение программ Пролог - машиной происходит по принципу:

Ты скажи: " Что сделать", а я разработаю "Как это сделать". Другими словами, в отличие от императивных языков программирования, на Прологе интерпретатор сам выбирает порядок исполнения операторов в программе.

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

На Прологе легко определить отношения, подобные отношению родитель(X,Y), что означает ИСТИНА если X является родителем Y, и ЛОЖЬ в противном случае.

Программа на языке Пролог состоит из предложений. Каждое предложение заканчивается точкой.

Аргументами отношений могут быть атомы (константные объекты) или переменные. В тексте программы названия переменных начинаются с большой буквы, а названия констант – с маленькой.

На Прологе отношения могут быть записаны в виде фактов и правил. В виде фактов записываются простейшие отношения.

Например:

human(oleg).

fruit(orange).

Правила нужны для получения новых отношений из уже известных.

Например:

ather(X,Y):-parent(X,Y),man(X).

Что означает: X является отцом Y, ЕСЛИ X родитель Y И X является

мужчиной.

Вопрос к системе формируется в виде цели, которая может содержать переменные. В этом случае Пролог-машина проверит все возможно допустимые состояния переменных и найдет те из них, при которых цель достижима.

Повторяющееся применение фактов к правилам, приводящее к новым фактам, называется прямым рассуждением
(forward
chaining
). При обратном рассуждении
(backward
chaining
) осуществляется поиск заключений (заголовков правил), соответствующих цели. Если такое заключение найдено, то в свою очередь должны быть доказаны цели, входящие в данное правило. В Прологе используется обратное рассуждение.

В Прологе поиск осуществляется в глубину. Алгоритм поиска показан на рисунке.

Здесь задействованы три списка. Первый, ПРЕДЛОЖЕНИЯ, содержит предложения. Во втором, ЦЕЛИ, находятся цели, подлежащие удовлетворению. Третий список, РЕШЕНИЯ, включает точки возврата и хранит следы предложений, применявшихся для достижения целей. Это своего рода трасса нахождения решения процедурой поиска.

Процедура ПОИСК просматривает список целей. Если он пуст, то, значит, не осталось ни одной цели, которую нужно доказать, и поиск считается успешным. В противном случае удаляется первая цель из списка ЦЕЛИ, и сканирование продолжается по списку ПРЕДЛОЖЕНИЯ в поисках подходящего предложения. Если таковое найдено, то указатель (в списке ПРЕДЛОЖЕНИЯ) на это предложение вместе с целью добавляется к списку РЕШЕНИЯ. Указатель отмечает, как далеко процедура ПОИСК продвинулась в списке ПРЕДЛОЖЕНИЯ перед нахождением нужного предложения. Затем проверяются цели выбранного предложения. Если хотя бы одна из них недостижима, указатель продвигается до следующего подходящего предложения в списке ПРЕДЛОЖЕНИЯ и его цели помещаются в список ЦЕЛИ. Такая реакция на неудачу называется возвратом
. Этот новый указатель замещает прежний в списке РЕШЕНИЯ, и всякий раз, когда совершается возврат, продвигается далее по списку ПРЕДЛОЖЕНИЯ. Если указатель достигает конца списка ПРЕДЛОЖЕНИЯ, то, следовательно, в списке нет предложений, доказывающих искомые цели, и ПОИСК завершается неудачей.

Контрольный пример

Простейшая программа на языке Пролог.

man(nikolay).

man(stepan).

woman(lida).

parent(lida, stepan).

parent(nikolay, stepan).

mother(X,Y):-parent(X,Y),woman(X).

Задание к работе

1. Изобразить граф, иллюстрирующий описываемые родственные отношения.

2. Составить программу, которая описывает родственные отношения.

В качестве фактов описать унарные отношения: мужчина, женщина; и бинарные: состоят_в_браке, родитель_ребенок.

Записать правила, которые определяют следующие отношения: муж, жена, родитель, ребенок, сын, дочь, брат, сестра, дядя, тетя, бабушка, дедушка.

3. Подобрать тестовые данные, проверяющие все полученные отношения. Тестовые данные должны содержать операции «И», «ИЛИ», «НЕ».

4. Оформить отчет о проделанной работе.

Содержание отчета

1. Описание родственных отношений, представленных в лабораторной работе, в виде графа.

2. Исходные тексты программ на языке Пролог.

3. Наборы тестовых данных и результаты работы программ.

4. Перечень и анализ ошибок, допущенных при решении задачи.

5. Выводы по работе.

Методические указания к занятию
№ 2

Использование рекурсивных правил и структурированных данных

Цель СРСП

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

Задание для подготовки к работе

Изучить темы «Рекурсивные правила», «Структурированные данные».

Порядок выполнения работы

1. Выполнить контрольные примеры.

2. Создать в системе программу, которая решает задачи согласно варианту.

3. Модифицировать программу CH06EX03.pro и подобрать цели иллюстрирующие структуру данных.

4. Составить отчет о проделанной работе.

Задание и методические рекомендации

Определения отношений, в которых используется само отношение, называется рекурсивным
. Рекурсия – один из фундаментальных механизмов программирования на Прологе. Рекурсию можно применять для достижения такого же эффекта, какой реализуется при употреблении итеративных управляющих конструкций (циклов) в процедурных языках. Примером использования рекурсии может служить определение отношения «предок» [1, 2]. Данное отношение можно выразить с помощью двух правил. Первое правило будет определять непосредственных предков, а второе – отдаленных. Первое правило легко сформулировать через отношение «родитель»:

предок(X, Z) :- родитель(X, Z).

Аналогичным образом можно попытаться сформулировать второе правило:

предок(X, Z) :- родитель(X, Z).

предок(X, Z) :- родитель(X, Y), родитель(Y, Z).

предок(X, Z) :- родитель(X, Y1), родитель(Y1, Y2), родитель(Y2, Z).

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

Подобные отношения целесообразно описывать с помощью рекурсии. Правило будет выглядеть следующим образом:

Для всех X и Z,

X – предок Z, если

существует Y, такой, что

X – родитель Y и

Y – предок Z.

или на языке Пролог:

предок(X, Z) :- родитель(X, Y), предок(Y, Z).

Таким образом, определение отношения «предок» будет выглядеть следующим образом:

предок(X, Z) :- родитель(X, Z).

предок(X, Z) :- родитель(X, Y), предок(Y, Z).

При описании рекурсивных правил следует соблюдать осторожность во избежание зацикливания рекурсии. Для этого любое рекурсивное определение отношения должно включать по крайней мере два правила:

1) нерекурсивное правило, определяющее исходный вид отношения, т.е. вид отношения в момент прекращения рекурсии;

2) рекурсивное правило – первая подцель, располагающаяся в теле этого правила, вырабатывает новые значения аргументов. Далее размещается рекурсивная подцель, в которой используются новые значения аргументов

В приведенном выше определении отношения «предок» первая фраза определяет исходный вид этого отношения. Как только она станет истинной, рекурсия прекратится. Вторая фраза – это рекурсивное правило. При каждом вызове данное правило поднимается на одно поколение вверх. Подцель «родитель(X, Y)» вырабатывает значение переменной Y, а в рекурсивной подцели «предок(Y, Z)» используется этот новый аргумент.

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

date (11, january, 1978).

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

date (Day, january, 1978).

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

human(sergei, ivanov, date(10, may, 1975)).

human(ivan, petrov, date(15, october, 1969)).

Для удобства взаимодействия с такой базой данных можно описать запросы, например:

human(FirstName, LastName, _). % запрос, перечисляющий всех людей из базы данных

human (FirstName, LastName, date(_, _, 1975). % все люди, родившиеся в 1975 году

birthday(human(_, _, Date), Date). % запрос, позволяющий найти человека по указанной дате рождения.

Контрольные примеры

Пример 1
. Вычисление факториала

factorial(X, _) :- X<0, ! ,fail.

factorial (0, 1) :- !.

factorial(N, Fact) :- N1=N-1, factorial(N1, Fact1), Fact=N*Fact1.

Пример 2
.Числа Фибоначчи:

F(1,1) :- !.

F(2,1) :- !.

F(I,R) :- I>2, I1=I-1, I2=I-2, F(I1,M), F(I2,N), R=N+M.

Задание к работе

1. Выполнить задачи согласно варианту.

2. Подобрать тестовые данные и оформить отчет.

Варианты заданий

1. Возведение в степень как повторяющееся умножение.

2. Возведение в степень как повторяющееся сложение.

3. Рекурсивное определение остатка от деления (mod).

4. Рекурсивное определение деления нацело (div).

5. Алгоритм Евклида.

6. Функция Аккермана

Ak(0,N) = N + 1

Ak(M,0) = Ak(M-1,1)

Ak(M,N) = Ak(M-1),Ak(M,N-1)

7. Наибольший общий делитель двух чисел.

8. Наибольший общий делитель последовательности чисел.

9. Наименьшее общее кратное двух чисел.

10. Наименьшее общее кратное последовательности чисел.

11. Сложение и вычитание через сложение/вычитание единицы.

12. Нахождение всех простых чисел, не превышающих заданное число.

13. .

14. .

15. .

16. Определить, является ли заданное число числом Фибоначчи.

17. Нахождение чисел Фибоначчи, не превышающих заданное число.

18. Вычисление факториала (ускоренный алгоритм).

19. Вычисление n
-го члена арифметической прогрессии, у которой первый член равен 1, а разность 2.

20. Вычисление n
-го члена геометрической прогрессии, у которой первый член равен 2, а знаменатель равен 4

21. Сумма натуральных чисел от 1 до n.

22. Сумма всех двузначных чисел, кратных трем.

23. Сумма всех трехзначных чисел, не делящихся ни на 5, ни на 7.

24. Вычислить сумму n
первых членов ряда:

1 + 1/2 + 1/3 + ...

25. Вычислить сумму n первых членов ряда:

4 - 4/3 + 4/5 - 4/7 + 4/9 - ... + (-1)^(n-1)
×
4 / (2
×
n - 1) + ...

26. Построить рекурсивную функцию для вычисления n
-го члена последовательности, в которой каждый следующий член равен сумме n
-2 -го и n
-3 -го. Первые 3 члена равны соответственно 1, 2, 3.

1 2 3 3 5 6 8 11

27. Построить рекурсивную функция для вычисления n
-го члена последовательности, в которой каждый четный член равен сумме двух предыдущих четных, а нечетный равен сумме двух предыдущих нечетных. Первые четыре члена равны соответственно 1, 2, 3, 4
.

1 2 3 4 4 6 7 10 11 16 18 ...

28. Построить рекурсивную функцию для вычисления n
-го члена последовательности, в которой каждый следующий

29. четный член равен произведению двух предыдущих, а каждый следующий нечетный член равен сумме двух предыдущих, а первые 2 члена равны соответственно 1 и 2.

1 2 3 6 9 54 63 ...

30. Построить рекурсивную функцию для вычисления n
-го члена последовательности, в которой каждый следующий член равен произведению двух предыдущих, а первые 2 члена равны соответственно 1 и 2.

1 2 2 4 8 32 ...

31. Построить рекурсивную функцию для вычисления n
-го члена последовательности, в которой первый член равен 0, второй 1, третий 2, а каждый следующий равен сумме трех предыдущих.

0
1 2 3 6 11 ....

Содержание отчета

1. Исходные тексты программ на языке Пролог.

2. Наборы тестовых данных и результаты работы программ.

3. Перечень и анализ ошибок.

4. Выводы по работе.

Методические указания к занятию № 3

Работа со списками

Цель СРСП

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

Задание для подготовки к работе

Изучить лекции по теме "Списки".

Порядок выполнения работы

1. Выполнить контрольные примеры.

2. Создать программу на языке Пролог, которая решает задачи согласно варианту.

3. Составить отчет о проделанной работе.

Задание и методические рекомендации

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

Контрольный пример

Создание списка всех натуральных чисел не превосходящих заданного.

create([],0).

create([X|T],X):-X>0, X1=X-1, create(T,X1).

Задание к работе

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

- Добавление элемента к списку.

- Удаление элемента из списка.

- Конкатенация списков.

- Определение длины списка.

- Выделение подсписка.

2. Решить дополнительные задачи согласно варианту, используя построенные функции.

3. Подобрать тестовые данные и оформить отчет.

Варианты заданий

1. Решить следующие задачи:

а) проверить является ли список палиндромом;

б) упорядочить список методом вставки;

в) добавить к каждому элементу списка 1;

г) выделить из списка подсписки положительных и отрицательных чисел.

2. Решить следующие задачи:

а) добавить элемент в i
-ю позицию списка;

б) подсчитать сумму всех элементов списка;

в) инвертировать список;

г) по паре чисел выдать список натуральных чисел, находящихся между числами этой пары на числовой оси.

3. Решить следующие задачи:

а) удалить из списка все повторяющиеся подсписки;

б) подсчитать количество положительных чисел в списке;

в) подсчитать сумму положительных и произведение отрицательных элементов списка;

г) подсчитать число повторяющихся элементов списка.

4. Решить следующие задачи:

а) удвоить элемент списка, если он положительный и утроить, если он отрицательный;

б) упорядочить список по убыванию с помощью сортировки (не вставкой);

в) объединить три списка;

г) выделить подсписки, содержащие букву «а» и объединить их.

5. Решить следующие задачи:

а) добавить элемент в i
-ю позицию списка;

б) подсчитать сумму целых чисел в списке;

в) выделить из списка подсписки положительных и отрицательных чисел;

г) упорядочить список по возрастанию.

6. Решить следующие задачи:

а) составить список, состоящий из натуральных чисел, лежащих на числовой оси между двумя заданными;

б) подсчитать количество отрицательных, положительных и нулевых элементов списка;

в) инвертировать список;

г) утроить список.

7. Решить следующие задачи:

а) удалить из списка заданный подсписок;

б) упорядочить список по убыванию;

в) заменить каждый элемент списка, состоящий из символов, на следующий символ алфавита;

г) удалить повторяющиеся элементы в списке.

8. Решить следующие задачи:

а) упорядочить список по возрастанию;

б) подсчитать в списке количество отрицательных, положительных и

нулевых элементов;

в) инвертировать список;

г) отнять от каждого элемента списка 1.

9. Решить следующие задачи:

а) выделить из списка буквы и числа;

б) проверить список на симметричность;

в) определить количество уровней вложенности списка;

г) найти сумму четных элементов списка.

10. Решить следующие задачи:

а) инвертировать список на всех уровнях вложенности;

б) найти суммы всех подряд идущих пар чисел в списке;

в) определить длину списка;

г) найти сумму нечетных элементов списка.

11. Решить следующие задачи:

а) добавить подсписок в указанную позицию;

б) инвертировать список;

в) удвоить значения положительных элементов списка и утроить значения его отрицательных элементов;

г) подсчитать число элементов списка больших 10.

12. Решить следующие задачи:

а) удаление подсписков указанной глубины;

б) выдать подсписок, компоненты которого принадлежат заданному

интервалу;

в) выделить из списка все элементы, которые делятся на 2 и на 3;

г) проверить список на симметричность.

13. Решить следующие задачи:

а) инвертировать список;

б) подсчитать сумму положительных элементов списка;

в) выделить положительные, отрицательные и нулевые элементы списка;

г) объединить 3 списка.

14. Решить следующие задачи:

а) упорядочить список по возрастанию методом простой вставки;

б) определить кратность вхождения подсписка в список;

в) подсчитать среднее значение списка;

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

Содержание отчета

1. Исходные тексты программ на языке Пролог.

2. Наборы тестовых данных и результаты работы программ.

3. Перечень и анализ ошибок.

4. Выводы по работе.

Методические указания к занятию №
4.

Бинарные деревья

2.1 Цель СРСП

1. Научиться описывать рекурсивные типы данных.

2. Выработать навыки представления структур в виде дерева.

Порядок выполнения работы

1. Решить задачу соответствующего варианта.

2. Подобрать тестовые данные и протестировать программу на компьютере.

3. Составить отчет о проделанной работе.

Задание и методические рекомендации

Типы данных являются рекурсивными, если они допускают, чтобы в его структуре данных была рекурсия.

Примером рекурсивного типа данных является бинарное дерево
. Бинарное дерево либо пусто, либо состоит из следующих трех частей:

- корень;

- левое поддерево;

- правое поддерево.

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

Бинарное дерево упорядочено, если в нем все вершины левого поддерева меньше корня, все вершины правого поддерева больше корня, и оба поддерева также упорядочены. Такое дерево называется бинарным справочником
. Преимущество упорядочивания состоит в том, что для поиска некоторого объекта в бинарном справочнике достаточно просмотреть не более одного поддерева.

Стоит заметить, что поиск в двоичном справочнике наиболее эффективен для сбалансированного дерева, то есть дерева, в котором два поддерева содержат примерно равное количество элементов. Если же дерево полностью разбалансировано, то поиск в нем так же неэффективен, как и поиск в списке.

Опишем предикаты для создания и модификации бинарного дерева. Бинарное дерево задается с помощью функтора

tree
(K, LeftT, RightT),

где К – элемент, находящийся в вершине; LeftT и RightT – левое и правое поддерево соответственно.

create_tree
(A, tree(A, empty, empty)). % создание дерева

insert_left
(X, tree(A, _, B), tree(A, X, B)). % включение элемента данных A, как левого поддерева B

insert_righ
t(X, tree(A, B, _), tree(A, B, X)). % включение элемента данных A, как правого поддерева B

Для обхода бинарного дерева «сверху вниз» опишем предикат:

up_to_down
(tree(X, LTr, RTr), Xs) :- up_to_down(Ltr, Ls), up_to_down(RTr, Rs), append([X|Ls], Rs, Xs).

up_to_down
(empty, []).

append
– это процедура append(LeftList, RightList, ListRes), где ListRes является результатом слияния списков LeftList, RightList.

Аналогичным образом можно описать процедуру обхода дерева «снизу вверх», «слева направо».

Контрольный пример

Фрагмент программы печатает все элементы, проходя его «в глубину».

show_tree(nil).

show_tree(tree(X,Left,Right)):-write(X),show_tree(Left), show_tree(Right).

Задание к работе

1. Составить программу, которая решает задачи соответствующего варианта.

2. Предусмотреть в программе возможности автоматического ввода/вывода деревьев.

3. Подобрать тестовые данные, проверяющие работу программы.

4. Провести анализ ошибок и полученных результатов, составить отчет о проделанной работе.

Варианты заданий

1. Подсчитать длину максимального пути и выдать его трассировку.

2. Выдать метки всех вершин с их кратностями.

3. Построить деревянное покрытие графа.

4. Выделить метку вершины дерева, имеющую наибольшее число вхождений.

5. В указанном ярусе дерева добавить вершину с указанной меткой.

6. Составить программу, реализующую сортировку линейного числового списка на основе бинарного отсортированного дерева.

7. Проверить дерево на изоморфизм.

8. Для связного графа построить деревянное покрытие, начиная с указанной вершины.

9. Выделить в дереве все поддеревья с указанной меткой.

10. Реализовать обход дерева в ширину с выдачей меток.

11. Удалить вершину с указанной меткой, в случае отсутствия указанной метки выдать сообщение о невозможности удаления.

12. Реализовать обход дерева в глубину с выдачей меток.

13. Реализовать поиск в дереве данного поддерева.

14. Подсчитать количество вхождений в дерево данной метки.

15. Выделить в дереве максимальное поддерево с заданной меткой.

16. Подс

читать количество вершин дерева. Выдать наиболее длинный путь дерева.

17. Подсчитать в дереве количество совпадающих вершин.

18. Выдать элемент бинарного дерева, который имеет в нем наибольшее число вхождений.

19. Сравнить два дерева на изоморфизм.

20. Построить дерево по алгебраическому выражению.

Содержание отчета

1. Исходные тексты программ на языке Пролог.

2. Наборы тестовых данных и результаты работы программ.

3. Перечень и анализ ошибок.

4. Выводы по работе.

Методические указания к занятию №5.

Работа с динамическими базами данных

Цель СРСП

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

Задание для подготовки к работе

Изучить лекционный материал.

Порядок выполнения работы

1. Решить задачу соответствующего варианта.

2. Подобрать тестовые данные и протестировать программу на компьютере.

3. Составить отчет о проделанной работе.

Задание и методические рекомендации

Реляционная модель данных предполагает, что база данных – это есть описание некоторого множества отношений. Пролог-программу можно рассматривать как такую базу данных, здесь отношения между данными представлены в виде фактов и правил. В Прологе есть специальные средства для модифицирования этой базы данных, то есть добавлять и удалять новые отношения из файла. Для этих целей служат встроенные предикаты [1, 5]:

consult(F)
– все предложения, содержащиеся в файле будут использоваться Пролог-машиной для достижения целей.

reconsult(F
) – если в файле есть предложения, касающиеся отношений, которые уже были определены ранее, старые отношения заменяются на новые из файла.

assert(C)
– добавляет предложение C из базы данных.

retract(C)
– удаляет предложение C из базы данных.

asserta(C)
– помещает предложение C в начале базы данных.

assertz(C)
– помещает предложение C в конце базы данных.

see(F)
– делает файл F текущим входным потоком.

tell(F)
– файл становиться текущим выходным потоком.

seen
– закрывает текущий входной поток.

told
– закрывает текущий выходной поток.

Контрольный пример

Программа добавляет и удаляет из базы данных новый факт.

add :- write('Введите имя мужчины: '),

read_string(S),

assertz(man(S)).

out :- write('Список имен мужчин:n'),

man(S),write(S),nl.

del :- write('Введите имя мужчины: '),

read_string(S),

retractall(man(S)).

main :- consult('db.pro'),add,out,del,out.

Файл db.pro
первоначально содержит следующие факты:

man(oleg).

woman(zina).

man(alexandr).

man(petr).

Задание к работе

1. Составить программу, которая решает задачу соответствующего варианта.

2. Подобрать тестовые данные, проверяющие работу программы.

3. Провести анализ ошибок и полученных результатов, составить отчет о проделанной работе.

Содержание отчета

1. Исходные тексты программ на языке Пролог.

2. Наборы тестовых данных и результаты работы программ.

3. Перечень и анализ ошибок.

4. Выводы по работе.

Методические указания к занятию №6

Использование возможностей логического сервера
AMZI! Prolog в среде Delphi

Цель работы

1. Научиться использовать Пролог в Delphi приложениях.

2. Выработать навыки использования Пролога в DELPHI приложениях.

Задание для подготовки к работе

Изучить материал по теме «Компонент LSEngine»

Порядок выполнения работы

1. Решить задачу соответствующего варианта.

2. Подобрать тестовые данные и протестировать программу на компьютере.

3. Составить отчет о проделанной работе.

Задание и методические рекомендации

Amzi! Prolog не предоставляет достаточно удобного интерфейса для работы с базой данных. Но возможности языка Amzi! Prolog можно использовать и в других языках и средах программирования, например Borland Delphi. В состав пакета Amzi! Prolog входит компонент, написанный для использования в Delphi (LSEngine). С помощью свойств и методов этого компонента разработчик приложения может производить запросы к откомпилированной базе данных Пролога.

Для работы с базой данных на Прологе в среде Delphi данный компонент необходимо поместить на форму приложения.

Этот компонент содержит большое количество методов, позволяющих производить запросы, модифицировать динамическую базу данных, работать с потоками и т.п. Ниже приведены часто используемые процедуры и функции для работы с компонентом LSEngine.

Процедуры для подключения Пролога к приложению

procedure Init(xplname: String);–
инициализация базы;

procedure InitLS(xplname: String);
– инициализация базы;

procedure InitLSXP(p: pointer
);– инициализация базы;

procedure InitLSX
; – инициализация базы;

procedure AddLSX(lsxname: String);
– добавление базы;

procedure AddPred(pname: String; parity: TArity; pfunc: TExtPred);
– добавление предиката;

procedure InitPreds(PIptr: TPredInitPtr);–
инициализация предиката;

procedure Load(xplname: String
);– чтение базы из файла;

procedure LoadXPL(xplname: String);–
чтение базы из файла;

function Main
:
Boolean
;– доказательство главной цели;

procedure Reset
;– сброс базы;

procedure Close
;– закрытие базы;

procedure CloseLS
;– закрытие базы.

Функции и параметры предикатов

procedure GetParm(n: integer; dt: TDType; p: pointer);–
получение параметра;

function GetPStrParm(n: integer):
string;– получение строкового параметра;

function GetIntParm(n: integer):
integer;– получение целого параметра;

function GetLongParm(n: integer):
longint;– получение параметра типа длинное целое;

function GetShortParm(n: integer):
longint;– получение параметра типа короткое целое;

function GetFloatParm(n: integer):
single;– получение параметра вещественного типа;

function GetParmType(n: integer):
TPType;– получение типа параметра;

function StrParmLen(n: integer):
integer;– получение длины параметра;

function UnifyParm(n: integer; dt: TDType; p: pointer
): Boolean;– унификация параметра;

function UnifyPStrParm(n: integer; s: string):
Boolean;– унификация строкового параметра;

function UnifyAtomParm(n: integer; s: string): Boolean
;– унификация параметра типа атом;

function UnifyIntParm(n: integer; i: integer): Boolean
;– унификация параметра целого типа;

function UnifyLongParm(n: integer; i: longint):
Boolean;– унификация параметра типа длинное целое;

function UnifyShortParm(n: integer; i: longint):
Boolean;– унификация параметра типа короткое целое;

function UnifyFloatParm(n: integer; f: single):
Boolean;– унификация параметра вещественного типа.

Вызов
Пролога
из
Delphi

function Exec(var tp: TTerm):
Boolean;– выполнение доказательства;

function ExecStr(var tp: TTerm; s: PChar):
Boolean;– выполнение доказательства, записанного в строке;

function ExecPStr(var tp: TTerm; s: string):
Boolean;– выполнение доказательства, записанного в строке;

function Call(var tp: TTerm
): Boolean;– вызов терма;

function CallStr(var tp: TTerm; s: PChar
): Boolean;– выполнение терма, записанного в строке;

function CallPStr(var tp: TTerm; s: string):
Boolean;– выполнение терма, записанного в строке;

function Red
o: Boolean;– восстановление;

procedure ClearCall
;– очистка стека вызовов.

Добавление и удаление фактов из динамической базы данных

procedure Asserta(t: TTerm);– выполнение предиката Asserta;

procedure Assertz(t: TTerm);– выполнение предиката Assertz;

procedure Retract(t: TTerm);– выполнение предиката Retract;

procedure AssertaStr(s: PChar);– выполнение предиката Asserta над строковой записью;

procedure AssertzStr(s: PChar);– выполнение предиката Assertz над строковой записью;

procedure RetractStr(s: PChar);– выполнение предиката Retract над строковой записью;

procedure AssertaPStr(s: string);– выполнение предиката Asserta над строковой записью;

procedure AssertzPStr(s: string);– выполнение предиката Assertz над строковой записью;

procedure RetractPStr(s: string);– выполнение предиката Retract над строковой записью.

Преобразование
строк
и
термов

procedure TermToStr(t: TTerm; s: PChar; n: integer);– преобразование терма в строку;

procedure TermToStrQ(t: TTerm; s: PChar; n: integer);– преобразование терма в кодовую строку;

procedure StrToTerm(var tp: TTerm; s: PChar);– преобразование строки в терм;

function TermToPStr(t: TTerm): string;– преобразование терма в строку;

function TermToPStrQ(t: TTerm): string;– преобразование терма в кодовую строку;

procedure PStrToTerm(var tp: TTerm; s: string);– преобразование строки в терм.

Создание
типов
Пролога

procedure MakeAtom(var tp: TTerm; s: string);– создание атома;

procedure MakeStr(var tp: TTerm; s: PChar);– создание строкового типа;

procedure MakePStr(var tp: TTerm; s: string);– создание строкового типа;

procedure MakeInt(var tp: TTerm; i: longint);– создание целого типа;

procedure MakeFloat(var tp: TTerm; f: Single);– создание вещественного типа;

procedure MakeAddr(var tp: TTerm; p: pointer);– создание адреса.

Получение значения термов Пролога

function GetTermType(t: TTerm): TPType;– получение типа терма;

procedure GetTerm(t: TTerm; dt: TDType; p: pointer);– получение терма;

function GetPStrTerm(t: TTerm): string;– получение имени терма;

function GetIntTerm(t: TTerm): integer;– получение значения целого терма;

function GetLongTerm(t: TTerm): longint;– получение значения терма типа длинное целое;

function GetShortTerm(t: TTerm): longint;– получение значения терма типа короткое целое;

function GetFloatTerm(t: TTerm): single;– получение значения терма вещественного типа.

Работа с функторами

procedure GetFA(t: TTerm; var s: string; var ap: TArity);– получение арности функтора;

function GetFunctor(t: TTerm): string;– получение функтора;

function GetArity(t: TTerm): integer;– получение арности;

procedure MakeFA(var tp: TTerm; s: string; a: TArity);– создание арности функтора;

function UnifyArg(var tp: TTerm; n: integer; dt: TDType; p: pointer): Boolean;– унификация арности функтора;

function UnifyPStrArg(var tp: TTerm; n: integer; s: string): Boolean;– унификация арности функтора;

function UnifyAtomArg(var tp: TTerm; n: integer; s: string): Boolean;– унификация аргументов;

function UnifyIntArg(var tp: TTerm; n: integer; i: integer): Boolean;– унификация целого аргумента;

function UnifyLongArg(var tp: TTerm; n: integer; i: longint): Boolean;– унификация аргумента типа длинное целое;

function UnifyShortArg(var tp: TTerm; n: integer; i: longint): Boolean;– унификация аргумента типа короткое целое;

function UnifyFloatArg(var tp: TTerm; n: integer; f: single): Boolean;– унификация аргумента вещественного типа;

procedure GetArg(t: TTerm; n: integer; dt: TDType; p: pointer);– получение аргумента;

function GetPStrArg(t: TTerm; n: integer): string;– получение строкового аргумента;

function GetIntArg(t: TTerm; n: integer): integer;– получение целочисленного аргумента;

function GetLongArg(t: TTerm; n: integer): longint;– получение аргумента типа длинное целое;

function GetShortArg(t: TTerm; n: integer): longint;– получение аргумента типа короткое целое;

function GetFloatArg(t: TTerm; n: integer): single;– получение аргумента вещественного типа;

function GetArgType(t: TTerm; n: integer): TPType;– получение типа аргумента;

function StrArgLen(t: TTerm; i: integer): integer;– получение длины строкового аргумента;

function Unify(t1: TTerm; t2: TTerm): Boolean;– выполнение унификации.

Работа со списком

procedure MakeList(var tp: TTerm);– создание списка;

procedure PushList(var tp: TTerm; t: TTerm);– помещение элемента в список;

function PopList(var tp: TTerm; dt: TDType; p: pointer): TRC;– извлечение элемента из списка;

function PopPStrList(var tp: TTerm; var s: string): TRC;– извлечение строкового элемента из списка;

function PopIntList(var tp: TTerm; var i: integer): TRC;– извлечение целочисленного элемента из списка;

function PopLongList(var tp: TTerm; var i: longint): TRC;– извлечение элемента типа длинное целое из списка;

function PopShortList(var tp: TTerm; var i: longint): TRC;– извлечение элемента типа короткое целое из списка;

function PopFloatList(var tp: TTerm; var f: single): TRC;– извлечение элемента вещественного типа.

Работа
с
потоками

procedure SetStream(st: TPStream; i: integer);– открытие потока;

function GetStream(st: TPStream): integer;– получение потока;

procedure SetInput(pfunc1: TGetC; pfunc2: TUngetC);– установка вводного потока;

procedure SetOutput(pfunc1: TPutC; pfunc2: TPutS);– установка выводного потока;

Получение версии языка

function GetPVersion: string;– получение версии языка.

Обработка ошибок

procedure ErrMsg(s: PChar);– сообщение об ошибке;

function ErrPMsg: string;– сообщение об ошибке;

procedure ErrRaise(s: string);– защищенный блок;

procedure ErrReadBuf(var i: LongInt; s: PChar);– чтение буфера ошибки.

Контрольный пример

Ниже приведён текст модуля, производящего запросы к базе данных.

unit lab6Unit;

interface

uses

Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,

Amzi, StdCtrls, Buttons;

type

TForm1 = class(TForm)

LSEngine: TLSEngine;

OutPut: TListBox;

GroupBox1: TGroupBox;

BitBtn1: TBitBtn;

Label1: TLabel;

Label2: TLabel;

ComboBox1: TComboBox;

procedure FormCreate(Sender: TObject);

procedure FormClose(Sender: TObject; var Action: TCloseAction);

procedure BitBtn1Click(Sender: TObject);

private

{ Private declarations }

t: TTerm;

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

{$R *.DFM}

procedure TForm1.FormCreate(Sender: TObject);

begin

try

LSEngine.InitLS('lab6');

LSEngine.LoadXPL('lab6');

LSEngine.Main;

except

showmessage('База не загружена');

end;

end;

procedure TForm1.FormClose(Sender: TObject; var Action: TCloseAction);

begin

try

LSEngine.CloseLS;

except

showmessage('База не закрыта');

end;

end;

procedure TForm1.BitBtn1Click(Sender: TObject);

var

tf:boolean;

begin

Output.items.Clear;

tf := LSEngine.CallPStr(t, ComboBox1.Text);

while tf do

begin

if LSEngine.GetArity(t)=1 then Output.items.add(LSEngine.GetPStrArg(t, 1)+' is '+LSEngine.GetFunctor(t))

else Output.items.add(LSEngine.GetPStrArg(t, 1)+' is '+LSEngine.GetFunctor(t)+' of '+LSEngine.GetPStrArg(t, 2));

tf := LSEngine.Redo;

end;

end;

end.

Задание к работе

1. Составить программу, которая отображает все данные лабораторной работы № 1 на форме DELPHI приложения.

2. Подобрать тестовые данные, проверяющие работу программы.

3. Провести анализ ошибок и полученных результатов, составить отчет о проделанной работе.

Содержание отчета

1. Исходные тексты программ на языке Пролог и Object Pascal (Delphi).

2. Наборы тестовых данных и результаты работы программ.

3. Перечень и анализ ошибок.

4. Выводы по работе.

МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ

САМОСТОЯТЕЛЬНОЙ РАБОТЫ СТУДЕНТОВ

СОДЕРЖАНИЕ

Тема 1: Основные понятия логики. Правильная постановка целей

Тема 2: Элементы формальной логики для управления техническими устройствами

Тема 3: Программирование на языке Prolog. Синтаксис и Рекурсия на Prolog

Тема 4: Построение семантической сети на основе фрагмента текста

Тема 5: Создание фрейма - визуального образа

Тема 6: Создание не визуального фрейма

Тема 1: Основные понятия логики.
Правильная постановка целей

Цель работы
: выработать у обучаемого навыки правильного выделения целей системы, ее декомпозиции и поиска возможных (как можно больше) путей ее достижения.

Содержание работы
: цель, дерево целей, декомпозиция целей; факты и правила; прямая и обратная цепочка рассуждений

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

Цель системы можно понять неправильно, либо правильно, но неточно. Умение правильно и точно определять цели, достигаемые при применении интеллектуальной программы - одно из базовых умений специалиста по ИИ.

Разделы и темы для самостоятельного изучения	Виды и содержание самостоятельной работы
Правильная постановка целей	Задания: Выделить цель, дерево целей, выполнить декомпозицию целей; определить факты и правила; прямую и обратную цепочку рассуждений в следующих задачах: 1. Как добраться на работу вовремя. 2. Как сделать салат. 3. Как узнать, хочет ли кошка есть. 4. Тест: знаете ли вы английскую грамматику? 5. Загадка: «угадай животное» (птица, зверь или рыба). 6. Как получить диплом специалиста.

Методические рекомендации к выполнению:

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

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

- Определение цели

- Уточнение цели

- Декомпозиция уточненной цели, построение дерева целей системы с указанием степени достижения цели

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

Пример выполнения задания:

«Создать компьютерную программу, которая оценит, умеет ли ребенок считать».

При построении дерева целей можно использовать, по крайней мере, две различные стратегии, основанные на рассуждениях вида:

1) что нужно сделать, чтобы получить заданный результат;

2) что получится, если я поступлю «вот так».

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

Например, «для того, чтобы достать высоко висящий предмет, следует подпрыгнуть и схватить, а при неудаче — подставить ящик, подпрыгнуть и схватить». При таком подходе мы как бы «обслуживаем заданную цель», поясняем, какими путями она точно могла бы быть достигнута, идем от цели к фактам. Варианты, которые мы генерируем, обладают различной экономичностью. Некоторые из них приводят к цели за малое число «сложных» шагов, другие требуют много «простых» шагов.

Например, получить диплом можно «экстерном» или обучаясь на протяжении 5 лет.

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

«если я подпрыгну, то, возможно, схвачу высоко висящий предмет»,

«если я встану на ящик, то точно смогу достать выше, подпрыгнув».

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

Первую стратегию
называют нисходящей
или, что тоже самое, «обратной цепочкой рассуждений», вторую
— восходящей или прямой
.

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

Дерево целей может быть получено методом «встречной волны», когда анализируются противоречия между результатами обратной и прямой волны. Такое дерево обеспечивает оптимальный путь достижения цели.

Контроль выполнения работы:

1. В отчете отразить последовательность разработки программы:

1) определения целей;

2) определения фактов, имеющих отношение к этим целям (важно, чтобы факты исчерпывающе соответствовали своей цели), например при проверке «знает ли ребенок правила сложения» следует проверить знание сложения с «О», с «1», без переноса разряда, с переносом разряда);

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

4) оценки данных, используя правила и механизм вывода.

Литература:

1. Братко И. Программирование на языке Пролог для искусственного интеллекта: Пер. с англ. – М.: Мир, 1990. – 560с.

2. Смолин Д.В. «Введение в искусственный интеллект», М.: Изд. Академия, 2005 г.

3. Адаменко А.Н., Кучуков А.М. Логическое программирование и Visual Prolog. – СПб.: БХВ-Петербург, 2003.

4. Девятков В.В. Системы искусственного интеллекта. - М.: Изд-во МГТУ им. Н. Э. Баумана, 2001.

5. Новицкая Ю.В. Основы логического и функционального программирования (учебное пособие). – http://ermak.cs.nstu.ru/flp/

Тема:
Элементы формальной логики для управления техническими устройствами

Цель работы
: выработать у обучаемых навыки записи задач в виде уравнений математической логики, продемонстрировать достоинства и недостатки такого метода управления техническими устройствами.

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

Разделы и темы для самостоятельного изучения

Виды и содержание самостоятельной работы

Элементы формальной логики для управления техническими устройствами

Написать программу на заданную тему. 1. Интеллектуальный лифт. При примерно одновременном нажатии кнопок вызова с разных этажей направляется сначала к ближайшему этажу. 2. Диагностика заболеваний у собаки (на основе приведенного фрагмента текста). 3. Интеллектуальный выключатель света. Посетитель гостиницы идет по этажам. Свет включается перед ним и выключается после того, как посетитель прошел этаж. 4. Классификации (животные, книги, произвольные)

Методические рекомендации к выполнению:

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

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

- Определение цели

- Уточнение цели

- Декомпозиция уточненной цели, построение дерева целей системы с указанием степени достижения цели

Некоторые типичные трудности. 1. Построение формул, образующих циклы в определении. 2. Неспособность выделять сущности, заданные неявно.

Контроль выполнения работы:

Возможны 2 формы защиты работы:

1. без применения ЭВМ. Форма сдачи — отчет.

2. написание программы на Prolog

Литература:

6. Братко И. Программирование на языке Пролог для искусственного интеллекта: Пер. с англ. – М.: Мир, 1990. – 560с.

7. Смолин Д.В. «Введение в искусственный интеллект», М.: Изд. Академия, 2005 г.

8. Адаменко А.Н., Кучуков А.М. Логическое программирование и Visual Prolog. – СПб.: БХВ-Петербург, 2003.

9. Девятков В.В. Системы искусственного интеллекта. - М.: Изд-во МГТУ им. Н. Э. Баумана, 2001.

10. Новицкая Ю.В. Основы логического и функционального программирования (учебное пособие). – http://ermak.cs.nstu.ru/flp/

Тема:
Программирование на языке Prolog. Синтаксис и Рекурсия на Prolog

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

Содержание работы
: Анализ задачи, построение дерева и выбор оптимальной стратегии перебора. Прямая и обратная цепочки рассуждений.

Разделы и темы для самостоятельного изучения

Виды и содержание самостоятельной работы

Программирование на языке Prolog

Задания: Написать программу. 1. Найти выход из квадратного лабиринта (начальная точка задана). 2. Проверить, является ли некоторое выражение допустимым с точки зрения некоторой грамматики. 3. Классификация (дихотомия). 4. Электронный консультант «Какую модель ЭВМ купить?» Синтаксис и Рекурсия на Prolog: 1. Вывести на экран целые числа в порядке убывания от заданного. 2. Вычислить факториал заданного числа. 3. Вывести на экран целые числа в порядке убывания от заданного 4. до заданного. 5. Возвести число в степень на Prolog. 6. Вычислить арифметическую прогрессию. 7. Задача повышенной трудности «Волк, Коза, Капуста, Фермер».

Контроль выполнения работы:

Возможны 2 формы защиты работы:

1. без применения ЭВМ. Форма сдачи — отчет.

2. написание программы на Prolog

Литература:

1. Братко И. Программирование на языке Пролог для искусственного интеллекта: Пер. с англ. – М.: Мир, 1990. – 560с.

2. Смолин Д.В. «Введение в искусственный интеллект», М.: Изд. Академия, 2005 г.

3. Адаменко А.Н., Кучуков А.М. Логическое программирование и Visual Prolog. – СПб.: БХВ-Петербург, 2003.

4. Девятков В.В. Системы искусственного интеллекта. - М.: Изд-во МГТУ им. Н. Э. Баумана, 2001.

5. Новицкая Ю.В. Основы логического и функционального программирования (учебное пособие). – http://ermak.cs.nstu.ru/flp/

Тема:
Построение семантической сети на основе фрагмента текста

Цель работы
: активизировать ассоциативное мышление обучаемых, научить строить простейшие семантические сети, показать проблемы, возникающие при определении типа отношений в сети.

Содержание работы
: анализ задачи, построение сети, применение методов вывода на сетях.

Разделы и темы для самостоятельного изучения	Виды и содержание самостоятельной работы
Построение семантической сети на основе фрагмента текста	Задания. Построить граф с указанием типов отношений и вершин: 1) институт; 2) семья; 3)государство; 4) автомобиль; 5) пароход; 6) покупка в магазине; 7) самолет; 8) сравнение двух текстовых строк; 9) разобрать введенное предложение по членам предложения.

Методические рекомендации к выполнению:

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

Контроль выполнения работы:

Возможны 2 формы защиты работы:

1. без применения ЭВМ. Форма сдачи — отчет.

2. написание программы на Prolog

Литература:

1. Братко И. Программирование на языке Пролог для искусственного интеллекта: Пер. с англ. – М.: Мир, 1990. – 560с.

2. Смолин Д.В. «Введение в искусственный интеллект», М.: Изд. Академия, 2005 г.

3. Адаменко А.Н., Кучуков А.М. Логическое программирование и Visual Prolog. – СПб.: БХВ-Петербург, 2003.

4. Девятков В.В. Системы искусственного интеллекта. - М.: Изд-во МГТУ им. Н. Э. Баумана, 2001.

5. Новицкая Ю.В. Основы логического и функционального программирования (учебное пособие). – http://ermak.cs.nstu.ru/flp/

Тема:
Создание фрейма - визуального образа

Цель работы
: Показать глубинный смысл понятия «фрейм» и его схожесть с понятием «объект». Показать область применения фреймов для моделирования событий реального мира. Получить опыт работы с механизмом обмена сообщениями (объектной модели).

Содержание работы
: анализ задачи, построение фрейма, реализация на алгоритмическом языке.

Разделы и темы для самостоятельного изучения

Виды и содержание самостоятельной работы

Создание фрейма - визуального образа

Задания. Написать программу «Фрейм — визуальный образ». 1. Игра: кошки-мышки. На экране случайным образом порождаются кошки и мыши. Если кошка видит мышь, она гонится за ней. Мышь убегает. Если кошка поймала мышь, то мышь умирает. Если одна кошка бросится сразу на 3 мыши, то загрызут саму кошку. 2. Игра: кошка - мышка - собака. Правила аналогичны. 3. Заставка экрана: мячики, отскакивающие друг от друга. По экрану летают мячики, при ударе друг о друга или стенки экрана отскакивают. 4. Стадион (фреймы «люди», фрейм «страх»): смоделировать развитие беспорядков. 5. Автомобильный перекресток.

Контроль выполнения работы:

Возможны 2 формы защиты работы:

1. без применения ЭВМ. Форма сдачи — отчет.

2. написание программы на Prolog

Литература:

1. Братко И. Программирование на языке Пролог для искусственного интеллекта: Пер. с англ. – М.: Мир, 1990. – 560с.

2. Смолин Д.В. «Введение в искусственный интеллект», М.: Изд. Академия, 2005 г.

3. Адаменко А.Н., Кучуков А.М. Логическое программирование и Visual Prolog. – СПб.: БХВ-Петербург, 2003.

4. Девятков В.В. Системы искусственного интеллекта. - М.: Изд-во МГТУ им. Н. Э. Баумана, 2001.

5. Новицкая Ю.В. Основы логического и функционального программирования (учебное пособие). – http://ermak.cs.nstu.ru/flp/

Тема:
Создание не визуального фрейма

Цель работы
: показать глубинный смысл понятия «фрейм», показать, что объект - это совсем не обязательно визуальный образ.

Содержание работы
: анализ задачи, построение фрейма, реализация на алгоритмическом языке.

Разделы и темы для самостоятельного изучения	Виды и содержание самостоятельной работы
Создание фрейма – ксак не визуальный образ	Написать программу 1) матрица результатов тестирования; 2) матрица уравнений (с методами решить, ввести данные)

Контроль выполнения работы:

Возможны 2 формы защиты работы:

1. без применения ЭВМ. Форма сдачи — отчет.

2. написание программы на Prolog

Литература:

1. Братко И. Программирование на языке Пролог для искусственного интеллекта: Пер. с англ. – М.: Мир, 1990. – 560с.

2. Смолин Д.В. «Введение в искусственный интеллект», М.: Изд. Академия, 2005 г.

3. Адаменко А.Н., Кучуков А.М. Логическое программирование и Visual Prolog. – СПб.: БХВ-Петербург, 2003.

4. Девятков В.В. Системы искусственного интеллекта. - М.: Изд-во МГТУ им. Н. Э. Баумана, 2001.

5. Новицкая Ю.В. Основы логического и функционального программирования (учебное пособие). – http://ermak.cs.nstu.ru/flp/

Вопросы контроля знаний: