name: РАЗРАБОТКА И ОЦЕНКА СЛОЖНОСТИ АЛГОРИТМОВ, НАХОДЯЩИХ ПРИМЕНЕНИЕ В АППАРАТНОМ И ПРОГРАММНОМ ОБЕСПЕЧЕНИИМНОГОПРОЦЕССОРНЫХ СИСТЕМ
keyword_list: ГРАФ КЭЛИ, аЛГОРИТМ, тОПОЛОГИИ, СИНТАКСИЧЕСКИЙ АНАЛИЗ, СЛОЖНОСТЬ АЛГОРИТМА, МНОГОПРОЦЕССОРНАЯ СИСТЕМА, вЫЧИСЛИТЕЛЬНАЯ СЛОЖНОСТЬ
abstract: Диссертационная работа посвящена актуальной теме, связанной с созданием алгоритмов, находящих применение в программном и аппаратном обеспечении многопроцессорных вычислительных систем (МВС). В диссертации разработан новый эффективный алгоритм, позволяющий вычислять кратчайшие маршруты между вершинами графа Кэли, заданного произвольной конечной группой подстановок. Этот алгоритм имеет линейную вычислительную сложность, в то время как другие известные алгоритмы обладают квадратичной сложностью. При помощи МВС вычислены ранее неизвестные характеристики некоторых больших графов Кэли. Данные графы могут найти применение при разработке перспективных топологий МВС. Впервые разработан беступиковый алгоритм синтаксического анализа, использующий иерархию маркированных скобок и позволяющий решать расширенную проблему синтаксического анализа. Также получена оценка сложности данного алгоритма. Этот алгоритм может найти применение при разработке языков программирования для МВС.
chairman_dissertation_council.surname: Цибульский Г. М.
chairman_dissertation_council.position: профессор
chairman_dissertation_council.degree: Доктор технических наук
organization_supervisor.surname: Румянцев М. В.
organization_supervisor.position: ректор
organization_supervisor.degree: Кандидат философских наук
rubrics.code: 20.53.01
rubrics.name: Общие вопросы
oecds.code: 01.02.EX
oecds.name: COMPUTER SCIENCE, THEORY & METHODS
speciality_codes.name: Теоретические основы информатики
speciality_codes.code: 05.13.17
supervisors.fio: Кузнецов А.А.
supervisors.scientific_degree: Доктор физико-математических наук
supervisors.speciality_code: Системный анализ, управление и обработка информации (по отраслям)
supervisors.responsible_type: Научный руководитель
opponents.fio: Винокуров С.Ф.
opponents.scientific_degree: Доктор физико-математических наук
opponents.speciality_code: Дискретная математика и математическая кибернетика
opponents.responsible_type: Оппонент
opponents.fio: Овчаренко А.Ю.
opponents.scientific_degree: Кандидат технических наук
opponents.speciality_code: Теоретические основы информатики
opponents.responsible_type: Оппонент
protection_organization.short_name: ФГАОУ ВО "Сибирский федеральный университет", Сибирский федеральный университет, СФУ
protection_organization.name: Федеральное государственное автономное образовательное учреждение высшего образования "Сибирский федеральный университет"
protection_organization.ogrn: 1022402137460
protection_organization.organization_type: Организация
protection_organization.okogu: Министерство науки и высшего образования Российской Федерации
protection_organization.okopf: Федеральные государственные автономные учреждения
author_organization.short_name: Сибирский университет науки и технологий; СибГУ им. М.Ф. Решетнева
author_organization.name: Федеральное государственное бюджетное образовательное учреждение высшего образования "Сибирский государственный университет науки и технологий имени академика М.Ф. Решетнева"
author_organization.ogrn: 1022402056038
author_organization.organization_type: Организация
author_organization.okogu: Министерство науки и высшего образования Российской Федерации
author_organization.okopf: Федеральные государственные бюджетные учреждения