Клеточно-автоматное моделирование самоорганизующихся реакционно-диффузионных процессов тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Киреева, Анастасия Евгеньевна

• Киреева, Анастасия Евгеньевна
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Киреева, Анастасия Евгеньевна

Оглавление

Оглавление

Введение

Глава 1 Моделирование процессов структурообразования с помощью тоталистического клеточного автомата

1.1 Основные понятия теории клеточных автоматов

1.2 Формальное определение тоталистического клеточного автомата

1.3 Эволюция тоталистического клеточного автомата

1.4 Зависимость эволюции №ТКА с матрицей весов, содержащей одно значение ингибитора, от значений весовых коэффициентов

1.4.1 Классификация устойчивых структур, формирующихся в результате эволюции ХГКА приа? = 2

1.4.2 Классификация устойчивых структур, формирующихся в результате эволюции при ¿/= 3

1.5 Зависимость эволюции КТКА с матрицей весов, содержащей два значения ингибитора, от значений весовых коэффициентов

1.6 Двухслойный тоталистический клеточный автомат

1.7 Выводы

Глава 2. Клеточно-автоматная модель каталитической реакции окисления

монооксида углерода на металлах платиновой группы

2.1 Реакция окисления СО на поверхности металлов платиновой группы

2.2 Механизм реакции окисления СО на поверхности платины Р^оо

2.3 Клеточно-автоматная модель реакции окисления СО на Р1

2.4 Результаты моделирования реакции окисления с помощью асинхронного

вероятностного КА К со

2

2.5 Влияние размера массива и интенсивности диффузии на динамику реакции окисления

2.6 Бифуркационная диаграмма реакции окисления, построенная с помощью К со

2.7 Выводы

Глава 3. Параллельная реализация асинхронных клеточных автоматов на основе блочно-синхроннош преобразования

3.1 Преобразование асинхронного КА в блочно-синхронный

3.2 Проверка применимости бл очно-синхронного преобразования асинхронных КА

3.2.1 Проверка применимости блочно-синхронного преобразования для асинхронного тоталистического КА КТКА

3.2.2 Проверка применимости блочно-синхронного преобразования для асинхронного двухслойного тоталистического КА

3.2.3 Проверка применимости блочно-синхронного преобразования для асинхронного КА , моделирующего реакцию окисления СО на Р1юо----92

3.3 Результаты распараллеливания блочно-синхронного КА

3.3.1 Результаты распараллеливания блочно-синхронного двухслойного тоталистического КА

3.3.2 Результаты распараллеливания блочно-синхронного КА Ксо, моделирующего реакцию окисления СО на Р^оо

3.4 Выводы

Заключение

Список литературы

Введение диссертации (часть автореферата) на тему «Клеточно-автоматное моделирование самоорганизующихся реакционно-диффузионных процессов»

Введение

Актуальность работы

Структурообразование лежит в основе многих природных явлений. Наиболее известными примерами возникновения устойчивых структур в живой и неживой природе являются конвективные и гидродинамические ячейки, вихри в атмосфере и океане, лазеры, концентрические круги и движущиеся спирали в реакции Белоусова-Жаботинского, поверхностные волны в реакциях гетерогенного катализа, раскраска животных и растений. Формирование различных пространственно-временных структур происходит в результате самоорганизации в сложных многокомпонентных нелинейных системах. Основная идея самоорганизации заключается в том, что в неравновесных условиях сложная система качественно изменяет свое макроскопическое поведение за счёт самопроизвольного упорядочивания составляющих её простых элементов [1, 2]. Изучение явлений самоорганизации имеет большое значение как с фундаментальной, так и с практической точки зрения. В системах самой различной природы могут возникать похожие устойчивые структуры. Следовательно, выявление общих принципов самоорганизации и структурообразования является ключевым в понимании основных механизмов физико-химических, биологических, социальных процессов и закономерностей их развития. С практической точки зрения, самоорганизация в наносистемах позволяет создавать наноструктуры с различной морфологией и формой, и как следствие, с различными свойствами.

Изучению устойчивых структур, возникающих в неравновесных открытых системах (диссипативных системах), посвящено большое число работ. Основы общей теории диссипативных структур сформулировал А. Тьюринг в 1952 г. [3], в этой работе он показал, что в гомогенной неперемешиваемой реакционной системе типа реакция-диффузия при определённых условиях может установиться периодическое в пространстве и стационарное во времени распределение концентраций. Экспериментально структуры Тьюринга были обна-

