Некоммерческое  акционерное общество

Кафедра Компьютерных Технологий

АЛМАТИНСКИЙ УНИВЕРСИТЕТ  ЭНЕРГЕТИКИ И СВЯЗИ

 

СИСТЕМЫ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА

 Методические указания к выполнению лабораторных работ

для студентов - бакалавров специальности

5В070400 - «Вычислительная техника и программное обеспечение»

 

 

Алматы 2013 

СОСТАВИТЕЛИ: Ахметова М. Системы Искусственного Интеллекта. Методические указания к выполнению лабораторных работ для студентов - бакалавров специальности 5В070400 - «Вычислительная техника и программное обеспечение»,  - Алматы: АУЭС, 2013 -  32 с.

    Методические указания содержат материал по выполнению лабораторных работ с примерами. Методические указания рекомендуются для студентов-бакалавров специальности 5В070400 - «Вычислительная техника и программное обеспечение».

Ил. 5, табл 1., библиогр. -  20 назв. 

 

Рецензент:  доцент Куликов А.А.

 

Печатается по плану издания некоммерческого акционерного общества «Алматинский университет энергетики и связи» на 2012 г.

 

© НАО «Алматинский университет энергетики и связи», 2013 г. 

 

Содержание 

Введение

3

Лабораторная работа №1. Разработка игровых задач на ПРОЛОГе, ЛИСПе.

4

Лабораторная работа №2 Разработка интеллектуальной компоненты с использованием подхода в пространстве состояний.

14

Лабораторная работа №3 Разработка интеллектуальной компоненты с использованием методов редукций

18

Лабораторная работа №4 Разработка интеллектуальной компоненты с использованием теорий исчисление предикатов.

21

Лабораторная работа №5 Проектирование продукционной модели ЭС, и разработка ее компонентов.

24

Лабораторная работа №6 Проектирование фреймовой ЭС, и разработка ее компонентов.

28

Список литературы

31

 

Введение 

Дисциплина «Системы искусственного интеллекта»  является базой для овладения студентами  основных методов  поиска решения, т.е. стратегии вывода с участием интеллекта. В дисциплине рассматривается классификация задач искусственного интеллекта, основные методы поиска в пространстве состояний и в пространстве разбиение задач, методы с использованием исчисление предикатов.

Одним из важных вопросов, возникающих при проектировании интеллектуальных систем, основанных на знаниях, является выбор метода поиска решения, т.е. стратегии вывода. Поэтому при выполнений лабораторных работ студент должен продемонстрировать: понимание содержательной постановки задачи лабораторной работы, навыки работы с используемым инструментарием. Прежде чем рассмотреть различные методы поиска сама задача должна быть поставлена  в рамках следующих подходов: подход, основанный на пространство состояний; подход, основанный на сведении задач на редукциях к подзадаче; подход как теорема, подлежащая доказательству. В методических указаниях приводятся методы поиска и навыки программирования  на ПРОЛОГ-е и ЛИСП-е.

Экспертные системы (ЭС) - это компьютерные программы, заменяющие человека-эксперта в определенной предметной области. Главные требования для проектирования ЭС - наличие эксперта-человека. Состав ЭС предполагает выполнение системой следующие функции. Система ведет переговоры как человек, выдает рекомендацию как человек, объясняет полученное решение как человек, наполняет знания новыми и изменяет свои старые знания как человек. Знать модели представления знаний для проектирования ЭС, иметь навыки создания компонентов ЭС и научиться ориентироваться в области проектирования ЭС является одним из важных задач, поставленных перед специалистами информационных технологий. В методических указаниях приводятся модели представления знаний и примеры создания базы знаний по таким моделям. 

Языки Искусственного Интеллекта (ИИ) основаны на языках функционального и логического программирования с ориентацией на декларативный стиль программирования, на базе языков ЛИСП и ПРОЛОГ. По завершении выполнения лабораторных работ студент должен приобрести умения: знать принципы хорошего стиля написания программ на языках функционального и логического программирования; читать и объяснять значения программных объектов на ЛИСП-е и ПРОЛОГ-е; иметь навыки применения и эффективного использования механизма рекурсии при разработке ЛИСП и ПРОЛОГ -  программах; создавать, использовать и изменять программы, манипулирующие структурами данных при применении различных методов решения задач ИИ.

Функциональное и логическое программирование. Языки Искусственного Интеллекта (ИИ) основаны на языках функционального и логического программирования с ориентацией на декларативный стиль программирования, на базе языков ЛИСП и ПРОЛОГ.

 

Лабораторная работа №1  Разработка задач на ПРОЛОГ-е, ЛИСПе

 

Цель работы: освоить основные возможности и базовые понятия языка ПРОЛОГ  и ЛИСП, изучить основные принципы построения программ на языке функционального и логического программирования.

Любая программа, написанная на Турбо-ПРОЛОГе, состоит из пяти разделов. Ключевые слова: domains, database, predicates, goal, clauses -  отмечают начала соответствующих разделов. Большинство программ не содержит всех пяти названных разделов. Турбо-ПРОЛОГ обеспечивает возможность включения в любом месте программы комментарий любой длины, которые обрамляются символами /* и */ [1,2].

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

Выполнение программы начинается, когда система встретит оператора цели. Цель – это формулировка задачи, которую данная программа должна решить. Турбо-ПРОЛОГ использует как внутренние цели, которые содержатся в программе, так и внешние цели, которые вводятся с клавиатуры после запуска программы. В этом случае Турбо-ПРОЛОГ выдает приглашение Goal (Цель). Турбо-ПРОЛОГ пытается сопоставить цель с фактами и правилами программы. Принцип сопоставления, который необходимо твердо усвоить, – сверху вниз и слева направо. База данных (БД)) на ПРОЛОГе. Статические базы данных являются частью кода программы и не могут изменяться во время работы. Динамические базы данных можно дополнять новыми фактами или удалять из них некоторые утверждения. Другая особенность динамической базы состоит в том, что она может храниться в отдельном файле, записана на диск или считана с диска в оперативную память. Для описания  предикатов динамической базы предназначен раздел программы: database. Например dstudent(string, symbol, integer).

В Турбо-ПРОЛОГе имеется набор встроенных предикатов для изменения фактов динамической базы: asserta (X) добавляет факт в начало базы данных; assertz(X) добавляет факт в конец базы данных; retract(X) удаляет из базы данных факт, сопоставимый с заданным фактом; consult(имя файла) открывает файл для добавления фактов в базу данных, размещенную в оперативной памяти [3-5].

Контрольные примеры на ПРОЛОГе. Все примеры были взяты из [6].

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

DOMAINS

   territory=ter(real, integer).

   population=pop(real, integer).

   info=c(string, territory, population, string).

PREDICATES

   country(info).

   show.

   search(string).

   search(integer, integer).

