Серия изданий Научно-образовательные и



Скачать 65.95 Kb.
Дата19.01.2013
Размер65.95 Kb.
ТипДокументы




Серия изданий

«Научно-образовательные и

научно-информационные

материалы

МГТУ им. Н.Э. Баумана —

национального

исследовательского

университета

техники и технологий»

Департамент образования города Москвы

  

Ассоциация московских вузов

  

Московский государственный технический университет

имени Н.Э. Баумана




Кафедра ИУ-3

«Информационные системы и телекоммуникации»

В.В. Девятков
Научно-образовательный материал

«Методические материалы к практическим занятиям

по дисциплине

«Представление знаний в информационных системах»




Москва

МГТУ им. Н.Э. Баумана

2011
Оглавление



Введение в язык представления знаний ПРОЛОГ 3

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

Описание конечного автомата на ПРОЛОГе 4

Полная программа на ПРОЛОГе 6

Схема ответов на вопросы по результатам практических занятий 7

a.Граф переходов автомата, представленного в программе. 7

b.Структура программы. 7

c.Результат работы программы. 8

d.Граф И-ИЛИ вывода результата. 8

Введение в язык представления знаний ПРОЛОГ



Настоящие методически материалы направлены на практическое ознакомление 6 с принципами представления знаний на языке логического программирования (ПРОЛОГ– ПРОграммирование ЛОГическое, ProLog - PROgramming LOGical). Практические занятия проводятся после прочтения лекций по языку ПРОЛОГ и состоят в ознакомлении с принципами проверки свойств конечных автоматов с помощью программы на Прологе. Для этого необходимо ознакомиться с тем, как эта программа составляется, как формулируются свойства автомата, подлежащие проверке, как осуществляется вывод для проверки.

Чистый ПРОЛОГ является декларативным языком программирования в отличие от процедурных языков программирования. Осуществляет поиск (вывод) решения по поставленной цели. Программа на ПРОЛОГе - это множество фактов и правил (т.е. база знаний).
Решение задачи в ПРОЛОГе осуществляется по формулировке цели с помощью специальной процедуры поиска. В терминах логики цель является логическим следствием исходного описания задачи, а поиск цели либо должен завершиться успешно, либо он заканчивается неудачей. ПРОЛОГ создан около 1970 Аланом Колмероэ (Alain Colmerauer) и другими в Марселе (Франция). На основе принципов логического вывода (Robinson, 1965; Kowalski, 1979). В ПРОЛОГе объекты и отношения между представляются символически. Алан Колмероэ первоначально развивал ПРОЛОГ для анализа языков и ответа на запросы. Последующие применения ПРОЛОГа: математическое доказательство теорем, экспертные системы, базы данных, медицина, логистика, архитектура и т.д. Программа на ПРОЛОГе – это список фактов и правил.

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



Переход автомата из одного состояния в другое выполняется всякий раз при поступлении входного символа. Переход из состояния si в состояние sj при поступлении входного символа x представляется тройкой (si, x, sj). Путем на графе, ведущем из состояния si, в состояние sj, называется последовательность (цепочка) входных символов, которыми помечены дуги переходов, ведущих из состояния si в состояние sj. Если из состояния si велет какой-либо путь в состояние sj , то будем говорить, что состояние sj достижимо из состояния si этим путем. Путь, ведущий из состояния si в состояние sj через состояния, среди которых не встречается ни одной пары одинаковых, называется простым. В противном случае путь называется сложным. Простой путь, ведущий из состояния si в то же самое состояние si, называется циклом. Сложный путь, ведущий из состояния si в то же самое состояние si, называется контуром. Состояние si, из которого ведет некоторый путь, называется начальным состоянием этого пути, а состояние sj, в который этот путь ведет, называется конечным.

Описание конечного автомата на ПРОЛОГе



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

  1. Одноместный предикат начальное(si) (initial(si)), соответствующий начальному состоянию si, и истинный, когда автомат находится в начальном состоянии si.

  2. Одноместный предикат конечное(sj) (final(sj)), соответствующий конечному состоянию sj, и истинный, когда автомат находится в конечном состоянии sj

  3. Трехместный предикат переход(si, x, sj) (transition(si, x, sj)), который определяет переход из состояния si в состояние sj при подаче на автомат входного символа x.


Для рассмотренного автомата переходы представляются следующими фактами:
переход (b1, x1, b2)

переход (b2, x1, b3).

переход (b3, x1, b4).

переход (b4, x1, b1.)

переход (b1, x2, b4).

переход (b2, x2, b3).

переход (b3, x2, b2).

переход (b4, x2, b1).

В английском варианте

transition(b1, x1, b2)

transition (b2, x1, b3).

transition (b3, x1, b4).

transition (b4, x1, b1.)

transition (b1, x2, b4).

transition (b2, x2, b3).

transition (b3, x2, b2).

