PDF-лекции, страница 5

Описание файла

PDF-файл из архива "PDF-лекции", который расположен в категории "лекции и семинары". Всё это находится в предмете "искусственный интеллект" из седьмого семестра, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст 5 страницы из PDF

Еслиони равны (имеют одинаковую структуру и состоят из одинаковых атомов), то значение функции равноT, иначе – ().(member a l)Значением первого аргумента должен быть атом, а второго – список. Функция производит поискзаданного атома на верхнем его уровне заданного списка. В случае успеха поиска значение функцииравно T, иначе – ( ).(gt n1 n2) или (> n1 n2)Значениями аргументов этой функции должны быть числа. Если первое из них больше второго, тозначение функции равно T, иначе – ().(lt n1 n2) или (< n1 n2)Аналог предыдущей функции, но числа сравниваются на «меньше».Логические функцииТак называются три функции, реализующие основные логические операции.(not e)Эта функция, реализующая «отрицание», является дубликатом функции null: если значение аргументаравно ( ) («ложь»), то функция выдает результат T («истина»), а при любом другом значении аргументавыдает результат ( ).(and e1 e2 … ek)(k≥1)Это «конъюнкция».

Функция по очереди вычисляет свои аргументы. Если значение очередного из нихравно ( ) («ложь»), то функция, не вычисляя оставшиеся аргументы, заканчивает свою работу созначением ( ), а иначе переходит к вычислению следующего аргумента. Если функция дошла довычисления последнего аргумента, то с его значением она и заканчивает свою работу.(or e1 e2 … ek)(k≥1)Это «дизъюнкция». Функция по очереди вычисляет свои аргументы. Если значение очередного из нихне равно ( ) («ложь»), то функция, не вычисляя оставшиеся аргументы, заканчивает свою работу созначением этого аргумента, в противном случае она переходит к вычислению следующего аргумента.Если функция дошла до вычисления последнего аргумента, то с его значением она и заканчивает своюработу.К числу логических функций можно отнести и лисповское условное выражение:(cond (p1 e1,1 e1,2 … e1,k1) … (pn en,1 en,2 … en,kn))(n≥1, ki≥1)Функция cond последовательно вычисляет первые элементы своих аргументов – обращения кпредикатам pi. Если все они имеют значение ( ) («ложь»), тогда функция заканчивает свою работу созначением ( ).

Но если был обнаружен предикат pi, значение которого отлично от ( ), т.е. он имеетзначение «истина», тогда функция cond уже не будет рассматривать остальные предикаты, апоследовательно вычислит формы ei,j из этого i-го аргумента и со значением последнего из них закончитсвою работу. Заметим, что поскольку значения предыдущих форм из этого аргумента нигде незапоминаются, то в качестве этих форм имеет смысл использовать только такие, которые имеютпобочный эффект, например, функции присваивания значений переменным или печати.Специальные функции(quote e) или 'eЭто функция блокировки вычислений: она выдает в качестве значения свой аргумент, не вычисляя его.Например, значением формы '(car (2)) является само выражение (car (2)).(gensym)15Это функция генерации уникальных атомов (символов): при каждом обращении к ней выдается новыйатом-идентификатор.