CLAUSES

   country(c("Australia", ter(7686.8, 6), pop(21585.1, 52), "Kanberra")).

   country(c("France", ter(674.8, 47), pop(64473.1, 20), "Paris")).

   country(c("India", ter(3287.6, 7), pop(1131191, 2), "New Delhi")).

   country(c("Hungary", ter(93.0, 109), pop(9930.9, 79), "Budapest")).

   country(c("Canadian", ter(9984.7, 2), pop(33091.2, 37), "Ottawa")).

   country(c("China", ter(9570, 3), pop(1322178.2, 1), "Pekin")).

   country(c("Russia", ter(17075.4, 1), pop(141887.5, 9), "Moskow")).

   country(c("USA", ter(9518.9, 4), pop(304000.0, 3), "Washington")).

   country(c("BreatBritain", ter(244.8, 76), pop(60776.2, 21), "London")).

   country(c("Greece", ter(131.9, 94), pop(10964.0, 70), "Athenes")).

   country(c("Kazakhstan", ter(2724.9, 9), pop(15658.3, 61), "Astana")).

   country(c("Madagascar", ter(587.0, 45), pop(19448.8, 55), "Antananarivo")).

   country(c("Maldives", ter(0.3, 186), pop(298.9, 166), "Male")).

   country(c("Estonia", ter(45.0, 129), pop(1342.4, 151), "Tallinn")).

   country(c("Japan", ter(377.8, 60), pop(127433.5, 10), "Tokyo")).

   country(c("Czechia", ter(78.9, 114), pop(10403.1, 79), "Prague")).

     show:-write("*********************************************************\n"),

  write("* COUNTRY\t*  TERRITORY  \t*  POPULATION  \t* CAPITAL *"),         nl,         write("*        \t* km    place \t* people  place\t*  \t*\n"),

         write("*******************************************************\n"), nl,

         country(c(X, ter(At, Bt), pop(Ap, Bp), Y)),

         writef("%s\t\t%-1\t%u\t%-1\t%u\t%s\n", X, At, Bt, Ap, Bp, Y),

               fail.

      search(X):-

         country(c(Y, ter(_, _), pop(_, _), X)),

         writef("The %s is the capital of the %s.\n", X, Y), fail;

              country(c(X, ter(At, Bt), pop(Ap, Bp), Y)),

         writef("The capital of %s is %s.\nThe territory is %-1, zanimaet %u mesto v mire.\nThe population is %-1, zanimaet %u mesto v mire.\n", X, Y, At, Bt, Ap, Bp), fail.

      search(T, P):-

         country(c(X, ter(_, Bt), pop(_, Bp), _)),

         Bt<=T,  Bp<=P, 

         writef(" %s, ", X), fail.

Результаты. Вывод информации на экран. Вывод информации организуется с помощью команды show.

Поиск по одному атрибуту.   Поиск можно осуществить по названию страны и по городу. Например, найдем информацию о стране Китай (China) и о городе Москва (Moskow): Goal: search ("China")., и второй запрос Goal: search ("Moskow ").

 Найдем все страны, которые занимают выше 10-го места по территории и населению и страны, которые занимают выше 100-го места по территории и выше 50-го по населению: Goal: search (10,10)., и второй запрос Goal: search (100,50).

Пример 2. Рекурсия.  Написать рекурсивную программу вычисления суммы ряда чисел cos(n). Результат выведите в виде таблицы. Применить нехвостовую и хвостовую рекурсии. Выполнение осуществляется с помощью команды RUN.

Выполнение работы. Не хвостовая рекурсия:

PREDICATES

   sum(integer, real).

CLAUSES

   sum(0, 1):-!.

   sum(N, R):-

      Next_N=N-1,

      sum(Next_N, P),

      R=cos(N)+P,

      writef(" % \t %-4", N, R), nl.

GOAL

  write("        *** Lab 3. Recurse ***"), nl, nl,

  write("Enter quantity of elements of a number: "),

  readint(X), nl,

  write("Number       SumCos"), nl,

  sum(X, Res).

Хвостовая рекурсия:

PREDICATES

   sum(integer, real, real).

CLAUSES

   sum(0, _, _):-!.

   sum(N, R, P):-

      Next_N=N-1,

      R=cos(N)+P,

      sum(Next_N, R, R),

      writef(" % \t %-4", N, R), nl.

GOAL

  write("        *** Lab 3. Recurse ***"), nl, nl,

  write("Enter quantity of elements of a number: "),

  readint(X), nl,

  write("Number       SumCos"), nl,

  sum(X, Res, 0).

Пример 3. Обработка списков. Написать программу для вывода n-го элемента списка.

DOMAINS

   list=integer*.

PREDICATES

   nth_element(integer, list, integer)

CLAUSES

   nth_element(1, [A|_], A):- !.

   nth_element(N, [_|L], A):-

      N1=N-1,

      nth_element(N1, L, A).

GOAL

  write("        *** Primer 3 ***"), nl, nl,

  write("Enter number of element of the list: "),  /*введите номер элемента в списке */

  readint(N),

  nth_element(N, [0, 1, 2, 3, 4], A),

  writef("Element # % = %", N, A), nl.    /*% обозначает формат вывода */

Результаты. Выполнение осуществляется с помощью команды RUN.

Пример 4. Рекурсивные структуры данных. Проверить, является ли дерево упорядоченным, уточнить: по возрастанию или по убыванию.

DOMAINS

   tree=t(integer, tree, tree); empty()

PREDICATES

   print_tree(tree).

   order(tree)

   order_left(integer, tree)

   order_right(integer, tree)

CLAUSES

   print_tree(empty):- !.

   print_tree(t(R, Left, Right)):-

      write(R, '\t'),

      print_tree(Left),

      print_tree(Right).

   order(empty):- !.

   order(t(_, empty, empty)):- !.

   order(t(R, Left, Right)):-

      order_left(R, Left),

      order_right(R, Right),

      order(Left),

      order(Right),

      write("Tree order by vozrast\n");

      order_left(R, Right),

      order_right(R, Left),

      order(Left),

      order(Right),

      write("Tree order by ubivan\n").

   order_left(_, empty).

   order_left(T, t(L, _, _)):- T>=L.

   order_right(_,empty).

   order_right(T, t(R, _, _)):- T<=R.

GOAL     

   write("        *** primer4. Tree ***"), nl, nl,

   Tree1=t(6, t(3, t(2, empty, empty),

                  t(4, empty, empty)),

             t(7, t(3, empty, empty),

                  t(8, empty, empty))),

   Tree2=t(6, t(7, t(8, empty, empty),

                   t(5, empty, empty)),

              t(3, t(4, empty, empty),

                   t(2, empty, empty))),

   Tree3=t(5, t(2, t(8, empty, empty),

                   t(1, empty, empty)),

              t(4, t(3, empty, empty),

                   t(2, empty, empty))),                

   write("Tree: "),

   print_tree(Tree3), nl,

   order(Tree3),

   write("Tree order!\n"), !;

   write("Tree not order\n").

Пример 5. Базы данных. Создать базу данных из начальной базы с учетом приведенных условий. Начальная база содержит факты произвольного вида. Удалить все дублирующиеся факты с выводом соответствующих сообщений. Выполнить реализацию внешней базы данных, при этом результат поместить во внешний файл. При реализации внутренней базы данных результат выводится в окно выполнения ПРОЛОГа.

DOMAINS

   list=string*.

DATABASE

   country(string).

PREDICATES

   import.

   export.

   nondeterm del(string).

   add(list).

CLAUSES

   import:-

      consult("Lab1In.txt"),

      write("   Database import from file!"), nl.

   export:-

      save("Lab1Out.txt"),

      write("   Database export in file!"), nl.

   del(H):- retract(country(H)).

   add([H|T]):-

      country(H), !,

      write("Double fact is delete: ", H), nl,

      add(T).

   add([H|T]):-

      assertz(country(H)), !, add(T).

   add([]).  

GOAL

   import,

   findall(H, del(H), T),

   add(T),

   export.

 Результаты

Файл Lab1_Imp.txt:

Файл Lab1_Exp.txt:

country("Russia")

country("Russia")

country("USA")

country("USA")

country("France")

country("France")

country("Breat Britan")

country("Breat Britan")

country("Germany")

country("Germany")

country("USA")

 

country("France")

 

country("Germany")

 

 

Пример 6. Строки и файлы. Написать программу, которая бы искала введенное слово в тексте (текст в файле) по максимальному количеству совпадающих первых букв. Результат сохранить в новом файле.

DOMAINS

   Str=string.

   Ch=char.

   Word=string.

   file=f1; f2.

PREDICATES

   find(Word).

   search(string, string, integer).

CLAUSES

   find(Word):-

      openread(f1, "lab7in.txt"),

      openwrite(f2, "lab7out.txt"),

      writedevice(f2),

      file_str("lab7in.txt", Str),

      str_len(Word, Len),

      search(Str, Word, Len),

      closefile(f1),

      closefile(f2).

   search(Str, Word, Len):-

      searchstring(Str, Word, Pos),

      writef("The word [%s] find on % position", Word, Pos);

      Len2=Len-1,

      substring(Word,  0, Len2, Word2),

      search(Str, Word2, Len2).

