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