- •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.8 Удаление элемента из списка
Функция содержит два аргумента X и U, и удаляет X из U.
(DEFUN DELETE (X U)
(COND ((NULL U) NIL)
((EQUAL X (CAR U)) (CDR U))
(T (CONS (CAR U) (DELETE X (CDR U))))
)
)
С помощью EQUAL проверяют, совпадает ли X с первым элементом списка U, если да, то для исключения X из U применяется функция CDR, иначе результирующий список получают путем добавления первого элемента списка U в начало списка, который соответствует остатку списка U с исключенным элементом X.
Определим функцию, удаляющую все элементы, входящие в список V из списка U, используя функцию DELETE.
(DEFUN DELETELIST (U V)
(COND ((NULL V) U)
(T (DELETE (CAR V) (DELETELIST (CDR V) U)))
)
)
Если V не (), то удаляем первый элемент списка V из списка U, из которого уже удален остаток списка V.
2.9 Функция, вычисляющая список общих элементов двух списков
(DEFUN INTERSECTION (U,V)
(COND ((NULL U) NIL)
((MEMBER (CAR U) V)
(CONS (CAR U)(INTERSECTION (CDR U) V)))
(T (INTERSECTION (CDR U) V))
))
Первая проверка U – пустой? Если да, то общих элементов между U и V нет. Поэтому результирующий список тоже будет пустым.
Второе условие: проверка вхождения 1-го элемента из U в список V. Если условие выполняется, то 1-й элемент U добовляется к списку общих элементов, списков V и (CDR U).
Рекурсивное обращение к функции INTERSECTION; аргументы функции: усеченный список U(“хвост списка”) и список V.
В ЛИСПе имеется встроенная функция INTERSECTION.
2.10 Функция, объединяющая два списка и не включающая повторяющиеся элементы
Отличается от APPEND тем, что в результирующий список не добавляется повторно элемент, встречающийся в обоих списках.
(DEFUN UNION (U,V)
(COND ((NULL U) V)
((MEMBER (CAR U) V)
(UNION (CDR U) V))
(T (CONS (CAR U)(UNION (CDR U) V)))
))
Функция UNION проверяет, является ли U пустым списком. Если U- пустой список, то результат V. Иначе, если первый элемент списка U входит в список V, то результат есть объединение хвоста списка U со списком V. Иначе, первый элемент добавляем в начало объединенного списка, который является результатом объединения списка U без первого элемента списка V.
2.11 Ассоциативные списки
Ассоциативным списком или списком соответствия называют список, состоящий из точечных пар ((X1 . Y1),...,(Xn . Yn)).
<ассоциативный список>::=
NIL|<точечная пара>.<ассоциативный список>
В таком списке каждому Yi соответствует Xi. Основное назначение ассоциативных списков - хранение промежуточной информации. Такие списки широко применяются, как основные структуры данных в программах и могут интерпритироваться как атрибут и его данные.
Имеются специальные функции для работы с такими списками:
1. (PAIR arg1 arg2)- позволяет образовывать из двух списков один ассоциативный. Если длина одного списка больше длины другого, то функция неопределена.
(PAIR '(A B C) '(1 2 3))->((A . 1)(B . 2)(C . 3))
2.Выбор элементов из ассоциативных списков
(ASSOC <арг.поиска> <асс.список>)
Проверяет, содержится ли в ассоциативном списке <асс.список> точечная пара, первый элемент которой есть <арг.поиска>, и если содержится, то функция возвращает s-выражение , в которое входит точечная пара. Если не содержится- NIL.
(ASSOC 'B '((H . K)(B . F)) -> (B . F)
ASSOC выполняет ассоциативный поиск.
3.(SUBLIST <асс.список> <список>)- производит замены, заданные в виде ассоциативного списка в списке, который является вторым аргументом функции.
(SUBLIST '((A . f)(B . P)(C . Q R X) '(A B (E A) C)->
(F P (E F) (Q R X))
Определим такую функцию:
(DEFUN SUBLIST (A W)
(COND ((NULL A) W)
(COND ((ASSOC W A) (CDR (ASSOC W A))) ((ATOM W) W))
(T (CONS (SUBLIST A (CAR W)) (SUBLIST A (CDR W)))
))
Здесь А - ассоциативный список, W - произвольное выражение, т.е. функция в заданном выражении W заменяет все входящие в него атомы элементами из ассоциативного списка А, которым имеется соответствие.