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

метки: Автомат, Клеточный, Двоха, Теорії, Автомать, Самовідтворення, Випадок, Приклад

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

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

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

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

^

Клітковий автомат K – це впорядкована множина з чотирьох компонентів:

K=< Z ^d , N, A, φ>

де Z ^d – множина d -мірних векторів з цілочисельними координатами – клітковий простір ;

N – скінченна множина потужності m векторів з Z ^d :

шаблон сусідства клітинки

^

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

глобальну функцію переходів c

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

Соціальна робота в різних країнах світу

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

однорідними структурами

КА в загальному випадку характеризуються наступні властивостями.

1. ^ після обчислення нового стану кожної клітинки решітки.

2. Решітка однорідна . Неможливо відрізнити жодні два місця на решітці по ландшафту.

3. Взаємодії локальні . Лише околишні клітинки (як правило, сусідні) здатні вплинути на дану клітинку.

4. Множина станів клітинки кінцева.

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

Для отримання різних конфігурацій КА, прийнято варіювати наступними параметрами:

• Стани елементів . У кожний момент часу кожен елемент КА приймає один стан зі скінченного набору станів. У залежності від цих станів в наступний момент часу набір елементів може прийняти новий стан. Якщо для елементів КА множини можливих станів відрізняються, такий клітинний автомат називається полігенним . Але на практиці використовуються комірки з еквівалентною множинами можливих станів алгебраїчною структурою – лінійні КА;

• Геометрія . Елементи можуть бути геометрично розташовані різноманітним чином. Розмірність простору може бути довільною, а число елементів – як безкінечним, так і скінченним. В останньому випадку виникає додаткова міра свободи в граничних умовах. Вони можуть бути різними, але на практиці використовуються постійні у часі (найчастіше – нульові) або періодичні граничних умовах. У динамічних КА геометрія може змінюватися з часом, а якщо геометрія різна на різних ділянках простору, такі кліткові КА називають неоднорідними ;

• Сусідство . Сусіди – це елементи, від яких залежить елемент КА. Стан елемента в наступний момент часу обчислюється із стану самого елементу і його сусідів. Сусідство у більшій мірі визначається геометрією КА. Для різних цілей можлива зміна числа вхідних станів елемента. Якщо для кожного елемента КА число входів і виходів однакове, такий КА називається збалансованим ;

• Локальне правило . Відповідно до локального правила змінюється стан елемента КА протягом часу. КА, в якому локальні правила різні для різних елементів, називається різнорідним . Локальне правило може бути недетермінованим, тобто змінюватися в часі або мати випадкову природу.

^

синхронні

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

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

Під час вивчення предметів природничо-математичного циклу

... Політ був успішним і за­початкував розвиток повітроплавання. Обов'язковим і головним елементом повітроплавання є велика й дуже легка оболонка, ... транспорту. Проте водно­час потрібно дбати про стан водойм, яким шкодять забруднення відходами із суден. Особливо , ... Хід уроку Оголошення теми та мети уроку – 3 хв., Учитель фізики., Учитель географії 1-й експерт суднобудівник На будівництво свого судна ...

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

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

Детерміновані та імовірносні кліткові автомати, Детерміновані КА

У детермінованих КА стан комірки α _in+1 в наступний момент часу однозначно визначається станом цієї клітинки і її найближчих сусідів у попередній момент часу. У цьому випадку стан даного елемента в момент часу n +1 є однозначною функцією F від двох змінних — стану цього елемента і суми станів його найближчих сусідів у попередній момент часу n. При такому визначенні клітинний автомат не має пам’яті. КА з пам’яттю можна отримати, припустивши, що функція F залежить, наприклад, також від стану елемента в ще більш ранній момент часу.

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

імовірнісними КА

Для вирішення найбільш складних завдань типу «реакція — дифузія — конвекція» з урахуванням флуктуацій був розроблений метод імовірносного клітинного автомата з застосуванням процедури Монте-Карло (ІКА-МК або просто ІКА).

Клітковий автомат представляє собою регулярну решітку, що складається з N ₂ = N₀ елементарних комірок. Форма решітки може бути не тільки квадратна, а й прямокутна з сильно витягнутими комірками. Кожна клітинка характеризується набором цілих чисел: числом молекул відповідного сорту в даній клітинці (наприклад, n _A , n _B , n _С в разі трьох сортів молекул A, B і C ) і своїми цілочисельними координатами (наприклад, i і j ).

Клітинці приписується також певний об’єм V _m і лінійний розмір l = (V _m )/3 . Об’єм V _m використовується при заданні ймовірностей протікання хімічних реакцій в комірках. Усі клітинки вважаються гомогенними (однорідними).

КА-ЗДР

звичайних диференціальних рівнянь

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

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

Автомат Калашникова (АК-47)

... прийнятий на озброєння в рамкахконкурсу "Абакан", мабуть, не стане не тільки основним, але іскільки масовою зброєю. 5.45мм автомат Калашникова АК-74 АК-74 пізніх випусків, із пластиковою ... Самим останнім і в даний час основним варіантом стававтомат АК-74М, що надходить на озброєння Російської Армії з початку 1990хроків. Цей автомат відрізняється головним чином тим, ...

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

