Искусственный интеллект – IV курс – День 04, лекции № 7, № 8 22.09.2009.

Программное обеспечение работ по ИИ

Экспериментальный и эволюционный характер разработок систем ИИ, требования к программному обеспечению

Система Искусственного интеллекта (Интеллектуальная Система = ИС) – программно-аппаратный комплекс, способный к решению таких задач, решая которые человек использует свои интеллектуальные способности.

Создание ИС – процесс сложный, он предполагает моделирование интеллектуальной деятельности человека (а мы знаем, что она чрезвычайно сложна и слабо изучена)

→

приходится много экспериментировать, создавать все новые и новые варианты, версии

(иногда очень сильно отличающиеся друг от друга)

→

нужны языки высокого/сверхвысокого уровня для быстрого прототипирования

Особенности задач ИИ (с точки зрения программирования):

1. сложные и динамически меняющиеся структуры данных;

2. большие по объему хранилища данных (базы знаний) и средства эффективной работы с ними;

3. символьные (в основном) данные;

4. модели, отражающие состояние проблемной среды;

5. переборные алгоритмы;

6. алгоритмы поиска по образцу;

7. гибкие структуры управления.

Языки, реально используемые в работах по ИИ:

лиспоподобные языки высокого уровня - различные диалекты/версии Лиспа

языки логического программирования - Пролог

языки объектно-ориентированного программирования - SMALL-TALK

языки на основе фреймов - KRL

универсальные языки программирования - C/C++, Java, Паскаль

языки, ориентированные на доступ - LOOPS

(используют специальные процедуры - демоны,

которые активируются при получении СООБЩЕНИЙ)

экспертные системы-оболочки - EMYCIN

Другие средства программной поддержки

Редакторы баз знаний:

штатные текстовые редакторы

автоматические журналы

средства синтаксического контроля

средства контроля содержания

Средства отладки: трассировка, остановы, автоматизация тестирования

Язык ЛИСП

В языке Лисп все действия описываются в виде функций. С точки зрения синтаксиса, обращения к функциям, как и обрабатываемые ими данные, представ­ляют собой так называемые S-выражения. В простейшем случае S-выражением является атом (идентификатор или число), в более сложном – список, который представляет собой заключенную в круглые скобки последовательность элементов списка. Отметим, что обращение к функции всегда является списком. Лисповские списки имеют рекурсивную структуру, поскольку элементом списка может быть произвольное S-выражение – как атом, так и список. Примеры списков:

(( ) (a b 1 (c)) class)

(car (quote (( ) ( ))))

(AT ROBOT (a 6))

