Одним из главных принципов уникальной «системы Физтеха», заложенной в основу образования в МФТИ, является тщательный отбор одаренных и склонных к творческой работе представителей молодежи. Абитуриентами Физтеха становятся самые талантливые и высокообразованные выпускники школ всей России и десятков стран мира.

Студенческая жизнь в МФТИ насыщенна и разнообразна. Студенты активно совмещают учебную деятельность с занятиями спортом, участием в культурно-массовых мероприятиях, а также их организации. Администрация института всячески поддерживает инициативу и заботится о благополучии студентов. Так, ведется непрерывная работа по расширению студенческого городка и улучшению быта студентов.

Адрес e-mail:

Дескрипционные логики и их сложность (С.П. Кикоть, весна 2015)

Лектор — С.П. Кикоть

Спецкурс проходит по вторникам в 18:30 в офисе ABBYY в ауд. 2-16. Нужны пропуска.

Анонс

Дескрипционные логики возникли как логические формализмы для представления знания. Они представляют собой языки (в сущности, фрагменты логики первого порядка) для создания онтологий — набора логических аксиом и определений, связывающих между собой понятия естественного языка. Онтологии могут быть существенной частью информационных систем нового поколения, так как позволяют осуществлять <<интеллектуальный>> поиск информации в базе знаний, то есть использующий логические связи между понятиями естественного языка. Примером такой информационной системы может служить база данных информации о белках Amigo, в которой белки размечены при помощи онтологии GO (Gene Ontology), содержащей структурированную информацию о частях клетки, биологических процессах и биохимических реакциях. За последние 15 лет были описаны несколько десятков языков различной выразительной силы, и для каждого из них были получены результаты о вычислительной сложности традиционных задач — проверки базы знаний на совместность, включения концептов, ответов на конъюнктивные запросы. Некоторые из этих языков приняты W3C в качестве стaндарта для создания онтологий. На основе алгоритмов дескрипционной логики в европейских университетах созданы десятки ризонеров — програмных продуктов, позволяющие проводить логические рассуждения в онтологиях (в частности, проверять их совместность, строить классификацию концептов по включению, извлекать модули).

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

Программа курса

  1. Парадигма дескрипционной логики. Базы знаний. Онтологии. Концепты. Различные дискрипционные логики (ALC, EL, SHIQ, SROIQ). Типичные задачи дискрипционной логики: включение концептов, совместность базы знаний, и их связь.
  2. Сложностные классы P, NP, PSPACE, EXPTIME. Типичные P-, NP-, PSPACE- и EXPTIME-полные задачи, используемые при анализе сложности логических фрагментов.
  3. Сложность модальной логики Kn и дескрипционной логики ALC.
  4. Сложность модальной логики Ku (K с универсальной модальностью) и дескрипционной логики SHIQ.
  5. Конъюнктивные запросы в дескрипционных логиках. Сложность по данным и комбинированная сложность. Конъюнктивные запросы в логике EL.
  6. Сложность ответов на конъюнктивные запросы в S, ELI, ALC, ALCI и QIO.
  7. Дескрипционные логики с AC0 сложностью по данным. OWL 2 QL. Переписывания конъюнктивных запросов.
  8. Нижние оценки на длину переписывания конъюнктивных запросов относительно OWL 2 QL для теорий неограниченной глубины.
  9. Нижние оценки на длину переписывания конъюнктивных запросов относительно OWL 2 QL для теорий глубины 1 и 2.
  10. Регулярные путевые запросы. Сложность ответов на регулярные путевые запросы в различных дескрипционных логиках.
  11. Сложность следующей задачи: по онтологии в более широком языке определить, можно ли ее переписать в более узком.
  12. Интерполяция в дескрипционной логике и извлечение модулей из онтологий.

Литература

Дескрипционные логики:

Сложность вычислений:

Полезные сетевые ресурсы:

Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

© 2001-2016 Московский физико-технический институт
(государственный университет)

Техподдержка сайта

МФТИ в социальных сетях

soc-vk soc-fb soc-tw soc-li soc-li
Яндекс.Метрика