Этот идентификатор получается склеиванием специального префикса иочередного номера (целого числа). Префикс и целое число, от которого начинается нумерациягенерируемых атомов, могут быть установлены заранее, как, например, в языке MuLisp:(setq *gensym-prefix* 'S) (setq *gensym-count* 2)После этого при последовательных обращениях к функции gensym она будет выдавать атомы S2, S3, S4и т.д.Блочная и связанные с ней функции(prog (v1 v2 … vn) e1 e2 … ek) (n≥0, k≥1)Эту специальную функцию называют «блочной», поскольку ее вычисление напоминает выполнениеблоков в других языках программирования. Вычисление функции начинается с того, что вводятсялокальные переменные vi, перечисленные в ее первом аргументе, и всем им в качестве начальногозначения присваивается пустой список nil.

После этого функция последовательно вычисляетостальные свои аргументы – формы ei. Вычислив последнюю из них, функция prog заканчивает работусо значением этой формы, уничтожив перед этим все свои локальные переменные vi .Вычисленные значения всех форм ei, кроме последней, нигде не запоминаются, поэтому имеетсмысл использовать в качестве них только функции с побочным эффектом. Некоторые из этих функцийперечислены ниже.В качестве одной из форм ei может быть записан атом-идентификатор, в этом случае он невычисляется, а трактуется как метка, на которую будет производиться переход внутри этого блока(функцией go).(return e)Это функция досрочного выхода из блока.

Она может использоваться только внутри блочной функцииprog, поскольку завершает вычисление ближайшей объемлющей блочной функции, устанавливая еезначение равным значению аргумента e.(go e)Функция реализует переход по метке. Аргумент ее не вычисляется, в качестве ее аргумента должен бытьзадан идентификатор – одна из меток ближайшей объемлющей блочной функции. Функция goполностью завершает вычисление той формы этой блочной функции, в которую она входит (на любомуровне), и осуществляет переход на вычисление формы, непосредственно следующей за указаннойметкой.(setq v e)Это аналог оператора присваивания.

В качестве аргумента v (он не вычисляется) должно быть заданоимя переменной, существующей в данный момент. Функция присваивает этой переменной новоезначение – вычисленное значение формы e. Это же значение является значением и самой функции setq,однако оно, как правило, не используется.Следующие две особые функции используются для упрощения записи часто используемыхконструкций (setq V (cdr V)) и (setq V (cons (e V)).(pop v)Аргументом этой функции (он не вычисляется) должно быть имя переменной, существующей в данныймомент и имеющей своим значением непустой список. Хвост этого непустого списка присваивается вкачестве нового значения указанной переменной, а также выступает в качестве значения самой функцииpop.(push е v)В качестве второго аргумента этой функции (он не вычисляется) должно быть задано имя переменной, вкачестве первого – произвольная форма.

Функция вычисляет эту форму и строит новый список, первыйэлемент которого – вычисленное значение, а хвост – список, являющийся значением переменной v.Результирующий список становится новым значением переменной v и значением самой функции push.Например, если переменная X имеет значение (d (e) g), а переменная U – значение (1 2), тозначение формы (pop X) равно ((e) g), а значение (push U X) равно ((1 2) d (e) g).Основным средством реализации циклических программ в Лиспе является рекурсия.Рассмотрим примеры простейших рекурсивных программ на Лиспе:(listp l) – функция-предикат, проверяющая является ли значение ее аргумента списком (на верхнемуровне). Если да, то значение функции равно T, иначе – ().(defun listp (lambda (x)(cond ((null x) T)16((atom x) ( ))( T (listp (cdr x))) )))(memb a l) - функция ищет атом, являющийся значением первого ее аргумента, в списке (на верхнем егоуровне), являющемся значением второго аргумента.

В случае успеха поиска значение функции равно T,иначе – ().(defun memb (lambda (a l)(cond ((null l) nil)((eq a (car l)) T)(T (memb a (cdr l)) ) ))(out a l) - функция удаляет из списка, являющегося значением ее второго аргумента, все вхождения (наверхнем) атома, являющегося значением первого аргумента.(defun out (lambda (a l)(cond ((null l) nil)((eq a (car l)) (out a (cdr l)))(T (cons (car l) (out a (cdr l))))) ))(equal e1 e2) – функция, сравнивающая два произвольных S-выражения – значения своих аргументов.Если они равны (имеют одинаковую структуру и состоят из одинаковых атомов), то значение функцииравно T, иначе – ().(defun equal (lambda (x y)(cond ((atom x) (eq x y))((atom y) ( ))((equal (car x) (car y)) (equal (cdr x) (cdr y)))( T ( ) ) )))День 5.

Язык ПЛЭНЕРПлэнер – один из потомков языка Лисп, созданный специально для реализации систем ИИ. Основныеобъекты языка (как и в Лиспе) – списки и атомы. Плэнер – очень громоздкий и сложный (для реализациии изучения) язык не нашедший, к сожалению, более или менее широкого практического применения.Вспомним «Особенности задач ИИ (с точки зрения программирования)»:8. сложные и динамически меняющиеся структуры данных;9. большие по объему хранилища данных (базы знаний) и средства эффективной работы с ними;10. символьные (в основном) данные;11.

модели, отражающие состояние проблемной среды;12. переборные алгоритмы;13. алгоритмы поиска по образцу;14. гибкие структуры управления.Основные составляющие языка Плэнер:-средства для работы со списками (лисповская часть, используется для работы со списками)плэнерская база данных (используется для моделирования ситуаций проблемной среды)встроенный режим возвратов (реализует один из основных методов перебора – бэктрекинг)аппарат работы с образцами (используется для анализа структуры списков)аппарат теорем (используется при планировании решения)позволяют достаточно эффективно (и быстро) реализовать соответствующие возможности.Три типа процедур языка Плэнер:- функции;- сопоставители (для работы с образцами);- теоремы (процедуры, вызываемые по образцу).17Примеры конструкций и процедур Плэнера:Обращение к функции:[ELEM -2 (A B C D)] → CВыдать второй (2), считая с конца списка (знак "минус" при 2), элемент списка (A B C D).Сопоставление образца с выражением:[IS (*X ПРИШЕЛ !*Y) (САША ПРИШЕЛ ИЗ МАГАЗИНА)] → TСопоставление успешно, то есть образец (*X ПРИШЕЛ !*Y) соответствует выражению (САШАПРИШЕЛ ИЗ МАГАЗИНА).

Побочный эффект: переменная X получает значение САША, а переменнаяY получает значение (ИЗ МАГАЗИНА)Утверждение плэнерской базы данных:(BOX A (3 7)) - ящик с названием А находится на плоском квадратном поле с пронумерованнымиклетками в третьей строке (по горизонтали) и в седьмом столбце (по вертикали).Запись утверждения в плэнерскую базу данных:[ASSERT (BOX A) (WITH COL RED)] – в базу данных записывается утверждение (BOX A), то есть"А является ящиком"; записывается также, что "цвет" (COL) этого ящика "красный" (RED).Поиск утверждения в плэнерской базе данных:[SEARCH (BOX [ ]) (TEST COL [NON GREEN])] – в базе данных ищется утверждение о некоторомящике, цвет которого не (NON) зеленый (GREEN); возможный ответ (результат поиска) – (BOX A).Определение плэнерской теоремы:[DEFINE ОСВОБОДИЛИ (ERASING (X)(=ЗАНЯТ= *X)[ASSERT (=СВОБОДЕН= .X)])]Если из базы данных вычеркивается утверждение о том, что "поверхность некоторого кубика X занята"(если так, то на него нельзя поставить другой кубик), то автоматически будет вызвана и выполнена этатеорема.

Свежие статьи
Популярно сейчас