автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Простейшие клеточные автоматы в математическом моделировании процессов

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М. В. Ломоносова

р г б оа

'ГГ" пРавах рукописи

ШАКАЕВА Милана Салаватовна

ПРОСТЕЙШИЕ КЛЕТОЧНЫЕ АВТОМАТЫ В МАТЕМАТИЧЕСКОМ МОДЕЛИРОВАНИИ ПРОЦЕССОВ ПЮТНССА.

Специальность 05.13.1В Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

АВТОРЕФЕРАТ

диссертации нп соискание ученой стапэли кандидата физшсо-математических наук

МОСКВА

1995

Работа выполнена б Московском государственном университете им. М. В. Ломоносова.

Научный руководитель: доктор физико-математических наук Г. Г. Малинецкий

Официальные оппоненты: доктор физико-математических наук,

профессор Ю.М. Романовский

Ведущая организация: Ярославский государственный университет

в Московском государственном университете им. М. В. Ломоносова по адресу: 119899, Москва, МГУ, 2-ой гуманитарный корпус. ВМиК, ауд. 685.

С диссертацией мохно ознакомиться в библиотеке факультета ВМиК.

доктор физико-математических наук А. С. Дмитриев

•24 иоМ^рл

1935г.

в

Автореферат

Ученый секретарь диссертационного совета кандидат физико-математических

/

1. ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ.

Актуальность___темы. Основной задачей при изучении

пространственно-временного поведения многих систем в природе является математическое моделирование их временной эволюции. Для эё решения традиционно использовались дифференциальные уравнения з частных производных. Можно условно выделить три этапа в 1зученин эволюции физических систем. Первый этап заключается в юпытке описать явление с помощью уравнений путей различных допущений и предположений относительно явления. В редких случаях ■ложно найти аналитическое решение полученных ■ уравнений. Чаще гсего в нашей власти лишь провести анализ динамики только для достаточно простых моделей. И вот тогда для их решения приходится ■фибегать к численным методам. Второй этап, таким образом, заключается в "переводе" дифференциальных уравнений в чзстных производных в 'конечно-разностные. На этом этапе непрерывное 1ространство и время заменяются на дискретные, непрерывные функции - на сеточные, производные - на разности между значениями ;еточных функций в соседних узлах пространственно-временной зешетки < путем "обрывания" рядов. представляющих собой изложения непрерывных функций ). Решение полученной системы сонечно - разностных уравнений имеет, следовательно, некоторую югреашость, называемую погрешностью дискретизации. И далее, так сак решать "вручную" конечно-разностные уравнения тоже не под :илу из-за большого объема вычислений, их решают с помощью ЭВМ. 1а третьем этапе осуществляется проекция действительных величин 1а машинное слово, имеющее конечное количество разрядов. Что вызывает еще и погрешность округления. А не существует ли менее школьного пути моделирования явлений природы?

Обычно на первом этапе . при выводе уравнений в частных троиззодных мы переходим от законов для физически малого объема 1утем усреднения ( интегрирования ) к уравнениям, описывающим макроскопические изменения в системе. Но иногда переход к «прерывному описанию затруднен из-за "дискретности" задачи I когда переменные, характеризующие явление, имеют малое соличество значении или когда существует "порог" при изменении теременной ). Например, если в "физически малом объеме" почти 5сегда оказывается одна или ни одной частицы, то переходить к

понятию плотности р=Пп ы(г)/у, где N - число частиц в объеме г,

просто неразумно. Плотность будет почти всегда нулевой и только изредка очень большой.

Далее, осуществив переход из микромира, который сан по себе дискретен ( на молекулярном уровне-) в макромир с непрерывными величинами, мы на втором этапе опять возвращаемся на дискретный уровень. Может быть, иногда лучше сразу использовать дискретные модели?

В последнее время для моделирования различных физических явлений довольно широко стали применяться клеточные автоматы. Последние представляют собой системы, состоящие из одинаковых клеток. Каждая клетка может находиться только в конечном наборе состояний. Ее эволюция, т. е. переход из одного состояния в другое, происходит в дискретные моменты времени и зависит только от ее собственного состояния в данный момент и от состояния ее ближайших соседей. Правила, описывающие эволюцию клетох, необычайно просты. Они одинаковы для всех клеток, независимо от их расположения, и не меняются со временем.

Оказалось, эти простейшие математические модели способны демонстрировать поведение, по сложности напоминающее процессы, протекающие в природе: рост, размножение, самоорганизацию, диффузию, химическое взаимодействие, течение жидкостей, образование фрактальных структур и т. д.

Существует круг задач, решение которых традиционными методами затруднено, либо вообще невозможно. Это могут быть задачи со сложной геометрией ( в которых проблемы возникают с заданием граничных условий, либо с описанием самой облзсти ); задачи, в которых процесс является нелинейным и носит пороговый характер; задачи, в которых описание переменных в виде непрерывных величин затруднено из-за малого количества их значений.

Использование клеточных автоматов для решения таких задач является более целесообразным. Характерными областями их использования могут быть задачи, связанные с описанием химических реакций с большим количеством реагентов ( различные реагенты могут быть представлены частицами разных типов в автоматах ); системы типа "реакция-диффузия"; течение несмешивающихся жидкостей; процессы фильтрации ( пористая среда может быть легко отображена в автоматах ); моделирование роста кристаллов;

моделирование процессов роста, размножения и самоорганизации в биологических системах: изучение самоорганизованной критичности в распределенных системах, возникающих в биологии, экономике, геологии ( изучение процессов эволюции генома-, рынка акций, земной коры "на грани хаоса"); моделирование систем взаимодействующих спинов.

Отметим основные достоинства использования клеточных автоматов для моделирования физических процессов:

1) значения величин в клеточных. автоматах представлены булевой алгеброй и поэтому не существует проблемы обработки действительных чисел, все вычисления являются точными, нет ошибок округления;

2) возможно решение для любой формы границ ( геометрия многих границ может быть эффективно описана в автоматах );

3) упрощается анализ разрывных решений ( по сравнению с традиционными конечно-разностными схемами );

4) так как вычисления в клеточных автоматах являются локальными ( эволюция данной клетки определяется только ей самой и еэ ближайшими соседями ), то модели, основанные на клеточных автоматах, идеально подходят к широко распространяющимся сейчас алгоритмам параллельных вычислений;

5) связь с физической реальностью : благодаря своей "микроскопической природе", модели клеточных автоматов могут демонстрировать явления, имеющие место в реальных системах, но которые не могут быть получены из макроуравнений, - те 'явления, которые теряются в результате аппроксимации при переходе от физической модели к непрерывным уравнениям ( например, явления, связанные с микроскопическими флуктуациями );

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

традиционных компьютеров, что несомненно имеет свои преимущества при изучении моделируемых явлений, делая этот процесс более наглядным.

Естественно, автоматы имеют не толко достоинства, но и недостатки. Среди них:

1) возникновение явлений, обусловленных дискретной природой клеточных автоматов, например, нарушение галилеевской инвариантности в двумерных решеточных газах, моделирующих течение жидкости , появление различных искусственных законов сохранения;

2) для получения количественных результатов с помощью клеточных автоматов иногда необходимо использовать либо ансамбль лэ большого числа автоматов, г.ибо автомат достаточно больших размеров, чтобы уменьшить ошибку, связанную со статистичес»ими флуктуациями.

В математическом моделировании и математической физике ключевое значение имеют базовые математические модели. Из них, как из кубиков, обычно иожно строить модели более сложны* процессов. Можно предположить, что таким же образом обстоит деле в мире клеточных автоматог. Поэтому важно выяснить как ведут с с-б! простейше клеточные автоматы, моделирующие физические явления.

Цель__и__задачи__исследования. Широкое применение клеточные

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

1. Каков?! простейшие типы упорядоченности в системе "реакция-диффузл-ч", описывающей колебательные химические реакции? I качестве базовой модели здесь был выбран клеточный аЕток*. предложенный У. Ооко и М. Кохмого. Как поведение автомата завис от параметров? Как повлияет на поведение модели увеличение чиг градаций концентрации?

2. Каковы простейшие типы упорядоченности в колебательнг | реакции, протекающей на поверхности, при ее описании с помоги простейшего двумерного клеточного автомата?

