TR | RU | KK | BE | EN |

Фронтальний клітинний автомат

фронтальний клітинний автомат калашникова, фронтальний клітинний автомат федорова
Фронтальний клітинний автомат frontal cellular automata, FCA — спеціальний тип обчислювальних алгоритмів, збудованих на моделях клітинних автоматів

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

Головним елементом алгоритму клітинних автоматів є визначення стану клітини за допомогою так званих правил переходу Ці правила описують стан клітини в наступному кроці на підставі визначення стану всіх клітин в його сусідстві поточний стан клітини часто не враховується Класичний алгоритм клітинних автоматів використовує це правило безпосередньо, тобто збирає інформацію Приклад зображений на малюнку 1а Для клітини в середині малюнка перевіряються правила переходу і вона отримує інформацію, досліджуючи стан своїх сусідів наприклад в оточенні фон Неймана Тому для реалізації обчислень в одному кроці необхідно вивчити цілий клітинний простір стрілка у верхній частині малюнка, перевіряючи правила переходу для кожної клитини і стан усіх сусідів для кожної клитини простору У фронтальних клітинних автоматах напрямок передачі змінюється на протилежний, як це показано на малюнку 1b Це перший крок, який ще не дає будь-яких видимих переваг тому, що і в цьому випадку доводиться досліджувати весь клітинний простір і немає істотної різниці, чи буде клитина отримувати або відправляти інформацію до всіх своїх сусідів

a

b

Рис1

Різниця між цими алгоритмами з'являється, якщо ми розглядаємо перехідний та сталий стани Якщо в сусідстві клітинки не відбуваються зміни, вона залишається в тому ж стані, і можна сказати, що вона знаходиться в сталому стані І навпаки, якщо відбуваються зміни в сусідстві, вона може змінити свій стан, тобто буде в перехідному стані Вже на цьому етапі виявляються відмінності між двома алгоритмами, так як збір інформації від сусідів не створює будь-яких передумов, які вказували б, чи слід збирати таку інформацію, чи ні Однак, при поширенні розсилці інформації від клітини до сусідів рішення може бути прийняте на підставі знання, чи змінився стан цієї клітини чи ні Клітина, яка не змінює свого стану, не буде посилати інформацію до свого оточення, однак, якщо зміни в її стані відбулися, клітини в усьому її оточенні отримають повідомлення, і на підставі цієї інформації здійснюють перевірку правил переходу, без вивчення свого сусідства Це другий крок, друга відмінність

Третій і останній крок полягає у використанні для розрахунку тільки клітин у перехідному стані Якщо сутністю другого кроку була розсилка сигналів тільки від клітин в перехідному стані і незмінним дослідженням усього клітинного простору, то головним елементом третього етапу модернізації алгоритму є обмеження дослідження клітин тільки тими з них, які знаходяться в перехідному стані

Як приклад ефективного застосування може бути показаний процес зростання кристала Фрагмент простору зі зростаючим кристалом зображений на малюнку 2 У будь-якому процесі росту кристалу або зерна, можна виділити три зони У першій зоні a не відбулося жодних змін початкового стану У другій зоні b такі зміни закінчилися, і подальші зміни більше відбуватися не будуть Нарешті, в третій зоні c зміни відбуваються в цей час часу і, отже, тільки клітини з третьої зони використовуються в розрахунках І перша, і друга зони повинні бути виключені з розрахунків у поточному кроці, оскільки зміни в клітинах цих зон не очікуються і не відбудуться Для вибраної клітини на малюнку 2 в перехідному стані показано стрілками напрямок передачі інформації, істотною для сусідів Таким чином, в поточному кроці тільки шість клітин в зоні c братимуть участь у розрахунку

Рис2

