Автор работы: Пользователь скрыл имя, 09 Февраля 2013 в 17:38, курсовая работа
Начиная с 80-х гг.. XX века изучение клеточных автоматов приобрело более специализированный оттенок. На базе общей теории создаются и изучаются разные конфигурации клеточных автоматов для конкретных исследовательских областей. Благодаря разносторонним исследованиям, удалось создать мощную математическую теорию, направленную на классификацию и изучение особенностей разных моделей.
ВВЕДЕНИЕ………………………………………………………………………. 4
1.ТЕОРЕТИЧЕСКАЯ ЧАСТЬ ………………………………………………….. 5
1.1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ……………………………………............. 5
1.2. СВОЙСТВА И КЛАССИФИКАЦИЯ КЛЕТОЧНЫХ АВТОМАТОВ……………………………………………………………………. 6
1.3. МОДЕЛИРОВАНИЕ КЛЕТОЧНЫХ АВТОМАТОВ ……………………. 8
1.4. ИГРА «ЖИЗНЬ»…………………………………………………………….. 16
2. ПРАКТИЧЕСКАЯ ЧАСТЬ. МОДЕЛИРОВАНИЕ ПЛАНЕРНОГО РУЖЬЯ ГОСПЕРА (GOSPER’S GLIDER GUN)………………………………. 30
3. ВЫВОДЫ……………………………………………………………………… 32
4. СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ………………………….. 33
МИНИСТЕРСТВО ОБРАЗОВАНИЯ и науки Украины
украинский
Государственный химико-
Факультет биотехнологии, компьютерных наук и инженерии
Кафедра КТВМ
по дисциплине: Моделирование систем
на тему: «Визуальное моделирование динамических процессов на примере простого клеточного автомата игры «Жизнь» ».
Днепропетровск
2012
МИНИСТЕРСТВО ОБРАЗОВАНИЯ и науки Украины
украинский
Государственный химико-
Факультет биотехнологии, компьютерных наук и инженерии
ЗАДАНИЕ
на курсовую работу по дисциплине
“Моделирование систем”
Студенту: Пришко Ю.В. 3-СКС-5 группы 3 курса факультета БТКНиИ специальности 220400
Тема: Визуальное моделирование динамических процессов на примере простого клеточного автомата игры «Жизнь».
Содержание работы:
Задача 1. Провести реализацию клеточного автомата в Matlab.
Срок выполнения проекта: с __ . __ . 2012 г. по __ . __ . 2012 г.
Срок защиты: __ . __ . 2012г.
Дата выдачи задания: __ . __ . 2012г.
Дата сдачи проекта на кафедру: __ . __ . 2012г.
Руководитель проекта: старший преподаватель Рогоза Б.Е.
Задание принял студент __________________ дата __ . __ . 2012 г.
СОДЕРЖАНИЕ
ВВЕДЕНИЕ………………………………………………………… |
4 |
1.ТЕОРЕТИЧЕСКАЯ ЧАСТЬ ………………………………………………….. |
5 |
|
5 |
|
6 |
|
8 |
|
16 |
|
30 |
|
32 |
|
33 |
ВВЕДЕНИЕ
Термин «клеточные автоматы» начал использоваться в середине XX века для обозначения совокупности зависимых элементов с заданными состояниями и правил, согласно которых состояния этих элементов и зависимости между ними изменяются во времени. Время и состояния при этом дискретные. Использование описанных моделей для формального моделирования самовоспроизводящихся организмов впервые предложено в работе Фон Неймана. Элементы клеточных автоматов предложено представить одномерными или двухмерными бесконечными прямоугольными таблицами. Состояние элемента изменяется в зависимости от его состояния и от состояния двух (или четырёх − для двухмерного случая) ближайших соседей.
Клеточные автоматы в силу своей дискретности сравнительно просто моделируются с помощью ЭВМ и благодаря этому, в 50-70-е гг.. XX века приобретают популярность. Исследователи разных научных областей изучают и используют клеточные автоматы с разнообразными особенностями для разных целей. В это время выходят основные труды, которые заложили базис для общей теории клеточных автоматов.
Примерно в это же время появились игры для клеточных автоматов − математические модели, которые имеют в основании игровое описание. Например, игра «Firing Squad» − задание про одновременный залп всего пушечного склада имеет в основе важную задачу синхронизации, а игра «Game of Life» является моделью поведения популяции в однородном окружении.
Начиная с 80-х гг.. XX века изучение клеточных автоматов приобрело более специализированный оттенок. На базе общей теории создаются и изучаются разные конфигурации клеточных автоматов для конкретных исследовательских областей. Благодаря разносторонним исследованиям, удалось создать мощную математическую теорию, направленную на классификацию и изучение особенностей разных моделей.
Клеточный автомат К есть упорядоченное множество из четырех компонент
где
− множество d-мерных векторов с целочисленными координатами − клеточное пространство;
N − конечное множество мощности m векторов из :
с нулевым вектором − шаблон соседства клетки;
А − конечное множество мощности k состояний клетки с выделенным состоянием покоя;
− алфавит клеточного автомата; − локальная функция переходов, определенная в дискретные моменты времени и изменяющая состояние клетки, являющейся нулевым элементом в шаблоне, в зависимости от состояний клеток, составляющих шаблон соседства при этом . Состояние всех клеток в момент времени t образует текущую конфигурацию
Применение локальной функции переходов к текущей конфигурации задает глобальную функцию переходов Упорядоченная совокупность конфигураций, получаемая из начальной последовательным применением глобальной функции переходов, образует эволюцию е клеточного автомата:
Одномерные (d = 1) клеточные автоматы, у которых m = 2 или к = 2, будем называть ординарными.
Клеточный автомат K* моделирует поведение клеточного автомата K с замедлением n, если для любой эволюции допускаемой клеточным автоматом K, существует гомоморфизм E*, причем такой, что При n = 1 будем говорить, что моделирование осуществляется в реальном времени.
Пусть задана машина Тьюринга
где
Z − одномерное целочисленное пространство − лента; S — конечное множество символов, включая пустой Ø − алфавит машины; Q – конечное множество состояний машины; − трехэлементное множество, элементы которого соответствуют направлениям перемещения по ленте; − функция переходов, определенная в дискретные моменты времени:
Отображение задает конфигурацию машины Тьюринга на момент t, а кортеж определяет эволюцию машин Тьюринга. Множество всех возможных эволюции машины Тьюринга обозначим через W. Будем говорить, что клеточный автомат K моделирует машину Тьюринга MT, если существует гомоморфизм
Если клеточный автомат моделирует универсальную машину Тьюринга то будем называть универсальным.
По аналогии с введенной Шенноном сложностью универсальных машин Тьюринга произведение называется сложностью универсальных клеточных автоматов.
Более простыми словами клеточный автомат – это дискретная динамическая система, представляющая собой совокупность одинаковых клеток, одинаковым образом соединенных между собой. Все клетки образуют, так называемую, решетку клеточного автомата. Решетки могут быть разных типов, отличаясь как по размерности, так и по форме клеток.
Каждая клетка является конечным автоматом, состояния которого определяются состояниями соседних клеток и, возможно, ее собственным состояниям.
Отметим, что в клеточных автоматах, как моделях вычислений, не рассматриваются входные и выходные воздействия. При аппаратной реализации клеточные автоматы обычно называют однородными структурами.
Клеточные автоматы в общем случае характеризуются следующими свойствами.
1. Изменения значений всех клеток происходят одновременно после вычисления нового состояния каждой клетки решетки.
2. Решетка однородна. Невозможно отличить никакие два места на решетке по ландшафту.
3. Взаимодействия локальны. Лишь клетки окрестности (как правило, соседние) способны повлиять на данную клетку.
4. Множество состояний клетки конечно.
Для получения различных конфигураций клеточных автоматов, принято варьировать следующими параметрами:
✧ состояния элементов. В каждый момент времени каждый элемент клеточного автомата имеет одно из конечного набора состояний. В зависимости от этих состояний в следующий момент времени набор элементов может принять новое состояние. Если для элементов клеточного автомата множества возможных состояний различны, такой клеточный автомат называется полигенным. Но на практике используются ячейки с эквивалентными множествами возможных состояний с алгебраической структурой – линейные клеточные автоматы;
✧геометрия. Элементы могут быть геометрически расположены различным образом. Размерность пространства может быть произвольной, а число элементов – как бесконечным, так и конечным. В последнем случае возникает дополнительная степень свободы в граничных условиях. Они могут быть различными, но на практике используются постоянные во времени (чаще всего – нулевые) или периодические граничные условия. В динамических клеточных автоматах геометрия может изменяться со временем, а если геометрия различна на различных участках пространства, такие клеточные автоматы называют неоднородными;
✧соседство. Соседи – это элементы, от которых зависит элемент клеточного автомата. Состояние элемента в следующий момент времени вычисляется из состояния самого элемента и его соседей. Соседство в большой степени определяется геометрией клеточного автомата. Для различных целей возможно изменение числа входных состояний элемента. Если для каждого элемента клеточного автомата число входов и выходов одинаковое, такой клеточный автомат называется сбалансированным;
✧локальное правило. В соответствии с локальным правилом изменяется состояние элемента клеточного автомата в течение времени. Клеточный автомат, в котором локальные правила различны для различных элементов, называется разнородным. Локальное правило может быть недетерминированным, т.е. изменяться во времени или иметь случайную природу.
Варьируя заданные параметры, можно получить клеточные автоматы необходимой конфигурации. Гибкость конфигурации и универсальность вычисления обеспечили высокую популяризацию клеточных автоматов в различных сферах. Произвольность в выборе параметров конфигурации очень удобна для использования, но это придаёт дополнительную сложность в классификации и систематизации знаний теории клеточных автоматов. Тем не менее, наиболее используемо на практике лишь небольшое семейство конфигураций клеточных автоматов. Как правило, каждый из них имеет своё название. Здесь приведён лишь небольшой список наиболее используемых вариантов конфигураций:
✧ мозаичный автомат. Клеточный автомат, использующий в локальном правиле каждого элемента не только состояние элемента и его соседей, но и значение общего входного параметра, который может изменяться со временем. Изменение этого параметра ведёт к смене набора правил смены состояний во всём пространстве элементов клеточного автомата.
Если из какого-либо начального состояния можно привести клеточный автомат в любую заданную конфигурацию путём варьирования значением общего входного параметра, клеточный автомат называют полным;