3. Какова точность решения уравнения диффузии с г.омса&к кг гг глы: автоматов? Как соотносится "автоматный" алгоритм трч/.щионно: схемой Монте-Карло? Каковы простейшие типы упорядоченности клеточном автомате, моделирующем образование осадка в систем типа "реакция-диффузия" ( неустойчивость Ли^еганга )?

4. Каковы простейшие дискретные модели, дозволяющие имитироват

развитие иерархической организации?

Метоаы_исследования. Для решения поставленных задач применялся численный эксперимент, методы теории вероятностей, теории динамических систем, теории автоматов.

31ХНЦая_новизна. В работе при исследовании одномерной модели обнаружены новые типы качественного поведения системы. В частности, аннигиляция волн при столкновении друг с другом. Это говорит о том, что волны могут вести себя не только как солитоны ( этот факт был обнаружен У. Ооно и М. Кохмото ), но и подобно автоволнам. Обнаружены пространственно-локализованные структуры, которые могут играть роль счетчика приходящих к ним волн, а таое явление "фазового перехода" ( когда одна "фаза" со временем полностью вытесняется другой ).

При исследовании двумерной модели, являющейся обобщением автомата У. Ооно и М. Кохмото, были обнаружены спиральные волны. Последние отличаются от ранее наблюдавшихся волн в возбудииьпг средах. Кроме того, были найдены движущиеся локализованные в пространстве объекты типа "планеров" в игре "Жизнь".

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

Пвактическое^значениеработы. Проведенный в диссертации анализ "базовых клеточных автоматов" для моделирования процессов нелинейного переноса позволяет использовать их при построении моделей более сложных процессов, при создании специализированных машин клеточных автоматов. Обнаруженные качественные эффекты могут оказаться полезны в -задачах химической технологии или при создании лекарственны:-: препаратов, опирающемся на математическое моделирование процессов в активных средах. Наконец, построенная модель динамики иерархических систем в настоящее время используется в Государственном комитете по высшему образованию для анализа долгосрочных последствий планируемых реформ высшей школы.

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

моделирования, Институте радиоэлектроники, Ярославском государственном университете. Институте математического моделирования в биологии ( Путно ), В Государственном комитете по высэему образованию и других организациях.

Ап2°<5ацияОсновные результаты работы были доложены на международной конференции "Математика. Компьютер. Образование" ( Ыосква-Пущино, 1995г. ), на Московском научном семинаре "Современные проблемы синергетики", а также на научных семинарах факультета ВМиК МГУ им. М. В. Ломоносова ( кафедра вычислительных методов ).

Публикации. По теме диссертации опубликовано восемь работ, перечисленных в конце автореферата.

QlBXSISBä__йиссевтации. Диссертация состоит из введения,

четырёх глав и списка литературы, включающего 59 наименований. Объем работы составляет 127 страниц.

2. СОДЕРЖАНИЕ ДИССЕРТАЦИИ.

82-§§§йё0ЦИ кратко обсуждается история возникновения клеточных автоматов, дается описание их структуры и основных свойств, а также обращается внимание на области их применения в математическом моделировании и обработке информации.

§JKES2Ü-E5䧧 рассматривается клеточный автомат, предложенный У.Ооно и М. Кохмото для описания колебательных химических реакций, и его обобщение на случай большего числа градаций концентрации.

Пусть л-ой клетке на бесконечной прямой в момент времени t ставится в соответствие величина л(л, t). Она принимает одно из трех значений 0, 1 или и ( и - положительное число ), используемых для обозначения трех дискретных уровней концентрации. Временная и пространственная переменные дискретны ( t-целое положительное, п-целое ).

Эволюция конфигурации л(п, t) определяется следующим правилом:

Aln,t)=a U(n-l,t, )+л(п+1,с)]/2-Ч1-а)л(л, t), (1)

A(n,t+l)=F(3(n, t)>, (2)

где A(n, t)-концентрация в п-ой клетке на прямой в момент времени t; а « [0,11-параметр, характеризующий коэффициент диффузии;

' 1, 1.5*х-Г(х)= 0, 0.5=чг<1. 5 я, х<0.5.

Предложенный клеточный автомат можно интерпретировать как аналог простейшей разностной схемы для уравнения типа "реакция-диффузия":

где при оихх=0 существует единственный предельный цикл 0-»я-»1-Ю. Соотношение (1) описывает диффузионное взаимодействие между клетками системы, (2)-(3) - циклические осцилляции. Когда диффузия отсутствует (т.е. а=0) каждая клетка совершает цикл 0-»?г->1->0 независимо от своих соседей.

Если действовать по аналогии с теорией динамических систем, то естественно выяснить, как ведет себя функция л(п,ь) при различных начальных данных л(п,0). Наиболее простыми начальными данными являются следующие : ...000111...; ... МММООО...; .. ЛИммм... . Их мы будем называть, следуя физической аналогии, "доменной стенкой". Эволюция начальных данных типа "доменной стенки" позволяет выделить несколько различных типов качественного поведения - "фаз" ( см. рис. 1 ).

Фаза 3. Диффузионные процессы в этом случае не являются достаточно сильными, так что две области, в которых есть цикл 3, но со сдвигом по времени, не взаимодействуют друг с другом и "стенка" между ними не движется ( см.рис. 2а ).

Фаза 3'. Картина аналогична предыдущей. Стенка в течение основного цикла периода 3 сдвигается то вправо, то влево, но в результате возвращается на место.

В промежуточном случае "стенка" начинает двигаться влево или вправо, представляя собой волну ( см. рис. 2б-в ). Это позволяет проанализировать "столкновения" таких волн. Если начальное расстояние между волнами равнялось четному числу клеток, то волны "отражаются" друг от друг;а ( см. рис. 26 ). Когда расстояние нечетно, они могут проходить друг через друга, что типично для солитонов в непрерывных и дискретных системах, либо "аннигилировать" как автоволны в возбудимых средах ( см. рис. 2в ). В области г волны отражаются или проходят друг через друга при

(4)

■ Рис.1. Фазовая диаграмма для 01110-модели.

а б в

Рис.2. Различные типы качественного поведения в 01110-модели: а - цикл 3 ( И=6, «=0.11 ), 6 - отражение волн ( 11=6, а=0.21 ), в - аннигиляция волн ( 11=6, а=0.31 ), г - возникновение сложный структур ( М=2, а=0.91 ), д- "фазовый переход" ( М=1.7, а=0. 67 ). Черные клетки соответствуют клеткам со значением К, заштрихованные - клеткам со значением 1, белые - клеткам со значением 0.

—................— 1 ваааа аа-г ЯЯ ■ - И - В IlHIlva р. • ■ - ■ а

■ ■■>>!■«•■■ Я -,<■»-. л m в - ■ ая тая

яя»»аяв» > . -г. . . . «а , - -яа ааа яаа

¿ai- •. . --m--- m л а ■ 9 • я 'Ч-.-Ш^т .Я B-. • а а- а ■ ■ а* ■ f. аа ааа яаа ааа -ва ааа аяа ааа ааа

«ааа 4 -■:■ <ая та v . .. • я я а ■т-- ■ та-- я ■ ВпВпйНнйнйнпЯпВгЯ

штат ■ --■» я аа • Tff ■ff'ffTiHBHflpg'ïffi

г *

Рис. 2. ( прохояеяже ).

Рис.3. Спиражьная волю ( И=6, а=0.35, окрестность Неймана ).

столкновении. В области я они отражаются или "аннигилируют" в зависимости от четности расстояния между ними.

Среди остальных областей на плоскости параметров, исследованных в диссертации, наиболее примечательными являются следующие.

Область лг. Доменная стенка движется в виде волны. При взаимодействии друг с другом эти волны аннигилируют независимо от начального расстояния между ними. С этой точки зрения в области Аг дискретная модель (1)-(3) является аналогом нелинейных возбудимых сред, в которых могут распространяться автоволны.

Область в. Эволюция доменной стенки в этой области приводит к "широкой" волне. При взаимодействии таких волн друг с другом могут возникать пространственно-локализованные, периодически меняющиеся по времени структуры ( см.рис. 2г ). Последние могут играть роль "счетчика" приходящих к ним волн.

Область с. Эволюция доменной стенки приводит к "фазовому переходу", связанному с вытеснением одной фазы другой ( см. рис. 2д ).

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

а) волны при столкновении друг с другом меняют свой тип;

б) при взаимодействии волн разных типов между собой одна волна исчезает, а другая меняет направление на противоположное; .