(1 2 # 4 5 6 7 8 3).

Пустой список () имеет в Лиспе и другое обозначение – nil, причем он одновременно относится и к атомам, и к спискам.

Некоторые S-выражения имеют значения, которые можно вычислять. Такие выражения называются формами. Простейшими формами являются числа, идентификаторы T и nil, а также переменные с уже определенными значениями; значением такой формы служит соответственно само число, сам идентификатор T и nil или текущее значение переменной.

Формой является также обращение к функции, т.е. список вида

(f a₁ a₂ . . . a_n) (n≥0)

где f - имя функции, а a_i - ее аргументы, которые для обычной функции должны быть формами. В Лиспе есть и специальные функции, у которых может быть произвольное число аргументов и аргументы которых либо не вычисляются, либо вычисляются особым образом.

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

Языка Лисп предоставляет большой набор встроенных (стандартных) функций, на основе которых составляется пользовательская программа. Ниже кратко описаны некоторые из встроенных функций – те, что были использованы в предыдущих разделах пособия. Все эти функции входят в наиболее известные версии Лиспа - Common Lisp и MuLisp.

Отметим, что комментарием в Лиспе считается любой текст между двумя точками с запятой (;)

Определение новых функций

Для этого служит встроенная функция defun, к которой можно обратиться так:

(defun f (lambda (v₁ v₂ . . . v_n) e)) (n≥0).

Сокращенный вариант обращения – (defun f (v₁ v₂ . . . v_n) e).

Значением этой функциональной формы является имя определяемой функции, т.е. f. Побочным же эффектом вычисления этой формы будет опре­деление новой лисповской функции с именем f, аргументами (формальными параметрами) v_i и телом e - формой, зависящей от v_i.

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

При последующем обращении в программе к новой функции (f a₁ a₂ . . . a_n)

сначала вычисляются аргументы (фактические параметры) a_i, затем вводятся локальные переменные v_i, которым присваиваются значения соответствующих аргументов a_i, а далее вычисляется форма-тело e при этих значениях переменных v_i, после чего эти переменные уничтожаются. Вычисленное значение формы становится значением функции f .

Основные операции над списками

(car l)

Значением аргумента l должен быть непустой список, тогда значением функции является первый элемент (верхнего уровня) этого списка. Например: (car '(AT ROBOT (a 6)) ) → AT.

Примечание: символ ' имеет особое значение, он показывает, что следующее за ним S-выражение берется в том виде, в каком оно записано (значение его – как формы – не вычисляется) – см. ниже.

(cdr l)

Значением аргумента l должен быть непустой список, и значением функции является «хвост» этого списка, т.е. список, полученный отбрасыванием первого элемента. Например, (cdr '(AT ROBOT (a 6)) ) → (ROBOT (a 6)).

Кроме этих двух функций, называемых селекторами элементов списка, часто используются функции, эквивалентные определенной их суперпозиции. Имена всех таких функций начинаются на букву c, а заканчиваются на букву r, между ними же может стоять произвольная комбинация из не более чем пяти букв a и d, причем буква a означает наличие в суперпозиции функции car, а буква d – функции cdr . Сама же последовательность букв соответствует порядку следования функций car и cdr в эквивалентной суперпозиции.

Например, (caddr l) (car (cdr (cdr l))) .

Предполагается, что список-аргумент l всех этих функций, так же как и ниже описываемой функции nth, содержит необходимое число элементов (в противном случае вычисление программы прерывается сообщением об ошибке).

(nth n l)

Значением аргумента n должно быть положительное целое число (обозначим его N), а значением аргумента l – список. Значением функции является N-й от начала элемент этого списка. Например,

(nth 2 '(AT ROBOT (a 6)) ) → ROBOT.

(last l)

Функция выбирает последний (от начала) элемент списка, являющегося значением ее аргумента. Например, (last '(AT ROBOT (a 6)) ) → (a 6).

(cons e l)

В отличие от предыдущих функций эта функция является конструктором, т.е. строит новый список, который и выдает в качестве своего результата. Первым элементом этого списка будет значение аргумента e, а хвостом списка – значение аргумента l. Например, (cons '(A B C) '(D E F) ) →

((A B C) D E F).

(append l₁ l₂)

Эта функция осуществляет конкатенацию двух списков, являющихся значением ее аргументов. Например, (append '(A B C) '(D E F) ) → (A B C D E F).

(list e₁ e₂ . . . e_n) (n≥1)

Эта функция имеет произвольное количество аргументов, из значений которых она строит список (количество элементов на верхнем уровне результирующего списка равно количеству аргументов).

Например, если переменная X имеет своим значением список (p (q r)), а переменная Y – список (t), то

значение формы (cons X Y) равно ((p (q r)) t),

значение формы (append X Y) равно (p (q r) t),

значение формы (list X Y) равно ((p (q r)) (t)).

Арифметические функции

(length l)

Значением аргумента l должен быть список, функция вычисляет количество элементов (верхнего уровня) этого списка. К примеру, значение (length X) равно 2, если переменная X имеет значение (p(q r)).

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

(add1 n)

Функция прибавляет число 1 к числу-аргументу и выдает результат в качестве своего значения.

(sub1 n)

Эта функция вычитает 1 из значения своего аргумента и выдает результат в качестве своего значения.

(+ n₁ n₂)

Значением функции является сумма значений ее аргументов.

(- n₁ n₂)

Значением этой функции является разность значений ее аргументов.

(mod n₁ n₂)

Функция выполняет деление нацело значение первого аргумента на значение второго, и результат выдает в качестве своего значения.

(rem n₁ n₂)

Результат вычисления этой функции – остаток от деления первого числа на второе.

Предикаты

Предикатом обычно называется форма, значение которой рассматривается как логическое значение «истина» или «ложь». Особенностью языка Лисп является то, что «ложью» считается пустой список, записываемый как () или nil, а «истиной» – любое другое выражение (часто атом T).

(null e)

Эта функция проверяет, является ли значение ее аргумента пустым списком: если да, то значение функции равно T, иначе – ().

(eq e₁ e₂)

Функция сравнивает значения своих аргументов, которые должны быть атомами-идентификаторами. В случае их совпадения (идентичности) значение функции равно T, иначе – ().

(eql e₁ e₂)

В отличие от предыдущей функции, данная функция сравнивает значения своих аргументов, которыми могут быть не только атомы-идентификаторы, но и атомы-числа. Если они равны, то значение функции равно T, иначе – ( ). Отметим, что во многих версиях Лиспа для сравнения любых атомов используется функция eq.

(neq e₁ e₂)

Аналог предыдущей функции, но значения аргументов сравниваются на «не равно».

(equal e₁ e₂)

Функция производит сравнение двух произвольных S-выражений – значений своих аргументов. Если они равны (имеют одинаковую структуру и состоят из одинаковых атомов), то значение функции равно T, иначе – ().

(member a l)

Значением первого аргумента должен быть атом, а второго – список. Функция производит поиск заданного атома на верхнем его уровне заданного списка. В случае успеха поиска значение функции равно T, иначе – ( ).

(gt n₁ n₂) или (> n₁ n₂)

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

(lt n₁ n₂) или (< n₁ n₂)

Аналог предыдущей функции, но числа сравниваются на «меньше».

Логические функции

Так называются три функции, реализующие основные логические операции.

(not e)

Эта функция, реализующая «отрицание», является дубликатом функции null: если значение аргумента равно ( ) («ложь»), то функция выдает результат T («истина»), а при любом другом значении аргумента выдает результат ( ).

(and e₁ e₂ … e_k) (k≥1)

Это «конъюнкция». Функция по очереди вычисляет свои аргументы. Если значение очередного из них равно ( ) («ложь»), то функция, не вычисляя оставшиеся аргументы, заканчивает свою работу со значением ( ), а иначе переходит к вычислению следующего аргумента. Если функция дошла до вычисления последнего аргумента, то с его значением она и заканчивает свою работу.

(or e₁ e₂ … e_k) (k≥1)

Это «дизъюнкция». Функция по очереди вычисляет свои аргументы. Если значение очередного из них не равно ( ) («ложь»), то функция, не вычисляя оставшиеся аргументы, заканчивает свою работу со значением этого аргумента, в противном случае она переходит к вычислению следующего аргумента. Если функция дошла до вычисления последнего аргумента, то с его значением она и заканчивает свою работу.

К числу логических функций можно отнести и лисповское условное выражение:

(cond (p₁ e_1,1 e_1,2 … e_1,k1) … (p_n e_n,1 e_n,2 … e_n,kn)) (n≥1, k_i≥1)