ружены в реакции Белоусова-Жаботинского и в реакции хлорит-иодид-малоновая кислота (ХИМ). Структуры Тьюринга представляют интерес не только для изучения кинетики химических реакций, аналогичные структуры возникают в биологии. На основе работ Тьюринга был разработан целый класс моделей реакционно-диффузионного типа. Классической моделью морфогенеза является реакционно-диффузионная модель активаторно-ингибиторного типа Гирера-Майнхардта [4, 5]. В этой модели клетки развивающегося организма могут продуцировать два морфогена: активатор и ингибитор, способные диффундировать в другие клетки. Разная скорость диффузии активаторов и ингибиторов приводит к неустойчивости и формированию пространственных структур. Математические модели генетического триггера Жакоба и Моно, Д.С. Чер-навского [6], описывающие процесс дифференциации клеток, основаны на ак-тиваторно-ингибиторном механизме. Основной характеристикой этих моделей является тригтерность - возможность переключения системы из одного состояния в другое, переключение происходит вследствие синтеза активных и неактивных ферментов. Дж. Марри предложил модель формирования структур на шкурах животных, основанную на активаторно-ингибиторном механизме [7], кроме того, Дж. Марри сделан большой обзор реакционно-диффузионных систем, использующихся для изучения нелинейных биологических процессов: возникновения биологических осцилляций, однородных колебаний и пространственных структур [8].

Большой вклад в исследование проблем самоорганизации внесли Г. Хакен, И. Пригожин [9], Г. Николис, A.M. Жаботинский, Б.П. Белоусов, Д.А. Янг, В.К. Ванаг и др. Существует несколько подходов к изучению самоорганизации сложных систем различной природы: синергетическая модель параметров порядка и принципа подчинения Г. Хакена, теория диссипативных структур И. Пригожина, концепция эволюции органических молекул М. Эйге-на, концепция эволюции открытых каталитических систем А.П. Руденко, модели формирования и эволюции нестационарных структур в режимах с обостре-

5

нием A.A. Самарского и С.П. Курдюмова и др.

Существенную роль в исследовании явлений самоорганизации играет теория нелинейных колебаний и волн, основоположниками которой являются Л.И. Мандельштам, A.A. Андронов, A.A. Витте, С.Э. Хайкин и др. [10, 11]. В рамках этой теории изучаются сложные, нерегулярные колебательные и волновые режимы, возникающие в открытых нелинейных динамических системах: автоколебания, бифуркации, стохастические колебания, хаос. Наиболее интересным и важным направлением теории нелинейных колебаний является исследование формирования и динамики автоколебаний и автоструктур. Термин «автоколебания» введён A.A. Андроновым и обозначает незатухающие устойчивые колебания в диссипативной динамической системе с нелинейной обратной связью, поддерживающиеся за счёт энергии постоянного внешнего воздействия, на фазовой плоскости автоколебаниям соответствует устойчивый предельный цикл. Автоструктуры определены в работе [12] A.B. Гапонова-Грехова и М.И. Рабиновича как пространственные образования, устойчиво существующие в диссипативных неравновесных системах и не зависящие от граничных и начальных условий, на фазовой плоскости автоструктурам соответствует устойчивый фокус.

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

Для изучения самоорганизации сложных нелинейных систем эффективно может быть использована теория клеточных автоматов, в которой динамика системы описывается простыми дискретными правилами переходов. Классическое определение клеточного автомата, дано в [14]: "Клеточные автоматы являются дискретными динамическими системами, поведение которых полно-

стью определяется в терминах локальных зависимостей. [...] Пространство представлено равномерной сеткой, каждая ячейка которой, или клетка, содержит несколько битов данных; время изменяется дискретными шагами, а законы мира выражаются единственным набором правил, по которым любая клетка на каждом шаге вычисляет своё новое состояние по состояниям её близких соседей. Таким образом, законы системы являются локальными и повсюду одинаковыми".

Понятие клеточных автоматов впервые ввел фон Нейман в 1940-е годы XX века на основе предложения С. Улама для построения модели самовоспроизводящихся структур [15]. В это же время Н. Винер и А. Розенблют разработали клеточно-автоматную модель возбудимой среды для описания проведения импульсов в сердечной мышце [16]. Работа фон Неймана по самовоспроизводящимся автоматам была завершена и опубликована А. Бёрксом в книге «Essays on Cellular Automata» в 1966 году. Независимо от фон Неймана в 1969 году немецким инженером К. Цузе были придуманы "вычисляющие пространства" - клеточные автоматы, они были определены как универсальная вычислительная среда для построения алгоритмов, эквивалентная по своим выразительным возможностям машине Тьюринга [17]. Большую популярность клеточным автоматам принесла игра "Жизнь" Дж. Конвея, позволяющая с помощью простых правил переходов воспроизводить макроскопическое поведение популяций: зарождение, развитие и гибель колоний живых организмов [18].

С развитием ЭВМ в 50-70-е годы клеточные автоматы приобретают важное практическое применение. Благодаря локальности межклеточных взаимодействий, естественному параллелизму и дискретности правил переходов, клеточные автоматы наилучшим образом соответствуют требованиям технологии больших интегральных схем. Аппаратная реализация клеточных автоматов позволила увеличить производительность и сократить число связей на кристалле, хорошо известными примерами воплощения принципов клеточных автоматов на аппаратном уровне являются: машины клеточных автоматов Т. Тоффоли и

7

Н. Маршлуса [14], сети транспьютеров, систолические системы, клеточные процессоры, параллельные сумматоры, умножители, декодеры и распознаватели сигналов.