GOAL

   write("      *** Lab 7. String & File ***"), nl, nl,

   write("Enter the word: "),

   readln(Word),

   find(Word).  

 

Программы на ЛИСПе. ЛИСП ориентирован на обработку нечисловых задач. Он основан на алгебре  списочных структур, лямбда-исчислении и теории рекурсий [7-9]. Язык имеет функциональную направленность, т. е. любое предложение заключенное в скобки, введенное вне редактора считается функцией и выполняется сразу после нажатия «ENTER». Чтобы предотвратить вычисление значения выражения, нужно перед этим выражением поставить апостроф «’». Апостроф перед выражением - это сокращение ЛИСПовской функции QUOTE. Определения функций могут храниться в файлах и  загружаться  используя  функцию  LOAD: (load <имя файла>). Эта функция загружает файл выражений и  выполняет  эти выражения. <Имя файла> - это строковая константа, которая представляет собой  имя  файла  без  расширения  (подразумевается  расширение "*.lsp"). Если  операция  успешно завершена, LOAD возвращает имя последней функции, определенной в файле. Если операция не выполнена, LOAD возвращает имя файла в виде строкового выражения. Функция LOAD не может вызываться  из  другой  функции  ЛИСП.  Она должна  вызываться  непосредственно с клавиатуры, в то время как  ни  одна  другая  функция ЛИСП не находится в процессе выполнения. Интерпретатор считает файлами, содержащими исходные тексты программ на ЛИСПе, все файлы, имеющие расширение LSP. Запуск системы XLisp  осуществляется командой: Xlisp-PLUS  После нескольких секунд загрузки на экране дисплея появится сообщение: XLISP-PLUS Version 2.1h Portions Copyright (C )  1988, by David Betz. Modified by Thomas Almy and others.

После чего появится знак  >, означающий приглашение системы к работе. Системный редактор начинает работать и выдает на экран свое меню: File, Edit и Run.

Функции разбора. Функция CAR возвращает в качестве значения первый элемент списка. (CAR  список) ð S - выражение (атом либо список). Функция создания CONS. Функция CONS строит новый список из переданных ей в качестве аргументов головы и хвоста. (CONS голова хвост). Для того чтобы можно было включить первый элемент функции CONS в качестве первого элемента значения второго аргумента этой функции, второй аргумент должен быть списком. Значением функции CONS всегда будет список. Функции присваивания: SET, SETQ, SETF. Функция SET - присваивает символу или связывает с ним некоторое значение. Причем она вычисляет оба своих аргумента. Установленная связь действительна до конца работы, если этому имени не будет присвоено новое значение функцией SET. Предикаты ATOM, EQ, EQL, EQUAL. Предикат - функция, которая определяет, обладает ли аргумент определенным свойством и возвращает в качестве значения NIL или T. Предикат ATOM проверяет, является ли аргумент атомом: (ATOM s - выражение). Значением вызова ATOM будет T, если аргументом является атом, и NIL - в противном случае. Список. Список - упорядоченная последовательность, элементами которой являются атомы либо списки. Списки заключаются в круглые скобки, элементы списка разделяются пробелами. Несколько пробелов между символами эквивалентны одному пробелу. Первый элемент списка называется «головой», а остаток, т. е. список без первого элемента, называется «хвостом». Список,  в котором нет ни одного элемента, называется пустым и обозначается «()» либо NIL. Символ - это имя, состоящее из букв, цифр и специальных знаков, которое обозначает какой-нибудь предмет, объект, действие. В языке ЛИСП как для вызова функций, так и для записи выражения принята единообразная префиксная форма записи, при которой как имя функции или действия, так и сами аргументы записываются внутри скобок:  (f x), (g x y), (h x (g y z)) и т. д. Рассмотрим некоторые примеры работы со списками [7,19].

Пример 1. Даны два списка. Получить результат произведения этих двух списков в виде списка.  Программа на ЛИСПе имеет следующий вид:

   (terpri)

  (defun  proizvedenie (spisok2   spisok1)

               (cond ((null  spisok1)  0)

               (T  (prince  (*  (car spisok2)  (car  spisok1))) (prince “ ”)

  (proizvedenie (cdr spisok2)  (cdr  spisok1)))))

  (princ “Введите списки”)

  (terpri)

  (setq a (read))

  (setq b (read))

  (setq c () )

  (terpri)

  (princ “Список в результате  произведения”)

  (terpri)

  (proizvedenie a  b)

  (terpri)

  (princ “Конец !!!”)

Пример 2. Даны две цифры. Получить результат сложения  этих двух цифр. Программа на ЛИСПе будет иметь следующий вид:

        (defun sum (N)

    (cond  ((=N 1) 1)

      (T (+ N( sum (-N  1))))))

Пример 3. Дан список. Получить результат сложения  элементов списка. Программа на ЛИСПе будет иметь следующий вид:

        (defun sl (L)

           (cond (( Null  L) 0)

              (T( + (car L))

                  (sl(cdr  L))))))

Пример 4. Дано число. Получить факториал этого числа. Программа на ЛИСПе будет иметь следующий вид:

         (defun  fact (N)

            (cond ((= N 1) 1)

               (T (* N(fact(-N 1))))))

Пример 5. Даны два списка. Получить результат Чередование двух списков в виде списка.  Программа на ЛИСПе будет иметь следующий вид:

         (defun  sher (x y)

             (cond ((Null x) y)

                (T  (cons (car x)

                     (sher y(cdr x))))))

Пример 6. Вычисление суммы N чисел.

(defun sum (N)

    (cond  ((=N 1) 1)

      (T (+ N( sum (-N  1))))))

   (setq N (read))

(terpri)

(princ ' !!!')

Пример 3. Выдать на экран среднее число из трех.

(defun sred (x y z)

  (cond ((> x y)

          (cond ((> y z) y)

                    ((> x z) z)

                    (t x)))

          (t(sred y x z ))))

Пример 7. Слоны. Задача: На доске 4х4 расставить 4 слона так, чтобы они все находились не под ударом друг друга.

(defun el_in (x y lst)

 (cond

   ((NULL lst) 0)

   ((and (eql (car(car lst)) x) (eql(car(cdr(car lst))) y))  1 )

   ( 1 (el_in x y (cdr lst)) ) ))

(defun el_bit (x y lst)

 (cond

   ((NULL lst) 0)

   ((and (eql (abs (-(car(car lst)) (car(cdr(car lst))))) (abs(- x y)))) 1)

   ( 1 (el_bit x y (cdr lst)) ) ))                                                                                      

(defun find_pos1 (lst_el state)

(cond

 ( (eql (length lst_el) 4) (print lst_el))

  ( 1

  (setq nx 0)

  (setq ny 0)

   (loop

     (setq nx (+ nx 1))

     (loop

      (setq ny (+ ny 1))

      (cond

       ((AND (eql (el_in nx ny lst_el) 0)  (eql (el_bit nx ny lst_el) 0))

             (push nx state)

             (push ny state)

              (find_pos1 (cons(list nx ny) lst_el) state)             

              (setq ny (pop state))

             (setq nx (pop state)) ) )                                       

      ((> ny 3) (setq ny 0) NULL)  )

     ((> nx 3) NULL)  ) )))

(defun solve()

 (find_pos1))

 

Задания для ПРОЛОГа

1. Выберите вариант задания и напишите свою программу, на ПРОЛОГе создав статическую базу данных на выбранную тему. Например, напишите программу, использующую предикат: изучает  (фамилия студента, предмет, оценка, срок) -  study(name subject,    numb data).

2.  Напишите утверждения для 6-7 студентов и нескольких предметов. Причем фамилия и предметы, даты могут повторяться. Предикат имеет аргументы символьного и целого числового типов.

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

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

5.  Написать программу предусматривающей  изменение параметров в базе данных.

6. Разработать на ПРОЛОГе многооконный интерфейс.

 

