Сошников Дмитрий Валерьевич к.ф.-м.н., доцент dmitryso@microsoft.com Факультет Прикладной математики и физики Кафедра Вычислительной математики и программирования. - презентация

1 Сошников Дмитрий Валерьевич к.ф.-м.н., доцент Факультет Прикладной математики и физики Кафедра Вычислительной математики и программирования Московский авиационный институт (государственный технический университет)

2 ©2009 Сошников Д.В. 2 Объектно-ориентированное программирование – известная парадигма борьбы со сложностью за счёт использования Инкапсуляции Наследования Полиморфизма Можно рассматривать с двух позиций: Как отдельную парадигму вычислений, основанную на передаче сообщений Как расширение традиционной модели вычислений описанными понятиями

3 ©2009 Сошников Д.В. 3

4 4 F-logic (Michael Kifer) Описывает формальную аксиоматическую системы со свойствами инкапсуляции, наследования и полиморфизма на основе расширения логики 1-го порядка Частично F-логика может быть смоделирована на Прологе для получения удобного синтаксиса ОО логического языка программирования Description Logics Семейство логик с различными сложностными характеристиками алгоритмов вывода, пригодные для описания структур объектов в объектной иерархии Используются для представления знаний об объектах при построении онтологий и распределенных хранилищ данных в Semantic Web

5 ©2009 Сошников Д.В. 5

6 6

7 7 Синтаксис Семантика F-структуры и выполнимость формул на F- структурах – аналог понятия интерпретации Семантика предикатов Свойства F-структур Свойства отношений наследования Сколемизация и клаузальная форма Теория доказательства в F-логике Типизированная F-логика

8 ©2009 Сошников Д.В. 8 object(rect(X,Y), [ (area(A):-A is X*Y), (perim(P):-P is 2*(X+Y)) ]). isa(square(X),rect(X,X)). object(point, [ area(0), perim(0) ]). object(circle(R), [ (area(A):-A is R*R), (perim(P):-P is 2*3*R) ]). ?- square(10) --> area(X). X=100 ?- point --> area(X). X=0 parea([],[]). parea([T|R],[T1|R1]) :- T --> area(T1), parea(R,R1). ?- parea( [point,circle(10),square(5)],R). R = [0,100,25] ?

9 ©2009 Сошников Д.В. 9 :-op(25,xfx,'-->'). O --> M :- get_methods(O,L), process(M,L). get_methods(O,L) :- object(O,L). get_methods(O,L) :- isa(O,Z), get_methods(Z,L). process(M,[M|_]). process(M,[(M:-Body)|_]) :- call(Body). process(M,[_|T]):-process(M,T).

10 ©2009 Сошников Д.В. 10 :-op(150,xfx,'==>').% Вычисление метода :-op(150,xfx,'::').% IS-A :-op(150,xfx,':::').% Транзитивное замыкание IS-A A:::B :- A::B. A:::C :- A::B, B:::C. c1::circle.c2::circle. r1::rect.s1::square. C==>area(A) :- C:::circle, !, C==>radius(R), A is R*R. P==>area(0) :- P:::point. S==>height(X) :- S:::square,!,S==>side(X). S==>width(X) :- S:::square,!,S==>side(X). R==>area(X) :- R:::rect, !, R==>height(H), R==>width(W), X is H*W. c1==>radius(10). c2==>radius(20). r1==>height(15). r1==>width(15). s1==>side(5). point::figure. circle::point. rect::figure. square::rect.

11 ©2009 Сошников Д.В. 11 calc_area([]). calc_area([H|T]):- H==>area(X), write(H), write('==>area = '), write(X), nl, calc_area(T). ?- calc_area([c1,r1,s1]). c1==>area = 100 r1==>area = 225 s1==>area = 25

12 ©2009 Сошников Д.В. 12 Пролог обладает развитыми средствами метапрограммирования, за счёт этого реализация расширений языка достаточно проста Мы можем легко расширить Пролог объектно-ориентированными возможностями с поддержкой наследования и полиморфизма Теоретическое исследование связи логики предикатов и принципов ООП содержится в работах M.Kifer по F-логике

13 ©2009 Сошников Д.В. 13 Концепты предметной области (сущности) Связи между ними Атрибуты Ограничения (свойства)

14 ©2009 Сошников Д.В. 14 Worker = Employee { E | P : Works-for } Worker (E) = Employee(E) (( P)Works-for(E,P)) Worker = Employee Works-for

15 ©2009 Сошников Д.В. 15 PARENT = PERSON CHILD PARENT_OF_FEMALES = PERSON CHILD.FEMALE

16 ©2009 Сошников Д.В. 16 А является подчиненным концептом для B (A B, B subsumes A), если A является частным случаем B Пример: PERSON CHILD PERSON PARENT CHILD.FEMALE PARENT PERSON CHILD.FEMALE PARENT ???

17 ©2009 Сошников Д.В. 17 Семантикой дескриптивной логики называется I = I - область интерпретации, множество всех объектов предметной области I - функция интерпретации, которая отображает Каждый концепт на подмножество I Каждую роль на подмножество I I