• Ітеративний автомат . КА, в якому лише один елемент використовує для зміни свого стану значення вхідного параметра;

• Односторонній клітковий автомат . Такий автомат припускає лише односторонню взаємодію елементів. Наприклад, в одновимірному масиві елементів значення кожного елемента залежить лише від його стану і від стану лівого (або правого) сусіда. Незважаючи на удавану вироджуваність зазвичайного КА, односторонні КА досить універсальні і використовуються для розпізнавання мовних форм;

• Л-система . Цей тип КА використовується для моделювання біологічних систем. Це динамічні КА (як правило, одно- чи двовимірні), в яких з часом один елемент може замінятися декількома або може бути видаленим із системи у відповідності з заданими правилами;

• Відмовостійка система . У таких системах моделюється робота КА в реальних умовах: з деякою ймовірністю кожен елемент КА може перейти в стан, що не відповідає локальному правилом. Завданням є створення алгоритмів, для яких робота КА буде правильною в незалежності від допущених помилок.

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

інвертующим

^

^

В одновимірному (лінійному) КА решітка представляє собою ланцюжок клітинок (одновимірний масив), в якій для кожної з них, крім крайніх, є по два сусіди. Для усунення крайових ефектів решітка «загортається» у тор. Це дозволяє використовувати наступне співвідношення для всіх клітин автомата

y ‘[i] = f (y [i-1], y [i], y [i +1]),

де f – функція переходів клітинки;

y ‘[i] – стан i-ої клітинки в наступний момент часу;

y [i-1] – стан (i-1)-ої клітинки в даний момент часу;

y [i] – стан i-ої клітинки в даний момент часу;

История возникновения прокатного стана

... сплавов и заготовок из стали. 2. Классификация и устройство Классификация прокатных станов. Главный признак, определяющий прокатного стана, - его назначение в зависимости от сортамента продукции или выполняемого ... в каждой из которых располагается 3 вида устройств (рис.2): рабочие клети (одна или несколько) - к ним относятся прокатные валки с подшипниками, станины, установочные механизмы, ...

y [i +1] – стан (i +1)-ої клітинки в даний момент часу.

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

Приклад 1 . Нехай функція переходів клітини має наступний вигляд:

y ‘[i] = y [i-1]  y [i]  y [i +1],

Як вихідні значення виберемо одиницю для центральної клітини і нуль – для всіх інших клітин.

Можна представити поведінку КА у часі. Назвемо її «піраміда».

Приклад 2.

Приклад 3.

y ‘[i] = y [i-1]  y [i]  y [i +1],

де  – символ логічної операції «сума по модулю два».

Вибираючи в якості початкового таке саме заповнення решітки, що й у прикладі 1, отримаємо поведінку, яка може бути названо «проділ».

Приклад 4.

y ‘[i] = y [i-1]  y [i]  y [i +1].

Цей автомат, при тих же початкових умовах, що і в попередньому прикладі, породжує фрактальну поведінку. Він є досить простою моделлю, яка демонструє самовідтворення.

^

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

У двовимірному (площинному) КА решітка реалізується двовимірним масивом. У ній кожна клітина має вісім сусідів. Для усунення крайових ефектів решітка так само, як і в попередньому випадку, «загортається» у тор. Це дозволяє використовувати наступне співвідношення для всіх клітинок автомата:

y ‘[i] [j] = f (y [i] [j], y [i-1] [j], y [i-1] [j +1], y [i] [j +1] , y [i +1] [j +1], y [i +1] [j], y [i +1] [j-1], y [i] [j-1], y [i-1] [j-1]).

Приклад 5 . Найбільш відомим із двовимірних КА є автомат, що моделює гру «Життя». У цьому автоматі, як і у всіх, розглянутих вище, клітинки можуть знаходитися в двох станах. Функція переходів клітинок реалізує наступні умови:

• якщо дана клітинка мертва (знаходиться у стані «нуль»), то вона оживе (перейде в стан «одиниця») за умови, що у неї є рівно три живих сусіда;
• якщо дана клітина жива, то вона залишиться живою тільки за умови, що у неї є два або три живі сусіда і помре в іншому випадку.

У цій грі інтерес представляє спостереження за розвитком популяції клітин при різних початкових умовах.

Приклад 6 . Як приклад фрактальної поведінки розглянемо КА, що функціонує за правилом:

y ‘[i] [j] = y [i] [j]  y [i-1] [j]  y [i-1] [j +1] y [i] [j +1] 

y [i +1] [j +1]  y [i +1] [j]  y [i +1] [j-1]  y [i] [j-1]  y [i-1] [j-1].

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

Приведемо початкову конфігурацію решітки та результат її самовідтворення через вісім кроків.

Необхідно зазначити, що в силу властивостей функції «сума за модулем два», самовідтворення має місце після будь-якого числа кроків, що є степенем двох, починаючи зі значення, яке визначається співвідношенням

де a і b – ширина і висота «зародка», відповідно.

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

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

Технологический процесс производства тонкостенных бесшовных труб ...

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