с) при столкновении волны с неподвижной стенкой ( циклом ) . картина может остаться прежней, либо стенка исчезает, а волна меняет направление движения на противоположное.

Во__втоцой__главе исследуется двумерный клеточный автомат,

являющийся обощением модели У. Ооно, и М. Кохмото.

Анализ многих непрерывных нелинейных систем показал, что поведение решений в одномерном и пространственно-многомерном сяучае может качественно отличаться. Кроме того, существует ряд

явлений в физических системах, которые определяются пространственной многомерностью задачи и не имеют аналогов в одномерном случае. Поэтому важно было выяснить, каковы простейшие типы упорядоченности в двумерном обобщении данной модели, насколько они отличаются от тех, что были выделены в одномерной.

Правило, описывающее эволюцию двумерного автомата, аналогично правилу (1)-(3) с тем лишь отличием, что автомат рассматривается на двумерной решетке и величина концентрации А11, J, г) в клетке ■ зависит теперь от двух пространственных координат х и у.

Л(х^';£)=а-( Е А(к, 1, Ь))/»+(1-а)*Л( I, Ы (5)

I к , I > * I 1 , ) > ( к , 1 I £ Н

дИ, с+1)=г(ди, (6)

где n - число клеток в окрестности, не считая центральной - клетки с координатами 1, j, и - нножество всех клеток в окрестности. В качестве окрестностей рассматриваются окрестности Мура ( клетки, которые имеют общую сторону с данной ) и Неймана ( клетки, которые имеют хотя бы одну общую вершину с данной ).

Как показывает численный эксперимент, эволюция простых начальных данных в виде квадратов (' начальных конфигураций, в которых клетки с каким-то" одним значением концентрации образуют квадрат размером п*п на фоне клеток с другим значением концентрации ) может приводить к различным локализованным циклам ( с помощью некоторых из них можно строить более сложные структуры ), волнам, всевозможным растущим конфигурациям. Последние могут быть самых разных видов. Среди них встречаются паттерны с однородной внутренней областью, паттерны, напоминающие "ковровые узоры", паттерны с линейными границами, паттерны с дендрическими границами.

Замечательньм свойством модели является наличие среди всевозможных волновых процессов спиральных волн. Спиральные волны наблюдаются в ходе различных колебательных химических реакций, например, в реакции Белоусова-Жаботинского. Тем более примечательно, что данная модель (5)-(6>, являясь двумерным обобщением модели, описывающей колебательные химические реакции,-демонстрирует такой тип поведения. Обнаруженные спиральные волны отличаются от спиральных волн в возбудимых средах. В возбудимых

средах перемещение волнового фронта происходит за счет перехода клеток из состояния покоя в состояние возбуждения и затем в состояние рефрактерности. В модели (5)-(6) спиральные волны представляют собой перемещение границы вежду областями клеток одинаковой концентрации, внутри которых состояние клеток меняется в основном цикле 0-л-»1-Л ( см. рис. 3 >. Данная спиральная волна раскручивается из центра, внешний конец ее передвигается без изменений, период одного оборота волны равен 36 временным тактам.

Не менее замечательным свойством модели является наличие в ней движущихся объектов типа планеров в игре "Жизнь". Перемещается они, в отличие от планеров игры "Жизнь", по вертикали или по горизонтали, а не в диагональном направлении и характерны только для окрестности Неймана ( см. рис. 4 ). Столкновения планеров друг с другом могут приводить к возникновению различных растущих конфигураций, среди которых, например, существует двухвитховая спиральная волна.

8__1Е£1ь§й__ОЭВ2 рассматриваются простейшие клеточные

автоматы для базовой модели математической физики - уравнения диффузии : о

и. ---и , (7)

1 2 "

где и(х,с) - плотность частиц в точке ж в момент времени г, в - коэффициент диффузии.

В качестве тестовых рассматриваются следующие две задачи: с

Задача (*):

Задача (**):

и «--а , 0 < * < 1, г > О,

2 *

и(0,с)»1, ы(1,г)=0, £ с О,

и(х,0)=0, 0 < * < 1.

в

и ---и , -т < * < в, С > О,

» 2 "

.0

«.(ж.О)*!1 • ~х***х \ \ 0 , х <-*°, * >*'

>х°.

На примере этих двух простых задач сравнивается различные численные методы решения уравнения (7). В частности, метод конечных разностей, метод Понте-Карло я метод, использующий клеточные автоматы.

В качестве клеточного автомата, моделирующего диффузию, был

Ряс. 4. Планер ( 11=6, а=0.35, окрестность Неймана ).

Рис. 5а. Структура осадка пря следующих значениях параметров: П.=0.1. Оь=Ое=0.01. а/Ъ^ЮО. к =2. ка=1. кп/.о=4.07.10-3,

к /а =2. 38 • 10 . » о

ш

i» 2» йо зе» йо Ля

450

Рис.56. Структура осадка пря следующих значениях параметров: П/0.1, 0^=0 И). 01, а/Ъ^ЮО. кв=5, к =2, к/»о=1. «66-КГ2,

к /а «6.6«-10 .

»• о

выбран автомат типа решеточного газа. Пространство в данном клеточном автомате представляет собой одномерную решетку, в узлах которой могут находиться частицы массы т=1. Каждая частица имеет скорость 3 ( |^|=1 ), направленную либо вправо, либо влево. Существует правило, запрещающее в одном узле находиться двум и более частицам, имеющим одинаковую по направлению скорость. Таким образом, в каждом узле может находиться не более двух частиц, скорость одной из которых направлена влево, а скорость другой - вправо. Правило эволюции автомата ( перемещения частиц ) состоит из двух шагов. На первом шаге ( шаг "столкновения" ) все частицы в данном узле с вероятностью pi меняют направление скорости на противоположное ( разворачиваются на 180° ), ас вероятностью р = 1-рд остаются на месте. На втором шаге ( шаг "перемещения" ) частицы перемещаются ровно на один узел Еправо или влево по направлению своей скорости. Далее все повторяется. Время, как и пространство, дискретно. Переход от одного момента времени t к следующему t+1 включает в себя выполнение двух действий: "столкновения" и "перемещения".

Погрешность решения Д, полученного с помощью усредения по ансамблю из w таких автоматов, имеет следующий вид 1 -

Л ------(8)

2-ЛГ

Отсюда ясно, что для решения задач математической физики с помощью клеточных автоматов может потребоваться ансамбль большого числа автоматов, либо один автомат большого размера для того, чтобы получить решение с достаточной точностью. Причем объем вычислений, исходя из формулы (8), того же порядка, что и в методе Монте-Карло.

Проведен небольшой сравнительный анализ различных методов. Точное решение найти удается в очень редких случаях, и, как правило, простых. Поэтому, так или иначе, приходится прибегать к методам, позволяющим получить приближенное решение поставленной задачи. Самым мощным и распространенным в настоящее время является, без сомнения, метод конечных разностей. Но он имеет свои недостатки. Это вопросы, связанные со сходимостью и устойчивостью разностных схем, а также проблема компромисса между "сложной" разностной схемой, адекватно отражающей явление, и совершенно непригодной для реализации на ЭВМ, и "упрощенной"

раэностной схемой, которая довольно просто мояет быть реализована на ЭВМ, но плохо описывает свойства задачи, а некоторые и, вообще, не отражает. Особенно это касается многомерных задач, задач со сложной геометрией. Попытки разрешить эту проблему привели в свое время к методу Монте-Карло. Единственным недостатком этого метода является необходимость большого количества испытаний для уменьшения статистической ошибки, что опять же усложняет реализацию на ЭВМ.

Другая возможность решения проблемы - использование клеточных автоматов. Что объединяет клеточные автоматы и метод Монте-Карло? Во-первых, класс задач, для решения которых есть смысл их использовать. Например, задачи со сложной геометрией ( пористые среды, фрактали и др. ). Во-вторых, необходимость большого количества вычислений для получения результатов с хорошей точностью. В методе Монте-Карло это приводит к большому числу испытаний, в клеточных автоматах - к автоматам больших размеров. Каковы преимущества клеточных автоматов по сразкзнив с методом Монте-Карло? В клеточных автоматах частицы ( клетки ) взаимодействуют между собой, тем самым воспроизводя связь с реальным явлением. Взаимодействие между частицами заложено в самом правиле, управляющем эволюцией автомата. В методе Монте-Карло рассматриваются блуждания независимых частиц. Для того, чтобы отразить их взаимодействие требуются дополнительные усилия, усложняющие процесс вычислений. Поэтому для моделирования процессов, в которых важную роль играет взаимодействие между отдельными частицами ( например, процессы образования осадка в результате" химической реакции между двумя веществами ), имеет смысл использовать именно клеточные автоматы.

Для того, чтобы продемонстрировать это преимущество, была рассмотрена конкретная задача, в которой имеют место не только диффузионные процессы, но и химическое взаимодействие между частицами среды, в результате которого продукт реакции выпадает в осадок ( неустойчивость Лиэеганга ). Реакция была обнаружена еще в прошлом столетии. При определенных условиях наблюдалось выпадение осадка в виде полос, колец, спиралей и т. д. Было предложено множество различных теорий, описывающих подобное явление ( список работ см. в диссертации ). Рассматривались такие вопросы как, например, изучение зависимости пространственного расположения очередного осадка и его ширины от его порядкового

номера.

Ясно, что описывать с помощью дифференциальных уравнений процессы выпадения осадка и его дальнейшего роста, которые происходят на уровне частиц, слохно. Поэтому есть смысл моделировать этот процесс с помощью клеточных автоматов, которые сами состоят из частиц. Двумерная модель этого явления, использующая клеточные автоматы, была предложена М. Дрозом и его коллегами. Так как мы решили иметь дело с простейшими моделями, то рассмотрим одномерный случай.

Постановка задачи заключается в следующем. В тонкой длинной пробирке равномерно распределены частицы вещества в с концентрацией Ь0 и коэффициентом диффузии £>,. В левый открытый конец пробирки подается вещество л с концентрацией а0 ( ь0/а0=0.01 ) и коэффициентом диффузии ( В/С4=Д 1 >. Частицы ведут себя аналогично частицам из описанной выше модели решеточного газа, моделирующего диффузию. Только коэффициенты диффузии у частиц разного типа разные. Кроме того, что частицы могут перемещаться случайным образом, они с некоторой вероятностью к взаимодействуют друг с другом, образуя новые частицы типа с ( л+в->с ), которые тоже перемещаются случайным образом с коэффициентом диффузии вс ( с/с^О.1 ). Когда концентрация частиц типа с в малой окрестности становится выше критической *в, частицы с выпадают в осадок ( назовем частицы с, выпавшие в осадок, частицами типа о, которые находятся в покое ). Частицы с, находящиеся в малой окрестности частиц 1>, присоединяются к ним и становятся неподвижными, если плотность частиц с в малой окрестности превышает величину к<кп. Частицы с, находящиеся непосредственно над частицами о, выпадают в осадок автоматически. Итак, можно выделить четыре основных процесса, протекающих в системе:

1) диффузия,

2) реакция,

3) выпадение осадка,

4) агрегирование.

При выбранных соотношениях между коэффициентами диффузии и начальными концентрациями между веществами див частицы вещества а начинают проникать в пробирку, вступают в реакцию с частицами в, в результате чего выпадает осадок. Фронт реакции ( граница / между веществом див) постепенно распространяется вправо вдоль

пробирки и мы можем наблюдать образование осадка ( частицы в ) в виде различных пространственных структур. Нужно заметить, что образование осадка происходит только на границе между веществом л и в. Картина в левой части пробирки ( между левым концом пробирки, откуда поступает вещество л, и областью, где одновременно присутствуют и частицы л и частицы в ) не меняется.

Как показывает численный эксперимент, проведенный с помощью описанного выше клеточного автомата, картина определяется параметрами kn и к. При малых значениях к ( ситуация, когда появившиеся в результате реакции л+в->с частицы "с тут же выпадают в осадок ) осадок представляет собой сплошную однородную структуру ( см.рис.5а ). При увеличении кп однородная структура разбивается на отдельные группы осадка ( см. рис. 56 ). Нужно заметить, что при определенных значениях параметров к и к па рисунке выделяются две-три крупных области осадка, каждая из которых состоит из более мелких подобластей. Ширина мелких группировок осадка зависит от параметра параметра агрегации к. Чем он меньше, тем они шире. Чем он ближе к кп, тем ширина подгрупп осадка внутри каждой из больших областей уже ( они напоминают "палочки" ( см. рис. 56 )). Как ' характеризовать результаты вычислительного эксперимента? По каким показателям сравнивать их с данными лабораторных наблюдений?

Диссипативные структуры такого типа не являются традиционными, . поэтому встает вопрос об их адекватном количественном описании. Простейшая, наиболее грубая характеристика, связана с анализом величины

X

r(x)= J D( у) dy.

о

График этой функции грубо может быть аппроксимирован прямой. Тангенс угла наклона этой прямой характеризует среднюю плотность распределения осадка по пространству.

Однако, как уже упоминалось, отдельные области осадка оказываются как бы разбиты на более мелкие подобласти. Чтобы характеризовать эту "тонкую структуру" были построены автокорреляционная функция и спектр мощности. Первый минимум автокорреляционной функции показывает, ■ как быстро убывает вероятность выпадения осадка в соседних точках при условии, что он выпал в данной. В проведенных расчетах величина лг лежала в интервале 1«х 40. Для более широких групп осадка она больше, для

осадка в виде "палочек" - гораздо меньше. Тем самым скорость убывания пространственных корреляций оказывается довольно велика.

Для большей наглядности оказалось удобным сгладить спектр мощности по 10 соседним гармоникам. Характерной особенностью спектра является наличие "провала" в области средних гармоник ( см. рис. 6 ). Для сплошного выпадения осадка он малозаметен ( см. рис. 6а ). Для структур осадка в виде областей он хорошо выделяется ( см. рис. 66 ). Причем, чем больше значение ка при достаточно высоком значении кл, тем область "провала" шире. Можно сказать, что гармоники, находящиеся до области "провала", отвечают за крупномасштабную структуру распределения осадка. Гармоники, расположенные за областью "провала", связаны с широким спектром, порождаемым каждой отдельной "палочкой".

Еще, одной полезной зависимостью, удобной для анализа структур осадка стала функция R(e), полученная в результате кластерного анализа. При таком анализе две структуры, расстояние между которыми меньше е, отождествляются. Общее число структур на характерной пространственной длине L и дает значение Же). Полуширина распределения Rie) показывает, каково характерное расстояние между отдельными областями осадка ( см.рис.7 ).