Расширение сферы применения ЭВМ в СССР привело к появлению ряда работ по исследованию производительности существующих многопроцессорных вычислителей и поиска новых архитектур с улучшенными показателями. Проблемам создания и развития многопроцессорных вычислительных систем посвящены работы известных советских учёных: В.З. Аладьевым [19], В.М. Глушкова, Э.В. Евреинова, В.В. Игнатущенко, A.B. Каляева, Ю.Г. Косарева, И.В. Прангишвили и многих других. Существующие вычислительные системы с жёсткой архитектурой ориентированы на решение определённых задач и малоэффективны для решения задач другого класса. Тогда как использование многопроцессорных систем с программируемой структурой, реализованных на основе однородных сред, позволяет создать универсальные устройства, предназначенные для эффективного решения задач различных классов [20 - 22]. Однородные вычислительные среды представляют собой совокупность элементарных вычислителей (однородных структур), объединённых друг с другом регулярными связями. Однородными структурами (автоматами с программируемой структурой) называются структуры, состоящие их однотипных функциональных ячеек, соединённых одинаковым образом с соседними [23]. Функциональные ячейки могут быть запрограммированы на выполнение функции, необходимой для решения конкретной задачи, кроме того с помощью задания связей между ячейками и направленности передачи сигнала может быть реализована любая функциональная схема. Таким образом, для решения конкретной задачи производится настройка однородной среды путём определения функции, реализуемой функциональной ячейкой, и логических связей между ячейками. Благодаря возможности представления решаемой задачи в виде структурной схемы и реализации набора операций, характерных для данной задачи, однородные среды позволяют достичь высокой эффективности при выполнении широкого

8

класса задач. Кроме того, идентичность ячеек и однородность связей делает возможным наращивание вычислительной мощности и увеличение производительности системы [24].

В это же время велись теоретические исследования свойств клеточных автоматов. С. Вольфрам предложил классификацию клеточных автоматов по поведенческим признакам [25]. Он выделил 4 класса в зависимости от устойчивого состояния, к которому эволюционирует клеточный автомат: 1) однородное глобальное состояние, соответствует устойчивому фокусу на фазовой плоскости, 2) регулярные, устойчивые или периодические во времени структуры (предельный цикл), 3) непериодические структуры или хаотическое поведение, на фазовой плоскости соответствует предельным циклам с различным периодом, в том числе и равным бесконечности, 4) сложные структуры, распространяющиеся по пространству и развивающиеся во времени, такие клеточные автоматы способны моделировать динамику сложных систем (complex system).

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

Эффективность клеточно-автоматного подхода к моделированию различных физико-химических, биологических, социальных явлений показана в рабо-

тах многих российских и зарубежных авторов. С помощью синхронных клеточных автоматов промоделированы процессы разделения фаз [14], эвакуация людей из горящего здания [27], движение автотранспорта [28], гидродинамические и газодинамические течения [29-31]. Асинхронные вероятностные клеточные автоматы позволяют моделировать такие физико-химические процессы как диффузия [32], диффузия с агрегацией [33], реакционно-диффузионные системы [34-37], кумулятивный синтез [38], распространение фронта огня [39].