Будемо розглядати як околи даної клітини лише ті з них, які мають загальну сторону з нею і називаються «головними сусідами».

Приклад 7 . Для ілюстрації фрактальної поведінки автомата з таким околом виберемо наступну функцію переходів:

y ‘[i] [j] = y [i] [j]  y [i-1] [j]  y [i] [j +1]  y [i +1] [j]  y [i ] [j-1].

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

При цьому період повного самовідтворення обчислюється на основі співвідношення:

T = max (

Для розглянутого «зародка» період самовідтворення по горизонталі , а по вертикалі – . Тому повний період самовідтворення T = 8.

Приведемо конфігурацію через чотири та вісім кроків.

^

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

Принципово інший клас КА виникає, якщо відмовитися від використання стану даної клітинки в якості вхідної змінної функції переходів. Такий клас назвемо «автоматами з клітинками без пам’яті».

При цьому зазначимо, що, незважаючи на те,що в автоматах цього класу клітинки пам’яттю не володіють, за рахунок перевизначення змінних, такі автомати в цілому мають пам’ять.

Цей клас автоматів є найпростішим, застосування якого забезпечує самовідтворення.

Приклад 8.

y ‘[i] = y [i-1]  y [i +1].

Гра «Життя»

Походження

Джон Конвей зацікавився проблемою, запропонованою в 1940-х роках відомим математиком Джоном фон Нейманом, який намагався створити гіпотетичну машину, яка може відтворювати сама себе. Дж. фон Нейману вдалося створити математичну модель такої машини з дуже складними правилами. Конвей спробував спростити ідеї запропоновані Нейманом, і врешті-решт йому вдалося створити правила, які стали правилами гри «Життя».

Правила

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

• Порожня (мертва) клітинка поруч із трьома живими клітинками сусідами оживає;

• Якщо у живої клітинки є дві або три живі сусідки, то ця клітинка продовжує жити; в іншому випадку (якщо сусідів менше двох або більше трьох) клітинка вмирає (від «самотності» або від «перенаселення»).

  5 стр., 2443 слов

  Технологічні аспекти теорії проектування інформаційних систем

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

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

Ці прості правила призводять до величезного розмаїття форм, які можуть виникнути у грі.

Фігури

Незабаром після опублікування правил, було виявлено декілька цікавих шаблонів (варіантів розстановки живих клітин в першому поколінні), зокрема: r-пентаміно і планер (glider).

Деякі такі фігури залишаються незмінними в усіх наступних поколіннях, стан інших періодично повторюється, в деяких випадках зі зміщенням всієї фігури. Існує фігура (Diehard) всього з семи живих клітин, нащадки якої існують протягом 130 поколінь, а потім зникають.

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

Дотепер більш-менш склалася наступна класифікація фігур:

• Стійкі фігури : фігури, які залишаються незмінними;

• Періодичні фігури : фігури, у яких стан повторюється через деяку кількість поколінь;

• Рухливі фігури : фігури, у яких стан повторюється, але з деяким зсувом;

• Рушниці : фігури, у яких стан повторюється, але додатково з’являються рухливі фігури фігура;

• Паровози : рухливі фігури, які залишають за собою сліди у вигляді стійких або періодичних фігур;

• Пожирачі : стійкі фігури, які можуть пережити зіткнення з деякими рухливі фігурами.

Райський сад

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

^

Лауреат Нобелівської премії з фізики 1999 Герард Хоофт запропонував нову теорію об’єднання гравітації і квантової механіки, використовуючи ідею кліткових автоматів.

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

Ця ідея була формалізована в 1964 році Джоном Беллом, який вивів серію нерівностей, що обмежують заплутаність частинок. Проте численні досліди, проведені фізиками з того часу, виявили порушення цих нерівностей. Тому теорії локальних змінних були визнані невиправданими.

Автоматизация участка нагревательных печей и толстолистового стана кварто

... Автоматизация измерения температурного режима слитка в методической печи Для полного представления о системе регулирования температуры в печах, более детально рассмотрим систему управления зонами нагревательной печи, ... валков, — СУ положением валков, — СР показателей состояния прокатываемых полос между клетями стана, — СР размеров профиля прокатываемых полос. — СУ ножницами, — СУ устройствами ...

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

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

Висновок

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

У зв’язку з цим універсальність КА можна розглядати з двох позицій. У першому випадку КА є універсальним, якщо він моделює поведінку інших КА із заданими параметрами. Інший підхід — алгоритмічний. Тут КА є універсальним, якщо він моделює універсальну машину Тюрінга.

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

Представляє інтерес дослідження КА з мінімальними значеннями параметрів.

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

1. И. И. Захарчук, «О сложности одномерных универсальных клеточных автоматов» – Дискретный анализ и исследование операций, октябрь—декабрь 2002. серия 1. том 9, № 4, 50-56.

2. Лев Наумов, Анатолий Шалыто, «Клеточные автоматы. Реализация и эксперименты».

3. М.В. Поникаров, «Использование игр клеточных автоматов для синхронизации в распределенных системах».

4. http://ru.wikipedia.org.

5. .

---

---