Основные разделы


Двумерный клеточный автомат

Клеточный автомат (КА) может быть описан с помощью определения следующих основных свойств: окрестности, количества состояний КА, функции, с помощью которой клеточный автомат вычисляет свое последующее состояние (в дальнейшем - правило). Варьируя эти свойства можно получить широкий спектр КА.

В данной работе рассматривается одномерная сеть клеточных автоматов (СКА), любой из которых может иметь два состояния "О" или "1" на каждом такте функционирования сети. Окрестность определяется множеством соседних клеток, от состояния которых зависит последующее состояние данной клетки, а также диапазоном правил, используемых при настройке КА. Впервые определение окрестности было дано Фон Нейманом [4]. Окрестность Фон Неймана включает наиболее близко расположенные физически соседние клетки.

Рассмотрим клеточные автоматы с двумерными решётками из правильных многоугольников, которые встречаются на практике чаще всего. Возможны всего три таких решётки: треугольная (рис.1.1), квадратная (рис.1.2) и гексагональная (рис.1.3). Ниже последнее утверждение будет доказано.

Рисунок 1.1 - Треугольная решетка клеточного автомата

Рисунок 1.2 - Квадратная решетка клеточного автомата

Рисунок 1.3 - Гексагональная решетка клеточного автомата

Теорема 1. Не существует другой решётки из правильных многоугольников, кроме треугольной, квадратной и гексагональной.

Доказательство:

Сумма углов правильного n-угольника . Тогда - величина каждого угла этого n-угольника. Пусть из правильных n-угольников удалось составить решётку. Тогда в ней угол в 2π радиан составляют углы целого числа (обозначим его k) фигур. То есть, k многоугольников можно составить так, чтобы они имели общую вершину. Найдём это k, как функцию от n. Это можно сделать из следующего уравнения:

Будем рассматривать эту функцию только при n≥3, так как треугольник - многоугольник с наименьшим количеством вершин. Возьмем производную от k (n) по n:

Очевидно, что при n≥3 функция k (n) убывает, так как . Таким образом, все возможные значения k меньше k (3), то есть шести. К тому же, k (n) > 2, так как

- истинно.

Решётку можно построить, только если целому n будет соответствовать целое k. Из изложенного выше следует, что возможны лишь четыре значения k: 6, 5, 4 и 3. Построим функцию n (k), обратную к k (n), и проверим, каким из возможных значений k соответствует целое n:

Имеем:

- треугольная решётка;

- не целое n, то есть решётку не построить;

- квадратная решётка;

- гексагональная решётка;

Таким образом, действительно возможны только три перечисленные выше решётки из правильных многоугольников.

В нашем случае, окрестность Фон Неймана включает три соседние клетки. В дальнейшем, если рассматривается СКА без специально определенных свойств, имеется в виду одномерная СКА, состоящая из КА, которые имеют два состояния, с взаимосвязями между клетками, определенными для окрестности Фон Неймана.

На рис.1.4 показана структура одномерной линейной СКА, длинны n, с нулевыми граничными условиями.

Перейти на страницу: 1 2 3

Прочитайте еще и эти статьи:

Имитационное и аналитическое моделирование преобразователя частоты
Преобразователь частоты применяется, главным образом, в супергетеродинных радиоприёмниках, а также в различных радиоизмерительных приборах - селективных вольтметрах, анализаторах спектра, модулометрах и девиометрах, установках для измерения ...

Разработка операционного устройства
Любой сложный преобразователь дискретный информации может быть представлен в виде совокупности операционных устройств (ОУ) и интерфейса (сопряжения этих устройств). Функцией ОУ является выполнение фиксированного множества операций F={f1, f2., ...

© Copyright 2020 | www.techattribute.ru