С помощью различных клеточно-автоматных моделей изучаются процессы самоорганизации сложных систем в физике, химии и биологии. С. Вольфрам показал, что во многих клеточно-автоматных моделях с различными правилами переходов и с различными начальными условиями возникают явления самоорганизации, в частности, формирование устойчивых структур (pattern formation) [40, 41]. Ряд работ JI.O. Чуа посвящён клеточно-нейронным сетям (CNN), являющихся модификацией клеточных автоматов, и различным структурам - паттернам, формирующимся в результате их эволюции [42, 43]. В [44 - 46] исследован процесс возникновения устойчивых структур в реакционно-диффузионных системах. Свойства самоорганизующихся клеточных автоматов и примеры структурообразования в некоторых моделях подробно рассмотрены в [47 - 49]. Например, в работе Д. Янга [50] представлена активаторно-ингибиторная модель формирования пятен на шкурах животных, в которой шкура животного представляется в виде множества окрашенных и неокрашенных клеток. Эта модель базируется на реакционно-диффузионной модели Тьюринга [3], в которой биологическая структура определяется динамикой морфогенов - химических веществ, способных реагировать друг с другом и диффундировать по пространству. Д. Янг использует модель с двумя типами морфогенов: активаторами и ингибиторами. Значение пигментной клетки вычисляется с помощью функции перехода, зависящей от суммы расстояний между данной клеткой и соседними окрашенными клетками. В зависимости от расстояния между клетками эта функция принимает положительные (является ак-

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

Тоталистическими называются клеточные автоматы (ТКА), вычисляющие новое состояние клетки в зависимости от суммы значений состояний соседних клеток. ТКА позволяют формировать устойчивые структуры, сходные с биологическими паттернами, химическими структурами, изображениями пористых материалов [51, 52]. В зависимости от значений активаторов и ингибиторов ТКА дают возможность генерировать компьютерное представление пористых сред с различной морфологией и изучать их свойства. Синтез и анализ морфологии пористых материалов представляет интерес в связи с тем, что такие материалы находят широкое применение в различных областях промышленности, в технике, строительной индустрии, химии и медицине.

Особый интерес представляют процессы самоорганизации в химии. Известно, что при проведении каталитических реакций в условиях, далеких от равновесных, могут возникать различные критические явления: множественность стационарных состояний, кинетические фазовые переходы, автоколебания, хаос, гистерезис. На поверхности катализатора при этом наблюдаются периодические во времени и в пространстве структуры: спирали, кольца, турбулентности, подвижные волны [53 - 55]. Помимо фундаментального интереса каталитические реакции имеют важное прикладное значение. Использование катализаторов помогает решить ряд практических проблем, связанных с очисткой выбросов промышленных предприятий и выхлопных газов двигателей. Классическим примером таких реакций является реакция окисления монооксида углерода (СО) на поверхности платины (Р^ю). Понимание механизма каталитических реакций способствует расширению области применения катализаторов и разработке экологически безопасных высокопроизводительных технологий.

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

Клеточные автоматы описывают динамику сложных систем на микроуровне, например, при моделировании химических реакций имитируются взаимодействия реальных атомов и молекул. Следовательно, для изучения динамики реальных физико-химических процессов необходимо проводить вычислительные эксперименты с использованием массивов больших размеров (~Ю10-10

10 клеток) в течение нескольких тысяч итераций. Решение таких задач требует применения эффективных алгоритмов распараллеливания. Достижение высокой эффективности при распараллеливании асинхронных клеточных автоматов сопряжено с определёнными трудностями. Решение проблемы предложено в работах [56, 57], где распараллеливание асинхронного клеточного автомата выполняется путём преобразования его в блочно-синхронный клеточный автомат. Несмотря на примеры успешного использования блочно-синхронного преобразования для клеточно-автоматных моделей таких физико-химических процессов, как эпитаксиальный рост кристалла [56] и каталитическое окисление СО на Рёцо [58], строго доказательства эквивалентности эволюции асинхронного и блочно-синхронного клеточных автоматов в общем случае не существует. Поэтому необходимо проверять применимость блочно-синхроннош преобразования для каждого класса задач отдельно.

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

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

12

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

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

2. Разработка двухслойной тоталистической клеточно-автоматной модели

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

3. Разработка вероятностной асинхронной клеточно-автоматной модели

со) реакции окисления монооксида углерода (СО) на поверхности платины (Р1100), анализ пространственно-временной динамики реакции в зависимости от значений констант скорости адсорбции СО и 02, и построение бифуркационной диаграммы.

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

Методы исследования:

Для решения поставленных задач используются методы теории клеточных автоматов, статистические методы анализа данных, методы теории параллельных вычислений, а также проводятся вычислительные эксперименты. Научная новизна работы состоит в следующем: • Предложена новая трёхмерная клеточно-автоматная модель процессов структурообразования, основанная на однонаправленной параллельной

композиции тоталистического и асинхронного клеточных автоматов.

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

• С помощью клеточно-автоматного моделирования определён диапазон значений констант скорости адсорбции СО и 02, в котором в реакции окисления СО на Р1 наблюдаются устойчивые колебания концентраций реагентов, и построена бифуркационная диаграмма реакции.

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

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

2. Бифуркационная диаграмма реакции окисления СО на платине, построенная в результате анализа эволюции асинхронной вероятностной кле-точно-автоматной модели К со-

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

4. Научно-исследовательский программный комплекс для имитационного моделирования на суперкомпьютере процессов самоорганизации: формирования устойчивых структур с помощью К $ и устойчивых колебаний с помощью К со-

Достоверность основных положений и выводов, сделанных в диссертации, а также результатов имитационного моделирования подтверждается строгими математическими доказательствами, тестированием программного комплекса на тестовых задачах, экспериментальными данными, полученными группой низкотемпературного синтеза в Институте катализа СО РАН [48], использованием методов и алгоритмов теории клеточных автоматов, обоснованных в [18-20, 50, 52, 53].

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

Апробация работы.

Основные результаты диссертации докладывались на Российских и международных конференциях: Международная конференция "Cellular Automata for Research and Industry" (ACRI 2012), Греция, 2012; IX Российская конференция с международным участием "Новые информационные технологии в исследовании сложных структур", Томск, 2012; Международная научная конферен-

15

ция "Параллельные вычислительные технологии" (ПаВТ 2012), Новосибирск, 2012; Parallel computing technologies (РаСТ 2011), Казань, 2011; XI Всероссийская конференция молодых учёных по математическому моделированию и информационным технологиям, Красноярск, 2010; Пятая Сибирская конференция по параллельным и высокопроизводительным вычислениям, Томск, 2009; Конференция молодых учёных по вычислительной математике и информатике, Новосибирск, ИВМиМГ СО РАН, 2009, 2011, 2012, 2013; XLVII Международная научная студенческая конференция (МНСК) "Студент и научно-технический прогресс", Новосибирск, 2009. А также на семинарах ИВМиМГ: "Математическое и архитектурное обеспечение параллельных вычислений" и по междисциплинарному интеграционному проекту №47 под руководством Михайлова Г.А.

