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

ПЕРЕЛІК УМОВНИХ ПОЗНАЧЕНЬ, СИМВОЛІВ, ОДИНИЦЬ, СКОРОЧЕНЬ І ТЕРМІНІВ

 

ОС – Однорідні структури

КА – Клітинні автомати

ЛФП – Локальна функція переходу

ГФП – Глобальна функція переходу

ЕОМ – Електронна обчислювальна  машина

LGA – Lattice Gas Automata

ДРЧП – Диференційні рівняння у  часткових похідних

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ЗМІСТ

 

РЕФЕРАТ ……………………………………………………………………………2

ПЕРЕЛІК УМОВНИХ  ПОЗНАЧЕНЬ, СИМВОЛІВ, ОДИНИЦЬ,

СКОРОЧЕНЬ І  ТЕРМІНІВ …………………………………………………………3

ВСТУП ………………………………………………………………………………5

1. ОСНОВНІ ПОНЯТТЯ ТЕОРІЇ КЛІТИННИХ АВТОМАТІВ
1. Історія виникнення та ідея клітинних автоматів ………………………….7
2. Основні поняття ……………………………………………………………..9
3. Основні види клітинних автоматів ………………………………………..12
4. Класи правил для найпростіших одновимірних клітинних автоматів …..14
5. Види правил для двовимірних клітинних автоматів ……………………..16
1. Необмежений ріст ……………………………………………………17
2. Обмежений ріст ………………………………………………………17
3. Конкурентний ріст …………………………………………………...18
4. Правила голосування ………………………………………………...19
5. Правило експоненціального затухання ……………………………..21
2. ДЕЯКІ ЗАСТОСУВАННЯ КЛІТИННИХ АВТОМАТІВ
1. Однорідні структури як формальна модель обчислювальної техніки ….22
2. Використання клітинних автоматів у фізиці ……………………………..25
3. Однорідні структури та диференційні рівняння ………………………….27
4. Використання клітинних автоматів у соціології ………………………...29
3. МОДЕЛЬ ПОШИРЕННЯ ІНФЕКЦІЇ НА БАЗІ КЛІТИНИХ АВТОМАТІВ
1. Концепція поширення властивості у просторі …………………………..32
2. Результати моделювання …………………………………………………..34

ВИСНОВКИ ………………………………………………………………………...41

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ І ЛІТЕРАТУРИ ………………………..42

ДОДАТОК А ………………………………………………………………………..43

 

ВСТУП

 

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

Сучасний  ріст інтересу до клітинних автоматів  обумовлений можливостями їхнього  використання у двох визначальних напрямках: формальна модель паралельної обробки  інформації і зручне середовище для моделювання найрізноманітніших фізичних і штучних дискретних систем, процесів і явищ, які допускають високий рівень розпаралелювання. Інтерес до них підсилюється можливістю практичної реалізації на основі сучасних успіхів у мікроелектроніці та нанотехнологіях.

Теорія  клітинних автоматів розвивається дуже великим колективом дослідників  у багатьох країнах світу, найперше у США, Німеччині, Італії, Франції, Японії, Угорщині та Великобританії. Був сформований ряд дослідницьких груп у цих країнах. У країнах колишнього Радянського Союзу ця тема є не дуже розвиненою. Також варто відмітити створення під егідою IFIP (International Federation for Information Processing) міжнародної робочої групи по клітинними автоматам.  

Концепція однорідних структур доволі успішно  застосовується для отримання простих  моделей диференційних рівнянь  фізики, для дослідження теорії динамічних систем, яка займається проблемами виникнення і поведінки таких явищ як фрактальність, упорядкованість, турбулентність і хаос в системах, що складаються із великої кількості елементів, які локально взаємодіють між собою.

У своїй  курсовій роботі я постарався розібратися  із теорією клітинних автоматів  та сферами їхнього застосування. Робота є актуальною для нашої  країни, оскільки досліджень на дану тему в Україні, як виявилося, проводиться  не достатньо багато. Клітинні автомати є дуже зручними для моделювання різних динамічних систем, і тому можуть бути використані, наприклад, для моделювання поширення інфекцій чи забруднення навколишнього середовища, що є дуже актуальним для нашого суспільства.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ОСНОВНІ ПОНЯТТЯ  ТЕОРІЇ КЛІТИННИХ АВТОМАТІВ 

 

1.  Історія виникнення та ідея клітинних автоматів

 

Однорідні структури (по іншому – клітинні автомати) відкривалися заново не один раз під  різними назвами – в теоретичній  математиці вони відомі як розділ топологічної динаміки, в електротехніці вони відомі як ітеративні сітки, в біології –  як кліткові структури, студенти їх можуть знати як гру на персональному  комп’ютері.

