- •1 Общая характеристика дисциплины
- •1.1 Значение дисциплины ии
- •1.2 Понятие "искусственный интеллект"
- •1.3 Краткая история развития ии
- •1.4 Классификация систем ии
- •Представления знаний - центральная проблема ии.
- •Компьютерной лингвистики, решение которой обеспечивает процесс естественно- языкового общения с эвм и процесс автомтического перевода с иностранных языков.
- •Компьютерной логики, имеющей особо важное значение для развития экспертных систем, поскольку ее цель – моделирование человеческих рассуждений.
- •1.5 Основные направления развития ии
- •2Языки систем искусственного интеллекта
- •2.1 Общие сведения о языках сии
- •2.2 Язык лисп
- •2.2.1 Алфавит
- •2.2.2 Атомы и точечные пары
- •2.2.3 Списки
- •2.2.4 Арифметические функции языка лисп
- •2.2.5 Функции setq и quote
- •2.2.6 Функции car и cdr
- •2.2.7 Композиция функций саr и cdr.
- •2.2.8 Пустой список
- •2.2.9 Функция cons
- •2.2.10 Логические значения и предикаты
- •2.2.11 Предикаты атом и eq
- •2.2.12 Предикат null
- •2.2.13 Предикаты, классифицирующие атомы
- •2.2.14 Арифметические предикаты сравнения
- •2.2.15 Операции над строками битов
- •2.2.16 Функция cond
- •2.2.17 Определяющее выражение функции
- •2.2.18 Определяемые функции
- •2.2.19 Рекурсивные функции
- •2.2.20 Prog- механизм.
- •2.3 Обращение (инверсия) списков
- •2.4 Вычисление факториала числа
- •2.5 Вычисление длины списка
- •2.6 Вычисление длины списка и его подсписков
- •2.7 Соединение списков
- •2.8 Удаление элемента из списка
- •2.9 Функция, вычисляющая список общих элементов двух списков
- •2.10 Функция, объединяющая два списка и не включающая повторяющиеся элементы
- •2.11 Ассоциативные списки
- •2.12 Функции, изменяющие значения указателей
- •2.13 Функции read и print
- •2.14 Функция eval
- •3 Представление задач и поиск решений
- •3.1 Представление задач в пространстве состояний
- •3.2 Сведение задачи к подзадачам
- •3.3Представление задач в виде доказательства теорем
- •3.4 Поиск решения в пространстве состояний
- •3.5 Алгоритм поиска в ширину
- •3.6 Алгоритм поиска в глубину
- •3.7Алгоритм равных цен
- •3.8 Алгоритмы эвристического (упорядочного) поиска
- •3.9 Поиск решения задачи, при сведении задачи к подзадачам
- •3.10 Представление знаний
- •3.10.1 Продукционные системы
- •3.10.2Семантические сети
- •3.10.3 Представление знаний фреймами
- •3.11 Сопоставление с образцом
- •3.11.1 Функции Mapcad, Apply и Funcall
- •3.11.2 Свойства Атомов
- •3.11.3 Функция сопоставления с образцом
- •3.11.4 Присваивание значений при сопоставлении с образцом
- •3.11.5 Функции Explope, Compress, AtomCar, AtomCdr
- •3.11.6 Задание ограничений при сопоставлении с образцом
- •3.12 Программная реализация лисп - машин
- •3.12.1 Структура памяти лисп - машины
- •3.12.2 Диалекты языка лисп
- •3.12.3 Аппаратная реализация языка лисп
- •4 Математические основы логического вывода
- •4.1 Решение задач с помощью доказательства теорем
- •4.2 Тождественные преобразования при доказательстве теорем
- •4.3 Принцип резолюции
- •4.4Примеры применения принципа резолюции
- •4.5 Система управления роботом strips.
- •5Решение задач искусственного интеллекта на языке пролог
- •5.1 Применение метода доказательства теорем в системе пролог
- •5.2 Особенности программирования на пролоГе
- •5.4 Арифметические предикаты
- •5.5 Предикаты управления возвратом
- •5.6 Программа вычисления квадратного корня
- •5.7 Вычисление n!
- •5.8 Область действия предиката отсечения
- •5.9 Отрицание на пролоГе
- •5.10 Определение структур управления
- •5.11 Организация циклов в языке пролог
- •5.11.1 Цикл repeat-fail
- •5.11.2 Сопоставление цикла с возвратом и рекурсии
- •5.12 Операторная запись.
- •5.13 Ввод-вывод в системе пролог
- •5.13.1 Предикаты ввода-вывода символов
- •5.13.2 Предикаты ввода-вывода термов
- •5.13.3 Примеры применения предикатов ввода-вывода
- •5.14 Предикат name
- •5.15 Предикаты проверки типов термов
- •5.16 Создание и декомпозиция термов
- •5.17 Предикаты работы с базой данных .
- •5.18 Бинарные деревья
- •5.18.1 Построение бинарного дерева
- •5.18.2 Преобразование списка в упорядоченное дерево
- •5.18.3 Преобразование дерева в список
- •5.18.4 Удаление элемента из дерева
- •5.18.5 Поиск в глубину
- •5.18.6 Поиск в ширину
- •5.19 Поиск решений в игровых программах.
- •5.20 Обратное усечение дерева.
2.2.15 Операции над строками битов
Приведенные ниже функции выполняют логические операции над битовыми представлениями своих аргументов.
(LOGAND2 X Y) <-> логическое "И"
(LOGOR2 X Y) <-> логическое "ИЛИ"
(LOGXOR2 X Y) <-> исключающее "ИЛИ"
Пример:
(LOGAND2 10 5) ==> (LOGAND2 1010 0101)->0
Т.е. операции производятся поразрядно над двоичными эквивалентами значений аргументов.
(LEFTSHIFT X Y) - первый аргумент есть восьмеричное число, второй - десятичное. Значение функции равно значению Х, сдвинутому на У разрядов влево (Y>0) или вправо (Y<0).
2.2.16 Функция cond
Число аргументов функции COND произвольно. Значения аргументов не вычисляются перед началом вычисления функции, а берутся в том виде, в каком они записаны. Более того, значения аргументов не могут быть вычислены. Каждый аргумент есть список из двух элементов:
(COND (P1 E1)(P2 E2)...(Pn En)), где
Р1, Р2, ... ,Рn- предикаты,
Е1, Е2, ... ,Еn- выражения на языке Лисп.
Порядок выполнения функции следующий. Если Р1=Т, то вычисляется значение выражения Е1 и оно возвращается в качестве результата, иначе происходит переход к анализу следующей скобки.Если Р2=Т, то вычисляем Е2 и т.д. Если все предикаты Рn-ложные, то результат- NIL.
Пример:
(COND ((ATOM A) NIL)(T T))->NIL
Если А - атом, то возвращается значение NIL, в противном случае, результат - Т.
2.2.17 Определяющее выражение функции
Можно ли сказать, что (COND ((ATOM A) NIL)(T T)) есть функция? Да, т.к. в зависимости от А это выражение позволяет вычислять требуемое значение. Но с другой стороны, вэтом выражение ничего не говорит о числе аргументов функции, их обозначении и задании их значений. Все эти сведения можно задать с помощью определяющего выражения функции. Определяющее выражение самостоятельно в программах не используется. Обычно его включают в состав функции, определяемой программистом.
Определяющее выражение задает тело такой функции. Формат определяющего выражения следующий:
(LAMBDA (X1 X2 ... Xn) e),
где X1,X2,...,Xn- аргументы определяемой функции,
е- выражение, с помощью которого вычисляется значение тела функции.
Определим функцию из предыдущего примера:
(LAMBDA (X) (COND ((ATOM X) NIL) (T T) )
Или иной пример функции двух переменных:
(LAMBDA (U V) (CONS (CAR U) (CDR V))).
Такая запись не имеет значения, так как определяющее выражение не вычисляется. Определяемое выражение может быть вычислено, если оно используется в качестве имени функции.
( (LAMBDA (X1 ... Xn) e) A1 ... An),
где А1,...,Аn - аргументы некоторой функции, имя которой заменено определяющим выражением.
Пример:
((LAMBDA(X)(COND((ATOM X)NIL)(T T)))'(B C))->T
2.2.18 Определяемые функции
Все описанные выше функции были встроенные. Говорят, что эти функции обладают свойством SUBR и FSUBR. Функции, задавамые программистом, называются определяемыми и вводятся с помощью определяющих выражений.
Определяемые функции могут быть двух типов: FEXPR и EXPR. У функций EXPR аргументы всегда вычисляются, следовательно, вместо аргументов можно писать другую функцию. У функций FEXPR вычисление аргументов блокируется за счет неявного применения функции QUOTE.
Функция называется обычной, если она имеет фиксированное число аргументов и если действия, указанные в ее определении, выполняются над значениями аргументов (CAR,CDR,CONS,ATOM,EQ).
Если хотя бы одно из этих двух условий нарушается, то функция называется специальной (напр. QUOTE - не выполняет действий над аргументом).
В общем случае, функции класса FSUBR отличаются от обычных встроенных функций еще и тем, что число аргументов для них может быть произвольным (напр. COND).
Для связи имени функции, определяемой программистом, с определяющим выражением в Лиспе используются функции: DEFUN (DF,DFUN,PUTD).
Функция, связывающая имя функции с определяещим выражением имеет формат
(DEFUN fun
(LAMBDA (X1 ... Xn) e)),
где fun - имя функции;
(LAMBDA...)- определяющее выражение;
После такого описания можно обращаться к этой функции, используя ее имя.
Пример:
(DEFUN NATOM (LAMBDA (X)
(COND ((ATOM X) NIL) (T T) )
)
)
Обращение к функции:
(NATOM 'A)->NIL
DEFUN – определяет тип EXPT
LAMBDA - определяет тип FEXPR.
можно упростить запись определения функции NATOM, опуская выражение LAMBDA с его скобками:
(DEFUN NATOM
(COND ((ATOM X) NIL) (T T) )
)
В muLisp общей формат DEFUM можно определить следующим образом:
(DEFUN fun (арг)
задача 1
записи на языке
задача 2
)
Задачи, приведенные в определении, бывают простыми и условными. Простая задача в качестве 1-го элемента списка содержит атом. В условной задаче на 1-м месте стоит предикат и ее формат (р е). Если предикат р истинен, то вычисляется значение е и вычисленное значение является значением определяемой функции. Если р – ложь, то выполняется переход к следующей задаче.
Определим функцию, объединяющую два элемента в список:
(DEFUM LIST1 (U V)
(CONS U (CONS V NIL))
)
- простая задача (CONS – атом)
Обращение к функции:
(LIST1 ‘(A B) ‘(C D)) ((A B)(C D))
(список из двух подсписков)
(LIST1 (CAR '(P Q R))(CDR '(PP QQ RR)) ) (P (QQ RR))
Определение функции “не атом” на языке muLisp
(DEFUN NATOM
((NULL (ATOM X)) T)
)
можно записать еще короче, опустив в записи (р е) е и значением, будет значение р:
(DEFUN NATOM
(NULL (ATOM X))
)