|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Сложность решения некоторых арифметических задач клеточными автоматами и клеточными автоматами с локаторамидипломная работа (Магистр)
- Научный руководитель: Гасанов Э.Э.
- Автор: Шестовских Екатерина Александровна
- Тип: Магистр
- Организация, в которой проходила защита: Институт динамики систем и теории управления имени В.М. Матросова СО РАН
- Год защиты: 2021
- Аннотация: В работе Екатерины Шестовских исследуется задача сравнения сложности решения некоторых простейших арифметических задач с помощью стандартных клеточных автоматов и клеточных автоматов с локаторами. Клеточные автоматы с локаторами отличаются от обычных клеточных автоматов тем, что автоматы могут посылать в эфир некоторые сигналы и получать из эфира суммарный сигнал. Решаются следующие задачи: 1) определение четности числа единиц в начальной конфигурации; 2) перевод числа представленного в виде массива единиц в двоичную запись; 3) сложение чисел, представленных единицами и минус единицами в начальной конфигурации; 4) умножение числа, представленного массивом единиц, на 2. Для каждой задачи предполагалось получить решение клеточными автоматами и клеточными автоматами с локаторами. Также предполагалось получить нижние оценки для обоих случаев, которые доказывали оптимальность по порядку предлагаемых решений. Тем самым предполагалось доказать 16 утверждений: для каждой задачи верхние и нижние оценки для двух типов клеточных автоматов. На данный момент в работе имеется доказательство 4 утверждений.
- Добавил в систему: Гасанов Эльяр Эльдарович