Кобильник Т.П. [kobylnyktaras@gmail.com]
Дрогобицький державний педагогічний університет імені Івана Франка, Україна
Download in PDF: http://fmo-journal.fizmatsspu.sumy.ua/journals/2018-v4-18/2018_4-18-Kobylnyk_FMO.pdf

КЛІТКОВІ АВТОМАТИ ЯК ЗАСІБ МОДЕЛЮВАННЯ СКЛАДНИХ СИСТЕМ

Анотація. Стаття присвячена характеристиці кліткових автоматів як методу моделювання складних систем. Багато складних явищ та процесів, таких як самовідтворення, ріст, розвиток тощо складно описати за допомогою диференціальних рівнянь та їх систем. Проте це вдається легко змоделювати за допомогою кліткових автоматів. Відповідно зростає популярність моделей, побудованих на їх основі. Клітковий автомат характеризується дискретним простором і часом. Така структура є зручною для моделювання різноманітних фізичних, біологічних та інформаційних процесів. Застосування кліткових автоматів дозволяє змоделювати складну поведінку об’єктів чи явищ без використання складного і громіздкого математичного опису. Популярність кліткових автоматів пояснюється їх відносною простотою у поєднанні з великими можливостями використання для моделювання сукупності однорідних взаємозв’язаних об’єктів. Поряд з цим відзначають і слабкий загальний теоретичний фундамент кліткових автоматів, недостатнє вивчення питань збіжності обчислювальних експериментів та стійкості отриманих результатів.
Для дослідження використовувались такі методи як системний науково-методологічний аналіз підручників і навчальних посібників, монографій, статей і матеріалів науково-методичних конференцій; спостереження навчального процесу; аналіз результатів навчання студентів у відповідності до проблеми дослідження; синтез, порівняння та узагальнення теоретичних положень, розкритих у науковій та навчальній літературі; узагальнення власного педагогічного досвіду та досвіду колег з інших закладів вищої освіти.
У статті наводиться історична довідка з розвитку теорії кліткових автоматів. Пропонується схема реалізації кліткових автоматів. Детальніше описується гра «Життя».
Подальші дослідження будуть зосереджені на аналізі можливостей використання кліткових автоматів для моделювання складних систем та методиці навчання моделювання на основі кліткових автоматів для студентів другого (магістерського) рівня вищої освіти педагогічного університету у межах дисципліни «Основи штучного інтелекту».
Ключові слова: клітковий автомат, моделювання, штучний інтелект, гра «Життя».

CELLULAR AUTOMATA AS A MEANS COMPLEX SYSTEMS MODELLING
Taras Kobylnyk
Drohobych Ivan Franko State Pedagogical University, Ukraine

