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

Содержание

Введение

§1. Клеточный автомат

§2. Математическое определение

§3. Классификация по типам поведения

§4. Тоталистичные клеточные автоматы

§5. Связанные определения клеточных автоматов

§6. Свойство обратимости

§7 Модель распространения лесного пожара

Заключение

Введение

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

Идея клеточных автоматов появилась в конце сороковых годов 20 века. Она была задумана и сформулирована Джоном Фон Нейманом и Конрадом Цусе независимо друг от друга как универсальная вычислительная среда для построения, анализа и сравнения характеристик алгоритмов.

При разработке клеточных автоматов Дж. Фон Нейман за основу взял работу С. Улама и впервые соединил в клеточных автоматах понятия вычислительное устройство и данные, с которыми система оперирует. Данные и вычислительные устройства собираются из одних и тех же структурных элементов. Джон Фон Нейман поставил перед собой задачу доказать возможность существования самовоспроизводящихся автоматов. Если такую машину снабдить надлежащими инструкциями, она построит точную копию самой себя. В свою очередь обе эти машины построят себе пары и так далее в прогрессии 2, 4, 8, 16…

Клеточный автомат

клеточный автомат математический модель

Клеточный автомат - дискретная модель, изучаемая в математике, теории вычислимости <http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8>, физике <http://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B7%D0%B8%D0%BA%D0%B0>, теоретической биологии и микромеханике. Включает регулярную решётку ячеек, каждая из которых может находиться в одном из конечного множества состояний, таких как 1 и 0. Решетка может быть любой размерности. Для каждой ячейки определено множество ячеек, называемых окрестностью. К примеру, окрестность может быть определена как все ячейки на расстоянии не более 2 от текущей (окрестность фон Неймана <http://ru.wikipedia.org/wiki/%D0%9E%D0%BA%D1%80%D0%B5%D1%81%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D1%84%D0%BE%D0%BD_%D0%9D%D0%B5%D0%B9%D0%BC%D0%B0%D0%BD%D0%B0> ранга 2). Для работы клеточного автомата требуется задание начального состояния всех ячеек, и правил перехода ячеек из одного состояния в другое. На каждой итерации, используя правила перехода и состояния соседних ячеек, определяется новое состояние каждой ячейки. Обычно правила перехода одинаковы для всех ячеек и применяются сразу ко всей решётке.

Основное направление исследования клеточных автоматов - алгоритмическая разрешимость <http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D1%8C> тех или иных проблем. Также рассматриваются вопросы построения начальных состояний, при которых клеточный автомат будет решать заданную задачу.

Математическое определение

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

.

Изменение состояний автоматов происходит согласно правилу перехода

,

где - множество автоматов, составляющих окрестность. К примеру, окрестность фон Неймана определяется как

,

В свою очередь окрестность Мура определяется как

.

Число всех возможных правил перехода определяется числом состояний и количеством соседей n и составляет

Классификация по типам поведения

Стивен Вольфрам <http://ru.wikipedia.org/wiki/%D0%A1%D1%82%D0%B8%D0%B2%D0%B5%D0%BD_%D0%92%D0%BE%D0%BB%D1%8C%D1%84%D1%80%D0%B0%D0%BC> в своей книге A New Kind of Science <http://ru.wikipedia.org/wiki/A_New_Kind_of_Science> предложил 4 класса, на которые все клеточные автоматы могут быть разделены в зависимости от типа их эволюции. Классификация Вольфрама <http://ru.wikipedia.org/wiki/%D0%A1%D1%82%D0%B8%D0%B2%D0%B5%D0%BD_%D0%92%D0%BE%D0%BB%D1%8C%D1%84%D1%80%D0%B0%D0%BC> была первой попыткой классифицировать сами правила, а не типы поведения правил по отдельности. В порядке возрастания сложности классы выглядят следующим образом:

·Класс 1: Результатом эволюции почти всех начальных условий <http://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D1%87%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%87%D0%BD%D1%8B%D0%B5_%D1%83%D1%81%D0%BB%D0%BE%D0%B2%D0%B8%D1%8F> является быстрая стабилизация состояния и его гомогенность <http://ru.wikipedia.org/wiki/%D0%93%D0%BE%D0%BC%D0%BE%D0%B3%D0%B5%D0%BD%D0%BD%D0%BE%D1%81%D1%82%D1%8C>. Любые случайные конструкции в таких правилах быстро исчезают.

·Класс 2: Результатом эволюции почти всех начальных условий <http://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D1%87%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%87%D0%BD%D1%8B%D0%B5_%D1%83%D1%81%D0%BB%D0%BE%D0%B2%D0%B8%D1%8F> является быстрая стабилизация состояния, либо возникновениеколебаний <http://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BB%D0%B5%D0%B1%D0%B0%D0%BD%D0%B8%D1%8F>. Большинство случайных структур в начальных условиях <http://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D1%87%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%87%D0%BD%D1%8B%D0%B5_%D1%83%D1%81%D0%BB%D0%BE%D0%B2%D0%B8%D1%8F> быстро исчезает, но некоторые остаются. Локальные изменения в начальных условиях <http://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D1%87%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%87%D0%BD%D1%8B%D0%B5_%D1%83%D1%81%D0%BB%D0%BE%D0%B2%D0%B8%D1%8F> оказывают локальный характер на дальнейший ход эволюции системы.