Проведенный анализ неустойчивости Лизеганга показал, что при определенных параметрах процесса возможно формирование сложных пространственных конфигураций осадка. Введенные в работе количественные характеристики таких структур давт удобный способ сравнивать результаты проведенных расчетов с тем, что может дать натурный эксперимент.

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

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

Рассмотрим иерархическую структуру, которая имеет п уровней

э •з-' в <í 8 ея <f S8

в

еН"

й io é fe fe fe fe ¡te

3

&

E dt

\

It

40

sE tó

ifeo fe fe "áo ifer

Рис. 6. Спектр мощности, сглаженный по 10 соседним гармоникам: а - для структуры осадка из рис. 5а, б - для структуры осадка из рис. 56.

9+

В" од--а.

ftf

Я?

I) ib 2¡> ¿ з||

в--8--

в

v! '

4

k

a ¿ 3"

t a

tí e.

Рис.7. Вид зависимости числа кластеров R(e) от величины е: а - для структуры осадка из рис. 5а, d - для структуры. осадка из рис. 5<5.

ч

( см. рис. 8 ). Каждый человек в этой структуре имеет ш подчиненных, представляющих собой организационно отдел ( пользуясь терминологией, принятой в программировании, вся структура представляет собой дерево, каждый узел дерева имеет т ветвей, выходящих из него ). Таким образом, на первом сверху уровне находится один человек - руководитель организации, на втором - т человек, образущие группу его заместителей, на третьем сверху - т человек ( т отделов, в каждом из которых находится .по т человек ) ■ и т. д. Каждый работающий в организации имеет следующие две характеристики: <2 - компетентность и стаж работы Величина о изменяется в пределах от 0 до п и показывает число уровней вверх, включая данный, на которых сотрудник является компетентным. Например, если то сотрудник компетентен на

данном уровне, но на любом другом, расположенном выше, он уже не компетентен. Если <2=2, то сотрудник компетентен как на этом уровне, та- и на следующем ( более высоком ). Если е=0, это значит, что сотрудник достиг уровня своей некомпетентности, эт менятся от 0 до бтиах - максимальный стаж работы в данной организации, отработав который сотрудник уходит на пенсию. Время с дискретно ( й=0,1,2,... ). Эволюция иерархической структуры происходит в" следующем порядке :

1. "Выход на пенсию". Если бт > бтмлх, то 0=0, бг=0.

2."Продвижение вверх по службе".

Если образовалась вакансия, то выбирается кандидат на продвижение вверх из числа подчиненных. Для этого сначала отбираются сотрудники с максимальной компетентностью 0 среди кандидатов, затем среди них выбирается сотрудник с наибольшим стажем работы эт. Отобранный таким образом сотрудник занимает вакансию, а его место освобождается. При этом компетентность сотрудника о уменьшается на 1. Вакансии просматриваются сверху вниз. Поэтому на каждом шаге возможно продвижение вверх только на один уровень. Ситуация, когда сотрудника в течение года могут повысить два и более раз невозможна.

3. "Прием на службу".

Для того, чтобы заполнить вакансии на нижнем уровне, на работу принимаются новые сотрудники. Их компетентность определяется следующим образом. Считается, что человек всегда компетентен на том уровне, на который его приняли на работу ( уровне 1 >. Далее, с вероятностью Р он компетентен на следующем вверх, (1+1)-ом,

Рис. 8. Структура ¡шраряичесгой организации. Число уровней п=4, число сотруд:шхой з хаядсч отдела Черные квадраты

соответствует компетентный работникам, серые - некомпетентным.

Р1

Рис. 9. Зависимость среднего времени хиэни т иерархической организации ( число уровней в ней п=6, число сотрудников в каждом отделе ш=3, максимальный стаж работы зтмах=20, усреднение проводилось по ансамбл» из 200 систем ) от уровня образования общества, характеризуемого величиной р .

уровне, с вероятностью р^ он компетентен на (1+2)-ом уровне с т. д. Величина р является параметром, характеризующим степень образованности людей в области, где функционирует данна* организация.

4. "Шаг по времени": зт( с+1 )=5Т( с)+1.

Далее эти четыре шага повторяются.- Начальные условия выбере! следующим образом. На каждый уровень примем на работу людей п< описанному выше методу с вероятностью р . Будем считать, что 1 момент создания организации люди компетентны на всех уровня: ( Рд=1 ). А затем уровень образованности падает так. что Р(<1. Начальный стаж работы сотрудников примем равным номеру уровня, если считать снизу вверх, т. е. 1. Как оказалось, в некоторы моменты времени в рамках данной модели возникает ситуация, когд вакансия на каком-то уровне не может быть заполнена из-з отсутствия кандидатов ( все подчиненные одновременно вышли н пенсию ). В качестве выхода из такого положения будем принимат на работу человека со стороны прямо на этот уровень способом аналогичным способу приема на работу в начальный момент времени только с уровнем образования р .

На рис. 9 представлена зависимость среднего "времени жизни" I усреднение проводилось по статистическому ансамблю из 100 одинаковых систем, за каждой из которых велось наблюдение н более 200 лет ) от величины р при следующих значениях остальнь параметров: число уровней п=6, число сотрудников в отделе т=2 максимальный стаж работы бтнах=20. Как видно из рисунка эт зависимость подобна зависимости т(р )=Т0+а(1. -р ) ~ь, где то, а ъ - некоторые величины, определяемые остальными параметра* системы. В данном случае Го=31, а=2.5 и Ь=1. 8.

Как показал вычислительный эксперимент увеличение чио> сотрудников в каждом отделе ведет к увеличению среднего време! низни организации. Увеличение же числа уровней в организац! приводит к неоднозначным изменениям в длительности времени жиз! организации. При невысоком уровне образованности ( Р(=0. например ) увеличение числа уровней вызывает снижение зреме] жизни организации, при достаточно же высоком уров: образованности ( Р(=0. 7 ) - наоборот ( приводит к бол* продолжительному времени жгзни ).

В государственных структурах, в транснациональных корпораци наличие многих иерархических уровней является жизнгнн

еобходимостью. Таковы психологические возможности человека число параметров;, за которыми человек может достаточно ффективно следить не превышает семи и число ' сотрудников, с оторыми человек в состоянии эффективно работать, весьма евелико ) и особенности больших систем ( необходимо следить за чень большим количеством параметров ). Из обсуждаемой модели ледует, что снижение уровня образования, а с ним и омпетентности сотрудников, может сделать неэффективным ункционирование и бессмысленным создание сложных иерархий.

3. ОСНОВНЫЕ РЕЗУЛЬТАТЫ.

1. С помощью простейшего одномерного клеточного автомата, юделирующего колебательные химические реакции, обнаружены новые ■ипы упорядоченности и новые качественные эффехты в таких >еакциях ( "вытеснение фазы", возникновение "счетчиков волн", юявление "автоволновой области" в пространстве параметров ).

2. Обнаружены новые качественные эффекты при анализе (вумерного клеточного автомата, являющегося обощением модели г. Ооно и М. Кохмото. Среди них новый тип спиральных волн и объекты •ипа "планеров" ( передвигающихся локализованных структур ).

3. Исследованы характеристики алгоритмов, основанных на использовании клеточных автоматов, для моделирования диффузии. С юмощыо этих алгоритмов изучена неустойчивость Лизеганга и фоанализированы основные типы одномерных структур.

4. По;троена новая модель функционирования иерархической >рганизации. В рамках этой модели выяснено, как влияет ее структура и уровень образования сотрудников на деятельность >рганизации.

Основные результаты диссертации опубликованы в следующих работах:

1. Иалянецкий Г. Г., Бакаева П. С. Анализ семейства клеточных автоматов, моделирующих колебательные химические реакции. Препринт ИПМ им. М. В. Келдыша, 1991, №57, 36с.

2. иалинецкий Г. Г.. ¡¡¡а к а ев а U. С. К исследованию клеточного автомата, моделирующего колебательные химические реакции.// Докл. АН СССР, 1991, т. 321, N4, с. 711.

3. Иалинецкий Г. Г., Еакаева IU.C. Об одном незаконном двумерном автомате. Препринт ИПМ им. М. В. Келдыша, 1992, №39, 30с.

4. Иалинецкий Г. Г., Шакаева П. С. О клеточном автомате, моделирующем колебательные химические реакции на поверхности.// Докл. АН ССССР, 1992, т. 325, №4, с. 716.

5. Иалинецкий Г. Г., Шакаева U.C. Клеточные автоматы в математическом моделировании и обработке информации. Препринт ИПМ им. М. В. Келдыша РАН, 1994, Н-57, 34с.

6. Malinetski i G.G.. shakaeva ff. С. Cellular Automata in Mathematical Modelling and Data Proccesing.// Pattern Recognition and Image Analysis, 1995, V.5, №1, p.64-78.

7. Иалинецкий Г. Г., Еакаева U.C. Клеточные автоматы в математическом моделировании колебательных химических реакций на поверхности.// Журнал физической химии. 1995, т. 69, #8, с. 1523.

8. иалинецкий Г. Г. , Шакаева U.C. Модель иерархической организации. Препринт ИПМ им. М. В. Келдыша, 1995. №39, 26с.

В заключение автор считает приятным долгом поблагодарить научного руководителя Малинецкого Г. Г. за постоянное внимание, поддержку и помощь в постановке задач и работе, а также Потапова А. Б. за ряд важных замечаний при обсуждении полученных результатов.

ВВЕДЕНИЕ.

1. Что такое клеточный автомат? История возникновения и основные направления развития.

2. Клеточные автоматы в математическом моделировании физических явлений.

3. Краткое содержание работы.

ГЛАВА 1. Одномерный клеточный автомат, моделирующий колебательные химические реакции.

1.1. Основные типы упорядоченности в 0М10 - модели.

1.2. Обобщение модели на случай большего числа состояний.

0MN10 - модель.

1.3. Выводы.

ГЛАВА 2. Двумерный клеточный автомат, моделирующий колебательные химические реакции на поверхности.

2.1. Описание модели.

2. 2. Эволюция простых начальных данных.

2. 3. Выводы.

ГЛАВА 3. Применение клеточных автоматов в моделировании процессов диффузии.

3.1. Моделирование процесса диффузии.

3.1.1. Постановка задач.

3.1.2. Классические методы решения.

3.1.3. Метод конечных разностей.

3.1.4. Метод Монте-Карло.

3.1.5. Использование клеточных автоматов.

3.2. Моделирование процесса образования осадка в системе типа "реакция-диффузия".

3. 3. Выводы.

ГЛАВА 4. Модель иерархической организации.

4.1. Описание модели.

4. 2. Результаты моделирования.

4.2.1. Новые сотрудники поступают только на нижний уровень.

4.2. 2. Новые сотрудники могут поступать на любой уровень.

4.2.3. Некомпетентному директору предлагают другое место.

4.3. Выводы.

1. Что такое клеточный автомат? История возникновения и основные направления развития.

Многие сложные системы в природе состоят из простых связанных подсистем, каждая из которых подчиняется элементарным законам или правилам. Однако результатом их коллективного функционирования может быть сложное поведение всей системы. Клеточные автоматы относятся к математическим моделям такого типа.

Исследование клеточных автоматов имеет почти полувековую историю. Клеточные автоматы были введены Дж. Нейманом в его работе о конструировании самовоспроизводящихся машин [11. В этой работе был построен достаточно сложный автомат, порождающий самовоспроизводящиеся конфигурации в клеточном пространстве. По мнению Дж. Неймана, многие биологические процессы естественно описывать на языке клеточных автоматов, а не дифференциальных уравнений. Оказалось также, что клеточные автоматы позволяют моделировать сложное поведение ряда распределенных систем более просто и наглядно, чем уравнения в частных производных. Например, клеточный автомат, предложенный Н.Винером и А. Розенблютом в 1947 году для описания сердечных аритмий, допускает простое аналитическое исследование. В то же время, уравнения в частных производных, имитирующие такое же поведение, требуют сложного компьютерного анализа [21.

Чтобы определить клеточный автомат, нужно задать решетку обычно одинаковых ячеек-клеток ( i=1,2,. ), набор возможных значений, которыми характеризуются их состояния < u^ и2,., ц } и правило эволюции конфигураций клеток во времени. Состояние клетки i,t) ( где i - координата клетки, величина а может принимать только значения { и u2.} ) меняется в дискретные моменты времени t=l,2. Состояние клетки в следующий момент времени зависит от состояния A(i,t) самой клетки и состояний ее соседей в данный момент. Например, в одномерном клеточном автомате величина A(i,t) для клетки с координатой i на бесконечной прямой изменяется во времени по следующему закону:

Aii,t+1 > = F( Aii-r.t), . . . ,A(i, t), . . . ,A(i+r, t) ), (1) где г - размер окрестности, 2г - число "соседей".

Функция F может быть детерминированной ( в этом случае говорят о "детерминированном" клеточном автомате ), а может зависеть от некоторой случайной величины ( это так называемые "стохастические" автоматы ).

Вид функции F, определяющей правило эволюции автомата, может быть задан "кодом" автомата:

Z^-Ad+j) j=-r

R= I F[A(i-r), . . . ,A(i+r)]-K . (2) Г

A ( i-r).A ( i + r ) >

В целом, для фиксированного числа к состояний клеток и числа 2г+1 соседей общее количество различных правил вида (1) равно

2г+1) к . То есть, в самом простом случае, при 2 и r=1 ( каждая клетка может принимать только два значения и правило эволюции зависит только от значений двух ближайших клеток - соседей ) з количество возможных правил равно 22 =256. Отсюда понятно, что с помощью компьютера можно изучить только ничтожную часть всего множества автоматов. Поведение их может быть очень разнообразным. Большинство полученных к настоящему времени результатов относится к классу законных суммирующих автоматов. Законными называют автоматы, для которых выполняются следующие два условия:

F(0, 0.0)=0, (3)

F( А[ i~r, t), . . . , i+r, t) ) = F( л(1+г, t), . . . , A{i-r, t) ). (4)

Суммирующими называются правила, зависящие не от значений отдельных клеток в окрестности, а от их общей суммы: г

Л(1,t+l)=F(£ A{i+j,t)). (5)

Различают также внешне суммирующие правила, зависящие отдельно от значения в данной клетке и от суммы значений ее соседей, исключая данную. Однако и этот, более узкий, класс автоматов очень велик. Естественно, важно было бы установить общие качественные и количественные закономерности поведения автоматов.

Можно выделить два основных подхода к изучению клеточных автоматов, которые условно называются статистическим и конструктивным. При конструктивном подходе рассматривается конкретный автомат и выясняется, как он ведет себя при различных начальных конфигурациях, какие структуры при этом возникают, как они взаимодействуют и т. д. При статистическом подходе считается, что начальные данные взяты наугад и рассматриваются статистические свойства возникающих конфигураций ( среднее число клеток в определенном состоянии, энтропии, размерности и т.д. ).

Обычно выделяют четыре класса качественного поведения законных суммирующих клеточных автоматов в случае неупорядоченных начальных данных ( см. рис. 1 ). Эволюция автоматов первого класса приводит к пространственно-однородным состояниям ( л(i,t)= О, t=1,2,; -ю < i < « ( см. рис. 1а )), эволюция автоматов второго класса - к простым периодическим во времени структурам ( см.рис. 16 ). Автоматы третьего класса порождают

Г)

С-20

Рис.1. Примеры конфигураций, порождаемых в результате эволюции клеточных автоматов четырех классов ( число состояний te=2, радиус окрестности г=2 ) в случае неупорядоченных начальных данных. Белые квадраты представляют клетки со значением О, черные - клетки со значением 1. Правила данных клеточных автоматов являются суммирующими» с кодами (а) 4, (б) 56, (в) 10, (г) 20. Код для суммирующих правил определяется формулой

2r+l)(к-1)

Cf= I knf[n] ( см. t4] ь п = О непериодические конфигурации клеток ( см.рис. 1в ). Клеточные автоматы четвертого класса демонстрируют довольно сложное поведение ( см.рис. 1г ), с различными локализованными и перемещающимися структурами. Такое качественное поведение автоматов могут описывать различные количественные характеристики [3].

Клеточные автоматы можно рассматривать как дискретные динамические системы. Их глобальные свойства могут быть получены путем изучения эволюции автоматов из множества всех возможных начальных конфигураций. Первые три класса автоматов имеют аналоги среди аттракторов непрерывных динамических систем ( устойчивых особых точек, предельных циклов, странных аттракторов ). Автоматы четвертого класса демонстрируют сложное поведение с долгими переходными процессами и поэтому прямого аналога среди аттракторов непрерывных динамических систем для них нет.

Теория динамических систем дает первый подход к количественной классификации поведения клеточных автоматов. При их исследовании можно так же, как в теории динамических систем, вводить разнообразные количественные характеристики аттракторов - ляпуновские показатели, различные виды энтропий и размерностей [3,41.

Особый интерес представляют собой автоматы четвертого класса. Было высказано предположение о том, что автоматы этого класса могут демонстрировать сколь угодно сложное поведение. В принципе поведение любой системы можно смоделировать, имитируя шаг за шагом ее эволюцию. Но в большинстве случаев можно найти более простой алгоритм. Например, чтобы умножить число с помощью компьютера на 2П, нет необходимости 2П раз складывать его с самим собой, можно просто сдвинуть его представление в памяти ЭВМ на п двоичных разрядов. Системы, для которых такие более простые алгоритмы существуют, называют вычислительно приводимыми. Именно это свойство помогает при описании явлений природы выделить небольшой набор существенных переменных, часто называемых параметрами порядка, или переходить к более простому статистическому описанию.

Гипотеза С. Уолфрема, известного специалиста по клеточным автоматам [3-51, состоит в том, что многие физические системы и их модели, для которых в настоящее время не известно простого описания, являются вычислительно неприводимыми. Для них в принципе не могут быть построены эффективные теории. Для них попросту нет способа выяснить, что получится в конце, если непосредственно не проследить эволюцию самой системы или имитирующей ее модели последовательно, шаг за шагом до конца. Единственный способ анализа таких систем - физический или вычислительный эксперимент.

Автоматы четвертого класса относятся именно к таким системам. Не существует простого алгоритма, позволяющего предсказать эволюцию даже локализованных начальных конфигураций. Ярким примером автоматов четвертого класса является двумерный клеточный автомат, называемый игрой "Жизнь" [6,7]. Модель демонстрирует происхождение, рост и развитие сообществ живых клеток < их обычно называют "организмами" ). Эта игра определяется следующими правилами. Рассмотрим квадратную решетку клеток на плоскости. Клетка в момент времени t в точке с координатами i, j на бесконечной плоскости ( t , i , j - дискретные переменные ) может находиться в одном из двух состояний л(i, j, t)=0 ( "мертвая клетка" ) или A(i,j,t)=l ( "живая клетка" ). Сначала задается некоторое исходное состояние A(i, j, 0), < i < о», -» < j < а далее на каждом шаге вычисляется величина i+i j+i

A'(i,jtt)= I I л( k, I, t)- A{i,j,t). (6) k = i-x i = j-1

Это сумма значений по ближайшим восьми соседям данной клетки ( такую окрестность называют также окрестностью Мура; если же в качестве соседей рассматриваются только клетки, имеющие с данной общую сторону, то окрестность называется окрестностью Неймана ). Значение в следующий момент определяется формулой

4(i,j,t+l> = F( а( i, j,t); А* ( i, j, t) ), (7) где F(0,3)=1; F(l,y)=l, если y=2 или y=3; Fix, y)=0 в остальных случаях.

Эта модель может описывать большой набор стационарных структур ( локализованных в пространстве конфигураций, повторяющих себя на каждом шаге) и циклов sp, повторяющих себя через р шагов ( см. рис. 2 ). В ней существуют движущиеся конфигурации: "планер" ( см. рис. 2 ), различные "корабли", "паровоз". Анализ игры "Жизнь" позволил построить конфигурацию "планерное ружье", испускающую поток "планеров" [6,7]. Столкновение "планеров" может приводить к их "аннигиляции", к возникновению стационарных структур или более сложных конфигураций.

Существует предположение, что автоматы четвертого класса эквивалентны универсальным вычислительным машинам. Это свойство доказано для одного одномерного автомата с числом состояний клетки fc=18 [81 и для игры "Жизнь" 17]. Все основные компоненты компьютера могут быть в ней смоделированы с помощью определенных начальных конфигураций. Имеющиеся в ней перемещающиеся объекты - "планеры" - можно использовать для передачи информации, а различные сценарии их столкновений - для реализации логических ill a

I: 1 t= о t= 5 1 t= 10 i m t= 15 ж t= 20 В

Рис.2. Различные конфигурации в игре "Жизнь". Черные квадраты представляют "живые" клетки, белые - "мертвые", а - стационарные структуры; б - примеры циклов ( чтобы узнать, что будет в следующий момент времени, достаточно заменить левый крайний столбец на средний, а затем средний - на правый крайний ); в - планер. операций. Например, "аннигиляция" планеров может выполнять логическую функцию "НЕ". Роль "часов" < а это важный элемент в вычислительной системе ) может играть "планерное ружье", выпускающее планеры с некоторой определенной частотой.

В настоящее время существует три основных направления, по которым развиваются клеточные автоматы [9-101. Объектом исследований первого направления являются сами клеточные автоматы. Здесь рассматриваются вопросы, касающиеся того, как ведут себя автоматы разных классов; вводятся различные виды энтропий, размерностей, ляпуновские показатели, изучается устойчивость автоматов к малым возмущениям в начальных данных, проводится аналогия между конфигурациями автоматов и элементами канторова множества, автоматы сравниваются с формальными языками и т. д. Это направление тесно связано с работами известного специалиста по теории клеточных автоматов С. Уолфрема 13-51.

Второе направление развития клеточных автоматов связано с рассмотрением их как систем, способных обрабатывать информацию, задаваемую начальными конфигурациями. Как уже было сказано выше, существуют клеточные автоматы, эквивалентные универсальным вычислительным машинам. Основные компоненты вычислительного устройства могут быть сконструированы в них с помощью различных начальных конфигураций. Об одном таком клеточном автомате - игре "Жизнь" уже было рассказано. Другая модель клеточного автомата - модель биллиардных шаров [11,121 - явилась практической основой для создания архитектуры машин клеточных автоматов, речь о которых пойдет ниже.

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

В последнее время машины клеточных автоматов, т. е. ЭВМ, сконструированные специально для вычислений с помощью клеточных автоматов и по своей архитектуре напоминающие клеточный автомат, получили широкое распространение в научных кругах, использующих идеи клеточных автоматов для решения различного рода проблем. Одной из первых таких машин является машина клеточных автоматов, созданная Т.Тоффоли и Н.Марголусом 1121. По скорости вычислений для моделей, представляющих собой клеточные автоматы, она сравнима с машинами типа Сгау-1.

Итак, два основных достоинства клеточных автоматов с точки зрения вычислительных систем - это локальность взаимодействия и параллельность вычислений. Второе из этих свойств, как мы уже упоминали, делает клеточные автоматы привлекательными для создания современных вычислительных систем с высокой степенью параллельности. С другой стороны, совершенствование ЭВМ идет сейчас по пути увеличения компактности и уменьшения пути прохождения сигнала с целью увеличить скорость вычислений и уменьшить расход энергии. В клеточных автоматах связи между отдельными элементами являются локальными и размеры автомата не зависят от пути прохождения сигнала. Поэтому машины клеточных автоматов могут быть одновременно и очень большими, и очень быстрыми.

Более того, топология моделируемого объекта в машинах клеточных автоматов воспроизводится самим же моделирующим устройством, в отличие от традиционных компьютеров, что несомненно имеет свои преимущества при изучении моделируемых явлений, делая этот процесс более наглядным.

Тенденция к уменьшению размеров отдельных элементов ЭВМ, а также к упрощению связей между ними ведет к тому, что в будущем элементы могут стать сравнимы с размерами отдельных молекул. Это нашло свое отражение в развитии молекулярных электронных устройств, где также используются идеи клеточных автоматов [131.

Третье направление развития клеточных автоматов связано с применением последних в математическом моделировании различных физических явлений. Об этом направлении и будет рассказано более подробно.

4. 4. Выводы.

Проведенный анализ построенной модели иерархической организации привел к ряду важных выводов.

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

С другой стороны, ряд результатов, связанных с зависимостью среднего времени жизни организации от числа сотрудников в отделе, с возможностью набирать компетентных сотрудников со стороны, со сменой некомпетентного директора, представляются достаточно естественными. Они подтверждаются опытом развития самых разных иерархических структур.

Гораздо менее очевидной и более любопытной является зависимость среднего времени жизни от числа уровней в организации. При высоком уровне образования оказывается среднее время жизни организации немонотонно зависит от числа иерархических уровней. Есть простое интуитивное соображение, показывающее, почему это может быть так. Отметим, что полностью некомпетентным чаще всего становится самый верхний уровень ( начальник организации ) или второй сверху ( заместители начальника ). Пусть Ri - вероятность того, что после очередного замещения вакансии на уровне i на данном месте появился некомпетентный сотрудник, a v - вероятность образования вакансии в каком-либо отделе на уровне с номером i. Тогда вероятность того, что директор организации станет некомпетентным, равна

Л) j? = £ t r1 1-r ){l-p)+i?i2(l-r )2(1-р)2+. . .+ п ^ п-1 п-1 п-1 п-1 п-1

1=1 (1-Я )l(l-P)l](l-F )\ п-1 п-1 где Р - уровень образования. Из устройства модели следует, что fi^O. Если уровень образования невелик и людей, которые способны руководить, мало, то жизнеспособность иерархии будет определяться тем, успеет ли "талант" ( компетентный на всех уровнях сотрудник ) добраться до верхнего уровня за время своей работы. Естественно, чем больше уровней в иерархии, тем меньше вероятность этого. Но, с другой стороны, при высоком уровне образования ( Р-> 1 ), Это значит, что последовательность я убывающая. Следовательно, вероятность некомпетентности директора с увеличением п падает, что приводит к увеличению времени жизни организации { "целое" может жить дольше, чем часть ). При остальных значениях величины р, характеризующей уровень образования, эта формула заслуживает более внимательного изучения. В частности, вопрос нахождения критического значения уровня образования pfcr, которое меняет характер зависимости времени жизни организации от числа уровней в ней ( при P<Pkr увеличение числа уровней приводит к уменьшению времени жизни организации, при р>р - к его увеличению ).