Работа выполнялась в рамках Проекта №7 ИВМиМГ, а также Проекта 15.9 Президиума РАН, междисциплинарного проекта №47 СО РАН, проекта №12-07-09289-моб_з и № 12-01-31455-мол_а.

Публикации.

По результатам работы опубликовано 14 работ, среди которых 11 статей, в том числе две статьи в журналах, входящих в список ВАК.

Структура диссертации.

Диссертация состоит из введения, трёх глав, заключения, списка литературы, содержащего 78 наименований. Работа содержит 53 рисунка и 8 таблиц.

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

Список литературы диссертационного исследования кандидат наук Киреева, Анастасия Евгеньевна, 2013 год

Список литературы

1. Хакен, Г. Синергетика / Г. Хакен; пер. с англ. В.И. Емильянова; ред. Ю.Л. Климонтовича, С.М. Осовца. - М.: Мир, 1980. - 406 с.

2. Хакен, Г. Информация и самоорганизация. Макроскопический подход к сложным явлениям / Г. Хакен; пер. с англ. Ю.А.Данилова. - М.: Мир, 1991. -240 с.

3. Turing, A.M. The Chemical Basis of Morphogenesis / A.M.Turing //Philosophical Transactions of the Royal Society of London. Series B. Biological Sciences. - 1952. -Vol. 237.-№641.-P. 37-72.

4. Gierer, A. A theory of biological pattern formation / A. Gierer, H. Meinhardt // Kybernetik. - 1972. - Vol. 12. - № 1. - P. 30-39.

5. Gierer, A. Generation of biological patterns and form: Some physical, mathematical and logical aspects / A. Gierer // Progress in Biophysics and Molecular Biology. - 1981.-Vol. 37.-P. 1-47.

6. Романовский, Ю.М. Математическая биофизика / Ю.М. Романовский, Н.В. Степанова, Д.С. Чернавский. - М.: Наука, Главная редакция физико-математической литературы, 1984. - 304 с.

7. Murray, J.D. A pre-pattern formation mechanism for animal coat marking / J.D. Murray // Journal of Theoretical Biology. - 1981. - Vol. 88. - № 1. - P. 161-199.

8. Марри, Дж. Нелинейные дифференциальные уравнения в биологии. Лекции о моделях / Дж. Марри; пер. с англ. В.Г. Бабского; под ред. А.Д. Мышкиса. - М.: Мир, 1983.-397 с.

9. Николис, Г. Самоорганизация в неравновесных системах / Г. Николис, И. Пригожин; пер. с англ. В.Ф. Пастушенко; под ред. Ю.А. Чизмаджева. - М.: Мир, 1979.-256 с.

10. Мандельштам, Л.И. Лекции по теории колебаний / Л.И. Мандельштам. - М.: Наука, 1972.-470 с.

11. Андронов, А.А. Теория колебаний / А.А. Андронов, А.А. Витт, С.Э. Хайкин.

104

- 2-е изд., перераб. и доп. Н.А. Железцовым. - М.: Физматгиз, 1959. - 916 с.

12. Гапонов-Грехов, А.В. Автоструктуры. Хаотическая динамика ансамблей. /

A.В. Гапонов-Грехов, М.И. Рабинович // Нелинейные волны. Структуры и бифуркации / под ред. А.В. Гапонов-Грехова, М.И. Рабиновича. - М.: Наука, 1987.

- 7-44 с.

13. Никитенков, Н.Н. Синергетика для инженеров: учебное пособие / Н.Н. Ни-китенков, Н.А. Никитенкова. - Томск: Изд-во Томского политехнического университета, 2009. - 168 с.

14. Toffoli, Т. Cellular Automata Machines: A New Environment for Modeling / Toffoli T, Margolus N. - USA: MIT Press, 1987. - P. 259.

15. von Neumann J. Theory of Self-Reproducing Automata (edited and completed by Burks A.W.) / von Neumann J. - USA: University of Illinois Press, 1966. - P. 388.

16. Винер, H. Проведение импульсов в сердечной мышце. Математическая формулировка проблемы проведения импульсов в сети связанных возбудимых элементов, в частности в сердечной мышце / Н. Винер, А. Розенблют. // Кибернетический сборник. Вып. 3. - М.: Изд-во иностранная литература, 1961. - 7-56 с.

17. Gardner, М. Mathematical Games - The fantastic combinations of John Conway's new solitaire game "life" / M. Gardner // - USA: Science American. 1970. - Vol. 223. -№ 4. - P. 120-123.

18. Zuse, K. Rechnender Raum / K. Zuse. - Braunschweig: Friedrich Vieweg & Sohn, 1969. - S. 70. (нем.).

19. Аладьев, В.З. Классические однородные структуры: Теория и приложения /

B.З. Аладьев, В.К. Бойко, Е.А. Ровба. - Гродно: ГрГУ, 2008. - 485 с.

20. Евреинов, Э.В. Цифровые автоматы с настраиваемой структурой (однородные среды) / Э.В. Евреинов, И.В. Прангишвили. - М.: Энергия, 1974. - 240 с.

21. Евреинов, Э.В. Однородные вычислительные системы, структуры и среды / Э.В. Евреинов. -М.: Радио и связь, 1981. - 208 с.

