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