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