Задания для ЛИСПа.

1.Проделайте следующие вычисления с помощью ЛИСПа:

а) 3.234∙(45.6+2.43);

б) 55+21.3+1.54∙2.5432-32;

в) (34-21.5676-43)/(342+32∙4.1).

2.Составьте список студентов своей группы  (ФИО ФИО ... ФИО).

3.Для каждого студента а) с помощью функции LIST составьте следующие списки: для самого студента - (дата рождения), (адрес), (средний балл по лекциям), (средний бал по лабораторным). Для отца и матери – (ФИО), (дата рождения), (адрес), (место работы).

4.С помощью CONS и SETQ объедините полученные списки и присвойте их в виде значений символам, означающим ФИО каждого студента: ФИО ст. - (((дата рождения ст.) (адрес ст.)((ср. балл(до десятых) по лекциям).

6.Для каждого студента составьте списки свойств а) оценки по лекциям; б) оценки по практикам; в) оценки по лабораторным работам.

7.Напишите функцию, которая спрашивает у пользователя ФИО студента из группы и выдает следующие данные о нем: год рождения; средний балл; родителей; списки свойств, присвоенные ему раньше.   

8.Напишите функцию: от одного аргумента (ФИО любого студента).

 

Контрольные вопросы

 

1.   Структура программы на Турбо-ПРОЛОГе. Назначение всех разделов.

2.   Связки в предикатах, целевых утверждениях.

3.   Чем отличается повторения от рекурсий в ПРОЛОГе

4.   Какое существует правило рекурсии в ПРОЛОГе.

5.   Перечислите базовые функции ЛИСПа.

6.   Назовите основные отличия предикатов EQ, EQL, EQUAL и =.

7.   Назовите отличия функций CONS и LIST.

8.    Какой элемент называется головой и хвостом списка в ЛИСПе?

9.    Функций определяющие элементы  списка  в ЛИСПе?

10.   Функций которые возвращают  список свойств  в ЛИСПе?

 

Интеллектуальные системы

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

 

Лабораторная работа №2. Разработка интеллектуальной компоненты с использованием подхода в пространстве состояний

 

Цель работы: использовать методы, существующие в пространстве состояний, чтобы построить игровую компьютерную программу.

Постановка задачи. Для примера рассмотрим пример игра в «8» и «15». Дано начальное состояние в виде массивов 3х3 и 4х4, целевое состояние точно такой же форме, но с другими данными [10]. Эти состояния показаны на рисунке 2.1.а,б. 

 

Рисунок 2.1- Состояния игры «8» и «15»   в виде массива чисел

 

В качестве формы описания состояний в данном примере выступает массив размером 3х3. А в качестве оператора движение пустой клетки - влево, вверх, вправо, вниз. Методы полного перебора.  Поиск в ширину.  (BFS - Breadth-first search). В методе полного перебора вершины раскрываются в том порядке, в котором они строятся. В качестве механизма реализаций или в качестве обработки списков для метода поиска в ширину в алгоритмах программирования выбран механизм «очередь». Для списка open реализуется механизм очередь, или его называют структура FIFO «first-in-first-out»,  т.е. «первым пришел – первым обслужен». Состояния добавлются в список справа  и удаляются с левого конца списка. Поиск в глубину (Depth-first search, DFS).  В методах перебора в глубину  прежде всего раскрываются те   вершины, которые были построены последними. Одним из классических алгоритмов поиска на графе пространства состояний служит метод поиска с возвратами бектрекинг [11]. Этот способ предлагает опреде­ленную организацию перебора всех возможных вариантов решения задачи, число которых может быть велико. Суть бектрекинга состоит в том, чтобы в каждой точке процесса решения задачи, где существует несколько априори равноправных альтернативных вариантов (путей) дальнейшего продолжения, выбрать один из них и следовать ему, предварительно запомнив другие альтернативы,  для того, чтобы в случае неуспешности выбранного варианта-пути вернуться в точку выбора и выбрать для продолжения решения другой возможный вариант-путь. От программиста требуется лишь определение точек бектрекинга с нужными альтернативами и инициация в необходимый момент процесса возврата. Эвристический метод. Этот способ позволяет во всех случаях найти некоторый путь от начальной вершины к целевой, стоимость которого минимальна. Предполагается, что нам задана функция стоимости c(ni,nj), дающая стоимость перехода от вершины ni к некоторой следующей за ней вершине nj. В методе равных цен для каждой вершины n в дереве перебора нам нужно помнить стоимость пути, построенного от начальной вершины s к вершине n. Пусть g(n) -  стоимость от вершины s к вершине n в дереве перебора. В случае дерева перебора мы можем быть уверены, что g(n) является к тому же стоимостью того пути, который имеет минимальную стоимость (т.к. этот путь единственный). Алгоритм, работающий по методу равных цен, может быть также использован для поиска путей минимальной длины, если просто положить стоимость каждого ребра равной единице. Если сделать резюме, то в данном методе выбираем единичную функцию f(n)=g(n)+w(n) – та цена, которую дают каждой вершине.  Здесь g(n) – длина пути, g(0) – начальный путь, g(n)= g(n-1)+1=> g(1)=0+1. w(n) – число фишек, которые находятся не на своем месте. Как правило, выбираем тот, что дешевле. Рассмотрим реализацию этого метода  на примере игры в «8» на Лиспе. Исходные тексты на Лиспе приведены в [11]. Он выполнен с помощью  лисповской функции HEURISTIC_SEARCH, реализующей эвристический поиск в пространстве состояний с использованием эвристической оценочной функции EST, зависящей от конкретной поисковой задачи. Отметим, что на шаге 3, выбирая из списка Open первый элемент-вершину, мы тем самым выбираем вершину с минимальной оценкой, поскольку список Open всегда упорядочен по неубыванию хранящихся в нем оценок вершин-состояний (это обеспечивается вспомогательной функцией MERGE).

 

 (defun HEURISTIC_SEARCH(StartState)

   (prog (Open Closed Current

          Deslist ;список дочерних вершин;

          Reflist ;список указателей;

          Depth   ;глубина текущей вершины;)

 ;Шаг 1:; (setq Open (list(list 'S0 StartState 0

 (EST (list StartState 0)) )))

 ;Шаг 2:;   HS (cond ((null Open) (return())))

 ;Шаг 3:;   (setq Current (car Open))

                                  (setq Open (cdr Open))

                                  (setq Closed (cons Current Closed))

                                  (setq Depth (caddr Current))

 ;Шаг 4:;   (cond ((IS_GOAL Current)

            (return (SOLUTION Current Reflist))))

 ;Шаг 5:;   (setq Deslist (OPENING Current))

 ; Исключение повторных вершин-состояний:;

                                  (setq Deslist (RETAIN_NEW Deslist))

                                  (cond ((null Deslist) (go НS)))

 ;Шаг 6:;   (setq Open (MERGE (ADD_DEPTH_EST (add1 Depth) Deslist) Open))

  (setq Reflist (append (CONNECT Deslist Current) Reflist))(go HS) ))

 

Данная лисповская функция использует вспомогательные функции OPENING, SOLUTION, IS_GOAL, CONNECT, EST и функцию RETAIN_NEW.  Функция OPENING порождает для своего единственного аргумента список дочерних вершин-состояний (он может оказаться и пустым). Описание каждого состояния задается списком, первый элемент которого – это уникальный идентификатор состояния, а второй элемент – собственно описание состояния задачи. Идентификаторы состояний необходимы для построения указателей функцией CONNECT. Функция CONNECT с двумя аргументами,  списком порожденных дочерних вершин и текущей (только что раскрытой, родительской) вершиной – генерирует список указателей от каждой дочерней вершины к исходной родительской. Функция SOLUTION с двумя аргументами, найденными целевым состоянием и списком всех указателей дерева перебора, вырабатывает список-решение задачи (решающий путь). Предикат IS_GOAL проверяет, является ли ее аргумент целевым состоянием. В случае положительного исхода проверки значением функции является само проверяемое состояние, в ином случае значение равно цели. В алгоритмах поиска применяется также вспомогательная рекурсивная функция RETAIN_NEW, которая оставляет в списке дочерних состояний Dlist только те, которые не порождались ранее, тем самым исключается зацикливание при поиске в произвольном графе:

 (defun RETAIN_NEW (Dlist)

  (prog (D)

    (cond ((null Dlist) (return ()) ))

    (setq D (car Dlist))

    (cond ((or (member D Open) (member D Closed))

             (return (RETAIN_NEW (cdr Dlist))) ))

    (return (cons D (RETAIN-NEW (cdr Dlist)))) ))

