Компьютерное моделирование физических явлений. Малютин В.М - 125 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

7. КЛЕТОЧНЫЕ АВТОМАТЫ
7.1. Особенности моделей клеточных автоматов
В этой главе мы познакомимся с другим классом геометрических
моделей, которые называются клеточными автоматами. Отличительной
особенностью клеточных автоматов являются их полная дискретность
и, следовательно, приспособленность к точному моделированию на
цифровом компьютере. Большой интерес к ним связан с тем, что они
являются универсальной моделью параллельных вычислений, так же,
как машины Тьюринга являются аналогичной моделью для
последовательных вычислений. Кроме того, наш интерес к ним
обусловлен, главным образом, тем, что многие модели клеточных
автоматов являются примерами простых динамических систем, которые
дают упорядоченные узоры, возникающие из случайных начальных
условий. Можно убедиться в том, что пространственные узоры многих
клеточных автоматов напоминают узоры, наблюдаемые в природных
явлениях, таких как коагуляция и рост кристаллов. Однако сейчас мы
будем рассматривать клеточные автоматы как интересные
компьютерные модели, которые сохраняют привлекательные
возможности для описания физических систем.
Автоматом называют устройство (или совокупность устройств),
которое без непосредственного участия человека выполняет процессы
приема, преобразования и передачи энергии, материалов или
информации в соответствии с заложенной в него программой.
В данном случае нас интересуют автоматы, выполняющие
дискретное преобразование информации, для которых заданы
множества А входных сигналов, Q внутренних состояний и V выходных
сигналов, а также две функции: функция переходов δ и функция
выходов α (рис. 7.1). Функция переходов определяет, в какое состояние
q' (из множества возможных состояний Q) перейдет автомат, если он
находится в состоянии q и на вход поступил сигнал a → δ(q,a) = q', а
функция выходов показывает, какой при этом образуется выходной
сигнал v (из множества выходных сигналов V): α(q,а) = v. Множество
сигналов и состояний дискретны, и, кроме того, дискретно множество
моментов, в которые поступают входные сигналы, выдаются выходные
сигналы и меняются состояния. В этом случае число возможных
значений аргументов функций переходов и выходов также конечно, и
эти функции можно задавать таблично. Подобные автоматы называются
конечными автоматами.
125

Страницы