18 ©2009 Сошников Д.В. 18

19 ©2009 Сошников Д.В. 19 Концепт задается предикатом принадлежности C c(X) Роль задается двухместным предикатом R r(X,Y) C D c(X) Λ d(X) R ( Y) r(X,Y) R.C ( Y) r(X,Y) c(Y) A B ( X) a(X) b(X)

20 ©2009 Сошников Д.В. 20 Subsumption problem – определение того, что один концепт является подмножеством другого Проблема противоречивости БЗ База знаний строится из A-Box – база фактов о конкретных индивидах T-Box – правила, задающие отношения на концептах предметной области

21 ©2009 Сошников Д.В. 21 person(anna). person(mitya). person(vickie). person(lena). child(anna,mitya). child(mitya,vickie). child(lena,boris). male(boris). female(lena). female(vickie). parent(X) :- person(X), child(X,_). fparent(X) :- person(X), child(X,Y), female(Y). :- op(200,yfx,'and'). exec(V,and(X,Y)) :- !, exec(V,X), exec(V,Y). exec(V,some(X)) :- !, call(X,V,_). exec(V,all(Y,C)) :- !, call(Y,V,Z),call(C,Z). exec(V,Z) :- call(Z,V). ?- exec(X,person and all(child,female)). X = mitya ? ?- exec(X,person and some(child)). X = anna ? ; X = mitya ? ; X = lena

22 ©2009 Сошников Д.В. 22

23 ©2009 Сошников Д.В. 23

24 ©2009 Сошников Д.В. 24 В зависимости от экспрессивности DL имеют различную сложность алгоритма вывода, от полиномиальной (FL-) до экспоненициальной (SHIQ). Возможно выбирать логику, выразительных возможностей которой хватает для решения задачи На практике DL применяются в Semantic Web для описания распределенных знаний

25 ©2009 Сошников Д.В. 25 Эволюция всемирной паутины: 1. Сеть для передачи данных между машинами (Web 0.0) 2. Сеть, являющаяся универсальным хранилищем данных (Web 1.0) 3. Сеть, как платформа для хостинга приложений (Web 2.0) 4. Сеть, являющаяся универсальным хранилищем знаний (Web 3.0)

26 ©2009 Сошников Д.В. 26 «В ближайшие 10 лет Semantic Web произведет такую же революцию в Интернет, как в свое время создание всемирной паутины» Тим Бернес Ли, создатель всемирной паутины, ~2000 г.

27 ©2009 Сошников Д.В. 27 Сделать паутину понимаемой не только людьми, но и агентами Унифицировать семантику на основе URI Способ аннотации веб-ресурсов на основе семантического описания

28 ©2009 Сошников Д.В. 28 Ключевые свойства Semantic Web: Повсеместное использование URI Повсеместное использование машинно- обрабатываемых форматов описания Формальная математическая основа

29 ©2009 Сошников Д.В. 29 Три языка, каждый реализующие всё более сложные конструкции XML-ориентированные Система универсальной квалификации имён на основе URI Чётко определённая математическая семантика на основе дескриптивных логик RDF, RDF-S, OWL

30 ©2009 Сошников Д.В. 30

31 ©2009 Сошников Д.В. 31 Представление (мета)информации на основе троек «объект-атрибут-значение» Составная часть тройки URI, как универсальный идентификатор "Tony Benn"

32 ©2009 Сошников Д.В Jan 13, /terms/creation-date /1.1/creator Jan 13, January 13, 2007

33 ©2009 Сошников Д.В. 33 Отображения RDF: RDF Graph RDF-Triple, простой язык троек RDF-XML, вариант на основе XML

34 ©2009 Сошников Д.В Jan 13, 2007 ex:creation-date RDF#Bag dc:creators RDF#type _1 ex: ex:homePage _2 Andrey Ustyuzhanin ex:fullName

35 ©2009 Сошников Д.В. 35 RDF-S, или RDS Schema: методика описания «типов данных» для RDF Иерархия типов (наследование) Иерархия отношений Области определений и значений для отношений RDF-S это RDF, с использованием определённых спецификацией отношений

36 ©2009 Сошников Д.В. 36 OWL: методика описания «типов данных» в терминах уже определённых типов данных RDF-S: Тип «Покупатель» подкласс типа «Человек», расширяющий его свойством «покупки» OWL: Тип «ЦелевойПокупатель» такой подкласс типа «Покупатель», для которого значение свойства «покупки» содержит более 3 пунктов

37 ©2009 Сошников Д.В. 37 Три вложенных подмножества по выразительности: OWL Lite, логика SHIF(D) полиномиальная вычислимость OWL DL, логика SHOIN(D) экспоненциальная вычислимость OWL Full, логика SHIQ(D) NP­сложная вычислимость

38 ©2009 Сошников Д.В. 38 Модели с недостаточно чёткой формализацией нежизнеспособны: Семантические сети Многоуровневые сценарии Семейство языков Semantic Web создавалось на основе соответствующего формализма Дескриптивные логики

39 ©2009 Сошников Д.В. 39 Не всё так гладко, как в теории...