Математика

Машины клеточных автоматов — Тоффоли Т., Марголус Н.

Машины клеточных автоматов
Научное издание

год издания — 1991, кол-во страниц — 280, ISBN — 5-03-001619-8, 0-262-20060-0, тираж — 5500, язык — русский, тип обложки — мягк., масса книги — 280 гр., издательство — Мир

КНИГА СНЯТА С ПРОДАЖИ

Сохранность книги — хорошая

Пер. с англ. П. А. Власова и Н. В. Барабанова

Формат 60x90 1/16. Бумага офсетная №1. Печать офсетная

Книга американских специалистов, излагающая теорию клеточных автоматов Дж. фон Неймана и описание машины клеточных автоматов на базе персональной ЭВМ (IBM-PC). Такие машины могут использоваться для моделирования физических процессов, при решении комбинаторных и вычислительных задач, задач прикладной кибернетики. Изложение отличается простотой и ясностью и рассчитано на первоначальное ознакомление с предметом.

Для математиков-прикладников, специалистов по теории автоматов, физиков разных специальностей, аспирантов и студентов университетов.

Идея клеточных автоматов была сформулирована независимо Дж. фон Нейманом и К. Цусе в конце 40-х годов. Оба рассматривали их как универсальную вычислительную среду для построения алгоритмов, эквивалентную по своим выразительным возможностям машине Тьюринга. Эта идея породила волну многочисленных теоретических и прикладных исследований. Прежде всего это касается работ по созданию формальных моделей и алгоритмов на основе локальных взаимодействий, универсальных клеточных процессоров и нейрокомпьютеров. Начиная с 1976 г. в Берлине регулярно проводятся международные конференции по параллельной обработке информации на клеточных автоматах. Современный интерес к ним усиливается возможностью реализации на СБИС с высокой степенью интеграции, перспективами обработки информации на молекулярном уровне.

Книгу «Машины клеточных автоматов», перевод которой предлагается читателям, выгодно отличают широта охвата проблемы, доступность изложения и образность подачи материала. Вначале вводятся основные понятия, даются необходимые исторические сведения и описывается машина клеточных автоматов CAM-6, созданная в Массачусетсом технологическом институте. Во второй части описываются различные классы правил, окрестностей и особенности динамики клеточных конфигураций. Начиная с простейших типов взаимодействий клеток, авторы постепенно подводят читателя к сложным вопросам развития клеточных структур и зависимости динамики конфигураций от пространственных и временных фаз жизни клеток. Третья часть книги посвящена моделям физических процессов в газах и твёрдых телах, фундаментальным свойствам клеточных автоматов.

Выбор гибкого, расширяемого языка программирования Forth, допускающего возможность создания диалектов, необходимых для решения того или иного класса задач, не случаен. Используемая в нём форма записи выражений — обратная польская запись — позволяет существенно повысить эффективность синтаксического анализа, а стековый характер языка идеально соответствует архитектуре машин клеточных автоматов. При этом значительно упрощается и задача отображения Forth-алгоритмов на СБИС.

Книга несомненно заинтересует многих читателей как превосходное, великолепно иллюстрированное введение в стратегически важную область вычислительной техники и информатики.

ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
Б. В. Баталов

Предисловие редактора перевода	5
Благодарности	6
Введение	7

Часть I. Обзор	8

1 Клеточные автоматы	8
1.1 Основные понятия	8
1.2 Мультипликация вручную	9
1.3 Машины клеточных автоматов	11
1.4 Исторические замечания и литература	12
2 Среда CAM	16
2.1 МашинаCAM-6	16
2.2 Основные аппаратные средства	17
2.2.1 Память: плоскость битов	17
2.2.2 Дисплей: цветовая карта	18
2.2.3 Динамика: таблицы правил	18
2.2.4 Геометрия в малом: окрестность	19
2.2.5 Геометрия в большом: обёртывание	19
2.3 Программное обеспечение: CAM Forth	20
3 Живая демонстрация	21
3.1 Игра «жизнь»	21
3.2 Повторение эхом	24
3.3 Трассировка	26
3.4 Как разводить глайдеры	27
4 Правила игры	30
4.1 Выбор вселенной	30
4.2 Словесная формулировка правил	33

Часть II. Возможности	37

5 Наши первые правила	37
5.1 Неограниченный рост	37
5.2 Ограниченный рост	39
5.3 Конкурентный рост	41
5.4 Правила голосования	41
5.5 Компьютер Бэнкса	44
5.6 «Случайные» правила	46
6 Динамика второго порядка	47
6.1 Возбуждение нейронов: правило с тремя состояниями	47
6.2 Задний ход	51
6.3 Непроницаемый барьер	53
6.4 Другие примеры	54
7 Соседи и окрестности	56
7.1 Слабо связанная пара	57
7.2 Волшебное число двенадцать	58
7.3 Объявление окрестностей	61
7.3.1 Основные назначения	61
7.3.2 Дополнительные назначения	63
7.4 Сводка окрестностей	65
7.5 Заказные окрестности	66
7.6 Создание таблиц	66
7.7 Цветовая карта и счётчик событий	68
8 Случайность и вероятностные правила	70
8.1 Экспоненциальное затухание	71
8.2 Простой генератор шума	72
8.3 Снова правила голосования	74
8.4 Замечания о шуме	76
8.5 Под вашу ответственность!	78
8.6 Источник шума	79
9 Антология методов	80
9.1 Сохранение частиц	80
9.2 Дифференциальные эффекты	83
9.3 Соединение двух половин	86
9.4 Генетический дрейф	89
9.5 Пуассоновское обновление	92
9.6 Асинхронные детерминированные вычисления	96
9.7 Одномерные клеточные автоматы	102
9.8 Приёмы расширения окрестности	105
10 Тождественность и движение	107
10.1 Случайное блуждание	108
10.2 Случайные перемещения	110
11 Псевдососеди	116
11.1 Пространственные фазы	117
11.2 Временные фазы и фазовое управление	118
11.3 Двухфазное правило	120
11.4 Инкрементное управление фазой	122
11.5 Рабочий цикл	123
11.6 Чередующиеся пространственные текстуры	126
12 Окрестность Марголуса	128
12.1 Правила для блока	128
12.2 Частицы в движении	130
12.3 Столкновения	132
12.4 Как преобразовать правило для блока в правило для клетки	134
12.5 Соседи по Марголусу	136
12.6 Выбор чётной/нечётной решётки	139
12.7 Фазочувствительный газ	140
12.8 Примеры	143
12.8.1 Фракталы	143
12.8.2 Криттеры	144
12.8.3 Асинхронное вычисление	146
12.8.4 Цифровая логика	148

Часть III. Физическое моделирование	151

13 Симптомы и причины	151
13.1 Мелкозернистые модели физических явлений	151
14 Обратимость	154
14.1 Обратимые клеточные автоматы	155
14.2 Метод второго порядка	156
14.3 Чередующиеся подрешётки	159
14.4 Метод защитного контекста	159
14.5 Метод разбиения	160
14.6 Обратимость и случайность	164
15 Диффузия и равновесие	165
15.1 Управляемая шумом диффузия	165
15.2 Расширение и установление теплового равновесия	169
15.3 Самодиффузия	173
15.4 Средняя длина свободного пробега	174
15.5 Проявление изобретательности	175
15.6 Регулируемый источник шума	178
15.7 Ограниченное диффузией агрегирование	179
16 Динамика жидкостей	183
16.1 Звуковые волны	183
16.2 Гидродинамика	185
16.3 Трассировка течения	186
16.4 Течение после препятствия	189
16.5 Другие решёточные газы	190
16.6 Автокорреляции	193
16.7 Волновая оптика	195
17 Коллективные явления	199
17.1 Критические параметры и фазовые переходы	200
17.2 Системы Изинга	200
17.3 Только спины	205
17.4 Банки энергии	209
17.5 Тепловая ванна	213
17.6 Отображение энергии	217
17.7 Только связи	220
17.8 Спиновые стёкла	223
18 Вычисления на основе баллистического метода	227
18.1 Модель вычислений посредством биллиардных шаров	228
18.2 Обратимый компьютер на основе клеточного автомата	232
18.3 Несколько экспериментов с моделью биллиардных шаров	236
18.3.1 Волшебный газ	237
18.3.2 Конец света	238

Выводы	241

А. Краткое руководство по языку Forth	243
А.1 Интерпретатор команд	243
А.2 Компилятор	244
А.З Словарь	245
А.4 Числа	247
А.5 Стек	248
А.6 Выражения	249
А.7 Редактирование и загрузка	250
А.8 «Константы» и «переменные»	252
А.9 Итерация	255
А.10 Стековые комментарии	256
А.11 DUP, DROP и т.д.	258
А.12 Выбор варианта	259
А.13 Условные предложения	260
А.14 Логические выражения	260
А.15 Литература для дальнейшего изучения Forth	263

В. Основы архитектуры CAM	264
В.1 Плоскостной модуль	264
В.2 Большие массивы: склеивание границ	265
В.3 Увеличение числа состояний клетки: группирование листов	266
8.4 Увеличение размерности: наложение слоёв	267
В.5 Отображение и анализ	267
В.6 Модульность и расширяемость	268

Литература	269

Книги на ту же тему

Ориентированные графы и конечные автоматы, Мелихов А. Н., 1971
Алгоритмы и вычислительные автоматы, Трахтенброт Б. А., 1974
Машины Тьюринга и рекурсивные функции, Эббинхауз Г. Д., Якобс К., Ман Ф. К., Хермес Г., 1972
Булева алгебра и конечные автоматы, Кунцман Ж., Наслен П., ред., 1969
Теория алгоритмов: основные открытия и приложения, Успенский В. А., Семёнов А. Л., 1987
Введение в синергетику: Учебное руководство, Лоскутов А. Ю., Михайлов А. С., 1990
Определение языков программирования интерпретирующими автоматами, Оллонгрен А., 1977
Основы кибернетики, Джордж Ф., 1984
Эволюционная кибернетика, Редько В. Г., 2001
Введение в прикладную комбинаторику, Кофман А., 1975
Введение в дискретную математику, Яблонский С. В., 1979
Фазовые переходы и критические явления, Стенли Г., 1973
Флуктуационная теория фазовых переходов, Паташинский А. З., Покровский В. Л., 1975
Корневые трансфер-матрицы в моделях Изинга, Дмитриев А. А., Катрахов В. В., Харченко Ю. Н., 2004
Фракталы и хаос в динамических системах, Кроновер Р., 2006

http://knigoprovod.ru

/Наука и Техника/Математика

ОГЛАВЛЕНИЕ

Книги на ту же тему