Другая вспомогательная рекурсивная функция CHECK_GOALS проверяет, есть ли среди дочерних состояний целевые. Значением этой функции является целевое состояние, если таковое найдено, и пустой список в ином случае:

 (defun CHECK_GOALS (Dlist)

   (cond ((null Dlist) ())

         ((IS_GOAL (car Dlist)) (car Dlist))

         (t (CHECK_GOALS (cdr Dlist))) ))

 Используются также еще две вспомогательные функции – ADD_DEPTH_EST и MERGE. Первая функция устанавливает глубину дочерних вершин и вычисляет их эвристическую оценку. Вторая функция выполняет слияние двух упорядоченных (по невозрастанию эвристической оценки) списков состояний в результирующий упорядоченный список:

 (defun ADD_DEPTH_EST (Dn Slist)

   (cond ((null Slist) ())

         (t (cons (list (caar Slist) (cadar Slist) Dn

                        (EST (list (cadar Slist) Dn)) )

                  (ADD_DEPTH_EST Dn (cdr Slist))) ) ))

  (defun MERGE (L1 L2)

   (cond ((null L1) L2)

         ((null L2) L1)

         ((> (car (cdddar L1)) (car(cdddar L2)))

            (cons (car L2) (MERGE L1 (cdr L2))))

         (t (cons (car L1) (MERGE (cdr L1) L2))) ))

К основным терминам для этой лабораторной работы относятся следующие термины: состояние, формы описания состояний, оператор, описание начального состояния, описание целевого состояния, запись в виде графа,  раскрытие вершин, метод поиска в глубину (Depth-first search, DFS), списки open и closed в методах поиска, метод поиска в ширину (BFS, Breadth-first search), структура очередь (FIFO «first-in-first-out»), структура стек (LIFO «last-in-first-out»), эвристический метод поиска.

 

Варинты задания

 

1.     Создать компьютерную программу с методом поиска в глубину.

2.     Создать компьютерную программус методом поиска в ширину.

3.     Создать программу, использующую эвристический метод.

4.     Создать программу, использующий «жадный» алгоритм поиска.

5.     Создать программу, использующий процедуру  «Минимакса».

 

Контрольные вопросы

 

1.     В чем различие методов поиска в глубину и ширину?

2.     Преимущество эвристических алгоритмов.

3.     Как осуществляется стратегия при поиске от данных?

4.     Как осуществляется стратегия при поиске от цели?

5.     Что означает структура: стек?

6.     Какой механизм поиска применяется при методе поиска в глубину?

7.     Какой механизм поиска применяется при методе поиска в ширину?

8.     Что означает структура: очередь?

9.     Что означает раскрытие вершин?

10. Какие бывают формы описания состояния?

 

Лабораторная работа №3 Разработка интеллектуальной компоненты с использованием методов редукций

 

Цель работы: использовать методы существующие в пространстве сведение задач к подзадачам, чтобы построить игровую компьютерную программу с описанием состояний в виде И/ИЛИ графов.

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

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

1)    формы описания задач/подзадач и описание исходной задачи;

2)    множества операторов и их воздействий на описания задач;

3)    множества элементарных задач.

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

И/ИЛИ графы. Решающий граф.  Для изображения процесса редукции задач и получающихся при этом альтернативных множеств подзадач используются обычно графоподобные структуры, вершины которых представляют описания задач и подзадач, а каждая дуга связывает пару вершин, соответствующих редуцируемой задаче и одной из результирующих подзадач, причем стрелки на дугах указывают направление редукции. Такие структуры называются И/ИЛИ графами.

Пример. Для иллюстрации этого подхода рассмотрим один из вариантов известной головоломки – задачи о ханойской башне, или пирамидке [12]. В ней используются 3 колышка (обозначим их буквами A, B, C) и 3 диска разного диаметра, которые можно нанизывать на колышки через отверстия в центре. В начале все диски расположены на колышке А, причем диски меньшего диаметра лежат на дисках большего диаметра. Требуется переместить все диски на колышек С, двигая их по очереди и соблюдая следующие правила. Перемещать можно только самый верхний диск, и нельзя никакой диск класть на диск меньшего размера. Для решения простейшего случая задачи, когда пирамида состоит только из одного диска, необходимо выполнить одно действие – перенести диск со стержня i на стержень j, что очевидно (этот перенос обозначается i -> j). Общий случай задачи изображен на рисунке, когда требуется перенести n дисков со стержня i на стержень j, считая стержень w вспомогательным. Сначала следует перенести n‑1 диск со стержня i на стержень w при вспомогательном стержне j, затем перенести один диск со стержня i на стержень j и, наконец, перенести n‑1 диск из w на стержень j, используя, вспомогательный стержень i. Итак, задача о переносе n дисков сводится к двум задачам о переносе n‑1 диска и одной простейшей задаче. Схематически это можно записать так: T (n, i, j, w) = T (n‑1, i, w, j), T (1, i, j, w), T (n‑1, w, j, i). Ниже приведена программа, которая вводит число n и печатает список перемещений, решающая задачу о Ханойских башнях при количестве дисков n. Используется внутренняя рекурсивная процедура tn (n, i, j, w), печатающая перемещения, необходимые для переноса n дисков со стержня i на стержень j с использованием вспомогательного стержня w при {i, j, w} = {1,3,2}. Последовательность вызовов процедуры tn при m=3 иллюстрируется древовидной структурой на рисунке 3.1 Каждый раз при вызове процедуры tn под параметры n, i, j, w выделяется память и запоминается место возврата. При возврате из процедуры tn память, выделенная под параметры n, i, j, w, освобождается и становится доступной память, выделенная под параметры n, i, j, w предыдущим вызовом, а управление передается в место возврата.

Рисунок 3.1- Стек Ханойских башен

 

В данной схеме круги – вызов функции tn, а переменная х – проверка условия выхода из рекурсии и печать перестановки на экран. Во многих случаях рекурсивные функции можно заменить на эквивалентные не рекурсивные функции или фрагменты, используя стеки для хранения точек вызова и вспомогательных переменных. Рассмотрим реализацию этого алгоритм на языке ПРОЛОГ [13].

Domains

Loc = right;middle;left. */присваиваием осмысленные имена типам аргументов

Predicates */сообщаем к каким типам принадлежит аргументы предиката

Hanoi(integer) – procedure(i).

move(integer,loc,loc,loc) – procedure(i,i,i,i).

inform(loc,loc) - procedure(i,i).                    

clauses                                                                 */цель игры

Hanoi(N) : -

                move(left, middle, right).

move(1,A, _ , C) : -             inform(A,C), !.

move(N,A, B , C) : -

N1= N – 1,

move(N1,A, C , B),                              */предикат (move)с помощью которого мы описываем    перенос N дисков с одного стержня на другой, используя    третий стержень в качестве промежуточного места для дисков

inform(A,C),         move(N1,B, A, C).

inform(loc1,loc2) : -                          */предикат inform (), который указывает на действие, выполняемое с конкретным диском

write ( "move a disk from", "loc1", to "loc2"), nl.

Goal*/в разделе цели Goal () указываем со сколькими дисками мы играем

Hanoi(3).

