|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
Конструирование конфигураций на плоскости автоматом с краскамидипломная работа (Бакалавр)
- Научный руководитель: Волков Н.Ю.
- Автор: Миндуллин Марат Халилович
- Тип: Бакалавр
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова, Филиал МГУ в г. Ташкенте
- Год защиты: 2021
- Аннотация: Рассматривается целочисленная плоскость и конечный инициальный автомат с красками, передвигающийся по ней и рисующий изображение – «конфигурацию». Клетка считается лежащей в конфигурации, конструируемой автоматом с краской, если она, начиная с какого-то момента имеет цвет, отличный от нейтрального (белого). Не принадлежат конфигурации клетки, которые бывают белыми бесконечное множество тактов. Целью работы является расслоить множество всех подмножеств целочисленной плоскости на конструируемые и неконструируемые автоматом с краской. Доказано, что все конечные множества и алгебраические дополнения к конечным множествам – конструируемы. Также рассматриваются бесконечные периодические «узоры» на дискретной плоскости: орнаменты (двумерные узоры) и бордюры (одномерные узоры). Строго говоря, бордюр – это множество на Z2, имеющее группу самосовмещений, содержащую параллельный перенос на ненулевой вектор, причем все векторы параллельного переноса в этой группе коллинеарны. Доказано, что любой бордюр и любой орнамент являются конструируемым множеством. Во всех случаях оценена сверху сложность конструирования указанных множеств автоматом с краской. Пока не удалось доказать существование неконструируемых множеств. Но в работе обозначено (на уровне гипотез) движение в эту сторону через выявление тождественности возможностей автомата с краской на плоскости и машины Тьюринга и через существование задач, не решаемых никакой машиной Тьюринга.
- Добавил в систему: Волков Николай Юрьевич
Прикрепленные файлы
| № | Имя | Описание | Имя файла | Размер | Добавлен |
|---|---|---|---|---|---|
| 1. | Mindullin_VKR_03-06-21.pdf | Mindullin_VKR_03-06-21.pdf | 508,4 КБ | 20 декабря 2021 [Volkov_N_Y] |