Міністерство освіти і науки, молоді та спорту України

Національний університет водного господарства та природокористування

Факультет прикладної математики та комп’ютерно-інтегрованих систем

Кафедра прикладної математики

Реферат на тему «Кліткові автомати»

Підготувала:

студентка групи ПМ-21

Боровська М.О.

Викладач:

Федорчук Н.А.

Рівне - 2012 План

Основні поняття 3

Властивості кліткових автоматів 5

Класифікація кліткових автоматів 5

Синхронні та асинхронні кліткові автомати 6

Рухливі і нерухомі кліткові автомати 6

Детерміновані та імовірносні кліткові автомати 6

Детерміновані КА 6

Імовірнісні КА 6

КА-ЗДР 7

Одновимірні кліткові автомати 9

Двовимірні кліткові автомати 11

Окіл з восьми клітинок 11

Окіл з чотирьох клітин 12

Автомати з клітинами без пам'яті 13

Гра «Життя» 14

Походження 14

Правила 14

Фігури 15

Застосування кліткових автоматів 16

Висновок 17

Використана література 18

Вступ

Термін «кліткові автомати» почав використовуватись у середині XX ст. для позначення сукупності залежних елементів з заданими станами і правил, згідно з якими стани цих елементів і залежності між ними змінюються в часі. Час і стани при цьому дискретні. Використання описаних моделей для формального моделювання самовідтворюваних організмів вперше запропоновано в роботі Фон Неймана. Елементи кліткових автоматів запропоновано представити одновимірними або двовимірними нескінченними прямокутними таблицями. Стан елемента змінюється в залежності від його стану і від стану двох (або чотирьох - для двовимірного випадку) найближчих сусідів.

Кліткові автомати в силу своєї дискретності порівняно просто моделюються за допомогою ЕОМ і завдяки цьому, в 50-70 ті рр.. XX ст. набувають популярності. Дослідники різних наукових областей вивчають і використовують кліткові автомати з різноманітними властивостями для різних цілей. У цей час виходять основні праці, які заклали базис для загальної теорії кліткових автоматів.

Приблизно в той же час з'явилися ігри для кліткових автоматів - математичні моделі, що мають в основі ігровий опис. Наприклад, гра «Firing Squad» - завдання про одночасний залп всього гарматного складу має в основі важливу задачу синхронізації, а гра «Game of Life» становить модель поведінки популяції в однорідному середовищі.

Починаючи з 80 х рр.. XX ст. вивчення кліткових автоматів набуло більш спеціалізованого відтінку. На базі загальної теорії створюються і вивчаються різні конфігурації кліткових автоматів для конкретних дослідницьких областей. Завдяки різнобічним дослідженням, вдалось створити потужну математичну теорію, направлену на класифікацію і вивчення властивостей різних моделей.