22. Каляев, А.В. Многопроцессорные системы с программируемой архитекту-

рой / А.В. Каляев. - М.: Радио и связь, 1984. - 240 с.

23. Праигишвили, И.В. Микроэлектроника и однородные структуры для построения логических и вычислительных" устройств / И.В. Прангишвили, Н.А. Абрамова, Е.В. Бабичева, В.В. Игнатущенко. - М.: Наука, 1967. - 228 с.

24. Евреинов, Э.В. Однородные универсальные вычислительные системы высокой производительности / Э.В. Евреинов, Косарев Ю.Г. - Новосибирск: Наука. Сибирское Отделение, 1966. - 308 с.

25. Wolfram, S. Universality and Complexity in Cellular Automata / S. Wolfram // Physica D. - 1984. - Vol. 10. - P. 1-35.

26. Бандман, O.JI. Клеточно-автоматные модели пространственной динамики / O.JI. Бандман // Системная информатика. Методы и модели современного программирования. - 2006. - №10. С. 59-113.

27. Tissera, Р.С. Evacuation Simulations using Cellular Automata / P.С. Tissera, M. Printista, M.L. Errecalde // Journal of Computer Science & Technology. - 2007. -Vol. 7. - № 1. - P. 14-20.

28. Gora, P. Traffic Simulation Framework - a Cellular Automaton-Based Tool for Simulating and Investigating Real City Traffic / P. Gora // Recent Advances in Intelligent Information Systems. - 2009. - P. 641-653. - ISBN 978-83-60434-59-8.

29. Masi, A.D. Hydrodynamics of stochastic cellular automata / A.D. Masi, R. Espos-ito, J.L. Lebowitz and E. Presutti // Communications in Mathematical Physics. - 1989.-Vol. 125.-№ l.-P. 127-145.

30. Wolfram, S. Cellular automation Fluids / S. Wolfram // Journal of Statistical Physics. - 1986.-Vol. 45.-P. 471-526.

31. Медведев, Ю. Г. Метод моделирования трехмерных потоков жидкости клеточными автоматами / Ю. Г. Медведев // Автометрия. - 2005. - Т. 41. -№ 3. - С. 37-48.

32. Бандман, O.JI. Дискретное моделирование физико-химических процессов / O.JI. Бандман // Прикладная дискретная математика. - 2009. - № 3. - С. 33-49.

33. Ackland, G.J. Microscopic model of diffusion limited aggregation and electro-

106

deposition in the presence of leveling molecules / G.J. Ackland, E.S. Tweedie // Physical Review E. - 2006. - V. 73. - № 1:011606.

34. Pechatnikov, E.L. Cellular Automaton for surface reactions / E.L. Pechatnikov, M. Frankowicz, R. Danielak // ACTA Physica Polonica B. - 1994. - Vol. 25. - № 6.

35. Weimar, J.R. Class of cellular automata for reaction-diffusion systems. / J.R. Weimar, J.P. Boon // Physical Review E. - 1994. - Vol. 49. - P. 1749-1752.

36. Ziff, R.M. Cellular automaton version of the AB2 reaction model obeying proper stoichiometry / R.M. Ziff, K. Fichthom, E. Gulari // Journal of Physics A: Mathematical and General. - 1991. - Vol. 24. - № 15. - P. 3727-3730.

37. Weimar, J.R. Diffusion and wave propagation in cellular automaton model of excitable media / J.R. Weimar, J.J.W. Tyson, T. Layne // Physica D: Nonlinear Phenomena. - 1992. - Vol. 55. - № 3-4. - P. 309-327.

38. Бандман, O.JI. Кумулятивный синтез: клеточно-автоматная модель физико-химических процессов на стадии схлопывания порошковой облицовки / О.Л. Бандман, С.А. Кинеловский // Прикладная дискретная математика. - 2011. -№ 2. - С. 113-124.

39. Hernández Encinas, A. Simulation of forest fire fronts using cellular automata / A. Hernández Encinas, L. Hernández Encinas, S. Hoya White, A. Martín del Rey, G. Rodríguez Sánchez // Journal Advances in Engineering Software. - 2007. - Vol. 38.-№ 6.-P. 372-378.

40. Wolfram, S. A New Kind of Science. / S. Wolfram. - USA: Wolfram Media, 2002.-P. 1197.-ISBN 1-57955-008-8.

41. Wolfram, S. Cellular Automata as Simple Self-Organizing Systems [Электронный ресурс] / S. Wolfram. Caltech preprint CALT-68-938. - 1982. - Режим доступа: http://www.stephenwolfram.com/publications/articles/ca/82-cellular/index.html, свободный. - (Дата обращения: 21.05.2013).

42. Chua, L.O. CNN: A paradigm for complexity. / L.O. Chua. - World Scientific series on Nonlinear science. Series A, 1998. - V. 31. - P. 320.

43. Chua, L.O. Autonomous cellular neural networks: A unified paradigm for pattern

107