Використання FCA, замість звичайних клітинних автоматів, дозволяє знизити обчислювальні витрати в 2D-моделях, але особливо істотно в 3D-CA, тому що значні області простору виключаються з розрахунку в кожному кроці за часом, і лише тонкий шар клітин бере участь у розрахунку У класичних CA практично кожен крок потребує таких самих витрат і час його обчислення протягом всього процесу моделювання залишається незмінним Час ж розрахунку одного кроку FCA залежить від кількості клітин, що беруть участь у розрахунку, і змінюється в широких межах, залишаючись завжди лише малою частиною в порівнянні з часом обчислень одного кроку в класичних CA Кожна клітина FCA насправді бере участь в розрахунках тільки один раз протягом усього процесу розрахунку, в той час, як в класичному алгоритмі, на кожному кроці обчислень

Приклади оцінки обчислювальних витрат для декількох простих варіантів

Перший варіант: двовимірний клітинний простір 100x100 клітин з одним зародком Розрахунки до моменту заповнення всього простору з сусідством фон Неймана чотири сусіда без затримок

Другий варіант: тривимірний клітинний простір 100x100x100 клітин з одним зародком Розрахунки до моменту заповнення всього простору з сусідством Мура 26 сусідів, кристал росте у кшталті сфери з середньою затримкою в перехідному стані, що дорівнює трьом крокам

Витрати на обчислення відрізнятися на декілька порядків При цьому, чим більше число кроків, тим більше ця різниця табл



Класичний алгоритм Фронтальний автомат Стосунок витрат класичного до фронтального
Вар 1 Вар 2 Вар 1 Вар 2 Вар 1 Вар 2
Число кроків від зародка до заповнення всього простору 50 184 50 184 1 1
Число досліджуваних клітин у всьому розрахунку 5105 1,84108 104 3106 50 61
Число комунікатів між клітинами в усьому розрахунку 2106 4,78109 4104 2,6107 50 184

Джереларед

  1. Dmytro Svyetlichnyy "Modelling of the microstructure: From classical cellular automata approach to the frontal one ", Computational Materials Science, t 50, 2010, s 92-97
  2. Łukasz Łach, Dmytro Svyetlichnyy "Modelowanie za pomocą frontalnych automatów komórkowych rozwoju mikrostruktury podczas walcowania", Hutnik-Wiadomości Hutnicze, 2010, s725-735
  3. Dmytro Svyetlichnyy "Proc COMPLAS IX", Barcelona 2007, s 983
  4. Dmytro S Svyetlichnyy 2011 Modeling of Macrostructure Formation during the Solidification by using Frontal Cellular Automata, Cellular Automata - Innovative Modelling for Science and Engineering, Alejandro Salcido Ed, ISBN 978-953-307-172-5, InTech

фронтальний клітинний автомат калашникова, фронтальний клітинний автомат ппш, фронтальний клітинний автомат томпсона, фронтальний клітинний автомат федорова


Фронтальний клітинний автомат Інформацію Про

Фронтальний клітинний автомат


  • user icon

    Фронтальний клітинний автомат beatiful post thanks!

    29.10.2014


Фронтальний клітинний автомат
Фронтальний клітинний автомат
Фронтальний клітинний автомат Ви переглядаєте суб єкт.
Фронтальний клітинний автомат що, Фронтальний клітинний автомат хто, Фронтальний клітинний автомат опис

There are excerpts from wikipedia on this article and video

Випадкові Статті

Більярд

Більярд

Білья́́рд — гра кулями на спеціально обладнаному столі. Усі сучасні варіанти гри проходять на с...
Гур'ївка

Гур'ївка

Гур'ївка у Вікісховищі Гу́р'ївка — село в Україні, в Новоодеському районі Миколаївської...
Каплиці Версаля

Каплиці Версаля

Сучасна Каплиця Версальського палацу є п'ятою в його історії. Каплиці палацу розвивались разом із па...
Keep the Faith

Keep the Faith

«Keep the Faith» — пісня Тако Гачечиладзе для конкурсу Євробачення 2017 в Києві, Україна1 Пісня...