Учебно-методическое пособие для студентов, обучающихся по специальности «Информатика»



Скачать 436.3 Kb.
страница3/4
Дата26.07.2014
Размер436.3 Kb.
ТипУчебно-методическое пособие
1   2   3   4

Языки искусственного интеллекта

Лисп (LISP) и Пролог (Prolog) - наиболее распространенные языки, предназначенные для решения задач искусственного интеллекта. Есть и менее распространенные языки искусственного интеллекта, например РЕФАЛ, разработанный в России. Универсальность этих языков меньшая, нежели традиционных языков, но ее потерю языки искусственного интеллекта компенсируют богатыми возможностями по работе с символьными и логическими данными, что крайне важно для задач искусственного интеллекта. На основе языков искусственного интеллекта создаются специализированные компьютеры (например, Лисп-машины), предназначенные для решения задач искусственного интеллекта. Недостаток этих языков - неприменимость для создания гибридных экспертных систем.



Специальный программный инструментарий

Библиотеки и надстройки над языком искусственного интеллекта Лисп: KEE (Knowledge Engineering Environment), FRL (Frame Representation Language), KRL (Knowledge Represantation Language), ARTS и др., позволяющие пользователям работать с заготовками экспертных систем на более высоком уровне, нежели это возможно в обычных языках искусственного интеллекта.



"Оболочки"

"Оболочки" – это пустые" версии существующих экспертных систем, т.е. готовые экспертные системы без базы знаний. Примером такой оболочки может служить EMYCIN (Empty MYCIN - пустой MYC1N), которая представляет собой незаполненную экспертную систему MYCIN. Достоинство оболочек в том, что они вообще не требуют работы программистов для создания готовой экспертной системы. Требуется только специалисты в предметной области для заполнения базы знаний. Однако если некоторая предметная область плохо укладывается в модель, используемую в некоторой оболочке, заполнить базу знаний в этом случае весьма не просто.



5. ПРОЛОГ - язык логического
программирования


5.1. Общие сведения о ПРОЛОГе.

ПРОЛОГ(ПРОграммирование в ЛОГике) - язык логического программирования, предназначен для решения задач из области искусственного интеллекта (создание ЭС, программы-переводчики, обработка естественного языка). Он используется для обработки естественного языка и обладает мощными средствами, позволяющими извлекать информацию из баз данных, причем методы поиска, используемые в нем, принципиально отличаются от традиционных.

Основные конструкции ПРОЛОГа заимствованы из логики. ПРОЛОГ относится не к процедурным, а к декларативным языкам программирования. Он ориентирован не на разработку решений, а на систематизированное и формализованное описание задачи с тем, чтобы решение следовало из составленного описания.

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

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



Фундаментальные свойства ПРОЛОГа:

  1. механизм вывода с поиском и возвратом

  2. встроенный механизм сопоставления с образцом

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

  4. отсутствие указателей, операторов присваивания и перехода

  5. естественность рекурсии

Этапы программирования на ПРОЛОГе:

  1. объявление фактов об объектах и отношениях между ними;

  2. определение правил взаимосвязи объектов и отношений между ними;

  3. формулировка вопроса об объектах и отношениях между ними.

Теоретической основой ПРОЛОГа является раздел символьной ло­гики, называемый исчислением предикатов.

Предикат – это имя свойства или отношения между объектами с последовательностью аргументов.

<имя_предиката>(t1, t2, ..., tn) ), t1,t2,...,tn – аргументы

Например, факт black(cat) записан с использованием предиката black, имеющего один аргумент. Факт написал(шолохов, "ТИХИЙ ДОН") записан с использованием предиката написал, имеющего два аргумента.

Число аргументов предиката называется арностью предиката и обозначается black/1 (предикат black имеет один аргумент, его арность равна единице). Предикаты могут не иметь аргументов, арность таких предикатов равна 0.

Язык Пролог вырос из работ Алана Колмерауэра (A. Colmerauer) по обработке естественного языка и независимых работ Роберта Ковалького (R. Kowalski) по приложениям логики к программированию (1973 г.).

Наиболее известна в России система программирования Turbo Prolog — коммерческая реализация языка для IBM-совместимых ПК. В 1988 г. вышла значительно более мощная версия Turbo Prolog 2.0, включающая усовершенствованную интегрированную среду разработки программ, быстрый компилятор и средства низкоуровневого программирования. Фирма Borland распространяла эту версию до 1990 г., а затем компания PDC приобрела монопольное право на использование исходных текстов компилятора и дальнейшее продвижение системы программирования на рынок под названием PDC Prolog.

В 1996 г. Prolog Development Center выпускает на рынок систему Visual Prolog 4.0. В среде Visual Prolog используется подход, получивший название «визуальное программирование», при котором внешний вид и поведение программ определяются с помощью специальных графических средств проектирования без традиционного программирования на алгоритмическом языке.

В Visual Prolog входят интерактивная среда визуальной разработки (VDE — Visual Develop Environment), которая включает текстовый и различные графические редакторы, инструментальные средства генерации кода, конструирующие управляющую логику (Experts), а также являющийся расширением языка интерфейс визуального программирования (VPI — Visual Programming Interface), Пролог-компилятор, набор различных подключаемых файлов и библиотек, редактор связей, файлы, содержащие примеры и помощь.

5.2. Предложения: факты и правила

Программа на ПРОЛОГе состоит из предложений, которые могут быть фактами, правилами или запросами.



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

Структура факта:



<имя_отношения>( t1,t2,...,tn) ), t1,t2,...,tn– объекты

Примеры фактов:

учится (ира, университет). % Ира учится в университете

родитель(иван, алексей). % Иван является родителем Алексея

язык_программирования (пролог). % Пролог – это язык программирования

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



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

Структура правила:



<имя_правила> :- <тело правила> или

<имя_правила > if <тело правила>

Левая часть правила вывода называется головой правила, а правая часть - телом. Тело может состоять из нескольких условий, перечисленных через запятую или точку с запятой. Запятая означает операцию «логическое И», точка с запятой – операцию «логическое ИЛИ». В предложениях используются переменные для обобщенной формулировки правил вывода. Переменные действуют только в одном предложении. Имя в разных предложениях указывает на разные объекты. Все предложения обязательно заканчиваются точкой.

Примеры правил:

мать (Х, У) :- родитель (Х, У), женщина(Х).

студент (X) :- учится (X, институт); учится (X, университет).

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



5.3. Запросы

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

Запросы с константами позволяют получить один из двух ответов: “да” или “нет”

Например, имеются факты:

знает (лена, таня).

знает (лена, саша).

знает (саша, таня).

а) Знает ли Лена Сашу?

запрос: знает (лена, саша).

Результат: yes

б) Знает ли Таня Лену?

запрос знает (таня, лена).

Результат: no

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

а) Кого знает Лена?

запрос: знает (лена, Х).

Результат:

Х = таня

Х = саша

б) Кто знает Сашу?

запрос: знает (Х, саша).

Результат: Х = лена

Запросы могут быть составными, т.е. состоять из нескольких простых запросов. Они объединяются знаком “,“, который понимается как логическая связка “и”.

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

Для ответа, есть ли общие знакомые у Лены и Саши, следует составить запрос:

знает (лена, Х), знает (саша, Х).

Результат:



Х = Таня

5.4. Переменные в ПРОЛОГе

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

Имя переменной должно начинаться с прописной буквы или символа подчеркивания и содержать только символы букв, цифр и подчеркивания: Х, _у, АВ, Х1. Переменная, не имеющая значения, называется свободной, переменная, имеющая значение – конкретизированной.

Переменная, состоящая только из символа подчеркивания, называется анонимной и используется в том случае, если ее значение несущественно. Например, имеются факты:

родитель (ира, таня).

родитель (миша, таня).

родитель (оля, ира).

Требуется определить всех родителей

Запрос: родитель(Х, _)

Результат:



Х = Ира

Х = Миша

Х = Оля

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

В ПРОЛОГе нет оператора присваивания, его роль выполняет оператор равенства =. Цель X=5 может рассматриваться как сравнение (если переменная X имеет значение) или как присваивание (если переменная X свободна).

В ПРОЛОГе нельзя для увеличения значения переменной записать X=X+5. Следует использовать новую переменную: Y=X+5.



5.5. Объекты и типы данных в ПРОЛОГе

Объекты данных в ПРОЛОГе называются термами. Терм может быть константой, переменной или составным термом (структурой). Константами являются целые и действительные числа (0, -l, 123.4, 0.23E-5), а также атомы.



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

abcd, “a+b”, “студент Иванов”, пролог, “Пролог”.



Структура позволяет объединить несколько объектов в единое целое. Она состоит из функтора (имя) и последовательности термов.

Например, data (15, апрель, 1983)

data – функтор, (15, апрель, 1983) – термы

Число компонент в структуре называется арностью структуры: data/3.

Структура может содержать другую структуру в качестве одного из своих объектов.

день_рождения (person(“Маша”,”Иванова”), data(15,апрель,1983))



Доменом в ПРОЛОГе называют тип данных. Стандартными доменами являются:

integer – целые числа.

real – вещественные числа.

string – строки (любая последовательность символов, заключенная в кавычки).

char – одиночный символ, заключенный в апострофы.

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



5.6. Основные разделы ПРОЛОГ-программы

Как правило, программа на ПРОЛОГе состоит из четырех разделов.



DOMAINS – секция описания доменов (типов). Секция применяется, если в программе используются нестандартные домены.

Например:

name = string

data = integer



PREDICATES – секция описания предикатов. Секция применяется, если в программе используются нестандартные предикаты.

Например:

знает (name, name)

студент (name)



CLAUSES – секция предложений. Именно в этой секции записываются предложения: факты и правила вывода.

Например:

знает (лена, иван).

студент (иван).

знаком_студент(X,Y):- знает (X,Y ), студент (Y).

GOAL – секция цели. В этой секции записывается запрос.

Например:

знаком_студент(лена,X).
Простейшая программа может содержать только раздел GOAL, например:

GOAL


write (“Введите Ваше имя: ”), readln (Name),

write (“Здравствуйте, ”, Name, “!”).



Комментарий: write – стандартный предикат вывода, readln – стандартный предикат ввода строкового значения

5.7. Поиск с возвратом

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

Рассмотрим механизм поиска на примере. Пусть имеются факты:

знает (лена, таня).

знает (лена, иван).

студент (иван).

Требуется определить, есть ли у Лены знакомые студенты.

Программа:

PREDICATES

знает (symbol, symbol)

студент (symbol)

знаком_студент(symbol, symbol)

CLAUSES


знает (лена, таня). % (1)

знает (лена, иван). % (2)

студент (иван). % (3)

знаком_студент(X,Y):- знает (X,Y), студент (Y). % (4)

GOAL

знаком_студент(лена, Name).



Поиск решения:

1. Пытаясь выполнить целевое утверждение знаком_студент(лена, Name), ПРОЛОГ проверяет каждое предложение из раздела CLAUSES. В результате сопоставления с предложением (4) - X=лена. Переменная Y унифицируется с переменной Name.

2. Переход к первой подцели знает (лена,Y) и поиск соответствующего предложения. В результате сопоставления с предложением (1) – Y=таня. Возле факта знает (лена, таня) устанавливается маркер.

3. Переход ко второй подцели студент (таня) и поиск соответствующего предложения. Факт не найден – возврат в точку отката.

4. Дальнейший поиск фактов, соответствующих первой подцели знает(лена,Y). В результате сопоставления с предложением (2) – Y=иван.

5. Переход ко второй подцели студент (иван) и поиск соответствующего предложения приводит к успешному завершению поиска.

Результат:

Name=иван

1 Solition

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

рис.2. Целевое дерево поиска с возвратом

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



Основные правила поиска с возвратом:

  1. Цели должны быть доказаны по порядку, слева направо.

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

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

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

5.8. Управление поиском с возвратом: предикаты fail и отсечения

Для управление поиском с возвратом используются два стандартных предиката: fail и отсечения.

1. fail – это тождественно-ложный предикат, искусственно создающий ситуацию неуспеха и заставляющий продолжить поиск. Использование предиката fail позволяет найти все решения задачи.

Пример 1. Вывести список студентов 4-го курса.

DOMAINS


name=string

kurs=integer

PREDICATES

Student(name, kurs)

spisok

CLAUSES


Student("Ира",2).

Student("Юра",4).

Student("Коля",1).

Student("Леша",4).

Student("Оля",4).

spisok:-Write("Список студентов 4 курса"), nl, Student(X,4),

Write(X), nl, fail.

GOAL


spisok.

Комментарий: nl (new line) – предикат перевода курсора на новую строку

    В данном примере после первого найденного решения (Х= «Юра») и его вывода предикат fail заставляет вернуться в точку отката и продолжить поиск, просматривая другие факты. В результате будут найдены все решения, удовлетворяющие запросу.

    Результат выполнения программы:

    Список студентов 4 курса

    Юра


    Леша

    Оля


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

Если задано предложение вида:

R:-A, B, ! , C.

то после достижения подцелей А и В процесс поиска других решений этих подцелей прекращается и вычислительный процесс перейдет к следующей подцели С.

Например, чтобы в примере 1 вывести все возможные пары одного из студентов 4-го курса со всеми остальными студентами, следует изменить правило spisok

spisok:- Student(X,4), !, Student(Y,_), X<>Y,
Write(X," - ",Y), nl, fail.

Результат выполнения программы:

Юра - Ира

Юра - Коля

Юра - Леша

Юра – Оля



5.9. Арифметические вычисления

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



X + Y

Сумма X и Y

X - Y

Разность X и Y

X * Y

Произведение X и Y

X / Y

Деление X на Y

X mod Y

Остаток от деления X на Y

abs(X)

Абсолютная величина числа X

sqrt(X)

Квадратный корень из X

random(X)

Случайное число в диапазоне от 0 до 1

random(Int,X)

Случайное целое число в диапазоне от 0 до Int

sin(X)

Синус X

cos(X)

Косинус X

tan(X)

Тангенс X

log(X)

Натуральный логарифм (ln) числа X

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

=, <, <=, >, >=, <>

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


Пример 1.

Найти среднее арифметическое двух чисел.

PREDICATES

Sr (real, real, real)

CLAUSES

Sr (A, B, S):- S = (A+B)/2.

GOAL

Sr (8, 12, S), write (S).


Результат:

10

Пример 2.

Определить является ли натуральное число четным или нечетным

PREDICATES

Chet (integer)

CLAUSES


Chet (A): - A mod 2 =0, write (A, ‘- четное’); Write (A, ‘- не четное’).

GOAL


Chet (18).

Результат:

18 – четное

5.10. Рекурсия

Рекурсия – это второе средство для организации повторяющихся действий в ПРОЛОГе. Рекурсивная процедура – это процедура, вызывающая сама себя до тех пор, пока не будет соблюдено некоторое условие, которое остановит рекурсию. Такое условие называют граничным. Рекурсия – хороший способ для решения задач, содержащих в себе подзадачу такого же типа. Рекурсивное правило всегда состоит по крайней мере из двух частей, одна из которых является нерекурсивной. Она определяет граничное условие.

Рассмотрим рекурсивное определение правила на примере правила predok

1. X является предком Z, если X - родитель Z

predok(X, Z):-roditel(X, Z)

2. X – предок для Z, если найдется такой Y, для которого X является родителем и Y является предком Z .

Predok (X,Z) :- roditel (X,Y), predok (Y,Z).

Первая часть этого правила нерекурсивная, она определяет условие завершения рекурсии. Поиск прекратится, как только будет найден ближайший предок - родитель.

Программа:

DOMAINS


name = string

PREDICATES

roditel (name, name)

predok (name, name)

CLAUSES

roditel (коля, оля).

roditel (оля, маша).

predok (X, Z):- roditel (X, Z).

predok (X, Z):- roditel (X,Y), predok (Y, Z).

GOAL


