Содержание
- 2. Тема: Клеточные автоматы Клеточные автоматы. Общие понятия. Игра «Жизнь» Лекция №12
- 3. Автоматы. Общие понятия. Автоматом называют устройство (или совокупность устройств), которое без непосредственного участия человека выполняет процессы
- 4. Автоматы. Общие понятия. Множество сигналов и состояний дискретны, и, кроме того, дискретно множество моментов, в которые
- 5. Клеточные автоматы Клеточные автоматы (КА) являются частным случаем конечных автоматов, используемых для моделирования динамического поведения однородных
- 6. Клеточный автомат. Определение Кле́точный автомат (КА) — набор клеток, образующих некоторую периодическую решетку с заданными правилами
- 7. Клеточные автоматы Клеточный автомат можно представить, как регулярную решетку (или "таблицу") ячеек ("клеток"), каждая из которых
- 8. Клеточный автомат. Общие понятия Клеточный автомат состоит из набора объектов (ячеек), обычно образующих регулярную решетку. Состояние
- 9. Общие понятия Клеточный автомат является дискретной динамической системой, поведение которой полностью определяется в терминах локальных зависимостей.
- 10. Общие понятия Совокупность состояний всех клеток решётки называется состоянием решётки. Состояние решётки меняется в соответствии с
- 11. Общие понятия Если новое состояние клетки зависит от текущего её состояния, то о соответствующем клеточном автомате
- 12. Общие понятия Одно из главных отличий клеточной системы от всех прочих вычислительных систем состоит в том,
- 13. Общие понятия Отметим основные свойства классической модели клеточных автоматов. • Локальность правил. На новое состояние клетки
- 14. Общие понятия • Множество возможных состояний клетки - конечно. Это условие необходимо, чтобы для получения нового
- 15. Общие понятия КА можно разделить на: - детерминированные; - вероятностные; - подвижные; - неподвижные; - однородные;
- 16. Общие понятия Клеточные автоматы с памятью можно получить, предположив, что функция F зависит, например, также от
- 17. Общие понятия Для таких автоматов ДУ решаются для каждой ячейки отдельно на протяжении фиксированного отрезка времени,
- 18. Общие понятия В ВКА вместо функции F необходимо задать набор вероятностей изменения состояния клетки, которые показывают,
- 19. Общие понятия Для решения наиболее трудных задач типа "реакция – диффузия – конвекция" с учетом флуктуаций
- 20. Общие понятия Флуктуации — случайные отклонения от среднего значения физических величин, характеризующих систему из большого числа
- 21. Правила построения КА Общие правила построения клеточных автоматов можно сформулировать следующим образом: Состояние клеток дискретно (обычно
- 22. Область применения КА Клеточные автоматы предоставляют большую свободу в выборе структуры и правил развития системы. Это
- 23. Общие понятия Клеточные автоматы различаются, в частности, количеством состояний клеток, размерностью сетки и правилом изменения состояний
- 24. Общие понятия Состояние клеточного автомата может быть описано матрицей, например: Здесь состояния клеток записываются в соответствующих
- 25. Примеры КА Автоматы серии "Поколения" Автоматы с числом состояний более чем два. Правила изменений состояния клетки
- 26. Примеры КА Например - 23/3/14 Означает, что клетка живет, если у нее 2 или 3 соседа,
- 27. Примеры КА "Искры" 2/2/25 На рисунке представлены 0-ая, 16-ая, 32-ая, 48-ая, 64-ая и 80-ая конфигурации:
- 28. Примеры КА "Букашки" 23/2/8 На рисунке представлены 0-ая, 16-ая, 32-ая, 48-ая, 64-ая и 80-ая конфигурации: Здесь
- 29. Примеры КА "Пламя" 235678/3468/9 На рисунке представлены 0-ая, 16-ая, 32-ая, 48-ая, 64-ая и 80-ая конфигурации
- 30. Примеры КА Автомат "Клеточная вселенная" Еще один пример клеточного автомата, открытый Дейвидом Гриффитом из Висконсинского университета
- 31. Примеры КА На рисунке представлен пример реализации такого автомата (поле 80х80, n=17). Каждый фрагмент на 12
- 32. Примеры КА Автоматы серии "Тьюрмиты" Тьюрмит - это некий синтез клеточного автомата и машины Тьюринга. От
- 33. Примеры КА Состояния принято обозначать латинскими буквами; цвета - числами от 0 до 15 (16-ти цветовая
- 34. Примеры КА "Кактус" (на рисунке представлена одна из возможных конфигураций) Система правил: A 0 2 1
- 35. Примеры КА "Спираль Тэрка" (на рисунке представлена одна из возможных конфигураций) Система правил: A 0 2
- 36. Примеры КА "Нить Ариадны:" Система правил: A 0 15 0 D A 15 0 0 B
- 37. Примеры КА "Спираль:" Система правил: A 0 15 0 D A 15 0 0 B E
- 38. Игра «Жизнь» Игра́ «Жизнь» - клеточный автомат, придуманный английским математиком Джоном Конвеем в 1970 году.
- 39. Игра «Жизнь» Место действия этой игры — «вселенная» — это размеченная на клетки поверхность, безграничная, ограниченная,
- 40. Игра «Жизнь» Каждое следующее поколение рассчитывается на основе предыдущего по таким правилам: пустая (мёртвая) клетка ровно
- 41. Игра «Жизнь» Игрок не принимает прямого участия в игре, а лишь расставляет «живые» клетки, которые взаимодействуют
- 42. Немного истории. Происхождение Джон Конвей заинтересовался проблемой, предложенной в 1940-х годах известным математиком Джоном фон Нейманом,
- 43. Компьютерная реализация Простейший алгоритм последовательно просматривает все ячейки решетки и для каждой ячейки подсчитывает соседей, определяя
- 44. Фигуры Глайдер (glider) Вскоре после опубликования правил, было обнаружено несколько интересных шаблонов (вариантов расстановки живых клеток
- 45. Фигуры Некоторые такие фигуры остаются неизменными во всех последующих поколениях, состояние других периодически повторяется, в некоторых
- 46. Фигуры Конвей первоначально предположил, что никакая начальная комбинация не может привести к неограниченному размножению и предложил
- 47. Фигуры К настоящему времени более-менее сложилась следующая классификация фигур: Глайдерное ружьё Госпера (en:Bill Gosper) — первая
- 48. Фигуры Устойчивые фигуры: фигуры, которые остаются неизменными Периодические фигуры: фигуры, у которых состояние повторяется через некоторое
- 49. Райский сад Райским садом называется такое расположение клеток, у которого не может быть предыдущего поколения. Практически
- 50. Еще раз … Функцию переходов (для клетки принято называть множеством правил КА. Наиболее известным примером КА
- 51. Вспомним … и запишем… Правила в игре "Жизнь", которую Вам предстоит реализовать: Выживание: Если заняты 2
- 52. Клеточные автоматы
- 54. Скачать презентацию