·Класс 3: Результатом эволюции почти всех начальных условий <http://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D1%87%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%87%D0%BD%D1%8B%D0%B5_%D1%83%D1%81%D0%BB%D0%BE%D0%B2%D0%B8%D1%8F> являются псевдо-случайные, хаотические <http://ru.wikipedia.org/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D1%85%D0%B0%D0%BE%D1%81> последовательности. Любые стабильные структуры, которые возникают почти сразу же уничтожаются окружающим их шумом <http://ru.wikipedia.org/wiki/%D0%A8%D1%83%D0%BC>. Локальные изменения вначальных условиях <http://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D1%87%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%87%D0%BD%D1%8B%D0%B5_%D1%83%D1%81%D0%BB%D0%BE%D0%B2%D0%B8%D1%8F> оказывают широкое, неопределямое влияние на ход всей эволюции системы.

·Класс 4: Результатом эволюции почти всех правил являются структуры, которые взаимодействуют сложным и интересным образом с формированием локальных, устойчивых <http://ru.wikipedia.org/wiki/%D0%A3%D1%81%D1%82%D0%BE%D0%B9%D1%87%D0%B8%D0%B2%D0%BE%D1%81%D1%82%D1%8C_(%D0%B4%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D1%8B)> структур, которые способны выживать длительное время. В результате эволюции правил этого класса могут получаться некоторые последовательности Класса 2, описанного выше. Локальные изменения в начальных условиях <http://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D1%87%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%87%D0%BD%D1%8B%D0%B5_%D1%83%D1%81%D0%BB%D0%BE%D0%B2%D0%B8%D1%8F> оказывают широкое, неопределямое влияние на ход всей эволюции системы.

Тоталистичные клеточные автоматы