predok (коля, маша).

Результат:



yes

Пример. Рекурсивное вычисление факториала

Задача нахождения значения факториала n! сводится к нахождению значения факториала (n-1)! и умножения найденного значения на n.

Правило для вычисления факториала:

1. 0! = 1

fact (0, 1):- !. % нерекурсивная часть правила

2. N! = (N-1)!*N.

fact (N, FN):- M=N–1, % рекурсивная часть правила

fact (M, FM), FN=FM*N.

Программа:

PREDICATES

fact (integer, integer)

CLAUSES


fact (0, 1):- !.

fact (N, FactN):- M=N–1, fact (M, FactM), FactN=FactM*N.

GOAL

fact (3, FN), write (“3!=”, FN).


Результат работы программы:

3!=6

Для наглядного представления нахождения решения удобно использовать дерево целей:





рис.3 Целевое дерево вычисления факториала
1   2   3   4

Похожие:

Учебно-методическое пособие для студентов, обучающихся по специальности «Информатика» iconУчебно-методическое пособие для студентов, обучающихся по специальности «История». / А. Г. Ситдиков. Казань: Издательство Казанского государственного университета, 2008. 33 с
В этногенез народов Поволжья и Приуралья. Часть I. Истоки этногенеза финских народов: учебно-методическое пособие для студентов,...
Учебно-методическое пособие для студентов, обучающихся по специальности «Информатика» iconУчебно-методическое пособие для студентов первого курса бакалавриата, обучающихся по направлениям 080100. 62 «Экономика» и080700. 62 «Бизнес-информатика»
Линейная алгебра. Учебно-методическое пособие для студентов первого курса бакалавриата, обучающихся по направлениям 080100. 62 «Экономика»...
Учебно-методическое пособие для студентов, обучающихся по специальности «Информатика» iconУчебно-методическое пособие по Новой истории стран Азии и Африки Брянск, 2008 Сагимбаев Алексей Викторович. Учебно-методическое пособие по курсу «Новая история стран Азии и Африки»
Учебно-методическое пособие предназначено для студентов дневного отделения Исторического факультета, обучающихся по специальности...
Учебно-методическое пособие для студентов, обучающихся по специальности «Информатика» iconУчебно-методическое пособие для студентов, обучающихся по специальности 07. 00. 02 Отечественная история

Учебно-методическое пособие для студентов, обучающихся по специальности «Информатика» iconУчебно-методическое пособие для студентов 4 курса (озо, одо) специальности 050602. 65 «Изобразительное искусство»
О. А. Бакиева. Народный костюм Севера: Учебно-методическое пособие для студентов 4 курса очной и заочной формы обучения специальности...
Учебно-методическое пособие для студентов, обучающихся по специальности «Информатика» iconУчебно-методическое пособие Нижний Новгород 2007 ббк 40. 3
Учебное пособие предназначено для студентов, обучающихся по специальности 013400 Менеджмент и маркетинг в природопользовании
Учебно-методическое пособие для студентов, обучающихся по специальности «Информатика» iconУчебно-методическое пособие для студентов 1 и 2 курсов дневного и заочного отделений исторического факультета, обучающихся по специальности 07. 00. 02. отечественная история

Учебно-методическое пособие для студентов, обучающихся по специальности «Информатика» iconМ. В. Ярощук Математическое моделирование
Учебно-методическое пособие предназначено для студентов 4 курса факультета вычислительной математики и кибернетики, обучающихся по...
Учебно-методическое пособие для студентов, обучающихся по специальности «Информатика» iconУчебно-методическое пособие по курсу «Информационные технологии» для студентов Института дополнительного образования
Технологии ado. Net и asp. Net. Учебно-методическое пособие по курсу «Информационные технологии» для студентов Института дополнительного...
Учебно-методическое пособие для студентов, обучающихся по специальности «Информатика» iconУчебно-методическое пособие для самостоятельных занятий Допущено Министерством сельского хозяйства Российской Федерации в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлению «Агрономия»
Учебно-методическое пособие разработано на основании требований Государственного образовательного стандарта высшего профессионального...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org