Версія для друку тут (zipped doc - 229кб)
мета завдання
Реалізувати клітинний автомат
опис завдання
Загальна теорія
Клітинні автомати є дискретними динамічними системами, поведінка яких повністю визначається в термінах локальних взаємозалежностей їх станів. Клітинний автомат є рівномірною n-мірну сітку (кінцеву або нескінченну), кожна клітинка (клітка) якої може приймати стан з деякого набору станів; час йде дискретними кроками, а закони розвитку (зміни станів клітин) виражаються єдиним набором правил, наприклад невеликий довідкової таблицею, по якій будь-яка клітина на кожному кроці обчислює свій новий стан по станам її близьких сусідів. Якщо заданий відповідний набір правил, то такий простий операційний механізм достатній для підтримки цілої ієрархії структур і явищ. Клітинні автомати дають корисні моделі для багатьох досліджень в природничих науках. Вони утворюють загальну парадигму паралельних обчислень, подібно до того, як це роблять машини Тьюринга для послідовних обчислень.
Хорошим прикладом для ознайомлення з принципами роботи клітинного автомата є гра Джона Хортона Конвея "Життя".
Різновиди клітинних автоматів
Клітинні автомати розрізняються, зокрема, кількістю станів клітин, розмірністю сітки і правилом зміни станів клітин. Ми розглянемо деякі різновиди автоматів з двовимірної сіткою.
У двовимірних автоматах сусідами клітин зазвичай вважаються 5 клітин - сама клітина і 4 її безпосередньо не діагональних сусіда (околиця фон Неймана), або 9 клітин - сама клітина і 8 її безпосередніх сусідів, включаючи діагональні клітки (околиця Мура).
Стан клітинного автомата може бути описано матрицею, наприклад:
Тут стану клітин записуються у відповідних осередках матриці.
Але набагато цікавіше уявити стан у вигляді зображення, де кожен піксель відповідає клітці, і поточний колір пікселя визначається станом клітини.
Конкретні приклади клітинних автоматів
Автомати з числом станів більш ніж два.
Правила змін стану клітини записуються наступним чином
де:
S - набір цифр від 0 до 8, визначає число "живих" сусідів, при якому клітина залишається "в живих",
B - набір цифр від 0 до 8, визначає число "живих" сусідів при якому "мертва" клітина стає "живою"
С - число, визначає число ходів "вмирання" клітини
Чи означає, що клітина живе, якщо у неї 2 або 3 сусіда, що при рівно трьох сусідів "народжується" нова клітина, і що клітина вмирає за чотирнадцять ходів.
Якщо число "живих" сусідів у клітини не дорівнює жодній з цифр з набору S, клітина починає "вмирати" і її стан збільшується з кожним ходом, поки не досягне C, після чого клітина пропадає. "Помираючи" клітина не бере участі в підрахунку числа "живих" сусідів при розрахунку наступного кроку. При народженні клітина отримує перший стан ( "клітина жива").
"Іскри"
2/2/25
На малюнку представлені 0 Перша, 16-а, 32-а, 48-а, 64-а і 80-а конфігурація:
"Букашки"
23/2/8
На малюнку представлені 0 Перша, 16-а, 32-а, 48-а, 64-а і 80-а конфігурація
"Полум'я"
235678/3468/9
На малюнку представлені 0 Перша, 16-а, 32-а, 48-а, 64-а і 80-а конфігурація
Ще один приклад клітинного автомата, відкритий Дейвідом Гриффітом з університету Вісконсіна в Медісоні. Стартуючи з довільно обраного початкового стану, автомат демонструє чотири різні фази, що завершуються химерними кристалічними утвореннями, сильно нагадують примітивні форми життя.
Правило поведінки автомата полягає в тому, щоб пронумерувати можливі стани від 0 до n - 1 і вважати, що якщо клітина знаходиться на даному такті в стані k, то на наступному такті вона повинна "з'їсти" будь-які сусідні клітини, що знаходяться в стані k - 1 . З'їдання проявляється в тому, що з'їдена сусідня клітина переходить зі стану k - 1 в стан k; клітина в стані 0 може поїдати сусідні клітини в стані n - 1.
На малюнку представлений приклад реалізації такого автомата (поле 80х80, n = 17). Кожен фрагмент на 12 ітерацій відрізняється від попереднього.
Тьюрміт - це якийсь синтез клітинного автомата і машини Тьюринга. Від клітинного автомата тьюрміт відрізняється тим, що в початковий момент часу його поле порожньо і якась одна клітина вважається початковою (тьюрміт займає початкову позицію, знаходиться в початковому стані, початковий напрямок, наприклад, на схід). Потім на кожному такті застосовується правило виду:
Стану прийнято позначати латинськими літерами; кольори - числами від 0 до 15 (16-ти кольорова палітра), причому початковий колір чорний (це не жорстке обмеження, при бажанні колірну гамму можна збагатити і придумати свої позначення); напрямок переміщення змінюється щодо поточного курсу тьюрміта, позначається числами -1 (повернути ліворуч), 1 (повернути праворуч), 0 (прямо).
Наприклад, правило А 0 15 0 В означає, що якщо тьюрміт знаходиться в стані А і стоїть на чорній клітці, то він повинен пофарбувати її в білий колір, просунутися на одну клітку в поточному напрямку і перейти в стан В.
Таким чином, якщо А - початковий стан тьюрміта, 0 - початковий колір, то набір правил тьюрміта повинен містити правило А 0 _ _ _.
"Кактус"
(На малюнку представлена одна з можливих конфігурацій)
A 0 2 1 A
A 2 10 -1 B
A 10 0 -1 B
B 0 2 1 A
B 2 + 2 -1 A
B 10 2 -1 A
оформлення
Оформлення не відрізняється від звичайного.
ZIP-архів вихідних текстів і виконуваними файлами, названий за схемою GZV_nnnnnnnn.zip (де G - остання цифра номера групи, Z - номер завдання, V - номер версії завдання, nnnnnnnn - номер студентського квитка) надсилайте на [email protected]. msu.su
Наприклад, студент 206 групи з номером студентського квитка 06529042, який здає оновлену (другу) версію програми по першого завдання, повинен надіслати архів з ім'ям 612_06529042.zip.
Не забудьте покласти в архів файл readme.txt. У файлі описати інтерфейс програми (алгоритм роботи з програмою, пункти меню, керуючі клавіші) і вказати наступні підзавдання:
Реалізація автомата: [вказати реалізований автомат (и)]
Можливість редагування початкового стану автомата: [+/-]
Робота з програмою: [алгоритм роботи з програмою]
Результати роботи
Примітки
- Завдання виконується строго індивідуально. За спільну роботу або обмін шматками коду ставиться нуль балів всім учасникам, якщо факт командної роботи не було зазначено в readme.txt завдань.
- Рекомендується написання програми під сімейство ОС Windows. Написання під інші операційні системи небажано і може викликати затримки з перевіркою таких робіт.
ЧаВо за завданням
Де можна знайти докладні матеріали з програмування під Windows?
У завданні в розділі "покоління" сказано, що при певному числі сусідів мертва клітина стає живою. Оживає чи вмираюча клітина (в підрахунку числа живих вона не бере)?
Ні, вмираюча клітина не вважається мертвою, тому стати живою не може.
Що значить "тьюрміт повертає ліворуч / праворуч"?
Припустимо, тьюрміт рухається на схід.
На зображенні темно-сірим кольором позначено, де тьюрміт був на попередньому такті, червоним - поточний стан тьюрміта, а світло-сірим - де він опиниться на наступному такті при русі наліво (верхній варіант), направо (нижній варіант) або прямо (середній варіант ).
У розділі "Покоління" в який момент ми позначаємо клітку "вмираючої": після того, як ми порахували новий стан автомата (в попередньому вона не вмирала) або відразу ж як тільки ми порахували, що число сусідів у неї таке, що вона повинна вже вмирати?
Відразу ж, як тільки у клітини з'явилося недозволений число сусідів, вона починає вмирати. Не повинно бути стану автомата, при якому у живої клітини число сусідів не збігається ні з одним з набору S.