Существует специальный класс клеточный автоматов, называемых тоталистичными. На каждом шаге эволюции клеточного автомата значение ячейки равно какому-либо целому числу(обычно выбираемого из конечного множества <http://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D0%BE%D0%B5_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE>), а новое состояние клетки определяется суммой значений клеток-соседей и, возможно, предыдущим состоянием клетки. Если состояние клетки на новом шаге зависит от её предыдущего состояния, то такой клеточный автомат называется внешним тоталистичным. Игра Жизнь <http://ru.wikipedia.org/wiki/%D0%98%D0%B3%D1%80%D0%B0_%D0%96%D0%B8%D0%B7%D0%BD%D1%8C>является примером внешнего тоталистического клеточного автомата с набором значений ячеек .

Связанные определения клеточных автоматов

Существует множество возможных обобщений концепций клеточных автоматов.

Один из них - использование сетки не с квадратами(гиперкубами <http://ru.wikipedia.org/wiki/%D0%93%D0%B8%D0%BF%D0%B5%D1%80%D0%BA%D1%83%D0%B1> в многомерном случае), а с другими геометрическими фигурами в её основе. Например, если поле представлено шестиугольным паркетом <http://ru.wikipedia.org/wiki/%D0%A8%D0%B5%D1%81%D1%82%D0%B8%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%BF%D0%B0%D1%80%D0%BA%D0%B5%D1%82>, то шестиугольники будут клетками. Однако иногда такие клеточные автоматы оказывались идентичными клеточным автоматам на сетке с квадратными клетками, только при этом было необходимо вместе специальные правила отношений с клетками-соседями. Другой способ обобщения - использование нерегулярной сетки(например, в виде Мозаики Пенроуза <http://ru.wikipedia.org/wiki/%D0%9C%D0%BE%D0%B7%D0%B0%D0%B8%D0%BA%D0%B0_%D0%9F%D0%B5%D0%BD%D1%80%D0%BE%D1%83%D0%B7%D0%B0>).

Ещё один способ - использование вероятностных правил. Такие клеточные автоматы называются стохастическими <http://ru.wikipedia.org/w/index.php?title=%D0%A1%D1%82%D0%BE%D1%85%D0%B0%D1%81%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%BA%D0%BB%D0%B5%D1%82%D0%BE%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&action=edit&redlink=1>. В таких системах задается вероятность, что на следующем шаге клетка сменит свой цвет на другой. Или, например, в игре «Жизнь» <http://ru.wikipedia.org/wiki/%D0%98%D0%B3%D1%80%D0%B0_%D0%96%D0%B8%D0%B7%D0%BD%D1%8C>добавляется правило, что клетка с определенной вероятностью может изменить свой цвет на противоположный, а другие правила этого клеточного автомата остаются без изменений.

Определение соседства клетки может меняться с течением времени и\или пространства. Например, на первом шаге соседями будут горизонтально смежные клетки, а на другом - вертикально смежные.

Существуют непрерывные клеточные автоматы <http://ru.wikipedia.org/w/index.php?title=%D0%9D%D0%B5%D0%BF%D1%80%D0%B5%D1%80%D1%8B%D0%B2%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BB%D0%B5%D1%82%D0%BE%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&action=edit&redlink=1>. В таких системах вместо дискретного набора состояний используются непрерывные функции (обычно определяемые на промежутке ).

Свойство обратимости

Клеточный автомат называется обратимым, если для каждой текущей конфигурации существует только одна предшествующая конфигурация. Если рассматривать клеточный автомат как функцию, отображающую одну конфигурацию в другую, то обратимость предполагает биективность <http://ru.wikipedia.org/wiki/%D0%91%D0%B8%D0%B5%D0%BA%D1%86%D0%B8%D1%8F> этой функции. Если клеточный автомат обратим, то его обратная эволюция также может быть описана клеточным автоматом. Конфигурации, не имеющие предшествующих, то есть недостижимые в данном клеточном автомате, носят название «Сады Эдема» <http://ru.wikipedia.org/wiki/%D0%A1%D0%B0%D0%B4_%D0%AD%D0%B4%D0%B5%D0%BC%D0%B0_(%D0%BA%D0%BE%D0%BD%D1%84%D0%B8%D0%B3%D1%83%D1%80%D0%B0%D1%86%D0%B8%D1%8F_%D0%BA%D0%BB%D0%B5%D1%82%D0%BE%D1%87%D0%BD%D0%BE%D0%B3%D0%BE_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D0%B0)>.

Для одномерных клеточных автоматов существуют алгоритмы определения обратимости или необратимости. Однако для клеточных автоматов с двумя и более измерениями таких алгоритмов нет.

Модель лесного пожара. Клеточные автоматы

Создать и визуализировать математическую модель распространения лесного пожара в Excel.

Условия:

·поле 30 на 30 клеток;

·одна клетка - один шаг и одно дерево;

·вокруг горящего дерева есть 8 ближайших клеток, на которые может перейти пожар,

·состояние дерева: горящее - красное, сгоревшее - черное, несгоревшее - зеленое.

·Загорится ли дерево (вероятность) зависит от направления ветра (всего 8 направлений);

·Вероятность возгорания, направление ветра и скорость ветра выставляется произвольно в начале программы, и являются исходными данными для формирования правил клеточного автомата.

Решение:

Правила для клеток автомата:

1.Зеленая клетка может превратиться только в «красную» по вероятностному закону, если в соседях у нее красная;

2.Красная - на следующем шаге, превращается в черную;

.Черная никогда не меняется.

В теории в автоматах существуют два принципиально разных вида клеток (по параметрам Причина-Следствие):

1.Клетка-приемник - использует данные о состояниях своих соседей и в конечном итоге изменяет свое состояние (как правило, для комплексного учета влияния соседей)

2.Клетка-причина - влияет на соседей и, в конечном счете, изменяет их состояние или создает предпосылки для такого изменения (и не исключено, что и свое).

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

Процесс пересчета состояний:

Цикл перебора клеток бежит пока не встретит «красную» в массиве. В самом массиве сразу ничего не меняется, а лишь проверяются соседи и если среди них есть «зеленая», то в нее бросается «Искра» (функция RND). Клетка, возможно, загорится, а возможно и нет. Изменения, если произойдут, зафиксируются в специальной коллекции. Матрица вероятностей «поджога соседей» формируется таким образом, что «красные» клетки бросает искры в основном по направлению ветра - и только на «зеленые» соседние клетки. После окончания цикла очередного шага, вносим изменения в массив, одновременно очищая «коллекцию изменений».

Заключение

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

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

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

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

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

1.Altman E., Khouzani M.H.R., Sarkar S. Optimal control of epidemic evolution // Proceedings of INFOCOM 2011. 2011. P. 1683-1691.

2.Beutel A., Faloutsos C., Prakash B.A., Rosenfeld R. Interacting Viruses in Networks: Can Both Survive? // KDD-2012. 2012.

3.Gubar E.A., Zhu Q. Optimal Control of Influenza Epidemic Model with Virus Mutations // 12th European Control Conference ECC 13. IEEE Control Systems Society. 2013. P. 3125-3130.

4.Kermack W.O., Mc Kendrick A.G. A contribution to themathematical theory of epidemics // Proceedings of the Royal Society. 1927. Vol. 115, No. A771. P. 700-721.

5.Pontryagin L.S., Boltyanskii V.G., Gamkrelidze R.V., Mishchenko E.F. The Mathematical Theory of Optimal Processes // Interscience, 1962.

Больше работ по теме: