|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
О программной реализации сравнения кодируемых регулярных языковдипломная работа (Бакалавр)
- Научный руководитель: Дергач П.С.
- Автор: Шевцова Ангелина Андреевна
- Тип: Бакалавр
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2020
- Аннотация: В работе А. Шевцовой решается следующая задача. Дана пара A,B регулярных языков в алфавите {0,1}. Говорим, что функция алфавитного кодирования f:{0,1}->{0,1}* допустима для языка, если она на нем однозначно декодируема. Нужно проверить на вложимость класс допустимых кодирований первого языка с классом допустимых кодирований второго языка. Студентка должна была разобраться в решении этой задачи, взятом из диссертации научного руководителя, и написать реализующую соответствующий алгоритм программу. В паре с ней работала студентка магистратуры Рахматова Валерия. Распределение обязанностей между ними было следующим: Ангелина пишет программу и общую описательную часть алгоритма. Валерия пишет математическую составляющую, доказывающую корректность используемого алгоритма. Для упрощения задачи студентке было разрешено считать, что шаги 1 и 2 уже выполнены. То есть ей уже на вход программы подается примитивный язык с полиномиальной функцией роста. Ей необходимо было выполнить шаги 3,4,5. Это было успешно реализовано в данной работе. Написана соответствующая программа.
- Добавил в систему: Дергач Пётр Сергеевич