ЗАКЛЮЧЕНИЕ.

В заключение сформулируем основные результаты диссертации.

1. С помощью простейшего одномерного клеточного автомата, моделирующего колебательные химические реакции, обнаружены новые типы упорядоченности и новые качественные эффекты в таких реакциях ( "вытеснение фазы", возникновение "счетчиков волн", появление "автоволновой области" в пространстве параметров ),

2. Обнаружены новые качественные эффекты при анализе двумерного клеточного автомата, являющегося обощением модели У. Ооно и М. Кохмото. Среди них новый тип спиральных волн и объекты типа "планеров" { передвигающихся локализованных структур ).

3. Исследованы характеристики алгоритмов, основанных на использовании клеточных автоматов для моделирования диффузии. С помощью этих алгоритмов изучена неустойчивость Лизеганга и проанализированы основные типы одномерных структур.

4. Построена новая модель функционирования иерархической организации. В рамках этой модели выяснено, как влияет ее структура и уровень образования сотрудников на деятельность организации.

В заключение автор считает приятным долгом поблагодарить научного руководителя Малинецкого Г. Г. за постоянное внимание, поддержку и помощь в постановке задач и работе, а также Потапова А. Б. за ряд важных замечаний при обсуждении полученных результатов.

1. Нейман Дж. Теория самовоспроизводящихся автоматов. М. , "Мир", 1971, 381с.

2. Packard N. H,, Wolfram s. Two-dimensional cellular automata.// Journal of Statistical Physics, 1985, V.38, p.901-946.

3. Компьютеры и нелинейные явления : Информатика и современное естествознание. М.: "Наука", 1988, 192с.

4. Налинецкнй Г.Г., Бакаева М. С. Клеточные автоматы в математическом моделировании и обработке информации. // Препринт ИПМ им. М. В. Келдыша РАН, 1994, №57, 34с.

5. Налинецкий Г. Г., Шакаева N.C. Cellular Automata in Mathematical Modelling and Data Proccesing.// Pattern

6. Recognition and Image Analysis, 1995, V.5, №1, p.64-78.11. vichniac g. y. Simulating physics with cellular automata.// Physica D, 1984, V.10, p.96-116.

7. Тоффоли Т. , Марголус Я. Машины клеточных автоматов. М.: "Мир", 1991.- 278с.13. carter f.l. The molecular device computer: point of departure for large scale cellular automata.// Physica D, 1984, V. 10, #1-2, p.175-194.

8. Droz м. ,chopard в. Cellular Automata approach to physical problems.// Helvetica Physica Acta, 1988, V.61, p.801-816.

9. Levermore c. D., Boghosian в.м. Deterministic cellular automata with diffusive behavior,// Cellular Automata and Modeling of Complex Physical Systems, ed. by P.Manneville, Springer, Berlin, 1990, p.118-129.

10. Oono Y., Kohmoto m. Discrete model of chemical turbulence.// Phys.Rev.Lett., V.55 (1985), .№27, p.2927-2931.

11. Frish u. and others. Lattice gas hydrodynamics in two and three dimensions.// Complex systems, 1987, V.1, p.649-707.

12. Gunstensen A. K., Rothman D.H, A lattice-gas model for three immiscible fluids.// Physica D, 1991, V.47, p.47-52.

13. Papatzacos p. Numerical calculations of the equation of flow in porous media: the lattice gas approach.// Numerical Journal of Computational Physics, 1993, V.104, p.313-320.

14. Liu F., Goldenfeid N. Deterministic lattice model for diffusion-controlled crystal growth.// Physica D, 1991, V.47, p.124-131.29. vicsek K. Pattern formation in diffusion-limited aggregation.// Physical Review Letters, 1984, V.53, Jf24, p.2281-2284.

15. Baer . Automata and biology.// Ann. Rev. Biophys., 1974, V.3, p.255.

16. Burks c. , Farmer d. Towards modeling DNA sequences asautomata.// Physica D, 1984, V.10, №1-2, p.157-167.

17. Пер Бак, Кан Чей. Самоорганизованная критичность.// В мире науки, 1991, #3, с.16-24.

18. Bak р. , Tang ch., wiesenfeld к. Self-organized criticality.// Physical Review A, 1988, V.38, #1, p.364-374.

19. Bak p., chen к., creutz м. Self-organized criticality in the "Game of Life".// Nature, 1989, V.342, p.780-782.

20. Chen к, Bak p. Is the universe operating at a self-organized critical state?// Physics Letters, 1989, A 140, №6, p.299-302.

21. Parodi o., ottavi н. Simulating the Ising model on a cellular automata.// Cellular Automata and Modeling of Complex Physical Systems, ed. by P.Manneville, Springer, Berlin, 1990, p.82-97.

22. Pederson J. Continious transition of cellular automata.// Complex systems., 1990, №4, p.653-665.

23. Додд P. , Зйлбек Дх. , Гиббен Дж. , Маррнс X. Солитоны и нелинейные волновые уравнения. М., "Мир", 1988.

24. Зыков В. С. Моделирование волновых процессов в возбудимых средах. М., "Наука", 1984.

25. Маяинецкий Г. Г. , Бакаева И. С. Анализ семейства клеточных автоматов, моделирующих колебательные химические реакции. // Препринт ИПМ им. М. В. Келдыша АН СССР, 1991, №57, 36с.

26. Малинецяяй Г. Г. , Шакаева М. С. К исследованию клеточного автомата, моделирующего колебательные химические реакции. // Докл. АН СССР, 1991, т. 321, *4, с. 711.

27. Ма!яяецкий Г. Г. , 1акаева М. С. Клеточные автоматы в математическом моделировании колебательных химических реакций на поверхности.// Журнал физической химии, 1995, т. 69, №8,с. 1523.

28. Малинецкий Г. Г., Панаева М.С. Об одном незаконном двумерном автомате.// Препринт ИПМ им. М. В. Келдыша АН СССР, 1992, №39, 30с.

29. Малинецкий Г. Г. , Шакаева М. С. О клеточном автомате, моделирующем колебательные химические реакции на поверхности.// Доклады АН СССР, 1992, т. 325, №4, стр. 716-723.

30. Ахромеева Т. С. , Курдюмов С. П. , Малинецкий Г. Г. , Самарский А. А. Нестационарные структуры и диффузионный хаос. М. , "Наука", 1992, 544с.

31. Зыков В. С. у Михайлов А. С. Вращающиеся спиральные волны в простой модели возбудимой среды.// Докл. АН СССР, 1986, т. 286, с. 341.

32. Тихонов А. И., Самарский А. А. Уравнения математической физики. М.: "Наука", 1977.

33. Гулин А. В., Самарский А. А. Численные методы. М.: "Наука", 1989, 432с.

34. Соболь И. М. Метод Монте-Карло. М.: "Наука", 1985, 80 стр.

35. Бусленко Н. П. и др. Метод статистических испытаний. М.: Физматгиз, 1962.

36. Квасников И. А. Термодинамика и статистическая физика. Теория неравновесных систем. МГУ, 1987.

37. Liesegang R.E.// Z. Phys. Chem., 1897, В.23, S.365.

38. Зельдович Я. Б. , Годес 0. М. 0 математической формулировкетеории периодического осаждения.// ЖФХ, 1949, вып. 2, 180-191 с.

39. Брун Е, Б., Гладышев Г. П. К теории периодического образования осадков при встречной диффузии реагирующих веществ. 1. Случайнеобратимой реакции. // ЖФХ, 1983, т. 57, #6, 1337-1342с.

40. Кнут 2. Искусство программирования для ЭВМ. М.: "Мир", 1976, т. 1, 734с.

41. Налынецкий Г. Г., Еакаева И. С, Модель иерархической организации.// Препринт ИПМ им. М. В. Келдыша РАН, 1995, №39, 26с.

42. Годфруа X. Что такое психология? М.: "Мир", 1992, т. 1, 496с., т. 2, 376с.