У звичайних  моделях обчислень, таких як машина Тюрінга, виділяють фіксовану структурну частину і дані, якими машина оперує – вони є змінними. Комп’ютер не може оперувати своєю «матеріальною частиною», не може розширюватися чи модифікувати себе, будувати нові, схожі на нього комп’ютери. У клітинних автоматах і об’єкти, що можуть інтерпретуватися як дані, і об’єкти, що інтерпретуються як обчислювальні пристрої, складаються із елементів одного типу і підкорюються однаковим локальним законам

  Однорідні  структури у їхньому першому  вигляді були визначені Дж. фон  Нейманом на базі пропозиції  С. Улама з ціллю отримати  реалістичну добре формалізовану  модель для дослідження складних  динамічних систем.   Сам С.  Улам використовував моделі подібні  до однорідних структур для  дослідження проблеми росту кристалів  і інших дискретних систем  з рекурентними правилами. Дж. фон Нейман застосовував кліткові автомати для моделювання процесів біологічного розвитку і, найголовніше, процесу самовідтворення. У кінці війни німецький інженер К. Цусе висловив новаторські ідеї паралельної обробки інформації, що включали мови програмування високого рівня та «обчислювальні простори» (тобто кліткові автомати). Правда, його ідеї не були відомі широкому колу науковців тому, напевно, паралелізм не був визначальним фактором на початку розвитку обчислювальної техніки.

     Другим етапом становлення теорії однорідних структур була публікація робіт Е. Мура і Дж. Майхілла на тему проблеми неконструйованості класичних моделей однорідних структур. Вони стали своєрідним каталізатором для багатьох математиків, щоб розпочати роботу над теорією однорідних структур. У кінці 60-х років минулого століття теорія кліткових автоматів входить в сучасний етап свого розвитку, що характеризується об’єднанням розрізнених теорій під однією концептуальною платформою та розширенням області її застосування в фізиці, математичній біології розвитку, паралельній обробці інформації, чисельних методах та інформації, що вивело концепцію однорідних структур на міждисциплінарний рівень.

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

 Однорідні  структури мають багато синонімів,  серед яких найбільш відомим  є «клітинні автомати» («Cellular Automata»). Однорідні структури (ОС) являються формалізацією поняття нескінченних регулярних решіток із ідентичних скінченних автоматів, які інформаційно зв’язані один з одним єдиним чином. Кожен автомат отримує інформацію від визначеної для нього скінченної множини сусідніх автоматів. Сусідство встановлюється єдиним чином для всіх автоматів і визначається вектором – індексом сусідства. Як правило, розглядаються d-вимірні регулярні решітки в Евклідовому просторі , в цілих точках якого розміщені копії деякого автомата Мура.

ОС-модель функціонує в дискретні моменти  часу так, що кожен автомат решітки синхронно змінює свій стан в дискретні моменти часу як функція станів всіх своїх сусідів в попередній момент часу . Ця локальна функція переходу може мінятися з часом, але залишається єдиною для всіх автоматів решітки в будь-який момент часу . Одночасне застосування локальної функції переходу до всіх автоматів решітки визначає глобальну функцію переходу, яка діє на всій решітці, змінюючи поточну конфігурацію станів всіх автоматів решітки на нову. Зміна конфігурації під дією такої функції визначає динаміку (історію) функціонування ОС-моделі.

Стани кожного  автомата ОС-моделі можна асоціювати з різними поняттями, такими як стан біологічних клітин, команди кліткових  мікропроцесорів, символи деякої формальної паралельної системи, характеристика точок якогось абстрактного поля. Подібні моделі можна застосувати  в різноманітних областях науки: розпізнавання образів, теорія еволюції і розвитку, морфогенез, математика, кібернетика, синергетика, фізика, хімія, штучний інтелект і т.д. Ми можемо інтерпретувати ОС не тільки як абстракцію біологічних клітинних систем, але  і як теоретичну основу штучних паралельних  систем обробки інформації[1,2,3].

 

2.  Основні поняття

 

Клітинні  автомати є дискретними динамічними  системами, поведінка яких повністю визначається локальними залежностями, а це також притаманне для великого класу неперервних динамічних систем, які описуються за допомогою диференційних  рівнянь у часткових похідних. З цієї  точки зору клітинні автомати в інформатиці є аналогом поняття  фізичного поля.

Клітковий автомат може мислитися як стилізований світ. Простір представлено у вигляді  рівномірної сітки, кожна комірка  якої, або клітка, зберігає декілька біт даних. Час іде дискретними  кроками, а закони світу виражаються  єдиним набором правил (наприклад  – невелика довідкова таблиця), за якими будь-яка клітка визначає свій стан у наступний момент часу у  залежності від стану її найближчих сусідів. Таким чином, закони системи  є локальними і єдиними всюди. Кліткові автомати утворюють загальну парадигму паралельних обчислень, подібно до машини Тюрінга для послідовних обчислень.

Класичне  поняття -вимірної однорідної структури[1] (кліткового автомата) визначається як впорядкована множина із чотирьох компонент:

-OC,

 де  – скінченна, непуста множина, яка називається алфавітом внутрішніх станів і являє собою множину станів, які може приймати кожен елементарний автомат структури. Алфавіт містить так званий стан покою, який позначається «0». В якості алфавіту можна користуватись множиною станів , яка містить елементів.

Компонента  являє собою множину всіх -вимірних кортежів – цілих координат точок з Евклідового простору , тобто є цілочисельна решітка в , елементи якої служать для ідентифікації автоматів структури. В кожну точку простору поміщається копія скінченного автомата Мура, алфавіт внутрішніх станів якого є . В цьому випадку кожен елемент визначає ім’я або координату елементарного автомата, що міститься в цій точці.

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

Кожен елементарний автомат структури в будь-який момент часу отримує інформацію тільки від своїх сусідів. Таким чином, сусідами кожного елементарного  автомата  будуть автомати , де . Коли індекс сусідства містить елемент , то кожен елементарний автомат належить своєму шаблону сусідства.

Прикладом простого індексу сусідства для  двовимірної однорідної структури  можуть слугувати індекс сусідства фон Неймана та індекс сусідства Мура . Якщо уявити структуру кліткового автомата у вигляді паперу в клітинку, де в кожній клітинці розміщується один елементарний автомат, то індекс сусідства фон Неймана – це такий собі хрестик, що складається з поточної клітинки плюс клітинки на сході, заході, півночі і півдні, індекс сусідства Мура – це центральна клітинка і її вісім найближчих сусідів. Ці індекси є класичними і найпоширенішими, їх легко можна визначити і на -вимірний випадок.