Нахождение минимального по мощности алфавита для дерева Линдона

Пермяков Николай Евгеньевич

Аннотация


Пермяков Н.Е. НАХОЖДЕНИЕ МИНИМАЛЬНОГО ПО МОЩНОСТИ АЛФАВИТА ДЛЯ ДЕРЕВА ЛИНДОНА, квалификационная работа: 22 стр.
Ключевые слова: СТРИНГОЛОГИЯ, СТРОКА ЛИНДОНА, ДЕРЕВО
ЛИНДОНА.
В процессе работы были реализованы точный алгоритм нахождения
минимального алфавита для дерева Линдона и приблизительный жадный
алгоритм, доказана корректность этих алгоритмов.
Доказана оценка среднего времени работы модифицированного точного алгоритма для проверки алфавита из 3 букв на случайных деревьях.
Были собраны экспериментальные данные для жадного алгоритма, по
которым можно наблюдать его среднюю относительную ошибку.