МЛиТА-2018‎ > ‎

Задания от Григорьева

Задачи.

Общий контекст данных задач --- поиск путей с ограничениями в терминах формальных граммтик в графах.   

1) Более теоретические
-  Переход от произвольных контекстно-свободных ограничений к ограничениям в форме языка Дика на двух типах скобок. Существует идея того, как свести произвольные КС-ограничения к ограничениям в терминах языка Дика на k типах скобок (для некоторого не фиксированного k, зависящего от изначальной граммтики): https://github.com/YaccConstructor/articles/blob/master/InProgress/Rytter_for_CFPQ/Rytter_for_CFPQ.pdf. Данная идея эксплуатирует теоремму Хомского-Шузенбергенра о представлении КС языков. Также существеут вариант доказательства этой теоремы, показывающий, что достаточно ровно двух типов скобок (Theorem 10.4.3 в "Introduction to Formal Language Theory" (Addison-Wesley series in computer science) by Michael A. Harrison). Предлагается совместить эти результаты и построить алгоритм сведения кроизвольных КС ограничений к ограничениям в виде языка Дика на двух типах скобок.

- Построение группы по языку. Предлагается взять статью https://arxiv.org/abs/math/9811105, в которой, кроме всего прочего, показывается, как по машине Тьюринга можно построить группу с языком, равным языку, принимаемому исходной машиной, и для фиксированного языка проделать цепочку (Грамматика языка -> машина Тьюринга, распознающая данный язык -> S-машина -> группа). Варианты языков
   - Существенно-неоднозначный контекстно-свободный язык
   - Недетерминированный однозначный контекстно-свободный язык
   - a^n b^n c^n
   - |a|=|b|
   - a^n b^n
   - Язык Дика на k типах скобок
   - a^n b^m c^n d^ m

2) Более практические.
Существует алгоритм поиска путей в графах с ограничениями в терминах конъюнктивных граммтик, основанный на операциях с булевыми матрицами (http://www.ispras.ru/proceedings/isp_30_2018_2/isp_30_2018_2_149/). Предлагается изучить данный алгоритм и создать его высокопроизводительные реализации.
- На центральном процессоре, на основе высокопроизводительной библиотеки для перемножения булевых матриц (реализует вариант алгоритма четырёх русских). Для этого портебуется расширить библиотеку недостающими операциями (поэлементное сложение, подсчёт кол-ва ненулевых элементов и т.д.) и реализовать на основе расширенной библиотеки сам алгоритм поиска путей. Потребуется хорошее знание языка C. Ссылка на GitHub: https://github.com/YaccConstructor/YaccConstructor/issues/320
- На графическом процессоре. Здесь потребуется найти или реализовать библиотеку высокопроизводительных матричных операций на графическом процессоре для булевых матриц и реализовать на основе этой библиотеки сам алгоритм поиска путей. Потребеутся хрошее знание язака Cuda C или OpenCL C. Ссылка на GitHub: https://github.com/YaccConstructor/YaccConstructor/issues/321

Комментарии.
1) Вероятно, будет иметь смысл организовать встречу со студентами. Либо для представления задач, либо уже для ответа на вопросы тех, кто их выберет (если таковые найдуться). Наверняка будут вопросы по содержанию задач. Организационные вопросы (формат взаимодействия со студентами) тоже нужно будет решить. Я готов подъехать в ЛЭТИ для этого.

Regards,
Semyon Grigorev.
Comments