|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
Об изменении автоматной сложности регулярных языков относительно вставки и обращениядипломная работа (Бакалавр)
- Научный руководитель: Дергач П.С.
- Автор: Бобоев Одилбек Икромович
- Тип: Бакалавр
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2020
- Аннотация: В работе О. Бобоева решается следующая задача. Дано слово длины n. В него разрешается вставлять в любые позиции любые буквы, а также можно инвертировать результат. Необходимо найти оценку на автоматную сложность получившегося множества слов. В работе рассматривается худший случай на такую сложность среди всех слов длины n. Студент смог получить соответствующие оценки. Нижняя – линейна, верхняя – квадратична. Хотелось также понять, в каких случаях реализуется линейная сложность, в каких – квадратичная, но этого сделать не удалось. Все результаты грамотно оформлены и аккуратно доказаны. Нижняя оценка – предъявлением различных остаточных функций, верхняя – приведением распознающего автомата и подсчетом числа его состояний. Для случая, когда все буквы слова различны, студент смог немного понизить верхнюю оценку.
- Добавил в систему: Дергач Пётр Сергеевич