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

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

Требования к студенту
  • Отличное знание языка программирования Python: алгоритмическое программирование, средства разработки, тестирования, отладки.
  • Отличное знание основ теории графов: матрица смежности, обходы графов, задачи поиска путей и алгоритмы для их решения.
  • Основы теории формальных языков: конечные автоматы, контекстно-свободные грамматики.
  • Основы линейной алгебры; матрицы, вектора, операции над матрицами и векторами.
Уровень

2 курс

Руководитель

Григорьев Семен Вячеславович

Консультант

Grigorev Semyon

Источник

Кафедра системного программирования СПбГУ