УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»

Бакалаврская работа на тему "Разработка среды и библиотеки CAMEL для решения задач с использованием клеточных автоматов"

(C) 2003 г. Л.А.Наумов
Научный руководитель: А.А.Шалыто, д.т.н., профессор

Санкт-Петербургский государственный институт точной механики и оптики (технический университет)

Отсюда можно скачать полный текст работы в формате pdf (580 кб)
Презентация в формате ppt (45 кб)
Иллюстрирующий фильм (640 кб)

На протяжении всей своей истории человечество постоянно генерировало какие-то идеи, обеспечивающие его развитие. Делались открытия и появлялись изобретения в самых разных отраслях жизни. Каменный топор, колесо, бумага, пенициллин, автомобиль - предметы, вещества и соответствующие им понятия, без которых развитие цивилизации представить невозможно. Истина, бог, время, функция - абстрактные понятия, возникшие в процессе развития человечества. Все они возникали тогда, когда знания и потребности человека достигали определённого уровня. По всей видимости, в конце 60-х годов XX века понятие "клеточный автомат" было просто необходимо для дальнейшего прогресса физики, биологии, химии, математики, компьютерных наук и других областей знаний, так они изобретались многократно под разными названиями, в разных странах, людьми, работающими в разных областях знаний. Тем не менее, концептуально возникшие понятия были практически эквивалентны. "Итеративные массивы", "вычисляющие пространства", "однородные структуры" и "клеточные автоматы" являются синонимами.

Когда Станислав Улам (Stanislaw Ulam) начинал свои исследования он, наверное, не предполагал, что, основываясь на его идеях, выдающийся американский учёный Джон фон Нейман (John von Neumann) придумает концепцию клеточных автоматов. Хотя фон Нейман был математиком и физиком, эта идея пришла к нему при решении задач из области биологии. Он использовал клеточные автоматы для создания более правдоподобных моделей пространственно протяжённых систем. В оригинале эта работа вышла в 1966 году, в то время как фон Нейман умер в 1957. Дописывал её Артур Бёркс (Arthur Burks), ставший известным специалистом по клеточным автоматам.

Однако вернёмся назад во времени. В конце Второй Мировой Войны, в то время как фон Нейман создавал один из первых электронных компьютеров, немецкий инженер Конрад Цузе (Konrad Zuse) прятался от нацистов в австрийских Альпах. Там, в уединении, у него возникло множество идей из области параллельных вычислений. Среди прочего он придумал и "вычисляющие пространства", то есть клеточные автоматы. Особый интерес Цузе вызывало их применения к задачам численного моделирования в механике. К сожалению политическая обстановка помешала работам учёному стать известными в то время. За работами же фон Неймана следил весь научный мир.

Профессиональные математики пришли к клеточным автоматам, рассматривая итерационные преобразования пространственно распределённых структур с дискретным набором состояний. Сразу стали возникать решения важных теоретических задач в этой области, например, вопросов обратимости и вычислимости. В группе компьютерной логики университета штата Мичиган Джон Холланд (John Holland) применял клеточные автоматы к решению задач адаптации и оптимизации.

Однако настоящий эффект разорвавшейся бомбы произвела статья ведущего рубрики математических игр и головоломок журнала "Scientific American" Мартина Гарднера (Martin Gardner). Он опубликовал описание клеточного автомата Джона Хортона Конвея (John Horton Conway) "Жизнь". Игра "Жизнь", как стали называть этот автомат, фактически, стала культовой и сделала понятия "клеточный автомат" чрезвычайно популярным особенно среди людей с техническим образованием.

Область применения клеточных автоматов чрезвычайно широка. Однако необходимо отметить, что в подавляющем большинстве случаев, они применяются либо в качестве параллельных вычислительных сред, либо в качестве сред моделирования пространственно распределённых систем (например, физических, биологических, химических, социологических и других).

Многофункциональная среда моделирования клеточных автоматов позволила бы использовать вычислительную машину в качестве:

• подчас весьма дорогостоящей экспериментальной установки для физических, биологических, химических и прочих опытов;
• средства реализации и визуализации алгоритмов параллельных вычислений.

Настоящая работа посвящена разработке среды CAME&L (Cellular Automata Modeling Environment & Library - среда моделирования и библиотеки разработчика клеточных автоматов), которая представляет собой мощное средство для решения задач с использованием клеточных автоматов. В работе рассматривается вопрос о том, почему возникла необходимость написания этой среды, производится её сравнение с существующими аналогами. Приводятся основные требования, которые можно предъявить к программному обеспечению этого класса, принципиальные вопросы, которые возникают при его разработке и то, как они решены в проекте CAME&L. Подробно описывается часть среды, названная CADLib (Cellular Automata Developers LIBrary - библиотека разработчика клеточных автоматов), служащая непосредственно для создания клеточных автоматов.

В первой главе приводится законченный, удобный, богатый формализм клеточных автоматов. Необходимо отметить, что строгого определения этому понятию, насколько известно автору, ещё не было дано. Математический аппарат, который здесь строится, во многом определяет основные понятия и характеристики среды CAME&L.

Во второй главе перечисляются задачи, которые ставятся перед программным обеспечением, служащим для создания моделей с использованием клеточных автоматов. Приводится перечень и описание существующих продуктов, разработанных для этих целей, а также описываются основные возможности программного обеспечения CAME&L.

В третьей главе описывается одна из важнейших частей программного обеспечения CAME&L, библиотека классов CADLib. Она предназначена для разработки клеточных автоматов при решении конкретных задач. Помимо классов в библиотеке содержатся функции, константы и макроопределения, упрощающие работу пользователя-исследователя.