Владимир Бронников
От чисел к знакам До настоящего времени человечество не придумало более простойи эффективной меры для описания явлений любой природы, чем знаковое представление. Все, что поддается измерению и описанию, на протяжении многих лет развития науки сводилось к количественным описаниям - числам, формулам, схемам.
Арифметика Аристотеля, постепенно развиваясь, перешла в алгебру,
а физические законы стали описываться формулами на все более усложняющемся языке
знаков. И единственным неизменным "знаком" с древнейших времен до наших дней
остается мера времени, которое явно или неявно присутствует в любых научных
описаниях.
Алгоритм для написания программы также можно описать набором
знаков (алфавитом) и правил, по которым эти знаки могут сочетаться. Таким образом,
нас окружает язык (множество языков) описания процессов и явлений, без которых
невозможно заниматься ни наукой, ни практическими приложениями.
С появлением компьютеров и соответственно новых способов описания
явлений при помощи алгоритмических языков роль числа осталась прежней. Однако
запоминание, обработка, накопление и анализ чисел выполняются теперь с огромными
скоростями (миллиарды операций с числами в секунду - таким быстродействием обладают
сегодня даже персональные компьютеры).
Эйфория начала шестидесятых годов нашего столетия по поводу возможности создания
программ и машин, обладающих свойствами "интеллекта", привели к появлению большого
числа моделей поведения человека и его центральной " вычислительной системы"
- мозга. Однако ожидаемого прорыва в информатике не произошло. И причина была
не в слабой технической базе того времени или недостатке идей, а в слабой формализуемости
(возможности описания на языке знаков и чисел) процессов мышления. В то же время
действительно ложные вычислительные задачи (моделирование глобального климата,
моделирование эволюционных процессов и т. п.) не могли быть даже описаны традиционными
математическими моделями.
И тогда ученые обратились к идеям одного из основателей кибернетики
Дж. фон Неймана и его работе "Самоорганизующиеся клеточные автоматы", вышедшей
в русском издании в 1968 году.
Место клеточных автоматов в описании картины мира
К середине двадцатого века наука накопила досаточно экспериментального
материала и ввела в оборот множество языков описания процессов, в основном связанных
с понятием дифференциального уравнения, и появление еще одного языка - языка
вычислительной математики для эффективного перевода математической модели явления
на язык чисел компьютера - казалось логическим шагом в развитии науки. А поскольку
основной задачей при этом являлось получение эффективного (то есть быстрого)
алгоритма решения задачи на компьютере, то чем сложнее была решаемая задача,
тем более приблизительными и трудоемкими были расчеты.
Вместе с основными направлениями теории искуственного интеллекта
развивалось теория автоматов (или, так все чаще говорят сегодня, автономных
агентов - autonomous agents). Все большее число задач описывалось простыми моделями
коллективного поведения автоматов, а широкое распространиение компьютеров привело
к массовому программированию таких моделей в различных областях науки - от биологии
и социологии до химии и физики.
Клеточные автоматы (Cellular Automata), являясь частным случаем
автономных агентов, оказались самыми эффективными моделями многих естественных
и искуственных систем высокой сложност. В то же время эти модели "удобны" -
они в максимальной степени приближены к средствам алгоритмического описания
для современных компьютеров. Это и определило их "живучесть" как простых моделей
сложных явлений.
Классичский пример клеточного автомата - (КА) "Снежинка" -
показывает, как триллионы молекул воды могут самоорганизовываться в симметричные
узоры снежинки, хотя этот процесс с первого взгляда хаотичен, и описние его
на любом языке математики невозможно!
Что же такое клеточные автоматы?
Первое, что необходимо определить - это структура пространства,
где "живут" клеточные автоматы. Представим себе, что задано некоторое "плоское
пространство" - поле, и для простоты рассмотрим лист бумаги, который расчерчен
на регулярные области. Пусть в частном случае это будут отдельные одинаковые
клетки т. е. перед нами обычный лист "в клеточку". Заметим, что мы уже сдулали
два теоретических упрощения: пространство выбрали двумерным (для наглядности),
а на плоскости задали топологический закон (отдельная клетка имеет строго иксированное
число соседей). Но даже при таком ограничении математические объекты, о которых
мы говорим, обладают на удивление сложным поведением. Ксатати, для моделирования
снежинок удобно использовать поле уже с шестигранной решеткой.
Второй параметр - это минимальная окрестность, то есть та
совокупность клеток решетки (вокруг выбранной клетки), где действует простой
локальный закон. Таких локальных окрестностей может быть множество - от одной
клетки до всего поля, но самыми исследованными являются окрестности из четырех
клеток или восьми клеток. Симметричная окрестность состоит из четырех соседей
- Север, Юг, Восток и Запад; это окрестность фон Неймана. Полная окрестность
состоит из восьми соседей; добавляется еще четыре клетки по диагоналям (окрестность
Мура).
Третьим переметром для определения поведения системы КА является
число состояний клетки на поле (от 1 до n); значение этого параметра зависит
от решаемой задачи. Так, для построения системы самовоспроизводящихся автоматов
Дж. фон Нейман использовал клетки с 29 состояниями! Самые исследованные автоматы
имеют два состояния - 1 и 0 (включено - выключено, живая - мертвая и т. д.);
этим состояниям в каждой конкретной задаче можно присвоить любой смысл. И даже
такая простая система имеет настолько сложное поведение, что уже позволяет моделировать
разнообразные биологические и физические системы. Четвертый параметр - это правило
"выживания" клетки, определяемое как ее состояние в момент времени k+1 в зависимости
от ее состояния и состояния клеток минимальной окрестности в момент времени
k. Нетрудно посчитать, что если правило работает в окрестности из восьми клеток,
то таких правил может быть AxAx8, где A - число состояний клетки. А вот для
окрестности КА с двумя состояниями клетки и окрестностью Мура существует 1077
вариантов правил поведения клетки. Из них, по понятным причинам, изучена только
малая часть правил.
Есть еще ряд ограничений, которыми исследователи определяют
модели КА. Прежде всего необходимо учитывать свойства границы поля, поскольку
в представляющих реальный интерес моделях такая граница всегда существует. Законы
поведения автоматов (а вы уже догадались, что "организмы" в отдельных клетках
поля - это суть маленькие автоматы-роботы) на границе поля адают отдельными
правилами.
И наконец, перейдем к одному из самых существенных свойств
систем КА. В сообществах таких организмов-автоматов вводиться понятие синхронного
времени - состояния всех клеток-автоматов изменяются одновременно! И это фундаментальное
свойство в корне отличает модель вычислений в КА от всех алгоритмов последовательного
вычисления в КА от всех алгоритмов последовательного вычисления, которые положены
в основу современных компьютеров.
Таким образом, алгиритмы для КА строятся исходя из предположения о том, что
моделируемое явление или процесс можно представить как пространственную систему,
состоящую из "физического" простарнства, в котором располагаются отдельные отдельные
"существа", причем каждое из этих существ "живет" по одним и тем же правилам
- законам (выше мы их называли правилами КА). Самый простой и в то же время
необычный клеточный автомат был предложен Дж. Конвеем; он описывается следующими
правилами.
Клеточный автомат Конвея
1. Каждая клетка имеет одно из двух состояний - "живое" и
"мертвое" (1 и 0).
2. Правила, которые определяют состояние клетки в момент времени
k+1, просты:
- если живая клетка на такте k имеет меньше 2 и больше 3 соседей (в минимальной
окрестности из восьми клеток), то на такте k+1 она умирает (здесь простая аналогия
с реальной жизнью - недостаток питания или перенаселенность),
- в пустой клетке на такте k+1 появляется живая клетка, если у исходной клетки
в минимальной окрестности ровно 3 соседа (три родителя!).
Теперь для исследования законов такого искусственного мира
достаточно задать начальное сотояние системы - какие из клеток поля в начальный
момент времени находятся в живом состоянии. Для того, чтобы любой из читателей
мог самостоятельно написать алгоритм для совего ПК, достаточно указать, что
для реализации такого преобразования поля клеток необходимо в памяти компьютера
зарезервировать два двумерных массива для состояния системы в момент времени
k и соответственно в момент времени k+1.
А теперь меленький тест для читателей.
Если вы запрограммировали эту задачку за 1 час, то вы профессионал
и вам в вашей компании положена приличная зарплата. Если на решение задачи потратили
несколько часов, то вы сносно программируете, но слабы в алгоритмах. И наконец,
если на решение задачи ушло обльше суток, то бросьте это занятие и попросите
написать программу любого студента 3-4 курса политехнического вуза. Если сможете
ему объяснить задачу, то считайте, что вы аналитик, а не программист...
Другие задачки для моделирования
Приведем несколько простых задачек для изучения систем более
сложных, чем автомат Конвея.
1. Аква-Тор (журнал "В мире науки", №2, 1985)
Это наиболее импатичная и простая задача по использованиюКА
для моделирования экологической системы.
Представим себе, что существует некая планета Аква-Тор - в
отличие от нашей матушки-Земли, она имеет форму тора (что является очень удобной
топологической моделью пространства КА). На этой планете живут два вида животных
(акулы и рыбы), вся поверхность однородна и представляет собо водную поверхность.
Принципиальным является наличие трофической цепи - акулы поедают рыб, а для
рыб на планете Аква-Тор всегда достаточно планктона и пищи. Численность акул
и рыб - это величина непостоянная, она зависит от поведения и привычек существ
этих двух видов. Чтобы понять законы, которые управляют такой системой, необходимо
разработать программу моделирования и проиграть на ней массу сценариев. Другой,
более дорогостоящей способ - создать физическую модель (попробуйте сделать это,
если в системе несколько тысяч особей...).
Давайте сформулируем правила поведения наших видов.
1. Наши особи "плавают" по узлам (или клеткам) решетки, причем
тор - это идеальная решетка для модели, поскольку, доплыв до края двумерного
поля, рыба (или акула) переплывает на смежную клетку, находящуются рядом на
торе. На размернутой плоскости это означает, что произошел "перескок" на противоположную
грань. Итак, для моделирования мы используем свернутое двумерное пространство
(двумерные массив).
2. За один условный такт времени на планете Аква-Тор каждая
рыба или акула может переместиться на одну клетку, если, разумеется, клетка
не занята по четырем возможным направлениям (окрестсность Неймана). Конкретное
направление выбирается с помощью генератора слуайных чисел.
3. Рыбы плавают по законам, задаваемым генератором случайных
чисел; если все соседние клетки заняты, то рыба остается на месте.
4. У акулы более сложное поведение. если в узле (слуайно выбранном)
есть рыба, то акула плывет туда и "поедает" рыбу в этом узле (клетке). Если
в ближайшем узле нет рыбы, то акула движется как рыба, то есть в свободную клетку.
5. Для удобства моделирования в программе надо задавать несколько
внешних параметров:
- число рыб (на 0 шаге моделирования); размещение случайно и равномерно
- число акул (на 0 шаге моделирования); размещение случайно и равномерно
- время в тактах, после которого рыба дает потомство
- время в тактах, после которого акула дает потомство
- время в тактах для поиска пищи акулой, по истечении которого она погибает.
6. За один такт времени программа должна просчитать состояние
каждой рыбы и каждой акулы и пометить его состояние в новом массиве (точная
копия состояния океана на планете в будущий момент времени). Когда все состояния
будут рассчитаны, и все особи получат новое состояние, записанное на "копии"
тора в момент времени T+1, образ тора (массив), соответствующий моменту T, обнуляется,
и расчет начинается снова на образе тора (массиве) T+1. Результаты нового расчета
заносятся в первый массив, который отражает уже состояние планеты Аква-Тор в
момент времени T+2, и так далее.
Ну, а теперь можно смело продемонстрировать учителю по биогогии
вышу способность решать задачи "из жизни популяций", не забывая каждый такт
времени работы программы выводить на экран монитора плоское поле планеты Аква-Тор
с изображениями рыб и акул на нем в данный момент времени. Рядом советуем отображать
два графика, демонстрирующих зависимость численности рыб и акул на нем, от модельного
времени. включайте свой компьютер, выбирайте исходные параметры модели (все
пять параметров, перечисленных выше) и наблюдайте за жизнью на планете Аква-Тор.
Осталось только написать программу на каком-нибудь знакомом
вам языке программирования. если у вас возникают проблемы, пишите мне по электронной
почте - bva@lanck.ru.
На Интернет-сервере http://www.lanck.ru/homepage/bron/
вы можете найти дополнительную информацию.
КОРОТКО ОБ АВТОРЕ:
Владимир Аркадьевич Бронников - директор по маркетингу компании