|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
О проверке вложимости классов допустимых функций кодирования регулярных языковкурсовая работа (Магистр)
- Научный руководитель: Дергач П.С.
- Автор: Рахматова В. С.
- Тип: Магистр
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Кафедра: Филиал МГУ в г. Ташкент
- Год защиты: 2019
- Курс: 1
- Аннотация: Курсовая работа Валерии Рахматовой связана со следующей задачей. Даны два регулярных языка и для каждого из них строится класс схем кодирования, однозначных на языке. Такие функции называем допустимыми для языка. Необходимо найти алгоритм проверки вложения таких классов. Алгоритмическая разрешимость данной задачи доказана в кандидатской диссертации научного руководителя.Однако,для практической реализации его нужно было оптимизировать, чем и занялась Валерия. Поскольку алгоритм в целом содержит множество шагов, на первой стадии работы Валерии нужно было реализовать следующую подзадачу. Считаем, что по регулярному языку P уже кем-то до нас неким образом построено конечное объединение C одноэлементных пучков (т.е. множеств неотрицательных точек на целочисленной плоскости, имеющих вид (a+bn,c+dm) с конкретными значениями a,b,c,d и произвольными m,n ∈N+.) Строятся всевозможные отрицательные тангенсы угла наклона прямых, проходящих через пары точек этого объединения. Обозначаем это множетсво через H(C). Необходимо проверить вложимость H(C1) ⊆ H(C2). Магистрантка разбила эту задачу на два этапа. Первый этап — представить множество H(C) в удобном для проверки вложения виде (ведь это, вообще говоря, бесконечные множества и напрямую вложимость не проверить).Второй этап—проверить вложимость полученных представлений. С первым этапом Валерия справилась и представила H(C) в виде конечного объединения рациональных дробей вида a+bn c+dm, где m,n ∈N+.
- Добавил в систему: Дергач Пётр Сергеевич