Введение к работе
Актуальность проблемы Клеточные автоматы являются математическими моделями естественных и технических распределенных систем, состоящих из большого числа элементов, которые локально взаимодействуют друг с другом. Такие системы характеризуются сложным глобальным поведением несмотря на крайне простые правила локальной эволюции ее элементов.
Концепция клеточно-автоматных вычислений активно используется при создании массово-параллельных высокопроизводительных вычислительных систем. Простота архитектуры элементарного процессора и локальность межпроцессорных связей делают нетривиальной задачу создания алгоритмов массово-параллельных локальных вычислений, что указывает на необходимость разработки оригинальных методик проектирования алгоритмов подобного типа.
В настоящее время интенсифицируются исследования по созданию молекулярных и нейронно-сетевых процессоров, использующих в своей работе принципы параллельной обработки информации в живых системах. Клеточные автоматы — это наиболее приемлемая математическая модель биологических вычислителей, кроме того они активно применяются при имитации разнообразных природных явлений: солитонов,. реакционно-диффузионных сред, химической турбулентности, динамики жидкостей и газа, динамики популяций, эпидемиологии, морфогенеза и т.п.
Особый интерес приобретают такие проблемы собственно теории клеточных автоматов, как предсказание эволюции, характеризация графов глобальных переходов, предельных множеств конфигураций и алгебраических систем, построенных' над клеточными автоматами, исследование тонких свойств клеточно-автоматных отображений и вычислительной мощности клеточных автоматов, взаимное моделирование классов, анализ новых классов клеточных автоматов (например, обратимые и асинхронные автоматы), сравнительный анализ клеточных автоматов и грамматик.
Исходя из вышесказанного можно заключить, что Проблема восстановления правил локальной эволюции элементов распределенной многокомпонентной системы по набору моментальных снимков ее глобальной эволюции становится крайне актуальной в плане автоматического создания математических моделей естественных систем, проектирования массово-параллельных алгоритмов и решения ряда принципиальных задач теории клеточных автоматов.
Цель и задачи исследования. Целью настоящего исследования является создание алгоритмов идентификации клеточных автомагов, т.е. вычисления минимального описания клеточного автомата по последовательности его конфигураций. Решались следующие задачи:
-
Создать полную классификацию клеточных автоматов, построить иерархию сложности описания и взаимной моделируемости;
-
Спроектировать алгоритмы идентификации клеточных автоматов для каждого из классов, оценить сложность идентификации, построить схемы параллельной идентификации;
-
Исследовать применимость алгоритмов идентификации к восстановлению правил локальной эволюции естественных систем;
-
Оценить применимость идеологии идентификации клеточных автоматов при проектировании массово-параллельных алгоритмов решения задач дискретной вычислительной геометрии.
Методы и объекты исследования. Исследования осуществлены на основе теории автоматов, теории кодирования, теории вероятностей и комбинаторики. Объектом исследования являются клеточные автоматы, которые представляют собой дискретные математические модели многокомпонентных естественных и искусственных систем, состоящих из большого числа относительно простых элементов, связанных между собой локально в регулярные структуры.
Клеточный автомат канонически описывается целочисленной решеткой L, каждый узел (клетка) х которой принимает состояния из непустого конечного множества Q и совершает переходы из состояния в состояние в дискретные моменты времени в соответствии с функцией локальных переходов / в зависимости от состояний ближайших к соседей окрестности и в прошедший момент времени: K=(h, Q, и, /}, и. L-»L*, /:Ql-*Q, х<«=Ди(ХУ).
Научная новизна. В работе впервые
(1) проведен полный сравнительный анализ всех возможных классов КА по
направлениям асинхронности, нестационарности, недетерминированности и структурной
вариабельности и построены иерархии принадлежности, моделируемости и сложности;
-
доказана разрешимость задачи восстановления функции локальных переходов по набору конфигураций КА, спроектированы алгоритмы идентификации всех классов КА и вычислены оценки сложности последовательной и параллельной идентификации;
-
построены алгебраические системы и ассоциированные матричные структуры над классами КА;
-
предложены методы вычисления неконструируемых конфигураций;
-
проведено практическое внедрение теоретических результатов на примерах идентификации систем движущихся объектов, нейронных сетей, морфогенетических структур, реакционно-диффузионных сред, популяций животных и растений;
-
предложены способы идентификации эпистемических и акциональных систем распределенного интеллекта;
(7) обоснована схема автоматического проектирования молекулярных
компьютеров по структуре решаемой задачи, методы проектирования протестированы на
задачах вычислительной геометрии и обработки изображений.
Практическая ценность работы. Результаты работы применены при проектировании, изготовлении опытных образцов и отладке программного обеспечения одноплатного параллельного сопроцессора ЛОКОН 9В51 (НИП "Галафокс"), использованы при проведении НИР "Исследование методов решения задач и программирования (обучения) нейросетевых компьютеров" (СПбГУ, АО "Светлана"), "Исследование структурно-функциональной организации рефлексов и моделирование нейронных сетей" (СПбГУ, МИРЭА), "Исследование параллельных реконфигурируемых компьютерных архитектур для суперкристалла", "Исследование состава, функций и разработка программного обеспечения для отказоустойчивых многопроцессорных систем на суперкристалле", "Разработка к исследование архитектур и прототипа программного обеспечения многопроцессорной системы на пластине", "Исследование массово-параллельных архитектур с учетом возможностей 1.5 мкм технологии для создания сверхвысокопроизводительных систем пятого поколения", "Исследование не-фон Неймановских массово-параллельных архитектур и возможности их реализации на пластине по субмикронной технологии" в отделе Микроэлектроники КТБ АО "Светлана"
(Санкт-Петербург). По результатам работы читается годовой курс в Санкт-Петербургском государственном университете.
Публикации. По теме диссертации опубликовано 35 работ и монография 21 п.л.
Апробация работы. Материалы диссертации были представлены на Международной конференции "Приложения баз данных и микрокомпьютеров" (Йена, 1988), IX Всесоюзной конференции по нейрокибернетике (Ростов-на-Дону, 1989), Ш-м Всесоюзном рабочем совещании "Теоретические исследования и банки данных по молекулярной биологии" (Новосибирск, 1988), Международной конференции "Моделирование и компьютеры в молекулярной биологии" (Новосибирск, 1990), XI, XIII и XIV семинарах по однородным вычислительным средам и систолическим структурам (Львов, 1990, 1991, 1992), Международном симпозиуме по нейронным сетям и нейронным вычислениям (Прага, 1990), 1-й Всесоюзной конференции "Однородные вычислительные структуры" (Львов, 1990), Международной конференции "Сложные системы: фракталы, спиновые стекла и нейронные сети" (Триест, 1991), Международной конференции "Биомод'92" (Санкт-Петербург, 1992), Международном симпозиуме по нейрокибернетике и нейрокомпьютерам (Ростов-на-Дону, 1992), П-й Международной конференции по промышленной и прикладной математике (Вашингтон, 1991).
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, приложений, заключения и списка литературы. Основной текст содержит 173 страницы, 45 таблиц и 97 рисунков. Список литературы включает 196 наименований.