formation and active wave propagation / L.O. Chua, M. Hasler, G.S. Moschytz, J. Neirynck // IEEE Transactions on Circuits and Systems. - 1995. - Vol. 42. - P. 559-577.

44. Weimar, J.R. Spontaneous nucleation in a reactive lattice gas automaton / J.R. Weimar // Spatio-temporal Organization in Nonequilibrium Systems / Ed. by S.C. Mtiller & T. Plesser - Projekt Verlag, 1992. P. 266-269.

45. Cross, M. Pattern formation and dynamics in nonequlibrium systems. / M. Cross, H. Greenside - Cambridge University Press, 2009. - P. 535.

46. Suzudo, T. Spatial pattern formation in asynchronous cellular automata with mass conservation / T. Suzudo // Physica A: Statistical Mechanics and its Applications. -2004. - V. 343.-P. 185-200.

47. Бандман, O.JI. Метод построения клеточно-автоматных моделей процессов формирования устойчивых структур / O.JI. Бандман // Прикладная Дискретная Математика - Дискретные модели реальных процессов. - 2010. - № 4. - С. 9199.

48. Griffeath, D. Self-Organization Of Random Cellular Automata: Four Snapshots / D. Griffeath // Probability and Phase Transition / Ed. by G. Grimmett. - MA: Kluwer, 1994.-P. 49-67.

49. Dorin, A. Physically Based, Self-Organizing Cellular Automata / A. Dorin // Multi-Agent Systems - Theories, Languages and Applications. Lecture Notes in Artificial Intelligence. - Springer-Verlag, 1998. - Vol. 1544. - P. 74-87.

50. Young, D.A. A local activator-inhibitor model of vertebrate skin patterns / D.A. Young // Mathematical Biosciences. - 1984. - Vol. 72. - P. 51-58.

51. Bandman, O.L. Using Cellular Automata for porous media simulation / O.L. Bandman //The Journal of Supercomputing. - 2011.-Vol. 57.-№2.-P. 121131.

52. Sahimi, M. Flow phenomena in rock: From continuum model to fractals, percolation, cellular automata and simulated annealing / M. Sahimi // Review of Modern Physics. - 1993.-Vol. 65,-№4.-P. 1393-1534.

53. Imbihl, R. Oscillatory Kinetics in Heterogeneous Catalysis / R. Imbihl, G. Ertl // Chemical Reviews. - 1995. - Vol. 95. - № 3. - P. 697-733.

54. Gorodetskii, V.V. Field electron and field ion microscopy studies of chemical wave propagation in oscillatory reactions on platinum group metals / V.V. Gorodetskii, V.I. Elokhin, J.W. Bakker, B.E. Nieuwenhuys // Catalysis Today. - 2005. -Vol. 105.-P. 183-205.

55. Слинько, М.Г. Нелинейная динамика каталитических реакций и процессов (обзор) / М.Г. Слинько, Т.И. Зеленяк, Т.А. Акрамов, М.М. Лаврентьев, B.C. Шеплев // Математическое моделирование. - 1997. - Т. 9. -№ 12. - С. 87109.

56. Bandman, O.L. Parallel simulation of asynchronous cellular automata evolution/ O.L. Bandman // Proceedings of the 7th International Conference on Cellular Automata for Research and Industry, ACRI 06 / Ed. By Yacoubi S., Chopard В., Bandini S. - LNSC. Springer, 2006. - Vol. 4173. - P. 41-47.

57. Nedea, S.V. Methods for parallel simulations of surface reactions / S.V. Nedea, J.J. Lukkien, A.P.J. Jansen, P.A.J. Hilbers // Proceedings of the 17th International Symposium on Parallel and Distributed Processing / Ed. by B. Werner. - IEEE Computer Society, 2003. - P. 256.

58. Маркова, В.П. Параллельная реализация асинхронного клеточного автомата, моделирующего реакцию окисления СО на палладии / В.П. Маркова, А.Е. Шарифулина (Киреева) // Прикладная Дискретная Математика. — 2011. — № 1.-С. 116-127.

59. Achasova, S. Parallel Substitution Algorithm. Theory and Application. / S. Achasova, O. Bandman, V. Markova, S. Piskunov. - Singapore: World Scientific, 1994.- 180 c.

60. Bandman, O.L. Cellular Automata composition techniques for spatial dynamics simulation / O.L. Bandman// Bulletin of the Novosibirsk Computing Center. Series: Computer Science. - 2008. - Vol. 27. - P. 1-39.

61. Chopard, B. Cellular Automata Modeling of Physical Systems. / B. Chopard,

109

M. Droz. - Cambridge University Press, 1998. - P. 337.

62. Демлов, Э. Межфазный катализ. / Э. Демлов, 3. Демлов. - М.: Мир, 1987. - С. 467.

63. Боресков, Г.К. Катализ: Вопросы теории и практики: избранные труды / Г.К. Боресков; отв. ред. Замараев К.И., Панов Г.И. - Акад. наук СССР, Сиб. отд-ние, Ин-т катализа. - Новосибирск: Наука, 1987. - 536 с.