К основным терминам для этой лабораторной работы относятся следующие термины: элементарные задачи, редукция задач, оператор редукции, описание начального состояния, описание целевого состояния, запись в виде графа, И/ИЛИ графы,  решающий граф, И-вершина, ИЛИ-вершина, заключительные вершины, разрешимость,  структура очередь (FIFO «first-in-first-out»), структура стек (LIFO «last-in-first-out»).

 

Варианты заданий

 

1.       Создать игровую программу, с описанием в виде И/ИЛИ графа. 

2.       Создать компьютерную программу, использующий метод редукций.

3.       Создать программу, использующий эвристический алгоритм.

4.       Создать программу, с стратегией прямого поиска.

5.       Создать игровую программу, с поиском на основе от цели.

 

Контрольные вопросы

 

1.            Различие методов поиска в глубину и ширину для метода редукций?

2.            Преимущество эвристических алгоритмов в методе редукций.

3.            Стратегия при поиске от данных для метода редукций?

4.            Как осуществляется стратегия при поиске от цели для метода редукций?

5.            Структуры применяемые для состояний при редукций?

6.            Какой механизм поиска применяется при методе редукций?

7.            Различие подходов в пространстве состояний и редукции задач.

8.            Что означает решающий граф?

9.            Что означает И/ИЛИ  граф?

10.        Что означает разрешимость вершин ?

 

Лабораторная работа №4 Разработка интеллектуальной компоненты с использованием теорий исчисление предикатов

 

Цель работы: использовать методы существующие в теории доказательство теорем в исчислении предикатов, чтобы построить игровую компьютерную программу с описанием состояний в виде И/ИЛИ графов.

Исчисление предикатов    первого порядка – это такая система в логике, в которой можно выразить большую часть того, что относится к математике, а также многое из разговорного языка. Это система содержит правила логического вывода, позволяющие делать верные логические построения новых утверждений, исходя из некоторого заданного множества утверждений. Благодаря своей общности и логической силе исчисление предикатов может всерьез претендовать  на использование его для машинного построения умозаключений.

Пример. В комнате находятся обезьяна, ящик и связка бананов, которая подвешена к потолку настолько высоко, что обезьяна может до нее дотянуться, только встав на ящик. Нужно найти последователь­ность действий, позволяющие обезьяне достать бананы. Предполагается, что обезьяна может ходить по комнате, двигать по полу ящик, взбираться на него и хватать бананы [12]. Ясно, что описание состояния этой задачи должно включать следующие сведения: местоположение обезьяны в комнате – в горизонтальной плоскости пола и по вертикали (т.е. на полу она или на ящике), местоположение ящика  на полу и наличие у обезьяны бананов. Состояние может изменяться со временем. Текущее состояние определяется взаиморасположением объектов. Исходное состояние можем описать в виде предложений на естественном языке:

1.                 Обезьяна у двери

2.                 обезьяна на полу

3.                 Ящик у окна

4.                 Обезьяна не имеет банана

Теперь рассмотрим эти состояния в более удобном виде для представления  взаимосвязи объектов. (см.таблицу 4.1)

 

Таблица 4.1. Взаимосвязь объектов задачи

Состояния

Расположение объектов

исходное

У двери

На полу

У окна

Не имеет

текущее

Горизонтальная позиция обезьяны

Вертикальная позиция обезьяны

Позиция ящика

Наличие или отсутствие банана у обезьяны

 

Задачу можно рассматривать как игру для одного игрока. Формализуем правила этой игры. Цель игры – состояние, у которого четвертая компонента равна «имеет»: состояние (         ----,    ----,    ----,    имеет). Каковы разрешенные ходы? Существует четыре типа ходов:         (1) схватить банан; (2) залезть на ящик; (3) передвинуть ящик;   (4) перейти в другое место.     Это предложение включает утверждения:

1)       Ход состоит в том, что обезьяна переходит из позиции Р1 в позицию Р2.

2)     Обезьяна находится на полу до и после хода.

3)     Положение ящика остается неизменным.

4)     Состояние «имеет банан» остается неизменным.

Главный вопрос «Может ли обезьяна, находясь в некотором начальном состоянии S, завладеть бананом?» Его также можно сформулировать в виде предиката  может завладеть( S), где аргумент S - состояние обезьяньего мира. Программа для «может завладеть» основываться на двух наблюдениях:

1) Для любого состояния S, в котором обезьяна уже имеет банан предикат может завладеть должен быть  истинным: в этом случае никаких ходов не требуется.

Может завладеть( состояние( ----, ----, -----, имеет)).

2) В остальных случаях требуется один или более ходов. Обезьяна может завладеть бананом в любом состоянии S1, если для него существует ход из состояния Р1 в некоторое состояние S2, такое, что, попав в него, обезьяна уже сможет завладеть бананом ( за ноль или более ходов).

Код программы на ПРОЛОГ-е [13].

predicates

                get_it.

                banana(symbol,symbol,symbol).

                search(symbol,symbol,symbol).     

clauses

                goal

                               write("Enter coordinates of monkey..."), nl,

                               readln(M), nl,

                               write("Enter coordinates of banana..."), nl,

                               readln(B), nl,

                               write("Enter coordinates of chair..."), nl,

                               readln(C), nl,

                               search(M,B,C).

                search(O,A,H):-

                               O=H,

                               write("Monkey near chair"), nl,

                               banana(O,A,H);

                               write("Monkey is far away from chair. Please enter new position for a monkey to move to..."), nl,

                               readln(N),

                               search(N,A,H).

                banana(X,Y,Z):-

                               X=Y,

                               write("Monkey is under banana"),

                               get_it;

                               write("Monkey is far away from banana. Enter new position for a monkey and banana to move to"),

                               readln(K),

                               banana(K,Y,K).

                get_it:-                   write("Monkey is under banana and can get it, Hallelua. Do you want to take it?"),nl,

                               readln(P),

                               P="yes",

                               write("Oh, Yeah");

                               write("I'm too young to die - said Monkey").

 

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

 

Варианты заданий

 

1.       Создать компьютерную программу, состояниями из множества ППФ.

2.       Создать компьютерную игровую программу «Обезьяна и Банан».

3.       Создать компьютерную игровую программу «Волк. Коза и капуста».

4.       Создать компьютерную игровую программу «Людоеды и Миссионеры».

5.       Создать свою компьютерную программу, стратегией полного перебора

 

Контрольные вопросы

 

1.                 Что означает ППФ?

2.                 Опишите граф И/ИЛИ для множества ППФ.

3.                 Назовите стратегии перебора  для ППФ?

4.                 Как осуществляется принцип резольвенции?

5.                 Назовите и опишите кванторов ?

6.                 В чем заключается концепция логического вывода?

7.                 Что такое пустое предложение?

8.                 Назовите операций математической логики.

9.                 Чем отличаются кванторы общности и существования?

10.            Что такое резольвента?

 

 

Экспертные системы

Существует ряд прикладных задач, которые решаются с помощью экспертных систем (ЭС). ЭС это компьютерная программа заменяющая человека-эксперта в какой то определенной предметной области. Главные требования для проектирования ЭС - наличие эксперта-человека. Состав ЭС предполагает выполнение системой следующие функции. Система ведет переговоры как человек, выдает рекомендацию как человек объясняет полученное решение, как человек наполняет свои знания новыми и изменяет свои старые знания как человек. Главное достоинство ЭС - возможность накапливать знания, сохранять их длительное время, обновлять и тем самым обеспечивать относительную независимость конкретной организации  от наличия в ней квалифицированных специалистов. На  современном этапе развития ЭС используется несколько форм представления знаний. Выделим из них четыре основные. Типичными моделями представления знаний являются: логическая модель; продукционная модель; модель, основанная на использовании фреймов; модель семантической сети [15].

 

Лабораторная работа №5 Проектирование продукционной модели ЭС, и разработка ее компонентов

 

Цель работы: Разработка основных требований для проектирования ЭС. Проектирование продукционной модели ЭС и структуры  ЭС и ее компонент.

