Линейная алгебра и мат. Статистика

класс: все клетки быстро принимают одинаковое состояние, которое становится стабильным. 2 класс

жүктеу/скачать 294.26 Kb. бет 27/49 Дата 09.01.2023 өлшемі 294.26 Kb. #468247

Бұл бет үшін навигация:

• 3 класс
• 3-го типа
• Двумерные клеточные автоматы
• Игра «Жизнь» В качестве примера двумерного клеточного автомата рассмотрим игру «Жизнь»
• Параллельная реализация Основная идея распараллеливания

1 класс: все клетки быстро принимают одинаковое состояние, которое становится стабильным. 2 класс: состояние всех клеток быстро стабилизируется, либо возникают периодические колебания. 3 класс: автомат порождает хаотические, непериодические структуры. Небольшие изменения исходного состояния влекут значительные изменения в результате. 4 класс: автомат порождает сложные, взаимодействующие между собой структуры, способные выживать длительное время, однако не достигает стабильности. Наибольший интерес с точки зрения этой классификации представляют автоматы 3-го и 4-го типов. Поведение автоматов третьего типа является хаотическим, даже если начальное состояние является вполне упорядоченным. Пример автомата 3-го типа — автомат с номером 30. Поведение же автоматов четвертого типа является смесью хаотического и детерминированного видов поведения — в процессе эволюции автомата возникают разнообразные структуры, которые взаимодействуют весьма нетривиальным образом. Среди элементарных автоматов таким поведением обладает автомат под номером 110. В частности, только для этого автомата было доказано, что он является алгоритмически универсальным. В 2000 году Мэтью Кук доказал, что этот клеточный автомат является Тьюринг-полным, то есть, на его основе можно реализовать любую вычислимую функцию. Элементарные клеточные автоматы обобщаются либо путем увеличения ранга, либо увеличением числа состояний. И в том, и в другом случае число возможных автоматов оказывается чрезвычайно большим. Нетрудно вывести формулу для числа одномерных клеточных автоматов ранга с числом состояний : Двумерные клеточные автоматы Клетки двумерных автоматов располагаются на плоскости в точках с целочисленными координатами, т. е. образуют прямоугольную решетку. Добавление второго измерения позволяет увеличить размер локальной окрестности клеток и, соответственно, предоставляет больше свободы при построения клеточных автоматов. Существенным отличием двумерных автоматов по сравнению с одномерными является то, что в двумерном случае возможны несколько различных типов локальных окрестностей. Традиционно используются два вида локальной окрестности — фон Неймана и Мура. В окрестности фон Неймана соседями данной клетки являются клетки, имеющие с заданной общую сторону (общее ребро). Таким образом, каждая клетка (за исключением, возможно, граничных клеток) имеет ровно четырех соседей. Если координаты клетки равны , то ее соседи имеют координаты — левый сосед, — правый сосед, — верхний сосед (ось ординат в клеточных автоматах обычно считается направленной вниз), — нижний сосед. В окрестности Мура две клетки являются соседними, если они имеют либо общее ребро, либо общую вершину. Т.е. в локальной окрестности каждой клетки (помимо ее самой) находится восемь клеток. Как видно, размер локальной окрестности двумерных автоматов существенно больше, чем в одномерном случае. Это, в частности, означает, что уже для двоичных двумерных автоматов число возможных наборов правил оказывается слишком большим ( для окрестности фон Неймана, для окрестности Мура) для того, чтобы было провести их полный анализ. Поэтому основным методом изучения двумерных автоматов является их синтез — выбор подходящей конфигурации и разработка набора правил для решения некоторой поставленной задачи (и последующий анализ данного конкретного автомата). Данные выше определения окрестностей можно параметризовать введением ранга. Будем считать, что клетка входит в локальную окрестность ранга клетки , если из можно попасть в сделав не более переходов. Для окрестности фон Неймана переходы выполняются через общую сторону клеток, для окрестности Мура — либо через общую сторону, либо через общую вершину (т. е. по диагонали). Игра «Жизнь» В качестве примера двумерного клеточного автомата рассмотрим игру «Жизнь», придуманную английским математиком Джоном Конвеем в 1970 году. Эта игра представляет собой двоичный двумерный клеточный автомат с окрестностью Мура ранга . Два состояния клеток в этом автомате интерпретируются биологическим образом: — «живая» клетка (или заселенная), изображается чёрным (закрашенным) квадратом; — «мертвая» клетка (или пустая), изображается белым (незакрашенным) квадратом. Правила эволюции этого автомата выглядят следующим образом: Любая живая клетка, у которой меньше двух живых соседей, умирает от «одиночества»; Любая живая клетка, у которой два или три живых соседа, продолжает жить; Любая живая клетка, у которой больше трех живых соседей, умирает от «перенаселенности»; Любая мертвая клетка, у которой ровно три живых соседа, становится живой. Данный автомат имеет 4-й тип по классификации Вольфрама. Любая случайная начальная конфигурация спустя (обычно) небольшое число шагов приводит к появлению простых устойчивых «объектов», либо стационарных, либо периодических, либо движущихся. Простейший движущийся объект — так называемый глайдер (планер) — состоит всего из пяти живых клеток. Благодаря популярным статьям Мартина Гарднера, посвященным игре «Жизнь», к этому автомату было привлечено значительное влияние большого числа исследователей. Их усилиями были исследованы многие начальные конфигурации, получено большое количество устойчивых или движущихся объектов и проанализированы результаты столкновения их между собой. В частности, таким образом были построены объекты, которые генерируют другие объекты, например, глайдеры. Параллельная реализация Основная идея распараллеливания стандартных клеточных автоматов тривиальна — пространство клеток разбивается на непересекающиеся области, каждая область (плюс ее граница, согласно используемому типу локальной окрестности) помещается на отдельный процессорный узел вычислительной системы. На каждом временном шаге эволюции каждый процессор обновляет состояния своих клеток, после чего «соседние» процессоры обмениваются состояниями граничных клеток. Обычно наиболее сложной является как раз стадия коммуникации. Оптимальной схемой распараллеливания двумерных автоматов является разбиение матрицы клеток на горизонтальных полос. Во-первых, такое разбиение минимизирует объем информации, необходимой для пересылки. Во-вторых, оптимизируется работа каждого процессора, т. к. внутренний цикл обработки клеток оказывается длинным. Для реализации такой схемы достаточно, чтобы топология вычислительной системы поддерживала кольцевое соединение процессоров. В принципе, можно реализовать и разбиение матрицы клеток на прямоугольные подобласти, если процессоры связаны между собой в виде прямоугольной решетки. Такая схема позволит еще больше распараллелить вычислительную стадию, но за счет увеличения объема межпроцессорных обменов и усложнения реализации этих обменов. Существенно более сложной является параллельная реализация асинхронных клеточных автоматов, т. к. порядок обновления клеток в таких автоматах существенно влияет на степень распараллеливания. Наиболее простой реализацией асинхронных автоматов является частично-асинхронная схема обновления клеток, когда каждый процессор обновляет свои клетки асинхронно, а межпроцессорные обмены выполняются по синхронной схеме. Статические структуры данных: векторы, массивы, таблицы, матрицы. Особенности представления и хранения данных. жүктеу/скачать 294.26 Kb. Достарыңызбен бөлісу: