Тип публикации: диссертация
Год издания: 2020
Ключевые слова: граф Кэли, алгоритм, топологии, синтаксический анализ, сложность алгоритма, многопроцессорная система, вычислительная сложность
Аннотация: Диссертационная работа посвящена актуальной теме, связанной с созданием алгоритмов, находящих применение в программном и аппаратном обеспечении многопроцессорных вычислительных систем (МВС). В диссертации разработан новый эффективный алгоритм, позволяющий вычислять кратчайшие маршруты между вершинами графа Кэли, заданного произвольПоказать полностьюной конечной группой подстановок. Этот алгоритм имеет линейную вычислительную сложность, в то время как другие известные алгоритмы обладают квадратичной сложностью. При помощи МВС вычислены ранее неизвестные характеристики некоторых больших графов Кэли. Данные графы могут найти применение при разработке перспективных топологий МВС. Впервые разработан беступиковый алгоритм синтаксического анализа, использующий иерархию маркированных скобок и позволяющий решать расширенную проблему синтаксического анализа. Также получена оценка сложности данного алгоритма. Этот алгоритм может найти применение при разработке языков программирования для МВС.