Наиболее распространенный способ представления знаний - в виде конкретных фактов и правил, по которым из имеющихся фактов могут быть выведены новые. Правила в базе знаний имеют вид: ЕСЛИ А  ТО  S, где  А - условие; S- действие. Действие S исполняется, если А истинно. Наиболее часто действие S, так же, как и условие, представляет собой утверждение, которое может быть выведено системой, если истинно условие правила А. Продукционная модель имеет вид: (i); P; Q: Ai => Bj ; N; i- номер правила, P- приоритет правила, Q - область применения правила  Ai => Bj – ядро продукции, i, j - с какой части берется утверждение, чаще всего i = БД, БЗ, диалог, О (блок объяснения)  j - тоже самое и помимо этого добавляется блок БЗ. АБД => ВБД ,N- комментарии к продукции [14].

Пример1. При разработке экспертной системы «Консалтинговые услуги» использована продукционная модель представления знаний. В качестве примера рассмотрим правило, словесное описание которого выглядит так: «Если процессор = «Celeron» и память = 256, то вывести данные обо всех компьютерах с такими параметрами». На языке запросов SQL данное правило запишется следующим образом:  SELECT * FROM basic WHERE proc like 'Celeron%' and memory='256' ORDER BY  art

Ядро продукции для рассмотренного правила имеет вид: А1БД И А2БД Þ ВБЗ, то есть левая часть берется из БД, а правая из БЗ.

Диалог строится с помощью интерфейса на естественном языке. Существуют две основные формы диалога: 1)ЭС-диалог на ограниченном подмножестве естественного языка (с использованием  словаря-меню при котором на каждом шаге диалога система предлагает выбор профессионального лексикона экспертов), он называется иногда «механизмом ключевых слов» и 2)диалог на основе из нескольких возможных действий. ЭС имеют две категории пользователей  и два отдельных “входа”, соответствующих различным целям взаимодействия пользователей с ЭС: обычный пользователь которому требуется консультация ЭС- диалоговый сеанс работы с ней, в процессе которой она решает некоторую экспертную задачу; экспертная группа инженерии знаний, состоящая из экспертов в предметной области и инженеров знаний.

Например при разработке экспертной системы «Консалтинговые услуги» была использован «механизм ключевых слов». Итак, диалог пользователя с системой можно выглядит следующим образом:

 

 

 

 

 

 

 

 

 

 

 

Рисунок 5.1 - Принскрин блока Диалог

 

Из приведенного примера видно, что пользователь задает вопрос системе на упрощенном естественном языке. В случае если вопрос удовлетворяет правилам, заложенным в экспертную систему, она находит ответ и выдает его пользователю.

Пример2. Имеется задача «Электронная сваха». Необходимо составить диалог по ключевому словам: «девушка»  (или «мужчина», «женщина»), «информация». В данной работе применяется также стратегия ключевого слова. Программа диалога располагает некоторыми функциями, которые поддерживаются естественным языком. Для того чтобы связать компоненты БД, БЗ с компонентой Диалог необходимо было определить полный список ключевых слов, на которые должна реагировать система.

Компонента Объяснение. Цикл работы экспертной системы иначе называется логическим выводом. Логический вывод может осуществляться различными способами, из которых наиболее распространенные – прямой порядок вывода и обратный порядок вывода. Прямой вывод. Правила просматриваются до тех пор, пока не будет найдено такое, у которого первый операнд (в левой части) соответствует информации, находящейся в рабочей области, затем правило изменяется. Процесс повторяется до тех пор, пока не будет достигнута цель или не будет найдено подходящего правила. Данный механизм вывода рекомендуется, если цель неизвестна и должна быть спроектирована или число возможных результатов велико. Обратный вывод. Правила просматриваются, находятся те, последовательность выполнения которых приводит к цели. Процесс выполняется рекурсивно. Непременным элементом экспертной системы считается блок объяснений позволяющий получить ответы на вопросы «Как была получена данная рекомендация?» и «Почему экспертная система приняла такое решение?». Вопрос «Почему?» позволяет проследить ход рассуждений системы от посылок к заключениям. Однако для более детального осмысления процесса вывода удобно было бы иметь возможность изучать его и в противоположном порядке – от заключений к посылкам. Отвечая на вопрос «Как?», экспертная система предъявляет пользователю шаг за шагом весь процесс получения решения с указанием использованных фрагментов базы знаний. Для вывода допустимо использовать сеть вывода, стоящую из нескольких правил. Например, сеть вывода состоит из трех правил:

- П1: Если А1 ИЛИ А2 истина, то В1- истина;

- П2: Если А3 ИЛИ А4 истина, то В2- истина;

- П3: Если В1 ИЛИ В2 истина, то В3- истина.

В данном случае помимо стандартной сети вывода есть дополнительная сеть вывода по шаблонам. В любой момент диалога можно приказать системе вывести данные с любыми ограничениями, используя названия полей-шаблонов. (см. рисунок 5.2)

  

 

Рисунок 5.2 - Схема блока Объяснение

 

При разработке экспертной системы «Консалтинговые услуги» была использована стратегия поиска использующий ответ на вопрос  «Почему?».

Ответ системы будет выглядеть следующим образом: «Потому что «вы выбрали размер монитора равный 17» (посылка А1) ИЛИ «вы не задавали тип процессора» (посылка А2),  поэтому «не указан размер жесткого диска» (заключение В1), «вы задали размер памяти =120» (посылка А3) ИЛИ «вы не задали размер видеокарты» (посылка А4), поэтому «не указана цена процессора » (заключение В2), так как В1 ИЛИ В2  не истины, поэтому «не указана общая цена компьютера» (заключение В4).

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

К основным терминам для этой лабораторной работы относятся следующие термины: экспертные системы, компоненты ЭС, база данных ЭС, база знаний, модели представления знаний, логическая модель, продукционная модель, механизмы компоненты Диалог, механизмы компоненты Объяснения, механизмы стратегии вывода.   

 

Задания для проектирования продукционной модели ЭС

 

1.   Спроектировать продукционную модель для «Электронная сваха»

2.   Создать компоненты  «БД»  и «БЗ» для предыдущей ЭС.

3.   Создать компоненту  «Диалог»   для предыдущей ЭС.

4.   Создать компоненту  «Объяснение»   для предыдущей ЭС

5.   Создать компоненту  «Диалог»   для своей ЭС.

6.   Спроектировать продукционную модель для своей области

7.   Создать все компоненты ЭС для своей предметной области

 

 Контрольные вопросы

 

1.   Что означает компонента БД для ЭС продукционной модели?

2.   Критерий для проектирования ЭС продукционного типа.

3.   Что означает компонента Диалог для ЭС продукционной модели?

4.   В чем преимущество продукционной модели перед другими?

5.   В чем заключается цель разработки экспертных систем?

6.   Назовите модели представления знаний?

7.   Какие имеются режимы функционирования ЭС?

8.   Какие имеются механизмы ключевых слов?

9.   Какая стратегия отвечает на вопрос «Почему» ?

10.   Какая стратегия отвечает на вопрос «Как» ?

 

Лабораторная работа №6 Проектирование фреймовой ЭС, и разработка ее компонентов

 

Цель работы: разработка основных требований для проектирования ЭС. Проектирование фреймовой модели ЭС и структуры  ЭС и ее компонент.

Фреймовая модель представления знаний была предложена М.Минским в 1979 году и является развитием семантических сетей. Фрейм - абстрактный образ для представления некоторого стереотипа восприятия. Каждый фрейм имеет собственное название и список слотов и их значений. Слот может быть терминальным или представлять собой фрейм нижнего уровня. Значениями могут быть данные любого типа, а также название другого фрейма. Таким образом, фреймы образуют сеть. Кроме того, существует связь между фреймами типа АКО (a kind of), которая указывает на фрейм более высокого уровня иерархии, откуда неявно наследуются список и значения слотов. При этом возможно множественное наследование – перенос свойств от нескольких прототипов [16,17]. Любой фрейм может быть представлен следующим образом:

(ИМЯ ФРЕЙМА:

(имя 1-го слота: значение 1-го слота),

(имя 2-го слота: значение 2-го слота),

 …

(имя N-гo слота: значение N-го слота)).

Фреймовая модель представляет собой систематизированную психологическую модель памяти человека и его сознания.

Типы фреймов. Фреймы подразделяются на:

1)     фрейм-экземпляр – конкретная реализация фрейма, описывающая текущее состояние в предметной области;

2)     фрейм-образец – шаблон для описания объектов или допустимых ситуаций предметной области;

3)    фрейм-класс – фрейм верхнего уровня для представления совокупности фреймов образцов [18].

Пример1. Построить фреймовую модель представления знаний в предметной области «Ресторан». Описание процесса решения.Для построения фреймовой модели представления знаний необходимо выполнить следующие шаги:

 1) Определить абстрактные объекты и понятия, необходимые для решения поставленной задачи. Оформить их в виде фреймов-прототипов.

 2) Задать конкретные объекты. Оформить их в виде фреймов-экземпляров (фреймов-объектов, фреймов-ролей).

 3) Определить набор возможных ситуаций. Оформить их в виде фреймов- ситуаций. Если существуют прецеденты по ситуациям в предметной области, добавить фреймы-экземпляры (фреймы-ситуации).

4) Описать динамику развития ситуаций (переход от одних к другим) через набор сцен. Оформить их в виде фреймов-сценариев.

 5) Добавить фреймы-объекты сценариев и сцен, которые отражают данные конкретной задачи.

Решение. Ключевые понятия данной предметной области – ресторан, тот, кто посещает ресторан и те, кто его обслуживают. У обслуживающего персонала и клиентов есть общие характеристики, поэтому целесообразно выделить общее абстрактное понятие – человек. Тогда фреймы «Ресторан» и «Человек» являются прототипами-образцами, а фреймы «Официант» и «Клиент» - прототипами-ролями. Также нужно определить основные слоты фреймов-характеристики, имеющие значения для решаемой задачи. Для отображения типов фреймов изобразим его в следующем виде:

< Фрейм Имя слота Значение слота Способ получения значения Демон >

Фреймы для нашего примера будут выглядеть следующем образом:

< ЧЕЛОВЕК пол Мужской или женский, возраст От 0 до 120 лет>

< РЕСТОРАН Название Адрес Часы работы Специализация Класс >

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

< ОФИЦИАНТ (AKO ЧЕЛОВЕК) возраст От 18 до 55 лет стаж работы зарплата график работы место работы Фрейм-объект >

< КЛИЕНТ (AKO ЧЕЛОВЕК) Вид оплаты Наличные или карточка По умолчанию (наличные) Статус Обычный или Vip По умолчанию (обычный) Форма заказа Заказ есть или нет По умолчанию (заказа нет)Чаевые >

 

 

 

 

 

 

 

Рисунок 6.1- Схема фреймов для предметной области «Ресторан»

 

Взаимосвязь различных видов фреймов данного примера отображается в виде графа (см.рисунок 6.1). В примере в качестве фреймов–образцов выступают фреймы: «Ресторан» и «Человек». А в качестве ролей фреймы «Ресторан Дос», «Кафе Маг», «Официант», «Клиент», «Серик», «Айжан», «Болат». Фреймами-ситуациями являются «Заказ», «Оплата».  Получить ответ на вопрос «Кто работает официантом в ресторане “Маг”?» можно так: необходимо найти фрейм «Ресторан “Маг”» и проследить связь с фреймом «Серик», являющимся наследником фрейма «Официант». Также можно найти слот «Место работы». Могут быть также следующие связи во фреймах:

<Клиент AKO Человек Официант AKO Человек Айжан AKO Официант Серик AKO Официант AKO Болат AKO AKO Клиент>

<Человек Ресторан Кафе-ресторан"Дос" AKO Ресторан Кафе "Маг" AKO Ресторан AKO AKO>

<Посещение ресторана Посещение «Маг» AKO Слот: посетитель Слот: место  работы Слот: ресторан Слот: официант >

<Заказ Оплата Болата Слот: сцена 2>

<Заказ Болата Слот: сцена 4 AKO Оплата AKO Слот: оплатил Слот: сделал Слот: принял>.

В данном примере наследником фрейма «Официант» является фрейм  «СЕРИК» и он работает в кафе «Маг» [20].

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

 

Варианты заданий

 

1.       Построить фреймовую модель «Библиотека».

2.       Построить фреймовую модель в предметной области «Аэропорт».

3.       Построить фреймовую модель в области «Железная дорога».

4.       Построить фреймовую модель в области «Торговый центр».

5.       Построить фреймовую модель в области «Автозаправка».

6.       Построить фреймовую модель в области «Автопарк».

 

         Контрольные вопросы

 

1.   Что означает компонента БД для ЭС фреймовой модели?

2.   Что означает компонента Диалог для ЭС фреймовой модели?

3.   В чем преимущество фреймовой модели перед другими ?

4.   Из каких компонентов состоит структура фрейма?

5.   Какие способы получения слотов знаете?

6.   Что такое демон?

7.   Что означает присоединенная процедура?

8.  Какие существуют типы фреймов?

 

Список литературы  

1.     Доорс Дж. И др. Пролог - язык программирования будущего /Пер.с англ. – М.:Финансы и статистика, 1990. - 144 с.

2.     Братко И. Программирование на языке Пролог для искусственного интеллекта –М.: Мир, 1990.

3.     Клоксин, Меллиш «Программирование на языке Пролог»- М.: Мир, 1987.

4.     Дж. Стобо «Язык программирования Пролог» - М.: Радио и связь, 1993.

5.     Л. Стерлинг, Э. Шапиро «Искусство программирования на языке Пролог» - М:Мир, 1990.

6.     Логическое программирование http: //ru.wukipedia.org/wiki/   

7.Хъювенен Э., Сеппянен Й. Мир Лиспа В 2-х т. Т.1: Введение в язык Лисп и функциональное прогаммирование. Пер. С финск. – М.:Мир, 1990. – 447 с.

8.Хъювенен Э., Сеппянен Й. Мир Лиспа В 2-х т. Т.2: Методы и системы прогаммирования. Пер. С финск. – М.:Мир, 1990. – 319с.

9.Сергиевский Г.М.  Функциональное и  Логическое программирование. –М.:Изд.Центр «Академия». -  2010. – 320 c.

10. Люгер, Джордж,,Ф. Искусственный интеллект: стратегии и методы решения сложных проблем – М.:2003. - 864 с.

11. Большакова. И., Мальковский М. Г., Пильщиков В. Н.  Искусственный интеллект. Алгоритмы эвристического поиска (учебное пособие) - М.: Издательский отдел факультета ВМК МГУ, 2002. - 83 с.

12. Нильсон Н. Искусственный интеллект. Методы поиска решений./ Пер. с анг. –М.:Мир, 1973. - С. 270.

13. Д. Марселус. Программирование экспертных систем на Турбо Прологе. Пер. с анг. М.:Финансы и статистика, 1994, - 256 с.

14. Ахметова М. Сарапшы жүйе және оның құрамы: Оқу құралы. Алматы: ҚазҰТУ, 2004 – 100 б.

15. Джексон Питер, Введение в экспертные системы. /Пер.с англ.: Уч.пособие, 2001. – 624 с.

16. Представление и использование знаний / Пер. с японск. /Под ред. Х.Уэно,  М.Исидзука, - М.:Мир, 1989. – 220 с.

17. Приобретение знаний. / Пер. с японск. /Под ред. С.Осуги,  Ю.Саэки М.Исидзука, - М.:Мир, 1990. – 304 с.

18. Фрейм. Модели представления знаний фреймами. http://alportal.ru.

19. Семенов М.Ю. Язык Лисп для персональных ЭВМ - М.:Издательство МГУ, 1989.

20. Ахметова М. Функционалдық-логикалық программалау және жасанды зерде жүйелері: Оқу құралы. -  Алматы: «Бастау» баспасы. 2012.- 330 б.