Abstract. The article is devoted to the characterization of cellular automata as a method for modeling complex systems. Many complex phenomena and processes, such as self-reproduction, growth, development, etc. are difficult to describe by using differential equations and their systems. However, this can be easily modeled by using cellular automata. Accordingly, models have become more popular built up from them. The cellular automata is characterized by discrete space and time. This structure is convenient for modeling a variety physical, biological and information processes. The use of cellular automata allows you to simulate the complex behavior of objects or phenomena without the use of complicated and cumbersome mathematical descriptions. Cellular automata is popular because of its relative simplicity in combination with the great possibilities of using for modeling a set of homogeneous interconnected objects. Along with this, we note the weak general theoretical foundation of cellular automata, the insufficient study of the problems of convergence of computational experiments and the stability of the results.
We used methods such as systematic review of textbooks and manuals, monographs, articles and materials of scientific and methodical conferences; analysis of student learning outcomes in accordance with the research problem; synthesis, comparison and synthesis of theoretical positions described in scientific and educational literature; generalization of our own pedagogical experience and experience of colleagues from other higher educational institutions.
In the article we present a historical background on the development of the cellular automata theory. We propose the implementation scheme of cellular automata and describe the Conway’s Game of life in more detail.
We will focus further research on the analysis of the possibilities of using cellular automata for the modeling of complex systems and teaching methodology of modeling based on cellular automata for students of the second (master's) level of higher education at a pedagogical university within the discipline "Fundamentals of Artificial Intelligence".
Key words: Cellular Automata, Modeling, Artificial Intelligence, Conway’s Game of Life.

Список використаних джерел

1. Аладьев В.З. Классические однородные структуры: Клеточные автоматы. СА: Palo Alto, Fultus Books, 2009. 535 с.
2. Аноприенко А.Я., Коноплёва А.П., Плотников Д.Ю., Малёваный Е.Ф. Применение клеточных автоматов для моделирования динамических процессов: опыт ДонНТУ. Материалы 4-й международной научно-технической конференции «Моделирование и компьютерная графика. 2011». Донецк, 5-8 октября 2011 г. С. 271-278.
3. Воробйов Є.С, Павленко М.А., Хлєбніков Є.Ю., Гладишев М.Г. Використання кліткового автомату у методі вибору варіанту маршруту польоту ударних літаків щодо ураження наземних цілей. Системи озброєння і військова техніка. 2018. № 1(53). С. 84-90.
4. Долгушин Д.Ю., Мызникова Т.А. Применение клеточных автоматов к моделированию автотранспортных потоков: монография. Омск: СибАДИ, 2012. 112 с.
5. Жихаревич В.В., Миронiв I.В., Остапов С.Е. Алгоритм розпізнавання символів тексту на основі конкуруючих клітинних автоматів. Радiоелектронiка, Інформатика, Управління. 2015. № 4 (35). С. 39-44.
6. Жуков В.Е. Клеточные автоматы в криптографии. Часть 2. Вопросы кибербезопасности. 2017. №4(22). С.47-66.
7. Макаренко О.С., Крушинський Д.А. Моделювання руху пішоходів на основі клітинних автоматів. Системні дослідження та інформаційні технології. 2010. № 1. С. 100-109.
8. Мацюк Н.А., Жихаревич В.В. Решение задачи коммивояжера средствами клеточных автоматов. Моделювання регіональної економіки. 2015. №2 (26). С. 263-272.
9. Минский М. Вычисления и автоматы. М.: Мир, 1971. 366 с.
10. Наумов Л.А., Шапыто А.А. Клеточные автоматы. Реализация и эксперименты. Мир ПК. 2003. №8. С.64-71.
11. Омарова Г.А., Казанцев Г.Ю. Применение клеточных автоматов для моделирования транспортных потоков. Проблемы информатики. 2015. №3. С.15-21.
12. Петровский А.В. Клеточные автоматы в моделировании работы перекрестка. Науковий вісник ХДМІ №1 (2), 2010. С.78-83.
13. Burks A.W. Essays on Cellular Automata. Urban, IL: University of Illinois Press, 1970. 375 p.
14. Gardner M. The Fantastic Combinations of John Conway’s New Solitaire Game Life. Scientific American, Vol. 223, No. 4. 1970. pp. 120-123.
15. Mainzer K. Thinking in complexity. The computational dynamics of matter, mind, and mankind. Berlin: Springer, 2007.
16. Mainzer K., Chua L. The Universe as automaton. Springer, 2012. 112 p.
17. Rendell, P.: A universal Turing machine in Conway’s Game of Life. In: Proceedings of HPCS’11, the 2011 International Conference on High Performance Computing and Simulation, pp. 764–772 (2011)
18. Sarkar P. A brief history of cellular automata. ACM Computing Surveys. 2000. vol. 32, No. 1. P. 80-107.
19. Schiff J.L. Cellular automata. A Discrete View of the World. A John Wiley & Sons Inc., Publication. University of Auckland, 2008. 279 p.
20. Sutner K. Classification of cellular automata. Encyclopedia of Complexity and Systems Science. Springer, 2009.
21. Toffoli T., Margolus N. Cellular Automata Machines: A New Environment for Modeling. Cambridge, Massachusetts: MIT Press, 1987. 280 p.
22. Ulam S. On some mathematical problems connected with patterns of growth of figures. Proceedings of Symposia in Applied Mathematics. 1962. 14. P. 215-224.
23. Von Neumann, J. Theory of self-reproducing automata (edited and completed by A.W. Burks). – Urbana, IL: University of Illinois Press, 1966. 388 p.
24. Wiener N., Rosenbluth A. The mathematical formulation of the problem of conduction of impulses in a network of connected excitable elements, specifically in cardiac muscle. Arch. Inst. Cardiol. Mex. 1946. 16. P. 205–265.
25. Wolfram S. A new kind of science. Champaign, IL: Wolfram Media Inc., 2002. 1280 p.
26. Zuse K. Rechnender Raum. Braunschweig: Friedrich Vieweg & Sohn, 1969. 70 p.