Фронтальный клеточный автомат
Фронтальный клеточный автомат (англ. frontal cellular automata, FCA) - специальный тип вычислительных алгоритмов, основанных на моделях клеточных автоматов .
Название «фронтальный» происходит от одного из популярных применений, а именно, рост кристаллов, когда граница растущего кристалла рассматривается как фронт изменения в его структуре. Главная особенность фронтальных клеточных автоматов – изменение направления информационного потока для ячеек (клеток), и как результат использование при вычислениях в каждом шаге только малой части всех ячеек.
Главным элементом алгоритма клеточных автоматов является определение состояния клетки с помощью так называемых правил перехода. Эти правила описывают состояние ячеек в следующем шаге на основании определения состояния ячеек в его соседстве (текущее состояние клетки часто не учитывается). Классический алгоритм клеточных автоматов использует это правило напрямую, то есть ячейка собирает информацию. Пример показан на рисунке 1а. Для ячейка в середине рисунка проверяются правила перехода и она получает информацию, исследуя состояние своих соседей (например, в окрестности фон Неймана). Поэтому для реализации вычислений в одном шаге необходимо изучить всё клеточное пространство (стрелка в верхней части рисунка), проверяя правила перехода для каждой ячейки и состояние всех соседей для каждой ячейки пространства. Во фронтальных клеточных автоматах направление передачи информации изменяется на противоположное, как это показано на рисунке 1b. Это первый шаг, который не дает каких-либо видимых преимуществ потому, что и в этом случае приходится исследовать всё клеточное пространство и нет существенной разницы будет ли ячейка получать или отправлять информацию ко всем своим соседям.
Разница между этими алгоритмами появляется, если мы рассматриваем переходные и установившиеся состояния. Если в соседстве ячейки не происходят изменения, она остается в том же состоянии, и можно сказать, что она находится в устойчивом установившемся состоянии. И наоборот, если происходят изменения в соседстве, она может изменить своё состояние, то есть будет в переходном состоянии . Уже на этом этапе проявляются различия между двумя алгоритмами, так как сбор информации от соседей не создает каких-либо предпосылок, которые указывали бы, следует ли собирать такую информацию, или нет. Однако, при распространении (рассылке) информации от ячейки к соседям решение может быть принято на основании знания, изменилось ли состояние этой ячейки или нет. Ячейка, которая не изменяет своего состояния, не будет посылать информацию к своему окружению, однако, если изменения в её состоянии произошли, ячейки во всём её окружении получат сообщение, и на основании этой информации произведут проверку правил перехода, без изучения своего соседства. Это второй шаг, второе отличие.
Третий и последний шаг заключается в использовании для расчета только ячеек в переходном состоянии. Если сущностью второго шага была рассылка сигналов только от ячеек в переходном состоянии и неизменным исследованием всего клеточного пространства, то главным элементом третьего этапа модернизации алгоритма является ограничение исследования ячеек только теми из них, которые находятся в переходном состоянии.
Как пример эффективного применения может быть показан процесс роста кристалла. Фрагмент пространства с растущим кристаллом показан на рисунке 2. В любом процессе роста кристалла или зерна, можно выделить три зоны. В первой зоне (a) не произошло никаких изменений исходного состояния. Во второй зоне (b) такие изменения закончились, и дальнейшие изменения больше происходить не будут. Наконец, в третьей зоне (c) изменения происходят в данный момент времени и, следовательно, только ячейки из третьей зоне используются в расчетах. И первая, и вторая зоны должны быть исключены из расчетов в текущем шаге, поскольку изменения в ячейках этих зон не ожидаются и не произойдут. Для выбранной ячейки на рисунке 2 в переходном состоянии показано стрелками направление передачи информации, существенной для соседей. Таким образом, в текущем шаге только шесть ячеек в зоне (c) будут участвовать в расчете.
Использование FCA, вместо обычных клеточных автоматов, позволяет снизить вычислительные затраты в двумерных (2D) моделях, но особенно существенно в трехмерных (3D CA), потому что значительные области пространства исключаются из расчета в каждом шаге по времени, и лишь тонкий слой участвует в расчете. В классических CA практически каждый шаг требует таких же затрат и время его вычисления в течение всего процесса моделирования остается неизменной. Время же расчета одного шага FCA зависит от количества клеток, участвующих в расчете, и изменяется в широких пределах, оставаясь всегда лишь малой частью по сравнению со временем вычислений одного шага в классических CA. Каждая ячейка FCA в действительности участвует в расчетах только один раз в течение всего процесса расчета, в то время, как в классическом алгоритме, на каждом шаге вычислений.
Примеры оценки вычислительных затрат для нескольких простых вариантов.
Первый вариант: двумерное клеточное пространство 100x100 ячеек с одним зародышем. Расчеты до момента заполнения всего пространства с окрестностью фон Неймана (четыре соседа) без задержек.
Второй вариант: трехмерное клеточное пространство 100x100x100 ячеек с одним зародышем. Расчеты до момента заполнения всего пространства с трёхмерной окрестностью Мура (26 соседей), кристалл растет в формы сферы со средней задержкой в переходном состоянии равной трём шагам.
Затраты на вычисления отличаются на несколько порядков. При этом, чем больше число шагов, тем больше эта разница (табл.)
Источник: Википедия
Связанные понятия
Оператор Кэнни (детектор границ Кэнни, алгоритм Кэнни) в дисциплине компьютерного зрения — оператор обнаружения границ изображения. Был разработан в 1986 году Джоном Кэнни (англ. John F. Canny) и использует многоступенчатый алгоритм для обнаружения широкого спектра границ в изображениях.
Кориолисовы расходомеры — приборы, использующие эффект Кориолиса для измерения массового расхода жидкостей, газов. Принцип действия основан на изменениях фаз механических колебаний U-образных трубок, по которым движется среда. Сдвиг фаз пропорционален величине массового расхода. Поток с определенной массой, движущийся через входные ветви расходомерных трубок, создает кориолисову силу, которая сопротивляется колебаниям расходомерных трубок. Наглядно это сопротивление чувствуется, когда гибкий шланг...
Подробнее: Кориолисов расходомер
Вычисления с памятью — способ построения вычислительных платформ, в которых используются принцип хранения результатов функций в массивах памяти, одномерных или двухмерных, в виде таблиц поиска, а вычисление функций заменяется извлечением значения из таблиц. Такие вычислительные платформы могут следовать как чисто пространственной модели вычислений, как в ПЛИС, так и временно́й модели вычислений (процедурной), когда функция вычисляется за множество тактов. Второй подход нацелен на уменьшение избыточности...
Обратимый клеточный автомат — клеточный автомат, в котором каждое состояние имеет единственного предшественника. Таким образом, это регулярная решётка из ячеек, состояние каждой из которых берётся из конечного множества состояний, и правило для одновременного обновления состояний ячеек, исходя из состояний её соседей. Условие обратимости заключается в том, что предыдущее состояние любой ячейки может быть определено, зная обновлённые состояния всех ячеек решётки. После обращения времени получается...
Поточный алгоритм (англ. streaming algorithm) — алгоритм для обработки последовательности данных в один или малое число проходов.
Метод подвижных клеточных автоматов (MCA, от англ. movable cellular automata) — это метод вычислительной механики деформируемого твердого тела, основанный на дискретном подходе. Он объединяет преимущества метода классических клеточных автоматов и метода дискретных элементов. Важным преимуществом метода МСА является возможность моделирования разрушения материала, включая генерацию повреждений, распространение трещин, фрагментацию и перемешивание вещества. Моделирование именно этих процессов вызывает...
Обработка сложных событий (англ. complex event processing, CEP) заключается в обработке множества событий, происходящих на всех уровнях организации, при этом идентифицируются наиболее существенные события из множества событий, анализируется их влияние и в режиме реального времени предпринимаются соответствующие действия.
Расширяющийся нейронный газ — это алгоритм, позволяющий осуществлять адаптивную кластеризацию входных данных, то есть не только разделить пространство на кластеры, но и определить необходимое их количество исходя из особенностей самих данных. Это новый класс вычислительных механизмов. Количество и расположение искусственных нейронов в пространстве признаков не задается заранее, а вычисляется в процессе обучения моделей в соответствии с особенностями входных данных, самостоятельно подстраиваясь под...
Алгоритм Баума — Велша используется в информатике и статистике для нахождения неизвестных параметров скрытой марковской модели (HMM). Он использует алгоритм прямого-обратного хода и является частным случаем обобщённого EM-алгоритма.
Математическая морфология (ММ) — (морфология от греч. μορφή «форма» и λογία «наука») — теория и техника анализа и обработки геометрических структур, основанная на теории множеств, топологии и случайных функциях. В основном применяется в обработке цифровых изображений, но также может быть применима на графах, полигональной сетке, стереометрии и многих других пространственных структурах.
Гистогра́мма в математической статистике — это функция, приближающая плотность вероятности некоторого распределения, построенная на основе выборки из него.
Сети адаптивного резонанса — разновидность искусственных нейронных сетей, основанная на теории адаптивного резонанса Стивена Гроссберга и Гейла Карпентера. Включает в себя модели обучения с учителем и без учителя, которые используются при решении задач распознавания образов и предсказания.
Подробнее: Адаптивная резонансная теория
Генерация столбцов или отложенная генерация столбцов — это эффективный подход к решению больших задач линейного программирования.
Оператор Ротуэлла , в дисциплине компьютерного зрения — оператор для обнаружения границ, представленный Чарлзом Ротуэллом (англ. C. A. Rothwell) на Симпозиуме IEEE по компьютерному зрению в 1995 году.
Элементарный клеточный автомат — это клеточный автомат с одномерным массивом ячеек в форме бесконечной в обе стороны ленты, который имеет два возможных состояния ячеек (0 и 1, «мёртвые» и «живые», «пустые» и «заполненные») и правило для определения состояния ячейки на следующем шаге, использующее только состояние ячейки и её двух соседей на текущем шаге. В целом такие автоматы являются одними из наиболее простых возможных клеточных автоматов, однако при некоторых правилах они показывают сложное поведение...
Человеческая
память ассоциативна, то есть некоторое воспоминание может порождать большую связанную с ним область. Один предмет напоминает нам о другом, а этот другой о третьем. Если позволить нашим мыслям, они будут перемещаться от предмета к предмету по цепочке умственных ассоциаций. Например, несколько музыкальных тактов могут вызвать целую гамму чувственных воспоминаний, включая пейзажи, звуки и запахи. Напротив, обычная компьютерная память является локально адресуемой, предъявляется адрес и извлекается...
Нейронные сети Кохонена — класс нейронных сетей, основным элементом которых является слой Кохонена. Слой Кохонена состоит из адаптивных линейных сумматоров («линейных формальных нейронов»). Как правило, выходные сигналы слоя Кохонена обрабатываются по правилу «Победитель получает всё»: наибольший сигнал превращается в единичный, остальные обращаются в ноль.
Осцилляции Зенера — Блоха — колебания частицы, движущейся в периодическом потенциале, под действием постоянной силы. Примером системы, в которой могут реализоваться такие колебания, является кристаллическое твердое тело. В реальных кристаллах создать условия для наблюдения осцилляций Зенера — Блоха трудно, однако они наблюдались в искусственных системах, например, сверхрешётках.
Строковое ядро — это ядерная функция, определённая на строках, т.е. конечных последовательностях символов, которые не обязательно имеют одну и ту же длину. Строковые ядра можно интуитивно понимать как функции, измеряющие похожесть пар строк — чем больше похожи две строки a и b, тем больше значение строкового ядра K(a, b).
Матрица жёсткости (матрица Дирихле) — матрица особого вида, использующаяся в методе конечных элементов для решения дифференциальных уравнений в частных производных. Она применяется при решениях задач электродинамики и механики.
Свёртка последовательностей — это результат перемножения элементов двух заданных числовых последовательностей таким образом, что члены одной последовательности берутся с возрастанием индексов, а члены другой — с убыванием (что и служит основанием для принятого названия данной операции).
Проектная сеть — технологическая платформа, онлайн-сервис или веб-сайт, предназначенные для предоставления возможности самоорганизации участникам, обладающим ключевыми компетенциями, в проектную команду, для выполнения мероприятий с изначально установленными целями, достижение которых определяет завершение проекта.
Подробнее: Проектные сети
Блочная сортировка (Карманная сортировка, корзинная сортировка, англ. Bucket sort) — алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем...
Сдвиг среднего значения — это непараметрическая техника анализа пространства признаков для определения местоположения максимума плотности вероятности, так называемый алгоритм поиска моды. Область применения техники — кластерный анализ в компьютерном зрении и обработке изображений.
Алгоритм «прямого-обратного» хода — алгоритм для вычисления апостериорных вероятностей последовательности состояний при наличии последовательности наблюдений. Иначе говоря, алгоритм, вычисляющий вероятность специфической последовательности наблюдений. Алгоритм применяется в трёх алгоритмах скрытых Марковских моделей.
Циклическая база данных (англ. Round-robin Database, RRD) — база данных, объём хранимых данных которой не меняется со временем, поскольку количество записей постоянно, в процессе сохранения данных они используются циклически. Как правило, используется для хранения информации, которая перезаписывается через равные интервалы времени.
Семплирование по Гиббсу — алгоритм для генерации выборки совместного распределения множества случайных величин. Он используется для оценки совместного распределения и для вычисления интегралов методом Монте-Карло. Этот алгоритм является частным случаем алгоритма Метрополиса-Гастингса и назван в честь физика Джозайи Гиббса.
Паксос (англ. Paxos) — семейство протоколов для решения задачи консенсуса в сети ненадёжных вычислителей. Консенсус — процесс получения согласованного результата группой участников, основная проблема — наличие помех в среде передачи данных. Данная задача используется, например, для утверждения транзакций в распределённых системах.
Алгоритм Карплуса-Стронга для синтеза струны — способ синтеза звука, заключающийся в пропускании короткого сигнала через линию задержки с фильтром. В зависимости от параметров, полученный звук может быть похож на звук струны, извлекаемый медиатором или тэппингом, либо на звуки некоторых ударных инструментов.
Математические основы квантовой механики — принятый в квантовой механике способ математического моделирования квантовомеханических явлений, позволяющий вычислять численные значения наблюдаемых в квантовой механике величин. Были созданы Луи де-Бройлем (открытие волн материи), В. Гейзенбергом (создание матричной механики, открытие принципа неопределённости), Э. Шрёдингером (уравнение Шрёдингера), Н. Бором (формулировка принципа дополнительности). Завершил создание математических основ квантовой механики...
Алгоритм Петерсона — алгоритм параллельного программирования для взаимного исключения потоков исполнения кода, разработанный Гарри Петерсоном в 1981 г. Хотя изначально был сформулирован для 2-поточного случая, алгоритм может быть обобщён для произвольного количества потоков. Алгоритм условно называется программным, так как не основан на использовании специальных команд процессора для запрета прерываний, блокировки шины памяти и т. д., используются только общие переменные памяти и цикл для ожидания...
Многочасти́чный фильтр (МЧФ, англ. particle filter — «фильтр частиц», «частичный фильтр», «корпускулярный фильтр») — последовательный метод Монте-Карло — рекурсивный алгоритм для численного решения проблем оценивания (фильтрации, сглаживания), особенно для нелинейных и не-гауссовских случаев. Со времени описания в 1993 году Н. Гордоном, Д. Салмондом и А. Смитом используется в различных областях — навигации, робототехнике, компьютерном зрении.
Поиском
наилучшей проекции (англ. Projection Pursuit) называется статистический метод, состоящий в нахождении такой проекции многомерных данных, для которой достигает максимума некоторая функция качества проекции.
Поверхность потенциальной энергии применяется для описания энергии системы, в особенности множества атомов, в терминах определённых параметров, обычно — координат атомов. Поверхность может определять энергию как функцию одной или нескольких координат. Если координата только одна, то поверхность называется кривой потенциальной энергии или профилем энергии.
Упругая карта служит для нелинейного сокращения размерности данных. В многомерном пространстве данных располагается поверхность, которая приближает имеющиеся точки данных и при этом является, по возможности, не слишком изогнутой. Данные проецируются на эту поверхность и потом могут отображаться на ней, как на карте. Её можно представлять себе как упругую пластину, погруженную в пространство данных и прикрепленную к точкам данных пружинками. Служит обобщением метода главных компонент (в котором вместо...
Матрица мер конвергенции — матрица содержащая в качестве элементов меры сходства объектов. Матрица отражает попарное сходство объектов. Сходство является показателем, измеренном в порядковой шкале и, следовательно, возможно лишь определение отношений вида: «больше», «меньше» или «равно».
Блочно-ориентированные модели — это представление нелинейных систем в виде различных комбинаций инерционных звеньев и нелинейных безынерционных математических элементов. Такое представление моделей позволяет связать в явном виде входные и выходные переменные объектов с различной структурой и степенью нелинейности. К таким системам относятся системы типа Гаммерштейна, Винера, Винера-Гаммерштейна, фильтра Заде, обобщенной модели Винера и Sm-системы.
В криптографии
атака по энергопотреблению является одной из форм атак по сторонним каналам, при которой криптоаналитик изучает потребляемую мощность устройства, выполняющего криптографические задачи (как например смарт-карта, устойчивый к взлому «черный ящик», интегральная схема и тому подобное). С помощью такой атаки возможно извлечь криптографические ключи или другую секретную информацию из устройства, не оказывая на него непосредственного воздействия.
Предобуславливание (также предобусловливание) — процесс преобразования условий задачи для её более корректного численного решения. Предобуславливание обычно связано с уменьшением числа обусловленности задачи. Предобуславливаемая задача обычно затем решается итерационным методом.
Слепая деконволюция — метод восстановления изображения без априорной информации о функции размытия точки оптической системы, которая вносит в регистрируемый полезный сигнал шум, искажения и т. п.
Векторная авторегрессия (VAR, Vector AutoRegression) — модель динамики нескольких временных рядов, в которой текущие значения этих рядов зависят от прошлых значений этих же временных рядов. Модель предложена Кристофером Симсом как альтернатива системам одновременных уравнений, которые предполагают существенные теоретические ограничения. VAR-модели свободны от ограничений структурных моделей. Тем не менее, проблема VAR-моделей заключается в резком росте количества параметров с увеличением количества...
Задача характеризации
элементов микросхем заключается в получении зависимостей функциональных параметров библиотечного элемента или блока от длительности фронтов сигналов на входе и от величины нагрузочных емкостей для заданных наборов этих величин. В коммерческих системах характеризации (SiliconSmart , Virtuoso Liberate Characterization Solution , Virtuoso Variety Statistical Characterization Solution , Virtuoso Liberate MX Memory Characterization Solution , Kronos Characterizer Plus ) такие зависимости...
Безопасность информационных потоков — набор требований и правил, направленных на определение того, какие информационные потоки в системе являются разрешёнными, а какие нет. Данная модель не является самостоятельной, и используется в дополнение к мандатной или дискреционной модели управления доступа.
Дифракция отражённых электронов (ДОЭ) — микроструктурная кристаллографическая методика, используемая для исследования кристаллографических ориентаций многих материалов, которая может использоваться для исследования текстуры или преимущественных ориентаций моно- или поликристаллического материала. ДОЭ может использоваться для индексирования и определения семи кристаллических систем, также применяется для картирования кристаллических ориентаций, исследования дефектов, определения и разделения фаз...
Алгоритм Гёрцеля (англ. Goertzel algorithm) — это специальная реализация дискретного преобразования Фурье (ДПФ) в форме рекурсивного фильтра. Данный алгоритм был предложен Джеральдом Гёрцелем в 1958 году. В отличие от быстрого преобразования Фурье, вычисляющего все частотные компоненты ДПФ, алгоритм Гёрцеля позволяет эффективно вычислить значение одного частотного компонента.
Кривая светового насыщения фотосинтеза — это графическое представление эмпирической взаимосвязи между интенсивностью света и фотосинтезом. По сути своей она представляет собой модификацию уравнения Михаэлиса-Ментен. Кривая показывает положительную корреляцию между интенсивностью света и скоростью фотосинтеза: по оси х отложены значения независимой переменной (освещенность), а по оси y — значение зависимой переменной (скорость фотосинтеза).