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

• Автор: Наумов, Лев Александрович
• Шифр специальности: 05.13.12
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Санкт-Петербург
• Количество страниц: 283 с. : ил.

Содержание
ВВЕДЕНИЕ
ГЛАВА 1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ КЛЕТОЧНЫХ АВТОМАТОВ. ОБЗОР ИНСТРУМЕНТАЛЬНЫХ СРЕДСТВ ДЛЯ АВТОМАТИЗАЦИИ ПРОЕКТИРОВАНИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ВЫЧИСЛИТЕЛЬНЫХ ЭКСПЕРИМЕНТОВ С ИХ ИСПОЛЬЗОВАНИЕМ.

1.1. Введение в историю и идеологию клеточных автоматов

1.2. Определение клеточного автомата.

1.3. Теорема о трех двумерных решетках из правильных многоугольников

1.4. Кольца. Свойства колец

1.5. Метрика.

1.6. Теорема об эквивалентности клеточного автомата набору

конечных автоматов.

1.7. Аппаратные и программные реализации клеточных автоматов

1.8. Требования к средствам автоматизации проектирования программного обеспечения вычислительных экспериментов с помощью клеточных автоматов
1.9. Обзор существующих средств автоматизации проектирования программного обеспечения вычислительных экспериментов с
помощью клеточных автоматов
1 Причины возникновения нового инструментального средства автоматизации проектирования программного обеспечения вычислительных экспериментов с использованием клеточных автоматов
1 Компонентная модель декомпозиции клеточных автоматов.
Выводы по главе
ГЛАВА 2. МЕТОД ВВЕДЕНИЯ ОБОБЩЕННЫХ КООРДИНАТ Д ЛЯ РЕШЕТОК КЛЕТОЧНЫХ АВТОМАТОВ.
2.1. Основы метода введения обобщенных координат для решеток клеточных автоматов
2.2. Спиральные обобщенные координаты для квадратной решетки
2.3. Спиральные обобщенные координаты для шестиугольной решетки
2.4. Спиральные обобщенные координаты для треугольной решетки
2.5. Обобщенные координаты для треугольной решетки, базирующиеся
на спиральных обобщенных координатах для шестиугольной решетки
2.6. Обобщенные координаты для квадратной решетки, основанные на кривой Пеано.
2.7. Преимущества обобщенных координат. Изоморфизм двумерных
решеток
Выводы по главе
ГЛАВА 3. РАЗРАБОТКА ИНСТРУМЕНТАЛЬНОГО СРЕДСТВА САМЕЬ ДЛЯ АВТОМАТИЗАЦИИ ПРОЕКТИРОВАНИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ВЫЧИСЛИТЕЛЬНЫХ ЭКСПЕРИМЕНТОВ С ПОМОЩЬЮ КЛЕТОЧНЫХ АВТОМАТОВ
3.1. Принципы проектирования предлагаемого инструментального средства.
3.2. Среда выполнения
3.2.1. Главное окно и окна документов
3.2.2. Главное меню.
3.2.2.1. Меню Ле
3.2.2.2. Меню МГ
3.2 Меню Vi.
3.2.2.4. Меню i.
3.2.2.5. Меню
3.2.2.6. Меню
3.2.2.7. Меню i.
3.2.2.8. Меню .
3.2.3. Формат файлов документов
3.3. Библиотека для разработки клеточных автоматов i
3.3.1. Диаграмма классов библиотеки
3.3.2. Ключевые классы.
3.3.3. Класс .
3.3.4. Классы i и i
3.3.5. Класс i
3.3.6. Класс САМе i
3.3.7. Класс и шаблоны ,
i, i
3.3.8. Класс .
3.3.9. Классы параметров компонентов и диалогов для запросов значений параметров
3.4. Разработка библиотеки, содержащей компонент.
Выводы по главе
ГЛАВА 4. ПРИМЕНЕНИЕ ИНСТРУМЕНТАЛЬНОГО СРЕДСТВА ДЛЯ АВТОМАТИЗАЦИИ ПРОЕКТИРОВАНИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ВЫЧИСЛИТЕЛЬНЫХ ЭКСПЕРИМЕНТОВ С ИСПОЛЬЗОВАНИЕМ КЛЕТОЧНЫХ АВТОМАТОВ
4.1. Проектирование вычислительных экспериментов с помощью инструментального средства .
4.2. Проектирование и реализация клеточного автомата Жизнь для различных вычислительных платформ.
4.2.1. Простая реализация, без указания вычислительной архитектуры и оптимизации.
4.2.2. Реализация с зональной оптимизацией
4.2.3. Реализация для многопроцессорной системы.
4.2.4. Реализация для вычислительного кластера
4.2.5. Реализация для обобщенных координат
4.2.6. Универсальная реализация, не зависящая от вычислительной платформы.
4.3. Проектирование и реализация клеточного автомата для решения уравнения теплопроводности
4.4. Проектирование и реализация вычислительного эксперимента для классификации структур, порождаемых одномерными двоичными клеточными автоматами из точечного зародыша.
4.4.1. Задание функции переходов одномерного двоичного клеточного автомата.
4.4.2. Начальные условия
4.4.3. Инвариантность относительно операции равенство.
4.4.3.1. Поведение типа салфетка Серпинского
4.4.3.2. Поведение типа двоичный треугольник Паскаля.
4.4.4. Инвариантность относительно операций равенство и инверсия
4.4.5. Инвариантность относительно операций равенство и зеркальное отображение
4.4.6. Инвариантность относительно операций равенство,
инверсия и зеркальное отображение.
4.4.7. Инвариантность относительно операций равенство и инверснозеркальное отображение
4.4.8. Классификации с учетом сдвигов на одну клетку
4.4.9. Классификации с учетом погрешностей
4.4 Дополнительные материалы
4.5. Автоматизация проектирования программного обеспечения систем с помощью инструментального средства .
4.6. Практическое использование результатов работы
Выводы по главе 4.
ЗАКЛЮЧЕНИЕ
СПИСОК ТЕРМИНОВ
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
ЛИТЕРАТУРА


Приведем примеры дискретизации вещества, изображенного на рис. Для этого наложим их на вещество рис. В каждую ячейку поместим значение, соответствующее той зоне материала, которую она охватывает. Используются и другие способы определения значения, которое следует поместить в клетку, соответствующую данной области среды. Клеточные автоматы образуют общую парадигму параллельных вычислений подобно тому, как машины Тьюринга образуют парадигму последовательных вычислений. В результате они могут быть использованы для реализации параллельных алгоритмов, как модели, обладающие естественным параллелизмом. Результат дискретизации вещества с помощью гексагональной решетки Рис. У клеточных автоматов обе эти составляющие собираются из принципиально изоморфных, неотличимых друг от друга элементов. Таким образом, вычислительная система может оперировать своей материальной частью, модифицировать, расширять себя и строить себе подобных 3. Хотя системы этого класса и были придуманы Джоном фон Нейманом, такая параллельная архитектура получила название нефоннеймановской, так как фоннеймановскую архитектуру он создал раньше. Данное утверждение может показаться спорным. Казалось бы, к архитектурной части логичнее отнести, например, решетку и правила автомата. Однако это скорее аппаратная часть. Здесь имеется в виду то, что, например, при рассмотрении автомата, реализующего игру Жизнь, при данных решетке и правилах, изменяя лишь состояния клеток, можно реализовать универсальную вычислительную систему, позволяющую производить любые вычисления. По своим выразительным способностям такая модель будет эквивалентна произвольным машинам Тьюринга и клеточным автоматам , . При этом клетки, описывающие архитектуру моделируемой вычислительной системы, будут неотличимы от клеток, представляющих собой данные. Клеточный автомат, называемый компьютером Бэнкса 1, также обладает свойством вычислительной универсальности. Использовать его крайне неэффективно, но с теоретической точки зрения факт его существования важный результат. С дискретное метрическое пространство, решетка автомата, набор его клеток. Наличие метрики позволяет обеспечить то, чтобы все клетки находились на конечном расстоянии от данной, так как ни для какой метрики никакие две точки дискретного метрического пространства не могут быть бесконечно удалены друг от друга. Кроме того, понятие метрики и координат клетки оказывается чрезвычайно полезным при определении множества клеток окрестности Ы, описываемой далее. Как правило, пространство С является одно, двух или трехмерным, однако оно может иметь и большую размерность. Таким образом, состояние всей решетки является элементом множества 2. У клеток, которые влияют на новое состояние данной. Его можно задавать, например, как множество относительных смещений из клетки, необходимых для достижения окрестных ячеек. Элементы этого множества будем называть соседями1 клетки. Отличие заключается в том, что в функции переходов клеточных автоматов с клетками с памятью текущее состояние клетки также передается в качестве параметра. Термин сосед не следует путать с терминами главный сосед, непосредственный сосед, сосед го кольца и прочими понятиями широко используемыми далее. Шаг автомата состоит в применении функции переходов к каждой клетке решетки. Он считается завершенным только после того, как новое состояние будет определено для всех элементов. Решетка однородна никакие две области не могут быть отличены друг от друга по ландшафту. Взаимодействия локальны. Обновление значений состояний всех клеток решетки происходит одновременно после вычисления нового состояния каждой из них. Автоматы, для которых не выполняется третье из них, называются асинхронными клеточными автоматами. На практике часто используются клеточные автоматы с двумерными решетками из правильных многоугольников. Автоматы именно с такими решетками будут преимущественно обсуждаться в настоящей работе. Рис. Рис. Рис. Термины квадратная решетка, решетка квадратов и решетка из квадратов аналогично для других многоугольников будем считать синонимами.