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


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

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

В данной работе рассматривается одномерная сеть клеточных автоматов (СКА), любой из которых может иметь два состояния "О" или "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

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

Измеритель угловых скоростей на основе неортогонально ориентированной гексоды ДУСов с электрическими обратными связями для космического корабля
Бесплатформенные инерциальные навигационные системы на пилотируемых космических объектах впервые были применены РКК «Энергия» в 1974 году. С 1982 года в системе управления космическими аппаратами (КА) «Союз» и «Прогресс» применяется трехкомпоне ...

Синтез логической схемы цифрового устройства
Выполнить синтез логической схемы цифрового устройства, имеющего 4 входа и 2 выхода, по заданным условиям его работы в виде таблицы истинности (прил.1). Выход F определяется по первой цифре номера варианта, а Q-по второй цифре варианта. Для ...

© Copyright 2023 | www.techattribute.ru