|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Конструирование изображений клеточными автоматамидипломная работа (Специалист)
- Научный руководитель: Гасанов Э.Э.
- Автор: Титова Елена Евгеньевна
- Тип: Специалист
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2009
- Аннотация: В работе Титовой Е.Е. рассматривается следующая задача. Имеется прямоугольник размера n x m из n m одинаковых элементарных автоматов. Множество состояний элементарного автомата – это множество Ek={0,1,…,k-1}. Каждый элементарный автомат имеет 4 входа и на эти входы подаются состояния четырех соседних автоматов (левого, правого, верхнего и нижнего). На нижний вход самых нижних автоматов и правый вход самых правых автоматов подается тождественный ноль. Левые входы самых левых автоматов и верхние входы самых верхних автоматов являются свободными управляющими входами. Описанная выше конструкция называется n x m-экраном. Изображение – это произвольная n x m матрица из 0 и 1. Скажем, что некоторое изображение реализуемо данным экраном, если существует такая последовательность управляющих входов, что на экране через некоторое время возникает матрица состояний, идентичная изображению, и это распределение состояний в дальнейшем удерживается сколь угодно долго. Скажем, что n x m-экран универсальный, если с помощью его реализуемо любое n x m-изображение, элементарный автомат, соответствующий универсальному экрану, называется универсальным. Задача состоит в построение универсального элементарного автомата, оценке числа его состояний и оценке времени построения изображений. Показано, что минимальный универсальный автомат необходимо имеет 3 состояния и такой автомат построен. Но для минимального автомата время конструирования изображение равно 3nm. Показано, что время построения самого плохого изображения не может быть меньше, чем min(n,m), и построен универсальный автомат, обеспечивающий такое время. Но недостатком последнего автомата является то, что с ростом min(n,m) растет число состояний этого автомата. Построен автомат с 5 состояниями, обеспечивающий время построения изображений, равное 2 min(n,m). Также построен автомат с 4 состояниями, обеспечивающий время построения изображений, равное n+m.
- Добавил в систему: Гасанов Эльяр Эльдарович