- Выявление "многозначных" слов. Многие слова естественного языка имеют более одного значения (наприер, коса) или могут называть различные объекты (истребитель "Тайфун", роман "Тайфун"). Один из метдов выявления таких слов состоит в нахождении множества слов, характеризующих конкретное значение. Например, для слова коса такими словами могут являться берег и волосы, прическа. Задача состоит в автоматическом построении указанных множеств. Смежной является задача определения конкретного значения слова в тексте. Область применения таких задач — текстовый поиск: в результат выдачи поисковый системы попадают только те документы, которые содержат слова в нужном значении.
- Определение семантической близости между словами. Насколько заданные слова близки по смыслу (сено и солома)? При этом сравниваемые слова могут быть многозначными.
- Выделение фактов. По заданному предложению необходимо определить, является ли оно описанием какого-либо события, и представить его в виде набора (что, где, когда).
- Выявление заданных отношений (например, общее-частное) между словами. Можно ли автоматически определить, что стол является мебелью?
- Разрешение анафоры. В тексте могут встречаться выражения, которые невозможно проинтерпретировать без обращения к предыдущему контексту. Например, местоимение он. Задача состоит в разработке методов автоматического поиска антецедента. (См. Разрешение анафоры).
Темы курсовых работ
Автоматическая обработка текстов
В области "понимания" естественного языка возникает множество задач, которые решают либо с использованием экспертных знаний
(например, в ручную составленных словарей), либо путем автоматического анализа большого количества текстов (корпуса). В качестве примера
можно привести следующие задачи.
Рациональные множества регулярных языков
Пусть задано n-элементное множество A={a1,..., an}. Сопоставим каждому элементу A регулярный язык в некотором алфавите B. Пусть V1,..., Vn — образы букв алфавита A. Тогда слову w=ak1 ... akm в A соответствует язык Vk1⋅ ... ⋅ Vkm (конкатенация образов букв), а множеству слов в A — множество языков в алфавите B. Рациональное множество регулярных язков суть образ регулярного языка в A. Такое множество задается парой (φ, R), где φ:A → Reg(B) — подстановка языков, а R — регулярный язык в A.
Пусть заданы множества R=(φ, R), R1=(φ, R1), R2=(φ, R2) и S=(φ, A∗). Возникают следующие алгоритмические задачи.
- Существует ли алгоритмы, проверяющие:
- принадлежность языка X∈Reg(B) множеству R?
- равенство R1=R2?
- равенство R=S (полнота R)?
- существование слов w1, w2∈R для которых φ(w1) = φ(w2)?
- Существуют ли указанные алгоритмы при условии, что языки V1,..., Vn имеют специальный вид, например, конечны?
- Какова минимальная мощность алфавита A, необходимая для представления множества R?
- Можно ли по заданной подстановке φ предварительно вычислить некоторые данные, которые позволят для любых слов w1 и w2 эффективно проверять равенство φ(w1)=φ(w2)?
Задачи, связанные с разложением регулярных языков на множители, возникают во многих прикладных областях, включая обработку запросов к базам данных, поиск вирусов, проектирование микросхем.
Анализ структуры социальных сетей
Рассмотрим ориентированный граф, вершины которого соответствуют пользователям социальных сетей, а ребра отражают
отношение "дружбы" между пользователями.
- Выделение сообществ: требуется выделить множества вершин, удовлетвоярющих определенным условиям. Например, для заданной вершины v и натурального k найти максимальное подмножество S вершин графа, которое содержит v и любая пара вершин которого соединена по крайней мере одним путем длины k, проходящим только по S.
- Определение путей распространения информации: по каким путям сообщения распространяются в сети? С какой скоростью? Какие участники сети являются ключевыми? Как определить круг читателей заданной вершины?
Информационная безопасность (логическое разграничение доступа)
Актуальным направлением развития систем управления доступом в информационных системах являются модели доступа, учитывающие значения атрибутов объектов (attribute-based access control = ABAC). Политика информационной безопасности задается набором правил, включающих логические условия на значения атрибутов. Пример: "сотрудники службы поддержки моложе 25 лет имеют право удалять файлы, созданные руководителями подразделений и превышающие по размеру 1Мб, только с 9 до 17 часов". Правила могут быть как разрешающими, так и запрещающими. В общем случае решение о предоставлении доступа зависит от значений свойств объекта, субъекта (обычно – пользователя, который запрашивает выполнения операции) и контекста. В приведенном примере свойства субъекта – это принадлежность службе поддержки и возраст, свойства объекта – создатель и размер файла, контекст – время выполнения операции. Подобные описания должны быть представлены в некотором формальном виде, пригодном для автоматической обработки.
Возможными задачами являются:
- разработка эффективного алгоритма проверки прав доступа, минимизирующего количество обращений к данным (значениям атрибутов);
- проверка корректности политики безопасности: может ли злоумышленник получить доступ, выполнив последователььность разрешенных действий;
- оптимизация политики безопасности (построение эквивалентного, но более простого набора правил).
