Аннотация:Данная работа состоит из двух частей. Первая часть о накрытии
семейства натуральных чисел с рядом ограничений. В этой части работы было доказано несколько утверждений и свойств арифметических
прогрессий, также использовались результаты работы [1]. В частности,
было доказано, что попарно пересекающиеся прогрессии пересекаются
в совокупности. Формулировка задачи первой части дипломной работы, следующая: пусть дано два непересекающихся непустых множества
натуральных чисел. Необходимо накрыть первое из множеств арифметическими прогрессиями так, чтобы при этом не накрыть никакой из
элементов второго множества. Главной целью этой задачи был вопрос
нахождения минимального количества элементов второго множества,
чтобы при этом максимизировать количество прогрессий, накрывающих первое множество. Была получена оценка в лучшем случае и верхняя и нижняя оценки на функцию Шеннона для худшего случая.
Во второй части работы описывается правильная линейная форма
для регулярных языков с полиномиальной функцией роста. Были улучшены некоторые результаты, полученные в работе [2]. Главной целью
этой части работы было установить, насколько увеличивается длина
регулярного выражения линейного вида при привидении этого выражения к правильному линейному виду и улучшение квадратичной оценки
полученной в [2]. Результатом решения этой задачи стало получение
верхних и нижних оценок для худшего случая, как и в первой части
работы.
Ключевые слова: натуральный ряд, арифметическая прогрессия, накрытие, правильная линейная форма, регулярные
языки.