Компьютерные науки - Учебники на русском языке - Скачать бесплатно

Р(х)=3х^2+5х^3
Q(x)=4x^3+3x^4
то первый терм R(x) равен 3х^2 (первому терму в Р(х)). Хвост R(x) равен 9х^3+3х^4, т.е. результату сложения Q(x) и хвоста Р(х);
б) степень первого терма в Р больше степени первого терма в Q. В данном случае пер-вый терм в Q образует первый терм в R, а хвост R получается при прибавлении Р к хвосту Q. Например, если
Р(х)=2х^3+5х^\'4
Q(x)=3x^3-x^4
то первый терм R(x) равен 3х^2 (первому терму в Q(x)), а хвост R(x) равен 2х^3+4х^4 (результату сложения Р(х) и хвоста Q(x));
в) степени первых термов в Р и Q равны, а сумма их коэффици¬ентов отлична от нуля. В таком случае первый терм в R имеет коэф¬фициент, равный сумме коэффициентов первых тер-мов в Р и Q. Сте¬пень первого терма в R равна степени первого терма в Р (или Q). Хвост R полу-чается при сложении хвоста Р и хвоста Q. Например, если Р и Q имеют вид
Р(х)=2х+3х^3
Q(x)=3x+4x^4
то первый терм многочлена R (х) равен 5х (результату сложения пер¬вого терма в Р(х) с первым термом в Q(x)). Хвост R(x) равен 3х^3+4х^4 (результату сложения хвоста Р(х) и хвоста Q(x));
г) степени первых термов в Р и Q одинаковы, но сумма коэффи¬циентов равна нулю. В данном случае многочлен R равен результату сложения хвоста Р с хвостом Q. Например, если
р(х)=2+2х
Q(x)=2-3x^2
то
R(x)=2x-3x^2
(это результат сложения хвостов многочленов Р (х) и Q (х)).
Рассмотренный процесс сложения многочленов можно непосред¬ственно записать на языке Пролог:
/* Граничные условия
слож_мн([], Q Q).
слож_мн(P, [], P).
/* Рекурсивное условие
/* (a)
слож_мн([x(Pc, Pp)|Pt], [x(Qc, Qp)|Qt],
[x(Pc,Pp)IRt]) :-
PpQp,
слож_мн(Рt, [х(Qс,Qр) | Qt], Rt).
/*(б)
слож_мн([x(Pc, Pp) | Pt], [x(Qc, Qp) | Qt],
[x(Qc, Qp) | Rt]) :-
PpQp,
слож_мн([x(Pc, Pp) | Pt], Qt, Rt).
/*(в)
слож_мн([x(Pc, Pp) | Pt], [х(Qc,Pp) | Qt],
[x(Rc, Pp) | Rt]) :-
Rc is Pc+Qc,
Rc =\\= 0,
слож_мн(Pt, Qt,Rt).
/*(r)
слож_мн([х(Рс, Рр) | Pt],
[x(Qc.Pp) | Qt], Rt) :-
Re is Pc+Qc,
Rc =:= 0,
слож_мн(Pt, Qt, Rt).
Заметим, что в двух последних утверждениях проверка на равен¬ство осуществляется следующим образом: степени первых термов складываемых утверждений обозначает одна и та же переменная Pp.
Списки как термы. В начале главы мы упомянули о том, что спи¬сок представляется с помощью терма. Такой терм имеет функтор \'.\', Два аргумента и определяется рекурсивно. Пер-вый аргумент являет¬ся головой списка, а второй - термом, обозначающим хвост списка. Пустой список обозначается []. Тогда список [а, b] эквивалентен терму.(а,.(b, [])).
Таким образом, из списков, как и из термов, можно создавать вложенные структуры. Поэтому выражение
[[a, b], [c, d], [a], a]
есть правильно записанный список, и на запрос
?- [Н | Т]=[[а, b], с].
Пролог дает ответ
Н=[а, b]
Т=[с]
Бинарные деревья
ПРЕДСТАВЛЕНИЕ БИНАРНЫХ ДЕРЕВЬЕВ
Бинарное дерево определяется рекурсивно как имеющее левое поддерево, корень и правое поддерево. Левое и правое поддеревья са¬ми являются бинарными деревьями. На Рис.  14 показан пример би¬нарного дерева.
 
Рис.  14. Бинарное дерево.
Такие деревья можно представить термами вида
бд(Лд, К, Пд),
где Лд - левое поддерево, К - корень, а Пд - правое поддерево. Дл» обозначения пустого бинарного дерева будем использовать атом nil. Бинарное дерево на рис.5.2.1 имеет левое подде-рево
бд(бд(nil, d, nil), b, бд(nil, е, nil))
правое поддерево
бд(nil,с, nil)
и записывается целиком как
бд(бд(бд(nil,d, nil), b, бд(nil,е, nil)), а, бд(nil, с, nil)).
ПРЕДСТАВЛЕНИЕ МНОЖЕСТВ С ПОМОЩЬЮ БИНАРНЫХ ДЕРЕВЬЕВ
Описание множеств в виде списков позволяет использовать для множеств целевое ут-верждение принадлежит, определенное ранее для списков.
Однако для множеств, состоящих из большого числа элементов, списковые целевые ут-верждения становятся неэффективными. Рас¬смотрим, например, как целевое утверждение при-надлежит (см. предыдущий разд.) позволяет моделировать принадлежность множеству. Пусть L - список, описывающий множество из первых 1024 нату¬ральных чисел. Тогда при ответе на за-прос
?- принадлежит(3000, b).
Прологу придется проверить все 1024 числа, прежде чем заключить, что такого числа нет:
нет
Представление множества бинарным деревом позволяет добиться лучшего результата. При этом бинарное дерево должно быть упоря¬дочено таким образом, чтобы любой элемент в левом поддереве был меньше, чем значение корня, а любой элемент в правом поддереве — больше. Поскольку мы определили поддерево как бинарное дерево, такое упорядочение приме-няется по всем поддеревьям. На Рис.  15 приведен пример упорядоченного бинарного дерева.
Дерево на Рис.  14 является неупорядоченным.
 
Рис.  15. Упорядоченное бинарное дерево.
Обратите внимание, что упорядочение приводит не к единствен¬ному варианту представ-ления множества с помощью дерева. Напри¬мер, на Рис.  16 изображено то же множество, что и на Рис.  15.
Будем называть линейным представление такого вида, как на Рис.  16, и сбалансиро-ванным - такое, как на Рис.  15.
 
Рис.  16. Линейное представление.
Моделирование принадлежности множеству. Имея множество, описанное бинарным де-ревом, мы можем моделировать принадлежность множеству с помощью целевого утверждения принадлежит_дереву. При этом используется оператор @<, выражающий от¬ношение «меньше, чем», и оператор @>, выражающий отношение «больше, чем».
/* Граничное условие: Х принадлежит
/* дереву, если Х является корнем.
принадлежит_дереву(Х, бд(Лд, Х, Пд)),
/* Рекурсивные условия
/* Х принадлежит дереву, если Х больше
/* значении корня и находится в правом
/* поддереве:
принадлсжит_дереву(Х, бд(Лд, У, Пд)) :- X@Y,
припадлежит_дереву(Х, Пд).
/* Х принадлежит дереву, если Х меньше
/* значения корня и находится в левом
/* поддереве:
принадлежит_дереву(Х, бд(Лд ,У ,Пд)) :-X@Y,
принадлежит_дереву(Х, Лд).
Если множество из первых 1024 чисел описать с помощью сба¬лансированного бинарно-го дерева Т, то при ответе на запрос
?- принадлежит_дереву(3000, Т).
Пролог сравнит число 3000 не более чем с 11 элементами множества. прежде чем отве-тит:
нет
Конечно, если Т имеет линейное представление, то потребуется сравнение 3000 с 1024 элементами множества.
Построение бинарного дерева. Задача создания упорядоченного бинарного дерева при добавлении элемента Х к другому упорядочен¬ному бинарному дереву формулируется следую-щим образом:
Граничное условие:
Добавление Х к nil дает бд(nil, Х, nil).
Рекурсивные условия:
При добавлении Х к бд(Лд, К, Пд) нужно рассмотреть два случая, чтобы быть уверен-ным, что результирующее дерево будет упорядо¬ченным.
1. Х меньше,чем К. В этом случае нужно добавить Х к Лд, чтобы получить левое подде-рево. Правое поддерево равно Пд, а значение корня результирующего дерева равно К.
2. Х больше, чем К. В таком случае нужно добавить Х к Пд, что¬бы получить правое поддерево. Левое поддерево равно Лд, а значе¬ние корня - К.
Такой формулировке задачи соответствует программа:
/* Граничное условие:
включ_бд(nil, Х, бд(nil, Х, nil)).
/* Рекурсивные условия:
/*(1)
включ_бд(бд(Лд, К, Пд), Х, бд(Лднов, К, Пд)) :-
Х@К,
включ_бд(Лд,Х,Лднов).
/*(2)
включ_бд(бд(Лд, К, Пд), Х, бд(Лд, К, Пднов)) :-
Х@К,
включ_бд(Пд, Х, Пднов).
На запрос
?- включ_бд(nil, d, Т1), включ_бд(Т1, а, Т2).
будут получены значения
Т1=бд(nil, d, nil)
Т2=бд(бд(nil, а, nil), d, nil)
Процедуру включ_бд() можно использовать для построения упо¬рядоченного дерева из списка:
/* Граничное условие:
список_в_дерево([], nil).
/* Рекурсивное условие:
список_в_дерево([Н | Т], Бд) :-
список_в_дерево(Т, Бд2),
включ_бд(Н, Бд2, Бд).
Заметим, что включ_бд не обеспечивает построения сбалансиро¬ванного дерева. Однако существуют алгоритмы, гарантирующие та¬кое построение.
Механизм возврата и процедурная семантика
При согласовании целевого утверждения в Прологе используется метод, известный под названием механизма возврата. В этой главе мы показываем, в каких случаях применяется ме-ханизм возврата, как он работает и как им пользоваться. Описывается декларативная и проце-дурная семантика процедур Пролога. Завершается глава об¬суждением вопросов эффективности.
Механизм возврата
При попытке согласования целевого утверждения Пролог выби¬рает первое из тех ут-верждений, голова которых сопоставима с целе¬вым утверждением. Если удастся согласовать тело утверждения, то целевое утверждение согласовано. Если нет, то Пролог переходит к сле-дующему утверждению, голова которого сопоставима с целевым утверждением, и так далее до тех пор, пока целевое утверждение не будет согласовано или не будет доказано, что оно не со-гласуется с ба¬зой данных.
В качестве примера рассмотрим утверждения:
меньше(X.Y) :-
XY, write(X),
write (\'меньше, чем\'),write(Y).
меньше(Х.У) :-
XY, write(Y),
write (\'меньше, 4CM\'),write(X).
Целевое утверждение
?- меньше (5, 2).
сопоставляется с головой первого утверждения при Х=5 и У=2. Одна¬ко не удается со-гласовать первый член конъюнкции в теле утвержде¬ния X<Y. Значит, Пролог нс может исполь-зовать первое утвержде¬ние для согласования целевого утверждения меньше(5, 2). Тогда Пролог переходит к следующему утверждению, голова которого со¬поставима с целевым утверждением. В нашем случае это второе утверждение. При значениях переменных Х=5 и Y=2 тело утвержде-ния согласуется. Целевое утверждение меньше(5,2) доказано, и Пролог выдает сообщение «2 меньше, чем 5». Запрос
?-меньше (2, 2).
сопоставляется с головой первого утверждения, но тело утверждения согласовать не удается. Затем происходит сопоставление с головой второго утверждения, но согласовать тело опять-таки оказывается невозможно. Поэтому попытка доказательства целевого утвержде¬ния меньше(2, 2) заканчивается неудачей.
Такой процесс согласования целевого утверждения путем прямого продвижения по про-грамме мы называем прямой трассировкой (forward tracking). Даже если целевое утверждение согласовано, с помощью прямой трассировки мы можем попытаться получить другие варианты его доказательства, т.е. вновь согласовать целевое утверждение.
Пролог производит доказательство конъюнкции целевых утверж¬дений слева направо. При этом может встретиться целевое утвержде¬ние, согласовать которое не удается. Если такое случается, то проис¬ходит смещение влево до тех пор, пока не будет найдено целевое ут¬верждение, которое может быть вновь согласовано, или не будут ис черпаны все предшествую-щие целевые утверждения. Если слева нет целевых утверждений, то конъюнкцию целевых ут-верждений согласовать нельзя. Однако, если предшествующее целевое утверждениг может быть согласовано вновь, Пролог возобновляет процесс доказа¬тельства целевых утверждений слева направо, начиная со следующе¬го справа целевого утверждения. Описанный процесс смещения вле¬во для повторного согласования целевого утверждения и возвраще¬ния вправо носит название механизма возврата.
Пример: задача поиска пути в лабиринте
В качестве примера использования механизма возврата напишем процедуру для поиска пути в лабиринте. Лабиринт представлен фак¬тами вида:
стена(I, J)                для позиции в I-м ряду и J-й колонке, где есть стена
отсутств_стена(I, J)       для позиции в I-м ряду и J-й колонке, где нет стены
выход (I, J)               для позиции в 1-м ряду и J-й колонке, являющейся выходом
Рассмотрим небольшой лабиринт:
    
    
Выход    
    

Последний ряд лабиринта описывается фактами:
стена(4,1).
стена(4,3).
стена(4,4).
отсутств_стена(4,2).
Если задана исходная позиция, путь к выходу можно найти сле¬дующим образом.
Граничное условие:
Если исходная позиция является выходом, то путь найден.
Рекурсивные условия:
Ищем путь из исходной позиции в северном направлении. Если пути нет, идем на юг. Если пути нет, идем на запад. Если нельзя, идем на восток. Если соседняя позиция на севере (юге, западе, восто¬ке) является стеной, то нет смысла искать путь из начальной пози¬ции к выхо-ду. Чтобы не ходить кругами, будем вести список пози¬ций, в которых мы побывали.
Изложенному способу решения задачи соответствует процедура путь: она ищет путь (второй аргумент) к выходу из некоторой пози¬ции (первый аргумент). Третьим аргументом яв-ляется список пози¬ций, где мы побывали.
/* Терм a(I, J) представляет позицию в
/* I-м ряду и J-й колонке.
/* Нашли путь ?
путь(а(I, J),[а(I, J)], Были) :- выход(I, J).
/* Пытаемся идти на север
путь(а(I, J),[а(I, J) | Р], Были) :-
К is I-1,
можем_идти(a (K, J), Были),
путь(а(I, J) ,Р, [a(K, J) | Были]).
/* Пытаемся идти на юг
путь(а(I, J),[а(I, J) | Р], Были) :-
К is I+1,
можем_идти(a (K, J), Были),
путь(а(I, J) ,Р, [a(K, J) | Были]).
 /* Пытаемся идти на запад
путь(а (I, J), [a (I, J) | P], Были) :-
L is J-1,
можем_идти(а(I, L), Были),
путь(а(I, L), Р, [а(I, L)| Были]).
/* Пытаемся идти на восток
путь(а (I, J), [a (I, J) | P], Были) :-
L is J+1,
можем_идти(а(I, L), Были),
путь(а(I, L), Р, [а(I, L)| Были]).
/* в позицию a(I, J) можно попасть при
/* условии, что там нет стены и мы
/* не побывали в ней прежде
можем_идти(а(I, J)), Были) :-
отсутств_стена(I, J),
not (принадлежит (a (I, J), Были)).
Для того чтобы понять, каким образом процедура ищет путь к выходу, рассмотрим про-цесс согласования запроса с описанием лаби¬ринта, описанного выше:
?-путь(а(4,2), Р, [а(4.2)]).
Выходом из лабиринта является позиция выход (3,1).
Выбор первого утверждения не приводит к согласованию целево¬го утверждения, по-скольку а (4,2) - не выход. Во втором утверждении делается попытка найти путь в северном на-правлении, т.е. согласовать целевое утверждение
путь(а(3, 2), Р2, [а(3, 2), а(4, 2)]).
Целевое утверждение не удается согласовать с первым утвержде¬нием
путь(а(3, 2), Р2, [а(3, 2), а(4, 2)])
так как а (3,2) не является выходом. Во втором утверждении пред¬принимается попытка найти путь, двигаясь на север, т.е. согласовать целевое утверждение
путь(а(2,2), РЗ, [а(2, 2), а(3, 2), а(4, 2)]).
Ни одно из утверждений не может согласовать
путь(а(2, 2), РЗ, [а(2, 2), а(3, 2), а(4, 2)]).
Первое утверждение - потому, что а (2, 2) не является выходом, вто¬рое - потому, что се-верная позиция является стеной, третье утверждение - потому, что в южной позиции мы уже побывали, а четвертое и пятое утверждения - потому, что западная и восточная границы - это стены.
Неудача в согласовании
путь(а(2, 2), РЗ, [а(2, 2), а(3, 2), а(4, 2)])
заставляет Пролог-систему вернуться в ту точку, где было выбрано второе утверждение при попытке согласовать
путь(а(3, 2), Р2, [а(3, 2), а(4, 2)]).
Решение пересматривается и выбирается третье утверждение.
В третьем утверждении осуществляется попытка найти путь, двигаясь на юг, но она ока-зывается неудачной, поскольку мы уже по¬бывали в позиции а (4, 2). Тогда, чтобы согласовать
путь(а(3, 2), Р2, [а(3, 2), а(4, 2)]),
выбирается четвертое утверждение. Мы успешно находим путь, дви¬гаясь в западном направлении к позиции а(3,1), которая и является выходом. Рекурсия сворачивается, и в резуль-тате полу¬чается путь
Р=[а(4, 2),а(3, 2), а(3,1)]
другие решения(да/нет)? да
Других решений нет
Альтернативный путь
[a(4,2), a(3,2), a(2,2), a(3,2), a(3,1)]
мы получить не можем, потому что не разрешается дважды бывать в одной и той же по-зиции.
Описанная процедура не обязательно находит кратчайший путь к выходу. Кратчайший путь можно найти, генерируя альтернативные пути с помощью вызова состояния неудачи и за-поминая кратчайший из них.
Элементы нечеткой логики
Как известно, классическая логика оперирует только с двумя значениями: истина и ложь. Однако этими двумя значениями довольно сложно представить (можно, но громоздко) большое количество реальных задач. Поэтому для их решения был разработан специальный ма-тематический аппарат, называемый нечеткой логикой. Основным отличием нечеткой логики от классической, как явствует из названия, является наличие не только двух классических состоя-ний (значений), но и промежуточных:
F{0…1}
Соответственно, вводятся расширения базовых операций логического умножения, сло-жения и отрицания (сравните с соответствующими операциями теории вероятностей):
 
 
 
Как можно легко заметить, при использовании только классических состояний (ложь-0, истина-1) мы приходим с классическим законам логики.
Нечеткое логическое управление может использоваться, чтобы осуществлять разнооб-разные интеллектуальные функции, в самых разнообразных электронных товарах и домашних приборах, к авто электронике, управлению производственными процессами и автоматизации.

Указатели
 
I
intelligence 1
artificial 1
И
интеллект 1
искусственный 1
интеллектуальная задача 1
 

Содержание
ЛЕКЦИЯ 1-2: БАЗОВЫЕ ПОНЯТИЯ ИИ 1
ЦЕЛЬ ПРЕПОДАВАНИЯ ДИСЦИПЛИНЫ 1
ТЕРМИНОЛОГИЯ 1
ФИЛОСОФСКИЕ АСПЕКТЫ ПРОБЛЕМЫ СИСТЕМ ИИ (ВОЗМОЖНОСТЬ СУЩЕСТВОВАНИЯ, БЕЗОПАСНОСТЬ, ПОЛЕЗНОСТЬ). 3
ИСТОРИЯ РАЗВИТИЯ СИСТЕМ ИИ. 5
ЛЕКЦИЯ 3: АРХИТЕКТУРА И ОСНОВНЫЕ СОСТАВНЫЕ ЧАСТИ СИСТЕМ ИИ 9
РАЗЛИЧНЫЕ ПОДХОДЫ К ПОСТРОЕНИЮ СИСТЕМ ИИ 9
ВСПОМОГАТЕЛЬНЫЕ СИСТЕМЫ НИЖНЕГО УРОВНЯ (РАСПОЗНАВАНИЕ ОБРАЗОВ ЗРИТЕЛЬНЫХ И ЗВУКОВЫХ, ИДЕНТИФИКАЦИЯ, МОДЕЛИРОВАНИЕ, ЖЕСТКОЕ ПРОГРАММИРОВАНИЕ) И ИХ МЕСТО В СИСТЕМАХ ИИ 11
ЛЕКЦИИ 4-7: СИСТЕМЫ РАСПОЗНАВАНИЯ ОБРАЗОВ (ИДЕНТИФИКАЦИИ) 14
ПОНЯТИЕ ОБРАЗА 14
ПРОБЛЕМА ОБУЧЕНИЯ РАСПОЗНАВАНИЮ ОБРАЗОВ (ОРО) 14
ГЕОМЕТРИЧЕСКИЙ И СТРУКТУРНЫЙ ПОДХОДЫ. 17
ГИПОТЕЗА КОМПАКТНОСТИ 19
ОБУЧЕНИЕ И САМООБУЧЕНИЕ. АДАПТАЦИЯ И ОБУЧЕНИЕ 19
ПЕРЦЕПТРОНЫ 20
НЕЙРОННЫЕ СЕТИ 22
История исследований в области нейронных сетей 22
Модель нейронной сети с обратным распространением ошибки (back propagation) 23
Нейронные сети: обучение без учителя 26
НЕЙРОННЫЕ СЕТИ ХОПФИЛДА И ХЭММИНГА 29
МЕТОД ПОТЕНЦИАЛЬНЫХ ФУНКЦИЙ 32
МЕТОД ГРУППОВОГО УЧЕТА АРГУМЕНТОВ МГУА 33
Метод наименьших квадратов 33
Общая схема построения алгоритмов метода группового учета аргументов (МГУА). 35
Алгоритм с ковариациями и с квадратичными описаниями. 36
МЕТОД ПРЕДЕЛЬНЫХ УПРОЩЕНИЙ (МПУ) 37
КОЛЛЕКТИВЫ РЕШАЮЩИХ ПРАВИЛ 38
МЕТОДЫ И АЛГОРИТМЫ АНАЛИЗА СТРУКТУРЫ МНОГОМЕРНЫХ ДАННЫХ 39
Кластерный анализ 39
Иерархическое группирование 41
ЛЕКЦИИ 8-11. ЛОГИЧЕСКИЙ ПОДХОД К ПОСТРОЕНИЮ СИСТЕМ ИИ 43
НЕФОРМАЛЬНЫЕ ПРОЦЕДУРЫ 43
Алгоритмические модели 43
Продукционные модели 44
Режим возвратов 45
Логический вывод 45
Зависимость продукций 46
Продукционные системы с исключениями 46
ЯЗЫК РЕФАЛ 47
ПРОЛОГ 49
Синтаксис 49
ТЕРМЫ 49
КОНСТАНТЫ 50
ATOM 50
ЧИСЛА 50
ПЕРЕМЕННЫЕ 50
ОБЛАСТЬ ДЕЙСТВИЯ ПЕРЕМЕННЫХ 50
СЛОЖНЫЕ ТЕРМЫ, ИЛИ СТРУКТУРЫ 51
СИНТАКСИС ОПЕРАТОРОВ 51
СИНТАКСИС СПИСКОВ 51
СИНТАКСИС СТРОК 51
УТВЕРЖДЕНИЯ 51
ЗАПРОСЫ 52
ВВОД программ 52
Унификация 53
Арифметические выражения 54
Введение 54
Арифметические выражения 55
Арифметические операторы 55
Вычисление арифметических выражений 55
Сравнение результатов арифметических выражений 56
Структуры данных 56
Списки 56
Бинарные деревья 61
ПРЕДСТАВЛЕНИЕ БИНАРНЫХ ДЕРЕВЬЕВ 61
ПРЕДСТАВЛЕНИЕ МНОЖЕСТВ С ПОМОЩЬЮ БИНАРНЫХ ДЕРЕВЬЕВ 61
Механизм возврата и процедурная семантика 63
Механизм возврата 63
Пример: задача поиска пути в лабиринте 64
ЭЛЕМЕНТЫ НЕЧЕТКОЙ ЛОГИКИ 66