64. Елохин, В.И. Автоколебания и химические волны в реакции окисления СО на Pt и Pd: кинетические модели Монте-Карло / В.И. Елохин, А.В. Матвеев, В.В. Городецкий. // Кинетика и Катализ. - 2009. - Т. 50. - № 1. - С. 46-53.

65. Elokhin, V.I. Stochastic Models of Physicochemical Processes in Catalytic Reactions - Self-Oscillations and Chemical Waves in CO Oxidation Reaction [Электронный ресурс] / V.I. Elokhin // Theory and Applications of Monte Carlo Simulations / Ed. by Victor (Wai Kin) Chan. - 2013. - P. 276. - ISBN: 978-953-51-1012-5. - Режим доступа: http://dx.doi.org/10.5772/45892, свободный. - (Дата обращения : 03.06.2013).

66. Latkin, E.I. Monte Carlo model of oscillatory CO oxidation having regard to the change of catalytic properties due to the adsorbate-induced Pt(100) structural transformation / E.I. Latkin, V.I. Elokhin, V.V. Gorodetskii // Journal of Molecular Catalysis A: Chemical.-2001.-V. 166.-P. 23-30.

67. Latkin, E.L. Manifestation of the adsorbed со diffusion anisotropy caused by the structure properties of the Pd(110) - (1x2) surface on the oscillatory behavior during CO oxidation reaction - Monte-Carlo model / E.I. Latkin, V.I. Elokhin, A.V. Mat-veev, V.V. Gorodetskii // Chemistry for Sustainable Development. - 2003. - Vol. 11. -P. 173-180.

68. Матвеев, А.В. Изучение природы критических явлений в реакциях NO+CO и С0+02 на грани Pd(l 10): гистерезис, автоколебания, волны: дис. ... канд. хим. наук: 02.00.15 / Матвеев Андрей Викторович. - Новосибирск. Институт катализа имени академика Борескова, 2004. - 119 с.

69. Latkin, E.I. The role of subsurface oxygen in oscillatory behaviour of CO+O2 re-

110

action over Pd metal catalysts: Monte Carlo model / E.I. Latkin, V.I. Elokhin, A.V. Matveev, V.V. Gorodetskii // Journal of Molecular Catalysis A: Chemical. - 2000. -Vol. 158.-P. 161-166.

70. Шарифулина (Киреева), A.E. Исследование поведения каталитической реакции окисления монооксида углерода на поверхности палладия с помощью вероятностной клеточно-автоматной модели / А.Е. Шарифулина (Киреева) // Труды конференции молодых учёных. - Новосибирск: ИВМиМГ СО РАН, 2009. -С. 157-164.

71. Шарифулина (Киреева), А.Е. Построение бифуркационной диаграммы реакции окисления СО на палладии с помощью асинхронного клеточного автомата / А.Е. Шарифулина (Киреева) // XI Всероссийская конференция молодых учёных по математическому моделированию и информационным технологиям. Программа и тезисы докладов. - Новосибирск, 2010. - С. 79-80.

72. Elokhin, V.I. Application of statistical lattice models to the analysis of oscillatory and autowave processes in the reaction of carbon monoxide oxidation over platinum and palladium surfaces / E.I. Latkin, V.I. Elokhin, A.V. Matveev, V.V. Gorodetskii // Kinetics and Catalysis. - 2003. - Vol. 44. - № 5. - P. 692-700.

73. Gorodetskii, V.V. Kinetic oscillations and surface waves in catalytic C0+02 reaction on Pt surface: field electron microscope, field ion microscope and high resolution electron energy loss spectroscopy studies. / V.V. Gorodetskii, W. Drachsel // Applied Catalysis A: General. - 1999. - Vol. 188. - P. 267-275.

74. Бандман, O.JI. Параллельная реализация клеточно-автоматных алгоритмов моделирования пространственной динамики / О.Л. Бандман // Сибирский журнал вычислительной математики. - 2007. - № 4. - С. 345-361.

75. Калгин, К.В. Подобие эволюций клеточного автомата при асинхронных и блочно-синхронных режимах / К.В. Калгин // Новые информационные технологии в исследовании сложных структур. Тез. докл. девятой Российская конференции с международным участием. - Томск: Изд-во НТЛ, 2012. - С 21.

76. Ивченко, Г.И. Введение в математическую статистику. / Г.И. Ивченко,

111

Ю.И. Медведев. - M.: ЛКИ, 2010. - 600 с.

77. Городничев, М.А. Совместное использование MPI и ОрепМР на кластерах [Электронный ресурс] / М.А: Городничев, К.В. Калгин, С.Е. Киреев, В.А. Пере-пёлкин - Режим доступа: http://www2.sscc.ru/SORAN-INTEL/paper/2Q 10/ MPI ОрепМР 100325.pdf, свободный. - (Дата обращения: 30.05.2013).

78. Аксенова, Е.В. Использование технологий MPI и ОрепМР для организации обменов сообщениями в вычислительных системах с кластерной архитектурой / Е.В. Аксенова, M.JI. Цымблер // Параллельные вычислительные технологии: Труды международной научной конференции. Челябинск: Изд-во ЮУрГУ, -2007.-Т. 2.-С. 282.