Реферат: Логическое и функциональное программирование
ЛОГИЧЕСКОЕ И ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ
Введение
Целью логического и функционального программирования является вывод решений и они тесно связаны с задачами, решаемыми в искусственном интеллекте и экспертных системах (ЭС). На начальном этапе развития систем искусственного интеллекта (СИИ) и ЭС даже выделился целый класс специализированных языков программирования: языки логического и функционального программирования.
 |
Процедурная программа состоит из последовательности операторов и предложений, управляющих последовательностью их выполнения. В основе такого программирования лежат взятие значения какой-то переменной, совершение над ним действия и сохранение нового значения с помощью оператора присваивания, и так до тех пор пока не будет получено желаемое окончательное значение.
Функциональная программа состоит из совокупности определений функций. Функции, в свою очередь, представляют собой вызовы других функций и предложений, управляющих последовательностью вызовов. Каждый вызов возвращает некоторое значение и вызвавшую ее функцию, вычисление которой после этого продолжается. Этот процесс повторяется до тех пор, пока запустившая процесс функция не вернет результат пользователю.
В логических языках программирования для решения задачи достаточно описания структуры и условий этой задачи. Поскольку последовательность и способ выполнения программы не фиксируется, как при описании алгоритма, программы могут в принципе работать в обоих направлениях, то есть программа может как на основе исходных данных вычислить результаты, так и по результатам – исходные данные.
Наиболее известными языками функционального программирования являются ЛИСП и РЕФАЛ, а логического – Пролог. Однако, с развитием языков программирования (в частности, с появлением объектно-ориентированных языков) и баз данных область их применения сузилась. Так ЛИСП используется как оболочка Автокад, а РЕФАЛ как средство для построения метаязыков и метакомпиляторов.
Поэтому в дальнейшем внимание будет уделено не рассмотрению конкретных языков функционального и логического программирования, а подходам, лежащим в основе их реализации и являющимися базовыми при создании систем принятия решений.
ЛИСП и Пролог в свое время являлись базовыми для создания экспертных систем. Поэтому, для того чтобы наглядно представить какой круг задач решается с помощью логического и функционального программирования, рассмотрим задачи, возникающие в ЭС. Прежде всего, это задачи прямого и обратного вывода.
Прямой и обратный вывод
При использовании прямой цепочки рассуждений решается задача по известным условиям найти последствия. Обратная цепочка рассуждений применяется для того, чтобы по известным результатам найти причины их вызвавшие.
Такие задачи часто записывают в терминах продукционных систем представления знаний, в которых знания записываются в виде продукций/правил, имеющих вид:
Если <условие>, То <вывод>.
 |
Рассмотрим сначала построение обратной цепочки рассуждений. Обратная цепочка рассуждений всегда начинается со следствия (часть То правила). Если в правилах, относящихся к проблемной области, не удается найти условную часть с выполняющимися условиями, необходимо ввести дополнительную информацию. Цепочка означает процедуру логической связи ряда правил.
Для представления таких задач принято использовать дерево решений - специальную диаграмму для представления возможных решений. Дерево решений состоит из вершин двух типов. Вершины решений, содержащие вопросы, обозначаются окружностями. Цели или логические выводы обозначаются прямоугольниками. Вершины нумеруются. Каждая вершина может иметь не более одного входа. Рассмотрим простейший пример с приемом на работу, часто используемый в литературе [1].
Дерево решений будем хранить в следующей таблице [2]:
Таблица дерева решений.
| № вершины | Переменная | Значение | Исходная вершина | Дуга | Тип вершины |
| 1 | Звание | - | - | - | решение |
| 2 | Должность | Отказ | 1 | нет | вывод |
| 3 | Возможность | да | 1 | да | вывод |
| 4 | Открытия | - | 1 | да | решение |
| 5 | Средний балл | - | 3 | да | решение |
| 6 | Должность | Научный сотрудник | 4 | да | вывод |
| 7 | стаж | - | 5 | < 3.5 | решение |
| 8 | должность | конструктор | 5 | > 3.5 | вывод |
| 9 | должность | Отказ | 7 | < 2 | вывод |
| 10 | должность | администратор | 7 | > 2 | вывод |
Для сохранения результатов будем использовать таблицу вывода (в начальный момент таблица пуста).
Таблица вывода
| № варианта | Переменная | Значение |
Алгоритм
1. Определить переменную логического вывода и ее значение.
2. Найти первое вхождение этой переменной в таблицу дерева решений с заданным значением и типом вершины «вывод». Если переменная не найдена – неудача. Установить переменную var = 1.
3. Выбрать исходную по отношению к полученной вершине вершину. Если ее нат, перейти к шагу 5. Если есть, записать в таблицу вывода новую строку со значениями полей № варианта = var , Переменная = Переменная из исходной вершины таблицы дерева решений, Значение = Дуга текущей вершины.
4. Сделать исходную вершину текущей. Перейти к шагу 3.
5. Найти следующее вхождение переменной вывода в таблицу дерева решений. Если нет, конец, иначе var = var + 1. Перейти к шагу 3.
Пусть отказано в приеме на работу. Тогда в ходе выполнения алгоритма таблица вывода будет формироваться следующим образом.
Здесь пропущена таблица вывода на предпоследнем этапе.
Механизм, основанный на прямой цепочке рассуждений, функционирует следующим образом:
1. Вводится условие.
2. Для каждой ситуации система ищет в базе данных (знаний) правила, в условной части которых содержится соответствующее условие.
3. В соответствии с констатирующей частью (частью ТО) каждое правило может генерировать новые ситуации, которые добавляются к уже существующим.
--> ЧИТАТЬ ПОЛНОСТЬЮ <--