transition (b4, x2, b1).

Введем помимо перечисленных выше фактов двуместный предикат достижимо(B1, [X], В2) (accessible(B1, [X], В2)). С использованием этого предиката введем следующие правила, обуславливающее условия достижимости состояния B2 из состояния В1 после подачи на автомат, находящийся в состоянии B1 последовательности входных символов, представленных списком [X].
% Нерекурсивное правило достижимости:
достижимо(B1, [X], В2) :- переход(B1, X, В2).

(accessible(B1, [X], В2)):- transition(B1, X, В2)).
% Рекурсивное правило достижимости:
достижимо(B1, [Х | Остальные], В2) :-

переход(B1, X, В3), достижимо(B3,[Остальные], B2).

(accessible(B1, [Х | Rest], В2) :-

transition (B1, X, В3), accessible(B3,[Rest], B2)).
Цель (проверяемое свойство автомата) может быть сформулирована, например, следующим образом:
достижимо(b1, [X1, X1, X1], b4)

(accessible(b1, [X1, X1, X1], b4))

Полная программа на ПРОЛОГе



Полная программа на ПРОЛОГе для настоящего примера выглядит следующим образом.
domains

list=symbol*
predicates
nondeterm transition(symbol, symbol, symbol)

nondeterm accessible(symbol, list, symbol)
clauses
transition(b1, x1, b2).

transition(b2, x1, b3).

transition(b3, x1, b4).

transition(b4, x1, b1).

transition(b1, x2, b4).

transition(b2, x2, b3).

transition(b3, x2, b2).

transition(b4, x2, b1).

accessible(B1, [X], B2) :- transition(B1, X, B2).
accessible(B1, [X|Rest], B2) :- transition(B1, X, B3), accessible(B3, [Rest], B2).
goal

accessible(b1, [X1, X1, X1], b4).

Схема ответов на вопросы по результатам практических занятий




    1. Граф переходов автомата, представленного в программе.


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


    1. Структура программы.


Данная программа содержит четыре раздела domains, predicates, clauses, goal. Далее следует рассказать, что содержится в этих разделах.

    1. Результат работы программы.


В программе требуется определить все пути длины три, ведущие из состояния b1 в состояние b4 и содержащие одинаковые входные символы. Результат работы приведенной программы при цели

accessible(b1, [X1, X1, X1], b4)
выглядит в ПРЛОГе следующим образом:
X1=x1

X1=x2
Первый ответ (X1=x1) означает наличие простого пути, ведущего из состояния b1 в состояние b4, все входные символы которого равны x1, а второй ответ (X1=x2) означает наличие сложного пути, все входные символы которого равны x2.

    1. Граф И-ИЛИ вывода результата.



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




Похожие:

Серия изданий Научно-образовательные и iconСерия изданий Научно-образовательные и
Цели проведения лабораторных работ по дисциплине «Интеллектуальные информационные системы»
Серия изданий Научно-образовательные и iconСерия изданий Научно-образовательные и
Развитие информационных технологий в XXI веке открывает новые возможности для решения этой проблемы путем автоматизации процессов...
Серия изданий Научно-образовательные и iconСерия изданий Научно-образовательные и
Однако, увеличение их количества зачастую не только не облегчает абитуриенту выбор, но, наоборот, усложняет его. Сориентироваться...
Серия изданий Научно-образовательные и iconСерия изданий Научно-образовательные и
Проведение лабораторных работ по курсам программирования требует от преподавателя четырёх видов деятельности: составление условий...
Серия изданий Научно-образовательные и iconБюллетень экспериментальной биологии и медицины
Вестник Московского университета (Серия Математика. Механика; Серия Химия; Серия Физика. Астрономия; Серия Геология; Серия 16. Биология;...
Серия изданий Научно-образовательные и iconСписок периодических изданий на 2012 год (библиотека вгавт)
Научно-технический прогресс. Инновации. Организация и финансирование научно-исследовательских работ
Серия изданий Научно-образовательные и iconНаучно-педагогические издания рао каталог основных изданий
Научно-педагогические издания рао, 2008-2009 год: каталог основных изданий: в 2 ч. – М.: Российская академия образования, 2009. –...
Серия изданий Научно-образовательные и iconТехническое задание № п/п подписной индекс Наименование Подписной период
Научно-техническая информация нти. Серия организация и методика информационной работы. Научно-технический сборник. Винити
Серия изданий Научно-образовательные и iconМосква просвещение-регион 2011 ббк 74. 262. 21-7 б 14 Серия ォ Современные образовательные технологии サ
В. Б. Багирян, В. Г. Смелова Интерактивное оборудование и интернет-ресурсы в школе
Серия изданий Научно-образовательные и iconОбщероссийские образовательные порталы Сайт Министерства образования и науки РФ
Каталог учебных изданий, оборудования и электронных образовательных ресурсов для образования
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org