Аннотация:В работе Алтынай Сабитовой исследуется следующая задача. Имеется клеточный автомат на плоскости. Начальная конфигурация представляет собой связную фигуру, и все автоматы в клетках этой конфигурации кроме одной находятся в одинаковом состоянии, называемом черным. Одна клетка конфигурации будет красной. Клетки в состоянии покоя будем считать белыми. Надо закрасить черным цветом все внутренние дыры исходной конфигурации. Предложен алгоритм решения этой задачи. Начиная с красной клетки, и идя вдоль горизонтали, находится граничная точка. Далее автомат движется вдоль границы, закрашивая ее, и подсчитывая углы, понимает это внешняя граница или внутренняя. Если внутренняя, то ищется следующая граничная точка, и так до тех пор, пока не будет построена внешняя граница фигуры. Далее закрашиваются все точки, которые находятся внутри этой границы. Доказаны теоремы о правильности работы алгоритма и получены оценки времени работы алгоритма, пропорциональные размеру фигуры. Для клеточных автоматов с локаторами предложено 2 алгоритма. Время работы первого алгоритма пропорционально количеству внешних углов фигуры. Время работы второго алгоритма пропорционально количеству поворотов во внутреннем лабиринте. Внутренний лабиринт – это часть внешней области, которая фактически врезается внутрь фигуры. Тем самым для фигур без внутреннего лабиринта второй алгоритм решает задачу за константное время.